Существует ли схема всех перечисленных структур данных и алгоритмов?

Question

Есть ли где-нибудь диаграмма или таблица, которая отображает множество (хотя бы популярных) структур данных и алгоритмов с их временем выполнения и эффективностью?

То, что я ищу, - это то, на что я могу взглянутьна и решить, какая структура / алгоритм лучше всего подходит для конкретного случая.Это было бы полезно при работе над новым проектом или просто в качестве учебного пособия.

Answer 1

Диаграмма или таблица не будут особенно полезными.

Если вы собираетесь использовать конкретный алгоритм или структуру данных для решения проблемы, вам лучше знать и понимать ее изнутри и снаружи. И это включает в себя знание (и знание того, как получить) их соответствующие эффективности. Это не особенно сложно. Большинство стандартных алгоритмов имеют простые интуитивно понятные среды выполнения, такие как N^2, N*logN и т. Д.

Это, как говорится, во время выполнения Big-O не все. Взять, к примеру, сортировку. Сортировка кучи имеет больший Big-O, чем, скажем, быстрая сортировка, но на практике быстрая сортировка работает намного лучше. Постоянные факторы в Big-O также могут иметь огромное значение.

Когда вы говорите о структурах данных, в них есть гораздо больше, чем кажется на первый взгляд. Например, хэш-карта выглядит просто как древовидная карта с гораздо лучшей производительностью, но вы получаете дополнительную структуру сортировки с древовидной картой.

Знание того, какой алгоритм / структура данных лучше всего использовать, - это вопрос знаний, а не справочная таблица.

Хотя вернемся к вашему вопросу, я не знаю ни одной такой ссылки. Было бы неплохо сделать это самостоятельно. В Википедии есть довольно приличные статьи об общих алгоритмах / структурах данных вместе с приличным анализом.

Answer 2

Я не верю, что такой список существует.Огромное количество известных алгоритмов и структур данных ошеломляет, и все время разрабатываются новые.Более того, многие из этих алгоритмов и структур данных являются специализированными, что означает, что даже если бы у вас был список перед вами, было бы трудно узнать, какие из них применимы для конкретных проблем, которые вы пытались решить.

Другая проблема с таким списком заключается в том, как количественно оценить эффективность.Если бы вы должны были ранжировать алгоритмы с точки зрения асимптотической сложности (big-O), то вы могли бы в конечном итоге поставить некоторые алгоритмы и структуры данных, которые асимптотически оптимальны, но неосуществимо медленны на небольших входах, перед известными алгоритмамибыть быстрым для практических случаев, но не может быть теоретически совершенным.В качестве примера рассмотрим поиск алгоритма медианы медиан для линейной статистики временного порядка, который имеет такой огромный постоянный фактор, что другие алгоритмы имеют тенденцию быть намного лучше на практике.Или рассмотрим быструю сортировку, которая в худшем случае равна O (n ² ), но на практике имеет среднюю сложность O (n lg n) и на намного быстрее, чем другие алгоритмы сортировки.

С другой стороны, если бы вы попытались перечислить алгоритмы по эффективности во время выполнения, этот список мог бы ввести в заблуждение.Эффективность во время выполнения зависит от ряда факторов, которые зависят от машины и ввода (таких как локальность, размер ввода, форма ввода, скорость машины, архитектура процессора и т. Д.). Как правило, это может быть полезно-просто, но во многих случаях вас могут ввести в заблуждение числами, чтобы выбрать один алгоритм, когда другой намного превосходит.

Существует также сложность реализации, которую следует учитывать.Многие алгоритмы существуют только в статьях или имеют справочные реализации, которые не оптимизированы или написаны на языке, который не является тем, что вы ищете.Если вы найдете алгоритм Святого Грааля, который делает именно то, что вы хотите, но не реализуете его, может быть невероятно сложно кодировать и отлаживать вашу собственную версию.Например, если бы не было преобладания реализаций красного / черного дерева, думаете ли вы, что сможете написать его самостоятельно?Как насчет кучи Фибоначчи?Или (из личного опыта) деревья Ван Эмде Боаса?Часто может быть хорошей идеей выбрать более простой алгоритм, который «достаточно хорош», но который легко реализовать в гораздо более сложном алгоритме.

Короче, я хотел бы, чтобы существовала такая таблица, которая действительно имела бы все этоинформация, но, практически говоря, я сомневаюсь, что это может быть построено таким образом, что это полезно.Ссылки на Википедию из комментариев @ hammar на самом деле довольно хороши, но лучший способ узнать, какие алгоритмы и структуры данных использовать на практике, - это попробовать их на практике.

Answer 3

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

Тем не менее, в NIST США имеется Словарь алгоритмов и структур данных , в котором содержится больше, чем большинство людей когда-либо знают или заботятся о них. Он охватывает большинство очевидных «больших», которые все знают, и очень много менее известных. В Кентерберийском университете есть другой , который (или, по крайней мере, мне кажется) немного скромнее, но все же охватывает большую часть того, о чем обычно заботится обычный программист, и немного лучше организован для поиска алгоритма. чтобы решить конкретную проблему, вместо того, чтобы основываться в первую очередь на том, что вы уже знаете название алгоритма, который вам нужен.

Существуют также различные коллекции / списки, которые являются более специализированными. Например, Репозиторий алгоритмов Stony Brook посвящен в первую очередь (исключительно?) Комбинаторным алгоритмам. Он основан на Руководстве по разработке алгоритмов , поэтому он может быть особенно полезен, если у вас есть / пользуетесь этой книгой (и, если вам интересно, эта книга, как правило, довольно высоко ценится) .

Answer 4

Первым приоритетом для компьютерной программы является правильность, а вторым, чаще всего, время программиста - что напрямую связано с удобством и расширяемостью.

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