У всех существующих ответов есть хорошие моменты, которыми стоит поделиться, и я подумал, что просто добавлю еще один фрагмент данных в уравнение: сравнение производительности нескольких различных ассоциативных структур данных.
Тест состоит из последовательновставка, затем поиск и добавление элементов массива.Этот тест не является невероятно строгим, и его не следует воспринимать как таковой, он просто указывает на то, чего ожидать.
Сначала в 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 с использованием недавней работы с хеш-таблицами, проделанной Грегори Коллинзом (в пакете hashtables).Это может быть как чисто (через ST монаду), так и нечисто через 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,387 с
- Haskell HashTable - 7,705 с, 41% времени в GC (
- Haskell HashMap - 9,368 с, 62% времени в GC
Knockingдо n = 1 000 000, мы получаем:
- Java HashMap - 0,700 с
- Haskell HashTable - 0,723 с
- Haskell HashMap - 0,789 с
Это интересно по двум причинам:
- Производительность, как правило, довольно близка (за исключением случаев, когда Java расходится более 1М записей)
- Огромное количество временитратится на сбор! (убийство Java в случае n = 10 000 000).
Это может указывать на то, что в языкахкак Haskell и Java, которые упаковали ключи карты, видят большой удар от этого бокса.Языки, которые либо не нуждаются, либо могут распаковать ключи и значения, вероятно, увидят в два раза большую производительность.
Очевидно, что эти реализации не самые быстрые, но я бы сказал, что используя Java в качестве базовой линии, онинаименее приемлемый / пригодный для использования во многих целях (хотя, возможно, кто-то, более знакомый с мудростью Java, мог бы сказать, считается ли HashMap разумным).
Я бы отметил, что Haskell HashMap занимает много места по сравнению с HashTable.
Программы на Haskell были скомпилированы с GHC 7.0.3 и -O2 -threaded и работают только с флагом +RTS -s для статистики GC во время выполнения.Java была скомпилирована с OpenJDK 1.7.