Что почитать по алгоритмам и структурам данных?

не поверите но
"алгоритмы и структуры данных".

Дональд Кнут "Искусство программирования" для начала...

"Алгоритмы на java", Сэджвик и Уэйн
Есть соответствующий стендфордский курс на курсере.
Java пусть не пугает. Там только минимум-миниморум сишного по-сути синтаксиса.

Курс, кстати, офигенный. Я первую часть только проходил, на вторую рука не поднялась.
Особенно автоматическое тестирование практических заданий понравилось. Просто офигенно. И по используемой памяти оценка и по производительности и результаты прогонов на куче тестовых наборов.

(0) а как Вы это хотите применять в ключе 1С? я к тому, что в 1С особо нет выбора какую реализацию коллекции выбрать или как реализован внутри map (через красно-черные деревья или по-другому), т.к. от программиста 1С это все закрыто. Также большинство книг по алгоритмам используют/разъясняют паттерны проектирования, которые в большинстве своем требуют ООП.

(5) Что-то ты путаешь. ООП с паттернами - это обычно отдельная тема.

(5) В 1С есть ООП

(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/ - отличная платформа для решения задач по программированию и изучению структур данных. Там есть карточки с описанием структур данных и задачами на эти структуры. Также есть задачи на дизайн и имплементацию СД.

(0) https://javarush.ru/groups/posts/2922-recenzija-na-knigu-strukturih-dannihkh-i-algoritmih-java-robert-lafore

(5) и вот так всегда...  Сначала "да зачем алгоритмы и структуры программисту 1С", а потом "ой, ну это же программист 1С, откуда он про алгоритмы и структуры знает".
Чтоб голова правильно работала, для этого и изучать надо все вышеперечисленное.

(6) н-р, паттерн синглтон использует инкапсуляцию (ООП), для хранения инстанса. декоратор - ну по сути тоже. и т.д.
я не говорю, что нет паттернов без ООП, но многие используют.

(7) а можно подробнее в чем он заключается? точнее как реализуются его принципы в 1С?

(10) так я не говорил, что учиться и изучать что-то другое (не 1С) - это плохо.

(0) не вижу практического смысла.

(0) а где ты эти знания собрался применять? Уже всё придумано за нас. Пиши ORDER BY и СУБД отсортирует наиоптимальнейшим образом

по графам начиная с 11й лекции https://www.youtube.com/playlist?list=PLDrmKwRSNx7J16QBIZMNmAUDRQjjwVTTG

вот курс неплохой https://www.youtube.com/playlist?list=PLrCZzMib1e9pDxHYzmEzMmnMMUK-dz0_7
простым языком без занудства

.

(2) Кнут чересчур академичен.
Н.Вирт "Алгоритмы и структуры данных"

(11) Имел в виду, что ООП с паттернами - отдельная тема от базовых структур данных с алгоритмами.

(15) Обычно начинают с теории оценки производительности алгоритмов. Ну и структуры ж данных еще.
"Плохие программисты думают о коде. Хорошие программисты думают о структурах данных и их взаимосвязях" (с) Линус Торвальдс

(16) Какие структуры данных использует СУБД для реализации индексов?

Просто (0) прислушался к Бедуину и начал спрыгивать с 1С :)

(0) смысл ... если работаете с табличками
БД то и sql на это . Он и максимум найдет и отсортирует

Чтобы велики типа поиска максимума в цикле
Или рекурсией алгоритмицки не придумывать

(16) Лучше на поле наложить индекс, чтобы облегчить работу СУБД. "Наиоптимальнейшая" сортировка по мнению СУБД может занимать двое суток для тебя.

Как  раз по теме ... структуры данных . Т.е. отношение
кортеж атрибут индекс и select

(0) Лучше всего почитать Гради Буча. Особенно если хочешь пойти в ООП. Для 1С тоже не помешает для карьеры архитектором, тим лидом и т.д.

(0) Был уже хороший ответ: (8). Добавлю к нему, что "Алгоритмы: построение и анализ" (CRLS) - это классическая книга, хороший университетский курс. Да книга не самая простая, но это нормальный серьезный   учебник (в отличие от, например, вышеупомянутой книги Вирта, при всем уважении к Вирту). Есть еще на русском языке хороший курс лекций Паши Маврина, это курс лекций в ИТМО: https://www.youtube.com/user/pavelmavrin.

Если вышеперечисленное сложновато, то можно попробовать книги Седжвика, вроде бы они были немного проще.

(30) > хороший университетский курс
Для входа в тему, особенно людям "со стороны", лучше что-то полегче. Седжвика я уже предлагал. Но насколько я понял по советам и описанию, Лафоре - еще попроще.

(31) >Для входа в тему, особенно людям "со стороны", лучше что-то полегче

(31) >Для входа в тему, особенно людям "со стороны", лучше что-то полегче

Cогласен, просто человек написал, что "Грокаем алгоритмы" уже прочитал, а это уже какой-никакой вход, хоть и лайтовый, поэтому предлагаю переходить на более тяжелые препараты :)

(0) Пиши свою СУБД. С парочкой связанных таблиц. Из самого сложного из конструкций языка - подустимы Struct. Потом нагрузи ее полтеррабайтом данных. Сразу придет понимание, что нужно почитать по алгоритмам.

(23) би-дерево, или как там его. А зачем это вообще знать?

(27) что-то не помню, чтобы СУБД напряглась при сортировке данных

начинать надо с чистого кода Мартина )

(36) так то сортировка одна из ресурсоемких операций

(38) а ты хочешь сказать что отсортируешь данные быстрее/экономичнее чем oracle? Операция ресурсоемкая, но СУБД выполняет её оптимальным образом. Зачем изобретать велосипед?

(37) это да. Даже 1сникам будет полезно

(39) нет, я не хочу этого сказать, я прокомментировал твою фразу что СУБД не напрягается при сортировке

(39) По крайней мере надо знать, что сортировка в любом случае дороже выборки по индексу, и почему надо проводить периодическую переиндексацию. И почему, например, файл индекса в 2 с лишком раза больше чем исходные индексируемые значения (а это было важно для баз dbf/cdx).
А для этого как раз книжка о теории программирования и нужна.

(35) если не знать, то не будешь на экспертном уровне понимать работу сервера: что такое количество чтений, как их анализировать, почему индекс занимает столько то места, как повлиять на это, как сервер может обходить индекс, и почему в каких то моментах он делает это неотимально и т.д.
в книге Querying Microsoft SQL Server Exam 70-461, которая для подготовки к экзамену по запросам, этой теме выделена отдельная глава
из книги скрин https://i0.wp.com/wiseadvice-it.ru/upload/medialibrary/fe0/20_1.jpg

(42) не то чтобы изучал, но хорошенько полистал книгу по алгоритмам и структурам данных. Не нашел там совершенно ничего, проливающего свет на внутреннюю кухню СУБД. Если уж интересует "как там в скуле работает", то куда полезнее почитать соответствующую литературу и документацию

(43) это всё хорошо, только причем тут "классические" алгоритмы?

(44) Способ хранения двоичных деревьев индекса в одномерном массиве(таблице) знаете? Левая ветка 2n, правая 2n+1. Где n-позиция ключевого поля в таблице данных. Так вот об этом у Вирта есть.

(46) не знаю. Но даже если бы знал, какая практическая польза от этих знаний? СУБД не предоставляет доступа покопаться в кишочках индекса, да и незачем

С этими алгоритмами примерно как с математикой. Математика программисту нужна... в 1% их всех программистских задач, в остальных 99% нафиг не нужна. С алгоритмами примерно то же самое. Это не универсальные знания, в подавляющем большинстве случаев они нафиг не нужны

(47) СУБД разные бывают, и вот например в dbf это ограничение было весьма актуально. Знать, откуда оно произошло, весьма полезно.

(47) Это как для автомобилистов - полезно знать теорию двигателей внутреннего сгорания и теорию машин и механизмов в общих чертах. Чтобы хотя бы понимать, что случилось с машиной, можно ли ехать дальше или срочно вызывать эвакуатор.

(49) я когда-то тоже так думал. Мол 1сник должен уметь на "ты" СУБД. Пришел в крупную команию, со здоровенными базами данных, а там... целая команда грамотных сертифицированных DBA, которые занимаются всей магией связанной с работой СУБД

(50) Для 1с это всё-таки менее характерно, и жесткую специализацию скорее можно считать исключением из правил.

Для программиста есть куда более полезные знания, которые он сможет применять в повседневности. Например, принципы SOLID, знание английского. Имхо, алгоритмы и структуры данных где-то ближе к концу списка "знаний must have"

(52) И в результате деятельности таких вот программистов мы имеем ситуацию, когда ту же самую задачу, которую успешно решали на P200, теперь приходится решать на core i5. Это и к 1с относится, кстати.

это не из-за алгоритмов, а из-за увеличения уровней абстракций и количества фреймворков

(54) Ну так одно с другим связано. Программисты не хотят влезать в детали и берут фреймворк, который ради универсальности дает увеличение ресурсоемкости на порядок. Иногда возникает мысль, что в отрасли действует некая "группа регрессоров", целью которой является замедлить развитие человечества.
Если бы программистам 60-х вдруг дать современный тот же Core i5 с free pascal внутри, страшно представить, что бы они могли сотворить (в хорошем смысле). А современные программисты эти ресурсы используют для того чтобы точка исполнения кода продиралась через уровни всех этих абстракций, делая что-то весьма тривиальное.

(45) прочитай на какой комментарий я отвечал тебе

(47) математика это в первую очередь инженерное мышление

(50) и они давали 1сниками рекомендации по построению запросов?

(0) Гимнастики для ума захотелось? А зачем книги? Вот практические задачи - подумай как решить:
- рекурсивно пометить на удаление то, на что ссылается объект
- поменять свойство доступность элементов, входящих в группу формы (они вложены, как матрёшка)
- есть папка неоднократного уровня вложенности - скопировать оттуда файлы с расширением xml в другую папку на один уровень, для уникальности прибавить к именам случайные ГУИДы
- генерировать все возможные комбинации нескольких элементов справочника
- для ведомости ИНВ-19 минимальную цену в пересортице строк найти, пересортившиеся строки пользователь укажет - это и будет граф (в УПП в 2013 году этого не было)
- расчетные показатели в отчете с использованием построителя отчетов (механизмами запросов было невозможно и пришлось пускать рекурсию по результату запроса)
- критические задачи найти в сетевом графике работ (задач, удлинение или сдвиг которых неминуемо приводит к сдвигу окончания проекта)
- более 30000 видов затрат, друг на друга ссылаются по графу, который пользователи задали на некоторых копейки зависли (сумма < 1 рубля) - надо списать на ближайшую где сумма > 1 рубля

и так далее...

(55) почему файл индекса в 2 раза больше файла данных?

отмечусь, мб что интересное найду здесь

(60) Количество записей индекса по одному полю составляет максимум 2n+1 от количества записей в основной таблице. А размер может быть всякий. В dbase например допускались индексные выражения, и там индекс мог быть намного жирнее исходного поля.

(53) ты путаешь. Раньше кода было с гулькин нос. Сейчас прогер строчку кода пишет, а за ней проворачивается миллион строк более низкоуровневого кода

(55) ты предлагаешь доблестно тратить время на очередное переизобретение уже готового?

(58) нет. Разве что в отдельных специфичных случаях

(46) Это heap

(52) Ахахахаха. Серьезно?! Очень часто на позицию java dev спрашивют про устройство HashMap, TreeMap, просят реализовать какую-либо структуру данных (LinkedList, Stack, Queue, HashTable, LRUCache, Trie). Задают вопросы по сложности алгоритмов, какие из них реализованы в языке, просят их реализовать. Дают задачи на кодирование, когда надо в блокноте решить задачи различного уровня.

(55) Фреймворки то и написали специально для того, чтобы ты свой велосипед каждый раз не писал. Взял готовое решение и написал бизнес-логику. Это все равно, чтобы каждый раз писать платформу 1С:Предприятие.

(62) А давай ты попробуешь в структуры данных еще раз?
http://prntscr.com/yi6too

(61) Скажи свои контакты, я потерял тебя со смертью аськи

(67) это что за хардкорные интервью такие? Специально сдул книгу оракла по подготовке к сертификации по Java:
https://www.amazon.com/OCP-Certified-Professional-Programmer-1Z0-809/dp/1119067901
там коллекциям посвящено семьдесят страниц, из них имплементации Map всего 2 страницы. Уж если папка оракл на экзаменах не спрашивает про кишочки коллекций, на кой другие эти спрашивают?

+(71) неправильно написал. Дженерикам + коллекциям посвящено 68 страниц

алгоритмы для чайников, алгоритмы для начинающих, структуры данных и алгоритмы на java.
с. скиена - алгоритмы.

(69) И что вы тут пытаетесь сравнивать? Речь о сравнении объема конкретного индекса и индексного поля основной таблицы, а не о сравнении общего объема таблицы и всех её индексов. Ваше сравнение не имеет смысла.

(68) Фреймворки разные бывают. Вот взять например турбовижн или дельфи. Они адекватными людьми сделаны, а не хипстерами миллениалами..

(74) Надо просто немного напрячься. Там как раз сравнение объема конкретного индекса и индексного поля.

(76) Сами напрягитесь. "Пространство данных" и "место, занимаемое индексом" относится к ТАБЛИЦЕ _Reference41. А не к конкретному полю.

(77) И собственно о 2n+1 я говорил относительно именно формата индексов dbf (idx/cdx), а в mssql могут использоваться другие способы хранения, например без хранения собственно значений ключей в индексе, а только с хранением ссылки на поле исходной таблицы, содержащей значение. Тогда 2n+1 будет относится к размеру идентификатора записи основной таблицы. А может хранить значения, но повторяющиеся ссылки неуникального индекса не разворачивать в дерево, а хранить в связанном с узлом списке. Способов полно.

А еще бывает индексируют туда и обратно, чтобы быстро LIKE работал.
Ну типа "МАМА" и "АМАМ". Вот тебе и сразу в два раза больше.

(77) специально для тебя там слева показана иерархия таблицы, состоящая из одного поля. И да, размер Пространства данных чуть больше, чем
25*2*100000 на служебные структуры.
Но все равно, мы не видим, что размер индекса больше, чем размер данных в 2 раза.
Тут не 1с хаять, тут думать надо.

(78) Ты несешь бред насчет sql. Почитай про b+ деревья.

(79) а чаще бывает, что страница индекса не наполнена на 100%, а где то ближе к 50% и ты радостный несешься на форум :-)

(0)тимофей хирьянов мфти лекции алгоритмы на питон.

(83) https://youtu.be/OrbrzWHbnns

(84)Ты наверное это хотел запостить в ветку где обсуждают Волков победил нокаутом Оверима? Тогда подходит)

(82) Провинциальный 1сник наверное хотел сказать про dbf. Там да. Индексный файл cdx, какой нибудь, запросто мог быть в два раза больше файла dbf. Туда просто можно засунуть кучу индексов, да еще и всяких составных да с выражениями на языке xBase. А если тупо одно поле проиндексировать, то ясен пень, там не намного больше будет.

(86) Ну я далек от dbf и прочей экзотики.
Sql и Postgree  юзают b+ дерево и не о каких там 2n записей или 2 n обьемах данных речи нет.

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

Так сокращается глубина дерева. Отсюда другой вывод - хотите быстрый поиск/быструю вставку в индекс - уменьшайте индексную колонку.

(85) Нет, это я приветствую ссылку на Хирьянова, которого смотрел в его лекциях по C++, сокрушаясь о их бессмысленности.

+(86) Да и без всяких составных индексов, в dbf реально индекс в 2 раза больше чем данные. Не знаю как они умудряются, но это так.

Наверное вставляют место для расширения

проверил на MDX
dbf 499кb
mdx 1141kb

специально открыл mdx в Notepad++
поискал ключ. ключ в единственном экземпляре.
Наверное резервируют место в страницах, для добавления новых ключей. Потому и такой размер.

(87) откуда информация про 3 записи? что за стандарт такой?

(92) вот с таких картинок https://cdn-images-1.medium.com/fit/t/1600/480/1*MRxhV0bPtbsHjUmuH9li_A.png

(92) Для минимума перебора. Но SQL для минимизации вложенности и перестроения предпочитает увеличить число ключей в узле (пока они входят на 8 Кбайтную страницу), тупо перебирая все ключи в узле. Вернее, перебирая не все, а также, биссекцией, скорее всего.

(94) я так понимаю что sql действует просто по принципам построения сбалансированного дерева, поэтому не понимаю про три записи

(95) В случае 3 записей - ты заходишь в узел в центральную запись и сравниваешь с искомым значение. Если равно - то идешь по центральной ветке, если меньше - идешь по правой ветке, иначе - по левой. 2 Чтения. Если будет больше 3 записей - будет больше чтений. Если будет 2 записи - все равно 2 чтения.

(75)Ну и много вы знаете серьезного ПО написанного на делфи и турбовижн?

(97) А ты мало? Трубу сейчас уже не найдёшь, а дельфей много.

(71) Хардкорные, это когда у тебя онлайн тест и 4 этапа этапа в офисе. Онлайн решаешь задачи. Потом в офисе: 2 на кодинг, 1 на систем дизайн, 1 поведенческий. Это очень распространено в FAANG и компаниях поменьше, яндекс и прочие.

(98) Скорее всего в телекофе делфи + оракл. НО там скорее всего уже отказываются от делфи и переходят на джава. Тот же мегафон давно уже на микросервисную джаву уходит.