Как реализовать хэш-таблицы на функциональном языке?

Ответ 1

Есть ли способ эффективно реализовать хеш-таблицы на чисто функциональном языке?

Хеш-таблицы представляют собой конкретную реализацию абстрактной структуры данных "словарь" или "ассоциативный массив". Поэтому я думаю, что вы действительно хотите спросить об эффективности чисто функциональных словарей по сравнению с императивными хеш-таблицами.

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

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

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

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

Есть много чисто функциональных словарей:

• Сбалансированные деревья (красно-черные, AVL, сбалансированные по весу, деревья пальцев и т.д.), Например, Map в OCaml и F # и Data.Map в Haskell.

• Попытки хэширования, например, PersistentHashMap в Clojure.

Но эти чисто функциональные словари работают намного медленнее, чем приличные хеш-таблицы (например, Dictionary.NET).

Остерегайтесь бенчмарков на Haskell, сравнивающих хеш-таблицы с чисто функциональными словарями, утверждая, что чисто функциональные словари конкурентоспособны. Правильный вывод состоит в том, что хеш-таблицы на Haskell настолько неэффективны, что они почти такие же медленные, как и чисто функциональные словари. Например, если сравнивать с .NET, вы обнаружите, что Dictionary.NET может быть в 26 раз быстрее хеш-таблицы на Haskell !

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

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

Ответ 2

Таблицы хэшей могут быть реализованы с чем-то вроде монады ST в Haskell, которая в основном обертывает IO-действия в чисто функциональном интерфейсе. Это делается путем принудительного выполнения операций ввода-вывода последовательно, поэтому он поддерживает ссылочную прозрачность: вы не можете получить доступ к старой "версии" хеш-таблицы.

Смотрите: hackage.haskell.org/package/hashtables

Ответ 3

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

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

Сначала в Java с использованием HashMap несинхронизированной реализации Map:

import java.util.Map;
import java.util.HashMap;

class HashTest {
    public static void main (String[] args)
    {
        Map <Integer, Integer> map = new HashMap<Integer, Integer> ();
        int n = Integer.parseInt (args [0]);
        for (int i = 0; i < n; i++)
            {
                map.put (i, i);
            }

        int sum = 0;
        for (int i = 0; i < n; i++)
            {
                sum += map.get (i);
            }


        System.out.println ("" + sum);
    }
}

Затем реализация Haskell с использованием недавней работы hashtable, выполненной Грегори Коллинзом (ее в пакете hashtables). Это может быть как чистым (через ST monad), так и нечистым через IO, я использую версию IO здесь:

{-# LANGUAGE ScopedTypeVariables, BangPatterns #-}
module Main where

import Control.Monad
import qualified Data.HashTable.IO as HashTable
import System.Environment

main :: IO ()
main = do
  n <- read `fmap` head `fmap` getArgs
  ht :: HashTable.BasicHashTable Int Int <- HashTable.new
  mapM_ (\v -> HashTable.insert ht v v) [0 .. n - 1]
  x <- foldM (\ !s i -> HashTable.lookup ht i >>=
               maybe undefined (return . (s +)))
       (0 :: Int) [0 .. n - 1]
  print x

Наконец, используя неизменяемую реализацию HashMap из hackage (из пакета HashMap):

module Main where

import Data.List (foldl')
import qualified Data.HashMap as HashMap
import System.Environment

main :: IO ()
main = do
  n <- read `fmap` head `fmap` getArgs
  let
    hashmap = 
        foldl' (\ht v -> HashMap.insert v v ht) 
           HashMap.empty [0 :: Int .. n - 1]
  let x = foldl' (\ s i -> hashmap HashMap.! i + s) 0 [0 .. n - 1]
  print x

Изучая производительность для n = 10 000 000, я считаю, что общее время работы следующее:

• Java HashMap - 24.387s
• Haskell HashTable - 7,705 с, 41% времени в GC (
• Haskell HashMap - 9.368s, 62% время в GC

Сбив его до n = 1,000,000, получим:

• Java HashMap - 0.700s
• Haskell HashTable - 0.723s
• Haskell HashMap - 0.789s

Это интересно по двум причинам:

• Производительность, как правило, довольно близка (кроме случаев, когда Java расходится выше 1M записей)
• Огромное количество времени проводится в коллекции! (убивая Java в случае n = 10,0000,000).

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

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

Я бы заметил, что Haskell HashMap занимает много места по сравнению с HashTable.

Программы Haskell были скомпилированы с помощью GHC 7.0.3 и -O2 -threaded и выполняются только с флагом +RTS -s для статистики GC во время выполнения. Java была скомпилирована с OpenJDK 1.7.