Najszybsza struktura danych dla contains () w Javie?
Jaka jest struktura danych w Javie, która ma najszybszą operację contains ()?
Np. mam zbiór liczb { 1, 7, 12, 14, 20... }
Biorąc pod uwagę inną dowolną liczbę x, jaki jest najszybszy (średnio) sposób generowania wartości logicznej, czy x jest zawarty w zbiorze, czy nie? Prawdopodobieństwo dla !contains() jest około 5x wyższy.
Czy wszystkie struktury map zapewniają działanie o(1)? Czy HashSet jest najszybszą drogą?
4 answers
Spójrz na set (Hashset, enumset) i hash (HashMap,linkedhash..., idnetityhash..) w oparciu o implementacje. mają O (1) for contains ()
Ten cheatsheet jest bardzo pomocny.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2013-07-14 16:40:51
Dla Twojego konkretnego przypadku liczb o stosunkowo dużej gęstości użyłbym Bitsetu, będzie on szybszy i znacznie mniejszy niż zestaw skrótów.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2010-07-16 22:15:20
Jedyną strukturą danych szybszą od HashSet jest prawdopodobnie TIntHashSet z Trove4J. wykorzystuje to primitives unikając konieczności używania obiektów Integer.
Jeśli liczba liczb całkowitych jest mała, można utworzyć wartość logiczną [], w której każda obecna wartość jest zamieniana na"true". To będzie O (1). Uwaga: HashSet nie ma gwarancji, że będzie o(1) i jest bardziej prawdopodobne, że będzie O (log (log(N))).
Otrzymasz tylko O (1) dla idealnej dystrybucji hash. Jednak jest bardziej prawdopodobne, że otrzymasz kolizje haszowanych łyżek i niektóre wyszukiwania będą musiały sprawdzić więcej niż jedną wartość.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2010-07-17 07:32:40
Hashing (hash set) jest najlepszy Z O(1)
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2010-07-16 18:07:10