Эффективная реализация неизменяемых карт?

Мне интересно, есть ли реализация карты, которая:

  • Неизменяемый, так что я могу использовать его в функционального программирования и без труда обеспечить транзакции и concurrency.
  • Быстрый. Я проверил двоичный файл Искать деревья (RB, AVL) и Tries, но ни один из них не был таким быстрым, как Хэш-таблицы. Есть ли карта реализация, поддерживающая постоянное время для обновлений и поиска? (или, по крайней мере, очень быстрое логарифмическое время)

Короче, существует ли функциональная структура данных, которая может сравниться с Hash Maps в производительности?

4 ответа

Clojure имеет неизменяемые отображения. (ссылка). Не знаете, какую базовую структуру данных он использует. Clojure исходный код даст вам дополнительную информацию!


Scala также имеет неизменяемые карты, но они медленнее, чем хеш-таблицы. Я подозреваю, что ответ на ваш вопрос - нет, вы не найдете неизменную реализацию карты с O (1) ожидаемыми операциями ввода/запроса времени.


Я не читал его, но я думаю, что некоторые люди считают чисто функциональные структуры данных как библию для такого рода вещей.


В любом случае, чтобы поделиться с людьми, это две интересные записи в блоге о реализации постоянных векторов в Scala с помощью Tries. Они также упоминают реализацию Clojure, а также новую IntMap в последних выпусках Scala.

http://www.codecommit.com/blog/scala/implementing-persistent-vectors-in-scala http://www.codecommit.com/blog/scala/more-persistent-vectors-performance-analysis

Для этих структур данных я тестировал с ключом как целые числа, но еще не строки. Поскольку мое реальное приложение будет использовать строки в качестве ключей, я не уверен, будет ли реализация более эффективной, чем хэш-карта. Что делать, если я использую HashCode строки в качестве ключа, а затем использовать Persistent Vector для поддержки карты? Я буду использовать 32-way trie для реализации Persistent Vector. Я думаю, что столкновения были бы очень редкими, и память была бы потрачена только соответственно. Но я не уверен в фактической сумме, необходимой для копирования обновлений.

Я скоро опубликую свои результаты.

licensed under cc by-sa 3.0 with attribution.