Насколько быстро Perl выбирает хэш?

Я использую хэш Perl для хранения пар ip -> имя хоста. У меня их миллионы.

Я кэширую системный вызов gethostbyip в хеше %HOSTNAME{$ip}.

Память не при чем. Время - это.

Насколько быстро работает perl-хеш-поиск в этом случае?

Будет ли он работать быстрее, если вместо него я буду использовать MysqlDB или BerkleyDB?


hash perl berkeley-db
person xoid    schedule 27.11.2014    source источник
comment
Сделайте бенчмарк.   -  person Toto    schedule 27.11.2014
comment
Mysql и BerkleyDB используют внешнее хранилище, в отличие от обычного хэша, поэтому ответ кажется очевидным.   -  person mpapec    schedule 27.11.2014
comment
Вам нужно $HOSTNAME{$ip}, а не %HOSTNAME{$ip}.   -  person Dave Cross    schedule 27.11.2014
comment
Поиск хэшей в Perl происходит молниеносно даже для довольно больших хэшей (насколько у вас есть ОЗУ для их хранения).   -  person salva    schedule 27.11.2014
comment
Как вы используете данные? Некоторые решения могут быть лучше только для некоторых шаблонов доступа.   -  person AnFi    schedule 27.11.2014
comment
@salva, точнее, размер хеша не влияет на скорость поиска хеша (O (1)).   -  person ikegami    schedule 27.11.2014
comment
Адреса IPv4 — это просто 32-битные числа. Если вы имеете дело только с IPv4 и память действительно не является проблемой, самым быстрым решением, вероятно, будет массив из 4 миллиардов элементов.   -  person ikegami    schedule 27.11.2014
comment
@ikegami: на практике скорость поиска хеша зависит от размера хеша из-за иерархических кешей памяти.   -  person salva    schedule 27.11.2014
comment
Больше, чем любая другая структура? Если нет, то не вижу смысла упоминать об этом.   -  person ikegami    schedule 27.11.2014

Ответы (1)


arrow_upward
1
arrow_downward

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

Если вы не можете хранить все это в ОЗУ, то это становится менее предсказуемым, и вам может потребоваться бенчмаркинг, чтобы определить, что быстрее для вашей конкретной комбинации программы и оборудования.

person Dave Sherohman    schedule 27.11.2014
comment
Использует ли perl hash индекс для поиска данного ключа, или он сканирует всю хеш-память, чтобы найти его, или perl хранит ключи отсортированными и выполняет двоичный поиск? - person xoid; 28.11.2014
comment
Ни один из вышеперечисленных. Хэш выделяет несколько сегментов и использует алгоритм хеширования для распределения элементов между сегментами. Ему не нужно индексировать, сканировать или искать, потому что он знает, к какой корзине принадлежит элемент, и может перейти туда напрямую — хеш-поиск выполняется за O(1). Конечно, возможны коллизии хэшей, и в этом случае несколько элементов будут храниться в виде связанного списка внутри ведра (которое нужно сканировать линейно), но хорошая реализация (например, в Perl) будет прозрачно увеличивать количество ведер перед это становится проблематичным. - person Dave Sherohman; 28.11.2014