Имя: Пароль:
IT
 
Что почитать по алгоритмам и структурам данных?
, , ,
0 ДНН
 
04.02.21
17:45
Кто что читал? Что посоветуете? Про всякие сортировки, графы, деревья, массивы, связанные списки и т.п.
Грокаем алгоритмы читал.
6 fisher
 
04.02.21
17:56
(5) Что-то ты путаешь. ООП с паттернами - это обычно отдельная тема.
7 Волшебник
 
04.02.21
18:16
(5) В 1С есть ООП
8 cViper
 
04.02.21
18:18
(0)
1)Структуры данных и алгоритмы в Java Лафоре Роберт | Лафоре Роберт   - книга написана довольно простым языком. Отлично для старта.
https://www.ozon.ru/product/struktury-dannyh-i-algoritmy-v-java-struktury-dannyh-i-algoritmy-v-java-23529814/

2) Алгоритмы. Построение и анализ | Штайн Клиффорд, Кормен Томас Х. - это уже более серьезный материал. Читал но выборочно.
https://www.ozon.ru/product/algoritmy-postroenie-i-analiz-33769775/?stat=YW5fMQ%3D%3D

https://leetcode.com/ - отличная платформа для решения задач по программированию и изучению структур данных. Там есть карточки с описанием структур данных и задачами на эти структуры. Также есть задачи на дизайн и имплементацию СД.
9 Garykom
 
гуру
04.02.21
18:19
10 Малыш Джон
 
04.02.21
18:21
(5) и вот так всегда...  Сначала "да зачем алгоритмы и структуры программисту 1С", а потом "ой, ну это же программист 1С, откуда он про алгоритмы и структуры знает".
Чтоб голова правильно работала, для этого и изучать надо все вышеперечисленное.
11 Uberschall
 
04.02.21
18:22
(6) н-р, паттерн синглтон использует инкапсуляцию (ООП), для хранения инстанса. декоратор - ну по сути тоже. и т.д.
я не говорю, что нет паттернов без ООП, но многие используют.
12 Uberschall
 
04.02.21
18:22
(7) а можно подробнее в чем он заключается? точнее как реализуются его принципы в 1С?
13 Uberschall
 
04.02.21
18:23
(10) так я не говорил, что учиться и изучать что-то другое (не 1С) - это плохо.
14 H A D G E H O G s
 
04.02.21
18:31
(0) не вижу практического смысла.
15 toypaul
 
гуру
04.02.21
18:33
16 Конструктор1С
 
04.02.21
18:39
(0) а где ты эти знания собрался применять? Уже всё придумано за нас. Пиши ORDER BY и СУБД отсортирует наиоптимальнейшим образом
17 vi0
 
04.02.21
18:42
по графам начиная с 11й лекции https://www.youtube.com/playlist?list=PLDrmKwRSNx7J16QBIZMNmAUDRQjjwVTTG
18 vi0
 
04.02.21
18:48
вот курс неплохой https://www.youtube.com/playlist?list=PLrCZzMib1e9pDxHYzmEzMmnMMUK-dz0_7
простым языком без занудства
19 Глупый ответ
 
04.02.21
18:50
.
20 Провинциальный 1сник
 
04.02.21
18:52
(2) Кнут чересчур академичен.
Н.Вирт "Алгоритмы и структуры данных"
21 fisher
 
04.02.21
18:52
(11) Имел в виду, что ООП с паттернами - отдельная тема от базовых структур данных с алгоритмами.
22 fisher
 
04.02.21
18:57
(15) Обычно начинают с теории оценки производительности алгоритмов. Ну и структуры ж данных еще.
"Плохие программисты думают о коде. Хорошие программисты думают о структурах данных и их взаимосвязях" (с) Линус Торвальдс
23 cViper
 
04.02.21
18:59
(16) Какие структуры данных использует СУБД для реализации индексов?
24 nicxxx
 
04.02.21
19:03
Просто (0) прислушался к Бедуину и начал спрыгивать с 1С :)
25 rsv
 
04.02.21
20:17
(0) смысл ... если работаете с табличками
БД то и sql на это . Он и максимум найдет и отсортирует
26 rsv
 
04.02.21
20:21
Чтобы велики типа поиска максимума в цикле
Или рекурсией алгоритмицки не придумывать
27 Волшебник
 
04.02.21
20:23
(16) Лучше на поле наложить индекс, чтобы облегчить работу СУБД. "Наиоптимальнейшая" сортировка по мнению СУБД может занимать двое суток для тебя.
28 rsv
 
04.02.21
20:25
Как  раз по теме ... структуры данных . Т.е. отношение
кортеж атрибут индекс и select
29 Курцвейл
 
04.02.21
20:39
(0) Лучше всего почитать Гради Буча. Особенно если хочешь пойти в ООП. Для 1С тоже не помешает для карьеры архитектором, тим лидом и т.д.
30 _DAle_
 
05.02.21
02:07
(0) Был уже хороший ответ: (8). Добавлю к нему, что "Алгоритмы: построение и анализ" (CRLS) - это классическая книга, хороший университетский курс. Да книга не самая простая, но это нормальный серьезный   учебник (в отличие от, например, вышеупомянутой книги Вирта, при всем уважении к Вирту). Есть еще на русском языке хороший курс лекций Паши Маврина, это курс лекций в ИТМО: https://www.youtube.com/user/pavelmavrin.

Если вышеперечисленное сложновато, то можно попробовать книги Седжвика, вроде бы они были немного проще.
31 fisher
 
05.02.21
11:00
(30) > хороший университетский курс
Для входа в тему, особенно людям "со стороны", лучше что-то полегче. Седжвика я уже предлагал. Но насколько я понял по советам и описанию, Лафоре - еще попроще.
32 _DAle_
 
05.02.21
12:51
(31) >Для входа в тему, особенно людям "со стороны", лучше что-то полегче
33 _DAle_
 
05.02.21
12:53
(31) >Для входа в тему, особенно людям "со стороны", лучше что-то полегче

Cогласен, просто человек написал, что "Грокаем алгоритмы" уже прочитал, а это уже какой-никакой вход, хоть и лайтовый, поэтому предлагаю переходить на более тяжелые препараты :)
34 H A D G E H O G s
 
05.02.21
12:55
(0) Пиши свою СУБД. С парочкой связанных таблиц. Из самого сложного из конструкций языка - подустимы Struct. Потом нагрузи ее полтеррабайтом данных. Сразу придет понимание, что нужно почитать по алгоритмам.
35 Конструктор1С
 
05.02.21
19:56
(23) би-дерево, или как там его. А зачем это вообще знать?
36 Конструктор1С
 
05.02.21
20:00
(27) что-то не помню, чтобы СУБД напряглась при сортировке данных
37 mikecool
 
05.02.21
20:02
начинать надо с чистого кода Мартина )
38 vi0
 
05.02.21
20:15
(36) так то сортировка одна из ресурсоемких операций
39 Конструктор1С
 
05.02.21
21:10
(38) а ты хочешь сказать что отсортируешь данные быстрее/экономичнее чем oracle? Операция ресурсоемкая, но СУБД выполняет её оптимальным образом. Зачем изобретать велосипед?
40 Конструктор1С
 
05.02.21
21:12
(37) это да. Даже 1сникам будет полезно
41 vi0
 
06.02.21
07:41
(39) нет, я не хочу этого сказать, я прокомментировал твою фразу что СУБД не напрягается при сортировке
42 Провинциальный 1сник
 
06.02.21
08:22
(39) По крайней мере надо знать, что сортировка в любом случае дороже выборки по индексу, и почему надо проводить периодическую переиндексацию. И почему, например, файл индекса в 2 с лишком раза больше чем исходные индексируемые значения (а это было важно для баз dbf/cdx).
А для этого как раз книжка о теории программирования и нужна.
43 vi0
 
06.02.21
08:22
(35) если не знать, то не будешь на экспертном уровне понимать работу сервера: что такое количество чтений, как их анализировать, почему индекс занимает столько то места, как повлиять на это, как сервер может обходить индекс, и почему в каких то моментах он делает это неотимально и т.д.
в книге Querying Microsoft SQL Server Exam 70-461, которая для подготовки к экзамену по запросам, этой теме выделена отдельная глава
из книги скрин https://i0.wp.com/wiseadvice-it.ru/upload/medialibrary/fe0/20_1.jpg
44 Конструктор1С
 
06.02.21
08:50
(42) не то чтобы изучал, но хорошенько полистал книгу по алгоритмам и структурам данных. Не нашел там совершенно ничего, проливающего свет на внутреннюю кухню СУБД. Если уж интересует "как там в скуле работает", то куда полезнее почитать соответствующую литературу и документацию
45 Конструктор1С
 
06.02.21
08:52
(43) это всё хорошо, только причем тут "классические" алгоритмы?
46 Провинциальный 1сник
 
06.02.21
09:02
(44) Способ хранения двоичных деревьев индекса в одномерном массиве(таблице) знаете? Левая ветка 2n, правая 2n+1. Где n-позиция ключевого поля в таблице данных. Так вот об этом у Вирта есть.
47 Конструктор1С
 
06.02.21
09:10
(46) не знаю. Но даже если бы знал, какая практическая польза от этих знаний? СУБД не предоставляет доступа покопаться в кишочках индекса, да и незачем

С этими алгоритмами примерно как с математикой. Математика программисту нужна... в 1% их всех программистских задач, в остальных 99% нафиг не нужна. С алгоритмами примерно то же самое. Это не универсальные знания, в подавляющем большинстве случаев они нафиг не нужны
48 Провинциальный 1сник
 
06.02.21
09:22
(47) СУБД разные бывают, и вот например в dbf это ограничение было весьма актуально. Знать, откуда оно произошло, весьма полезно.
49 Провинциальный 1сник
 
06.02.21
09:24
(47) Это как для автомобилистов - полезно знать теорию двигателей внутреннего сгорания и теорию машин и механизмов в общих чертах. Чтобы хотя бы понимать, что случилось с машиной, можно ли ехать дальше или срочно вызывать эвакуатор.
50 Конструктор1С
 
06.02.21
09:34
(49) я когда-то тоже так думал. Мол 1сник должен уметь на "ты" СУБД. Пришел в крупную команию, со здоровенными базами данных, а там... целая команда грамотных сертифицированных DBA, которые занимаются всей магией связанной с работой СУБД
51 Провинциальный 1сник
 
06.02.21
09:35
(50) Для 1с это всё-таки менее характерно, и жесткую специализацию скорее можно считать исключением из правил.
52 Конструктор1С
 
06.02.21
09:37
Для программиста есть куда более полезные знания, которые он сможет применять в повседневности. Например, принципы SOLID, знание английского. Имхо, алгоритмы и структуры данных где-то ближе к концу списка "знаний must have"
53 Провинциальный 1сник
 
06.02.21
09:51
(52) И в результате деятельности таких вот программистов мы имеем ситуацию, когда ту же самую задачу, которую успешно решали на P200, теперь приходится решать на core i5. Это и к 1с относится, кстати.
54 Вафель
 
06.02.21
10:20
это не из-за алгоритмов, а из-за увеличения уровней абстракций и количества фреймворков
55 Провинциальный 1сник
 
06.02.21
10:26
(54) Ну так одно с другим связано. Программисты не хотят влезать в детали и берут фреймворк, который ради универсальности дает увеличение ресурсоемкости на порядок. Иногда возникает мысль, что в отрасли действует некая "группа регрессоров", целью которой является замедлить развитие человечества.
Если бы программистам 60-х вдруг дать современный тот же Core i5 с free pascal внутри, страшно представить, что бы они могли сотворить (в хорошем смысле). А современные программисты эти ресурсы используют для того чтобы точка исполнения кода продиралась через уровни всех этих абстракций, делая что-то весьма тривиальное.
56 vi0
 
06.02.21
10:51
(45) прочитай на какой комментарий я отвечал тебе
57 vi0
 
06.02.21
10:52
(47) математика это в первую очередь инженерное мышление
58 vi0
 
06.02.21
10:54
(50) и они давали 1сниками рекомендации по построению запросов?
59 GANR
 
06.02.21
10:56
(0) Гимнастики для ума захотелось? А зачем книги? Вот практические задачи - подумай как решить:
- рекурсивно пометить на удаление то, на что ссылается объект
- поменять свойство доступность элементов, входящих в группу формы (они вложены, как матрёшка)
- есть папка неоднократного уровня вложенности - скопировать оттуда файлы с расширением xml в другую папку на один уровень, для уникальности прибавить к именам случайные ГУИДы
- генерировать все возможные комбинации нескольких элементов справочника
- для ведомости ИНВ-19 минимальную цену в пересортице строк найти, пересортившиеся строки пользователь укажет - это и будет граф (в УПП в 2013 году этого не было)
- расчетные показатели в отчете с использованием построителя отчетов (механизмами запросов было невозможно и пришлось пускать рекурсию по результату запроса)
- критические задачи найти в сетевом графике работ (задач, удлинение или сдвиг которых неминуемо приводит к сдвигу окончания проекта)
- более 30000 видов затрат, друг на друга ссылаются по графу, который пользователи задали на некоторых копейки зависли (сумма < 1 рубля) - надо списать на ближайшую где сумма > 1 рубля

и так далее...
60 H A D G E H O G s
 
06.02.21
10:59
(55) почему файл индекса в 2 раза больше файла данных?
61 Immortal
 
06.02.21
11:00
отмечусь, мб что интересное найду здесь
62 Провинциальный 1сник
 
06.02.21
11:05
(60) Количество записей индекса по одному полю составляет максимум 2n+1 от количества записей в основной таблице. А размер может быть всякий. В dbase например допускались индексные выражения, и там индекс мог быть намного жирнее исходного поля.
63 Конструктор1С
 
06.02.21
12:38
(53) ты путаешь. Раньше кода было с гулькин нос. Сейчас прогер строчку кода пишет, а за ней проворачивается миллион строк более низкоуровневого кода
64 Конструктор1С
 
06.02.21
12:41
(55) ты предлагаешь доблестно тратить время на очередное переизобретение уже готового?
65 Конструктор1С
 
06.02.21
12:43
(58) нет. Разве что в отдельных специфичных случаях
66 cViper
 
06.02.21
12:52
(46) Это heap
67 cViper
 
06.02.21
12:58
(52) Ахахахаха. Серьезно?! Очень часто на позицию java dev спрашивют про устройство HashMap, TreeMap, просят реализовать какую-либо структуру данных (LinkedList, Stack, Queue, HashTable, LRUCache, Trie). Задают вопросы по сложности алгоритмов, какие из них реализованы в языке, просят их реализовать. Дают задачи на кодирование, когда надо в блокноте решить задачи различного уровня.
68 cViper
 
06.02.21
13:07
(55) Фреймворки то и написали специально для того, чтобы ты свой велосипед каждый раз не писал. Взял готовое решение и написал бизнес-логику. Это все равно, чтобы каждый раз писать платформу 1С:Предприятие.
69 H A D G E H O G s
 
06.02.21
13:07
(62) А давай ты попробуешь в структуры данных еще раз?
http://prntscr.com/yi6too
70 H A D G E H O G s
 
06.02.21
13:19
(61) Скажи свои контакты, я потерял тебя со смертью аськи
71 Конструктор1С
 
06.02.21
14:29
(67) это что за хардкорные интервью такие? Специально сдул книгу оракла по подготовке к сертификации по Java:
https://www.amazon.com/OCP-Certified-Professional-Programmer-1Z0-809/dp/1119067901
там коллекциям посвящено семьдесят страниц, из них имплементации Map всего 2 страницы. Уж если папка оракл на экзаменах не спрашивает про кишочки коллекций, на кой другие эти спрашивают?
72 Конструктор1С
 
06.02.21
14:30
+(71) неправильно написал. Дженерикам + коллекциям посвящено 68 страниц
73 novichok79
 
06.02.21
14:32
алгоритмы для чайников, алгоритмы для начинающих, структуры данных и алгоритмы на java.
с. скиена - алгоритмы.
74 Провинциальный 1сник
 
06.02.21
17:25
(69) И что вы тут пытаетесь сравнивать? Речь о сравнении объема конкретного индекса и индексного поля основной таблицы, а не о сравнении общего объема таблицы и всех её индексов. Ваше сравнение не имеет смысла.
75 Провинциальный 1сник
 
06.02.21
17:27
(68) Фреймворки разные бывают. Вот взять например турбовижн или дельфи. Они адекватными людьми сделаны, а не хипстерами миллениалами..
76 H A D G E H O G s
 
06.02.21
19:02
(74) Надо просто немного напрячься. Там как раз сравнение объема конкретного индекса и индексного поля.
77 Провинциальный 1сник
 
07.02.21
08:27
(76) Сами напрягитесь. "Пространство данных" и "место, занимаемое индексом" относится к ТАБЛИЦЕ _Reference41. А не к конкретному полю.
78 Провинциальный 1сник
 
07.02.21
08:33
(77) И собственно о 2n+1 я говорил относительно именно формата индексов dbf (idx/cdx), а в mssql могут использоваться другие способы хранения, например без хранения собственно значений ключей в индексе, а только с хранением ссылки на поле исходной таблицы, содержащей значение. Тогда 2n+1 будет относится к размеру идентификатора записи основной таблицы. А может хранить значения, но повторяющиеся ссылки неуникального индекса не разворачивать в дерево, а хранить в связанном с узлом списке. Способов полно.
79 Кирпич
 
07.02.21
08:42
А еще бывает индексируют туда и обратно, чтобы быстро LIKE работал.
Ну типа "МАМА" и "АМАМ". Вот тебе и сразу в два раза больше.
80 H A D G E H O G s
 
07.02.21
09:05
(77) специально для тебя там слева показана иерархия таблицы, состоящая из одного поля. И да, размер Пространства данных чуть больше, чем
25*2*100000 на служебные структуры.
Но все равно, мы не видим, что размер индекса больше, чем размер данных в 2 раза.
Тут не 1с хаять, тут думать надо.
81 H A D G E H O G s
 
07.02.21
09:08
(78) Ты несешь бред насчет sql. Почитай про b+ деревья.
82 H A D G E H O G s
 
07.02.21
09:13
(79) а чаще бывает, что страница индекса не наполнена на 100%, а где то ближе к 50% и ты радостный несешься на форум :-)
83 2mugik
 
07.02.21
09:22
(0)тимофей хирьянов мфти лекции алгоритмы на питон.
84 H A D G E H O G s
 
07.02.21
09:25
85 2mugik
 
07.02.21
09:33
(84)Ты наверное это хотел запостить в ветку где обсуждают Волков победил нокаутом Оверима? Тогда подходит)
86 Кирпич
 
07.02.21
09:39
(82) Провинциальный 1сник наверное хотел сказать про dbf. Там да. Индексный файл cdx, какой нибудь, запросто мог быть в два раза больше файла dbf. Туда просто можно засунуть кучу индексов, да еще и всяких составных да с выражениями на языке xBase. А если тупо одно поле проиндексировать, то ясен пень, там не намного больше будет.
87 H A D G E H O G s
 
07.02.21
10:06
(86) Ну я далек от dbf и прочей экзотики.
Sql и Postgree  юзают b+ дерево и не о каких там 2n записей или 2 n обьемах данных речи нет.

SQL, кстати, использует b+ дерево хитро, размещая в ветке/листе дерева не 3 записи,  как показано на картинках, а сколько войдет на 8 кбайтную страницу, так как она все равно будет считана при обращении.

Так сокращается глубина дерева. Отсюда другой вывод - хотите быстрый поиск/быструю вставку в индекс - уменьшайте индексную колонку.
88 H A D G E H O G s
 
07.02.21
10:08
(85) Нет, это я приветствую ссылку на Хирьянова, которого смотрел в его лекциях по C++, сокрушаясь о их бессмысленности.
89 Кирпич
 
07.02.21
10:22
+(86) Да и без всяких составных индексов, в dbf реально индекс в 2 раза больше чем данные. Не знаю как они умудряются, но это так.
90 Кирпич
 
07.02.21
10:23
Наверное вставляют место для расширения
91 Кирпич
 
07.02.21
10:29
проверил на MDX
dbf 499кb
mdx 1141kb

специально открыл mdx в Notepad++
поискал ключ. ключ в единственном экземпляре.
Наверное резервируют место в страницах, для добавления новых ключей. Потому и такой размер.
92 vi0
 
07.02.21
11:14
(87) откуда информация про 3 записи? что за стандарт такой?
93 Кирпич
 
07.02.21
12:06
94 H A D G E H O G s
 
07.02.21
12:19
(92) Для минимума перебора. Но SQL для минимизации вложенности и перестроения предпочитает увеличить число ключей в узле (пока они входят на 8 Кбайтную страницу), тупо перебирая все ключи в узле. Вернее, перебирая не все, а также, биссекцией, скорее всего.
95 vi0
 
07.02.21
12:34
(94) я так понимаю что sql действует просто по принципам построения сбалансированного дерева, поэтому не понимаю про три записи
96 H A D G E H O G s
 
07.02.21
12:38
(95) В случае 3 записей - ты заходишь в узел в центральную запись и сравниваешь с искомым значение. Если равно - то идешь по центральной ветке, если меньше - идешь по правой ветке, иначе - по левой. 2 Чтения. Если будет больше 3 записей - будет больше чтений. Если будет 2 записи - все равно 2 чтения.
97 cViper
 
07.02.21
12:50
(75)Ну и много вы знаете серьезного ПО написанного на делфи и турбовижн?
98 ДенисЧ
 
07.02.21
12:52
(97) А ты мало? Трубу сейчас уже не найдёшь, а дельфей много.
99 cViper
 
07.02.21
12:53
(71) Хардкорные, это когда у тебя онлайн тест и 4 этапа этапа в офисе. Онлайн решаешь задачи. Потом в офисе: 2 на кодинг, 1 на систем дизайн, 1 поведенческий. Это очень распространено в FAANG и компаниях поменьше, яндекс и прочие.
100 cViper
 
07.02.21
12:55
(98) Скорее всего в телекофе делфи + оракл. НО там скорее всего уже отказываются от делфи и переходят на джава. Тот же мегафон давно уже на микросервисную джаву уходит.
101 cViper
 
07.02.21
12:55
+(100) телекоме
102 vi0
 
07.02.21
13:14
(96) что то это описание не похоже на сбалансированное дерево
103 H A D G E H O G s
 
07.02.21
13:24
(102) Давайте лучше послушаем хорошую музыку
https://youtu.be/GPwsKRUtKB4
104 Кирпич
 
07.02.21
16:45
BTree с тремя ключами - это игрушечное BTree для рисования на доске. В боевом всегда много ключей на странице.
105 GAS
 
07.02.21
18:22