Лучший алгоритм для пары ключ / значение, где ключ - это int64 в Delphi, до Delphi 2009?

Question

Мне нужен алгоритм для хранения пары ключ / значение, где ключом является Int64. В настоящее время я использую отсортированный IntList (такой же, как TStringList, но хранит int64). Это дает мне O (log n) для операций поиска, вставки и удаления. Поскольку мне никогда не нужны отсортированные элементы, это немного неэффективно. Мне нужна какая-то хеш-таблица для операций O (1). Проблема в том, что большинство реализаций, которые я могу найти, предполагают, что ключ является строкой. Теперь я мог бы явно преобразовать ключ Int64 в строку, но это кажется расточительным. Есть идеи?

Я не знаю количество элементов до того, как они введены в структуру данных.

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

Answer 1

Delphi 2009 и более поздние версии добавили Generics.

Итак, начиная Delphi 2009, вы можете реализовать свою пару ключ / значение аналогично тому, как вы это делаете в .NET, используя TDICTIONARY.

И TDICTIONARY в Delphi использует таблицу хеш-таблиц и имеет O (1) операций.

Answer 2

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

Предполагая, что ваши ключи не кратны чему-то (например, адреса, которые будут кратны 4, 8, 16 и т. Д.), Вы могли бы немного ускорить процесс, используя список нескольких из этих объектов IntList, и вычислить сначала индекс в этот массив списков. Используя оператор mod и простое число, можно легко рассчитать индекс списка. Как всегда, это компромисс между скоростью и потреблением памяти.

Вы могли бы также погуглить для хорошей реализации разреженных массивов. В библиотеке IIRC есть библиотека EZDSL Джулиана Бакнолла.

Answer 3

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

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

Некоторые реализации приведены здесь: Реализация хеш-таблицы для Delphi 5

Answer 4

Некоторые мысли, а не полноценное решение.

Если нет определенных доказательств того, что сам поиск является узким местом (не используйте свое «чувство» для обнаружения узких мест, используйте профилировщик кода), я бы придерживался IntList ... Если время, потраченное на фактический поиск / insert / delete не составляет по крайней мере 20% от общего времени процессора, даже не беспокойтесь.

Если вам все еще нужна хеш-таблица, тогда ...

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

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

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