Связанные списки или хеш-таблицы?

Question

У меня есть связанный список из примерно 5000 записей («НЕ», вставленных одновременно), и я просматриваю список, в некоторых случаях ищу определенную запись (хотя это не очень часто), должен ли я рассматривать Хэш-таблицу как более оптимальный выбор для этого случая, заменяя связанный список (который является двусвязным и линейным)? Использование C в Linux.

Answer 1

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

Если он медленный, но код протестирован, работает и понятен, и есть другие более медленные области, над которыми вы можете работать, чтобы ускориться, сделайте это в первую очередь.

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

Учитывая, что вам нужно искать в списке только в некоторых случаях, вероятность того, что это существенное узкое место в вашем коде, мала.

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

Answer 2

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

Answer 3

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

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

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

Answer 4

Вы измерили и нашли результат поиска производительности при поиске? A hash_map или hash table должно быть хорошо.

Answer 5

Я советую против хэшей почти во всех случаях.

Есть две причины; во-первых, размер хеша фиксирован.

Второе и гораздо более важное; алгоритм хеширования. Откуда ты знаешь, что правильно понял? как он будет вести себя с реальными данными, а не с тестовыми данными?

Я предлагаю сбалансированное б-дерево. Всегда O (log n), нет неопределенности в отношении алгоритма хеширования и нет ограничений по размеру.

Answer 6

Если вы только просматриваете коллекцию, я не вижу никаких преимуществ использования хэш-карты.

Answer 7

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