Я создаю таблицу символов для проекта, над которым я работаю. Мне было интересно, какие мнения людей имеют о преимуществах и недостатках различных методов, доступных для хранения и создания таблицы символов.
Я выполнил справедливый бит поиска, и наиболее часто рекомендуются бинарные деревья или связанные списки или хеш-таблицы. Каковы преимущества и недостатки всего вышеперечисленного? (работает в С++)
Предположительно, ваш прецедент будет "вставлять данные один раз (например, запуск приложения), а затем выполнять много чтений, но мало, если какие-либо дополнительные вставки".
Поэтому вам нужно использовать быстрый алгоритм поиска необходимой информации.
Поэтому я считаю, что HashTable был наиболее подходящим алгоритмом для использования, поскольку он просто генерирует хэш вашего ключевого объекта и использует его для доступа к целевым данным - это O (1). Остальные - O (N) (Связанные списки размера N - вам нужно перебирать список по одному, в среднем по N/2 раза) и O (log N) (Двоичное дерево - вы вдвое уменьшаете пространство поиска с помощью каждая итерация - только если дерево сбалансировано, так что это зависит от вашей реализации, несбалансированное дерево может иметь значительно худшую производительность).
Просто убедитесь, что в HashTable достаточно пробелов (ведра) для ваших данных (R.e., Soraz комментировать этот пост). Большинство реализаций каркаса (Java,.NET и т.д.) Будут иметь качество, которое вам не нужно будет беспокоиться о реализации.
Проводили ли вы курс по структурам данных и алгоритмам в университете?
Используются стандартные компромиссы между этими структурами данных.
То, что все, кажется, забывают, состоит в том, что для маленьких Ns, IE немного символов в вашей таблице, связанный список может быть намного быстрее, чем хэш-таблица, хотя теоретически его асимптотическая сложность действительно выше.
Существует знаменитый qoute из Pike Notes по программированию на C: "Правило 3. Необычные алгоритмы медленны, когда n мало, а n обычно невелико. Необычные алгоритмы имеют большие константы. Пока вы не знаете, что n часто собирается будь большой, не увлекайтесь". http://www.lysator.liu.se/c/pikestyle.html
Я не могу сказать из вашего сообщения, если вы будете иметь дело с небольшим N или нет, но всегда помните, что лучший алгоритм для больших N не всегда хорош для небольших Ns.
Похоже, что все может быть правдой:
Если это так, вы можете рассмотреть отсортированный список по любой из этих других структур. Это будет хуже, чем другие во время вставок, поскольку отсортированный список - это O (N) для вставки, по сравнению с O (1) для связанного списка или хеш-таблицы, а O (log 2 N) для сбалансированное двоичное дерево. Но поиск в отсортированном списке может быть быстрее любой из этих других структур (я объясню это коротко), поэтому вы можете выйти на первое место. Кроме того, если вы выполняете все свои вставки сразу (или иначе не требуете поиска, пока все вставки не будут завершены), вы можете упростить вставку к O (1) и сделать более быстрый сортировку в конце. Более того, отсортированный список использует меньше памяти, чем любая из этих других структур, но единственный способ, который это может иметь значение, - это иметь много мелких списков. Если у вас есть один или несколько больших списков, хеш-таблица, скорее всего, не выполняет отсортированный список.
Почему поисковые запросы могут быть быстрее с отсортированным списком? Ну, ясно, что это быстрее, чем связанный список, с последним временем поиска O (N). При двоичном дереве поиски остаются только O (log 2 N), если дерево остается идеально сбалансированным. Сохранение сбалансированного дерева (например, красно-черного) добавляет сложности и времени ввода. Кроме того, как с привязанными списками, так и с бинарными деревьями каждый элемент является выделенным отдельно 1 node, что означает, что вам придется указывать указатели на разыменования и, вероятно, переходить на потенциально широко изменяющиеся адреса памяти, увеличивая вероятность промаха в кеше.
Как и для хэш-таблиц, вы должны, вероятно, прочитать > пара другие вопросы здесь, в StackOverflow, но здесь есть следующие основные моменты:
Конечно, если вы действительно заботитесь о том, как любая из этих структур данных будет работать, вы должны их протестировать. У вас должно быть мало проблем с поиском хороших реализаций любого из них для большинства распространенных языков. Не должно быть слишком сложно бросить некоторые из ваших реальных данных в каждой из этих структур данных и посмотреть, какая из них лучше всего работает.
Мне нравится ответ Билла, но он на самом деле не синтезирует вещи.
Из трех вариантов:
Связанные списки относительно медленны для поиска элементов из (O (n)). Поэтому, если у вас много элементов в вашей таблице, или вы собираетесь делать много поисков, то это не лучший выбор. Тем не менее, их легко построить, и их легко написать. Если таблица небольшая и/или вы только выполняете небольшое сканирование через нее после ее создания, то это может быть для вас выбор.
Таблицы хэшей могут быть невероятно быстрыми. Однако для этого вам нужно выбрать хороший хеш для ввода, и вам нужно подобрать стол, достаточно большой, чтобы держать все без большого количества хеш-коллизий. Это означает, что вы должны знать что-то о размере и количестве вашего ввода. Если вы это испортите, вы получите действительно дорогой и сложный набор связанных списков. Я бы сказал, что, если вы заранее не знаете, насколько велика таблица, не используйте хеш-таблицу. Это не согласуется с вашим "принятым" ответом. К сожалению.
Это оставляет деревья. У вас есть вариант здесь: сбалансировать или не сбалансировать. То, что я нашел, изучая эту проблему в коде C и Fortran, мы имеем здесь, что вход в таблицу символов имеет тенденцию быть достаточно случайным, что вы теряете только уровень дерева или два, не балансируя дерево. Учитывая, что сбалансированные деревья медленнее вставляют элементы и сложнее реализовать, я бы не стал их беспокоить. Однако, если у вас уже есть доступ к красивым отлаженным библиотекам компонентов (например, С++ STL), вы также можете пойти и использовать сбалансированное дерево.
Несколько вещей, на которые следует обратить внимание.
Двоичные деревья имеют только O (log n) поиск и сложность вставки, если дерево сбалансировано. Если ваши символы вставляются довольно случайным образом, это не должно быть проблемой. Если они будут вставлены по порядку, вы создадите связанный список. (Для вашего конкретного приложения они не должны быть в каком-либо порядке, поэтому вам должно быть все в порядке.) Если есть вероятность, что символы будут слишком упорядоченными, Red-Black Дерево - лучший вариант.
Таблицы хэшей дают среднюю сложность вставки и поиска O (1), но здесь также существует оговорка. Если ваша хеш-функция плохая (и я имею в виду очень плохой), вы также можете создать связанный список. Однако любая разумная функция хеш-функции должна делать, поэтому это предупреждение действительно только для того, чтобы вы знали, что это может произойти. Вы должны просто проверить, что ваша хеш-функция не имеет большого количества коллизий по вашему ожидаемому диапазону входов, и все будет в порядке. Еще одним незначительным недостатком является использование хэш-таблицы фиксированного размера. Большинство реализаций хэш-таблицы растут, когда они достигают определенного размера (точнее, коэффициент загрузки, см. здесь). Это делается для того, чтобы избежать проблемы, возникающей при вводе миллиона символов в десять ведер. Это приводит только к десяти связанным спискам со средним размером 100 000.
Я бы использовал только связанный список, если бы у меня была очень короткая таблица символов. Это проще всего реализовать, но лучшая производительность для связанного списка - наихудшая производительность для двух других опций.
Другие комментарии были сосредоточены на добавлении/извлечении элементов, но это обсуждение не является полным без учета того, что требуется для повторения всей коллекции. Короткий ответ здесь состоит в том, что хэш-таблицы требуют меньше памяти для перебора, но для деревьев требуется меньше времени.
Для хэш-таблицы издержки памяти на итерации по парам (ключ, значение) не зависят от емкости таблицы или количества элементов, хранящихся в таблице; на самом деле, итерация должна требовать только одной переменной индекса или двух.
Для деревьев объем требуемой памяти всегда зависит от размера дерева. Вы можете либо поддерживать очередь невидимых узлов, итерации, либо добавлять дополнительные указатели в дерево для упрощения итерации (создание дерева для целей итерации, как связанный список), но в любом случае вам необходимо выделить дополнительную память для итерации.
Но ситуация меняется, когда дело доходит до времени. Для хэш-таблицы время, необходимое для итерации, зависит от емкости таблицы, а не от количества сохраненных элементов. Таким образом, таблица, загруженная с 10% емкости, займет примерно 10 раз дольше, чтобы перебрать более чем связанный список с теми же элементами!
Это, конечно, зависит от нескольких вещей. Я бы сказал, что связанный список прав, поскольку он имеет несколько подходящих свойств для работы в качестве таблицы символов. Бинарное дерево может работать, если у вас уже есть одно, и не нужно тратить время на запись и отладку. Мой выбор был бы хэш-таблицей, я думаю, что для этой цели более или менее используется.
Этот вопрос проходит через разные контейнеры в С#, но они похожи на любом используемом вами языке.
Если вы не ожидаете, что ваша таблица символов будет небольшой, я должен избегать связанных списков. Список из 1000 элементов в среднем займет 500 итераций, чтобы найти в нем какой-либо элемент.
Двоичное дерево может быть намного быстрее, если оно сбалансировано. Если вы сохраняете содержимое, сериализованная форма, скорее всего, будет отсортирована, и когда она будет перезагружена, результирующее дерево будет полностью не сбалансировано как следствие, и оно будет вести себя так же, как связанный список, потому что это в основном, чем он стал. Сбалансированные алгоритмы дерева решают эту проблему, но делают весь shebang более сложным.
Хешмап (пока вы выбираете подходящий алгоритм хеширования) выглядит как лучшее решение. Вы не упомянули о своей среде, но почти все современные языки имеют встроенный хашмап.