Comments 18
«Алгоритмы» vs «Структуры данных»
Молоток vs как забивать гвоздь ))
Примем за массив последовательный список элементов.
Что такое "список" и что значит "последовательный"?
Так вот «O» здесь — это «эффективность», а N — это количество итераций для вычисления результата.
Эээ, нет.
По сути, структура — это совокупность именованных элементов.
Файловая система, это совокупность именованных элементов, потому что файл, это именованная область данных на диске. Файловая система, это структура? Кстати, что значит "именнованных"? Словарь, это совокупность именнованных элементов или нет?
И если в массиве к элементу можно обратиться по индексу, то в структуре нельзя
Конечно, ведь структуру вы описали выше, а тут про списки )
А вставка в упорядоченный список имеет эффективность O(Log2N). Подобная эффективность объясняется тем самым алгоритмом двоичного поиска места вставки
С этого места поподробнее. 2 вопроса:
Зачем вы указываете основание логарифма, какое значение оно имеет в теории сложности?
Как вы на односвязном списке (вы про них всю дорогу пишите, вроде) сделаете вставку за логарифм?
Как вы на односвязном списке (вы про них всю дорогу пишите, вроде) сделаете вставку за логарифм?
В авторской классификации там, неожиданно для всех, оказался std::map
Сего дня я решил, что напишу про алгоритмы структур данных.
Лучше бы вы этого не делали.
Спасибо, вспомнились студенческие годы. Но, пожалуйста, если вы посягнули на краткое изложение Кнута, то хотя бы не путайтесь в терминологии.
Big O - это не эффективность алгоритма, а лишь оценка эффективности. Пусть это и небольшое изменение, но значительно меняет смысл. Она не бывает О(2); может быть лишь O(1), O(N). O(Log2N) и т. д.
Массив - это не последовательный список, а просто набор значений в памяти.
Списки - они не связанные, с связные; их не связали, а в них есть связи. И std::map, судя по документации использует в реализации красно-черные деревья, а по сути это ассоциативный массив, но никак не список. Вот std::list - это список.
Не нужно для Хэш-таблицы создавать все ключи сразу и бессмысленно резервировать память. Это всё делается по мере необходимости.
А расскажите чем список от набора отличается? Даже вот интересно прям стало.
Вы говорите, что массив это последовательный список. Список это самостоятельная структура данных. Если в статье о структурах данных кто-то говорит о списке, подразумевается связный список, а не некая абстрактная кучка значений. Это устоявшаяся терминология и в данном контексте вы используете её не верно. Вместо слова "набор" можете использовать любое понравившееся вам слово, хоть кучка, хоть пачка, но не стоит употреблять слова, которые могут быть ассоциированы с другими структурами данных.
Если эти элементарные вещи вам не понятны, то, не стоит писать статьи на такие темы.
В статье есть интересные места, но общий уровень такой низкий что даже новичкам ее порекомендовать нельзя.
смешались
в кучусписки и деревья. В упорядоченный список нельзя вставить за логарифм и бинарный поиск не поможет (ведь нельзя проскочить сразу полсписка, придется проходить все элементы по одному), но можно в дерево. std::map - дерево. А у деревьев есть не совсем тривиальные алгоритмы балансировки, чтобы дерево не превратилось ну собственно в список. Да и в целом деревья - свой мир с кучей вариаций для разных задач. Среди моих любимых https://ru.wikipedia.org/wiki/Куча_(структура_данных) и https://ru.wikipedia.org/wiki/Система_непересекающихся_множествописаны, причем не совсем правильно, только хеш-таблицы с так называемой "закрытой адресацией". А есть еще вариант (и он, возможно, даже более распостранен из-за дружелюбности к кешу) хеш-таблиц с "открытой адресацией" - там когда ячейка уже занята мы не создаем список, а ищем другую свободную ячейку (в простейшем случае - пихаем в ближайшую пустую из соседних справа, но есть и более хитрые алгоритмы).
В качестве утешения могу сказать что в этом вопросе многое зависит от места работы. Кто-то может всю жизнь делать формочки и никогда ни про какие списки не узнать. Да что там кто-то - я в целом интересуюсь такими штуками да и на работе задачи разнообразные, но, скажем, в программировании микроконтроллеров мне даже сортировка пригодилась ровно один раз в жизни (сортировать интервалы для pwm чтоб светить несколькими диодами с помощью одного таймера). Про что-то более сложное и говорить смысла нет.
Ну и да, если хотите все-таки на практике познакомиться с алгоритмами@структурами данных, то рекомендую https://adventofcode.com/ (он сейчас как раз идет, но прошлые годы тоже проходить можно). Там есть некоторые перекосы, но в целом мне нравится то как там проверяется правильность решения. Никто не придирается к коду и не спрашивает вопросы про О большое, просто объем входных данных подобран так чтобы решение "в лоб" считалось часы или дни (в лучшем случае), а решение с хорошим алгоритмом работало за секунды даже на медленном скриптовом языке. Соответственно запускаешь наивный подход, тесты вроде проходит но на основных данных видишь что результата не дождаться, начинаешь думать.
описаны, причем не совсем правильно, только хеш-таблицы с так называемой "закрытой адресацией". А есть еще вариант (и он, возможно, даже более распространён из-за дружелюбности к кешу) хеш-таблиц с "открытой адресацией" - там когда ячейка уже занята мы не создаем список, а ищем другую свободную ячейку (в простейшем случае - пихаем в ближайшую пустую из соседних справа, но есть и более хитрые алгоритмы).
Всё правильно, только вы в терминологии перепутали местами.
Ахо, Хопкрофт, Ульман 'Структуры данных и алгоритмы'
При закрытом хешировании в таблице сегментов хранятся непосредственно элементы словаря, а не заголовки списков. Поэтому в каждом сегменте может храниться только один элемент словаря. При закрытом хешировании применяется методика повторного хеширования. Если мы попытаемся поместить элемент х в сегмент с номером h(x), который уже занят другим элементом (такая ситуация называется коллизией), то в соответствии с методикой повторного хеширования выбирается последовательность других номеров сегментов h1(x), h2(x), ..., куда можно поместить элемент х. Каждое из этих местоположений последовательно проверяется, пока не будет найдено свободное.
Если уж товарищ решил копнуть тему, то следовало бы для начала дать человеческое определение O(n) а про структуры данных начинать с "абстрактных типов данных" (АТД / ADT).
Я уж подумал что ошибиться в таком комментарии было бы сиволично но нет, не перепутал.
https://en.wikipedia.org/wiki/Open_addressing
Open addressing, or closed hashing
адресация открытая, а хеширование закрытое.
А насчет определений и ADT - я так понимаю автор статьи практик. Все эти понятия ему не особо важны, он (и не только он) и без ADT много лет программирует. И хотя подходы могут быть разные и не все одинаково эффективны, но такой подход от практики (когда ты пишешь себе спокойно на условном 1С условные отчеты, а потом тебе не говорят что надо для начала прочесть все тома кнута, а наглядно показывают как на твоей задаче можно сделать эффективнее. Дальше ты если заинтересуешься то и до определений дойдешь) тоже имеет право на существование.
А, понятно. У Ахо, просто, термин "открытая адресация" для этой структуры не используется, и это ввело меня в заблуждение.
Что такого rocket-science в ADT? Если бы автор понимал, что, например, "массив" или "список" определяются в первую очередь не тем как они в памяти или коде представлены, а тем какие операции с ними можно выполнять (что, собственно, и есть ADT), то facepalm-а типа "некий связанный набор данных, где каждый элемент указывает на то, где находится следующий" в статье было бы по крайней мере меньше :)
Здравствуйте. "Паскаль в иллюстрациях" - моя первая книга по программированию. Чудесная книга! Потом у меня ее какой-то студент из Африки зачитал. Спасибо, что напомнили о ней.
Теперь хотелось бы раз'яснить связь между алгоритмами и структурами данных. От выбора структуры данных зависит все: и выбор модели, и, конечно, выбор и эффективность алгоритма. Например, т.н. "транспортные задачи". В матричном представлении решаются линейным программированием, в сетевом - потоковыми алгоритмами.
P.S О(f(n)) <= C*f(n), где C - положительная константа.
А вставка в упорядоченный список имеет эффективность O(Log2N). Подобная эффективность объясняется тем самым алгоритмом двоичного поиска места вставки, о котором я вещал в прошлой статье.
Как осуществить двоичный поиск без доступа к произвольному элементу?
«Алгоритмы» vs «Структуры данных»