LINUX.ORG.RU

Быстрый «хеш» со статичным набором ключей?

 ,


0

1

Может, встречал кто-нибудь максимально быструю реализацию на Perl такой логики:

1) В конструктор объекта или tied-переменной передаётся статичный набор ключей и начальных значений

2) Конструктор создаёт ссылку на анонимный массив, для каждого ключа генерирует функцию по типу use constant: KEY_{NAME}() => $count++, для каждого из индексов $count++ - кладёт по ссылке на анонимный массив соотв. индексу значение

3) Класс предоставляет методы «взять,записать значение по ключу»: внутри этот метод проверяет, есть ли соотв функция KEY_{NAME} - и если есть, вызывает её, получает индексы - и дальше по этому индексу кладёт или берёт значение.

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

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

★★★★★

Гугли «perfect hashing».

anonymous ()

внутри этот метод проверяет, есть ли соотв функция KEY_{NAME}

Вот это отображение строки в функцию/число и будет медленным. Хотите максимально быстро - используйте enum и товарищей - те перекладывают всё, что может быть медленным, на compile time.

anonymous ()
Ответ на: комментарий от anonymous

enum же и создаёт те же самые use constant-подобные функции, возвращающие число:

 use enum qw(
      :Months_=0 Jan Feb Mar Apr May Jun Jul Aug Sep Oct Nov Dec
      :Days_=0   Sun Mon Tue Wed Thu Fri Sat
      :LC_=0     Sec Min Hour MDay Mon Year WDay YDay Isdst
  );

  if ((localtime)[LC_Mon] == Months_Jan) {
      print "It's January!\n";
  }

LC_Mon -здесь - это функция, её можно и как LC_Mon() вызвать.

DRVTiny ★★★★★ ()
Ответ на: комментарий от anonymous

also посмотреть на Class::XSAccessor::Array

Спасибо, уже смотрю.

DRVTiny ★★★★★ ()
Ответ на: комментарий от DRVTiny

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

anonymous ()
Ответ на: комментарий от anonymous

Почему через хеш?

Это же просто функция.

perl -e 'use constant R=>"hello\n"; my $x="R"; print $x->()'
hello

И так тоже:

perl -e 'use constant R=>"hello\n"; $x="R"; my $l=\&{$x}; print ref($l)." => ".$l->()'
CODE => hello

DRVTiny ★★★★★ ()
Последнее исправление: DRVTiny (всего исправлений: 2)
Ответ на: комментарий от anonymous

И даже так:

use strict;
use constant R=>"hello\n";
no strict "refs";
my $x="R"; *{__PACKAGE__."::$x"} = sub { "bye\n" };
my $l = \&{$x};
print ref($l)." => ".$l->()

Output:

Constant subroutine main::R redefined at -e line 1.
Prototype mismatch: sub main::R () vs none at -e line 1.
CODE => bye

Охренеть, дайте два...

$ perl -e 'use strict; use 5.16.1; use constant R=>"hello\n"; no strict "refs"; my $x="R"; *{__PACKAGE__."::$x"}=sub () { "bye\n" }; print R; my $l=\&{$x}; print ref($l)." => ".$l->()'
Constant subroutine main::R redefined at -e line 1.
hello
CODE => bye

DRVTiny ★★★★★ ()
Последнее исправление: DRVTiny (всего исправлений: 1)
Ответ на: комментарий от DRVTiny

Symbolic reference? Это не очень-то безопасно и наверняка медленнее, чем hard references. Внутри оно всё равно должно как-то отобразить строку (имя функции) в CODE, то есть, найти её в stash. То есть, сделать hash lookup, хотя бы и во внутреннем хэше.

Вызов же функции не из строки, а напрямую (use enum whatever; whatever()) компилируется один раз сразу в вызов CODE.

anonymous ()

Насколько я помню, начиная с какой то версии перла была проведена оптимизация случая, bless {key => $val, ...}, когда набор ключей при создании объекта был константным и не менялся в процессе работы — доступ к хешу ускоряется. А так он ровно в два раза тормознее массива.

Casus ★★★★★ ()
Ответ на: комментарий от Casus

Ровно в 2 раза независимо от количества ключей в хеше? Тогда это O(1). Однако, существуют коллизии, их количество зависит от количества ключей, а значит, алгоритмическая сложность хеша зависит от n, а как именно - зависит от алгоритма хеширования..

DRVTiny ★★★★★ ()
Ответ на: комментарий от annulen

Посмотрел я на это, но так и не понял, как пользоваться. Какие-то компиляции gcc с оптимизацией под sse4... О чём это, кто все эти люди? :) Но посмотрю обязательно ещё, должно наступить просветление.

DRVTiny ★★★★★ ()
Ответ на: комментарий от DRVTiny

Ровно в 2 раза независимо от количества ключей в хеше?

Практически, да. Дело в том, что хеш перестраивается по мере роста, увеличивается количество корзин. Я экспериментировал с этим, колллизии редкость, как правило в одной корзине не более чем один элемент.

Casus ★★★★★ ()
Ответ на: комментарий от DRVTiny
$ perl -le 'for($_=1; $_ < 1000; $_ += $_) { $h{$_}=$_+2 for (1..$_); print "$_: @{[scalar %h]}"}'
1: 1/8
2: 2/8
4: 3/8
8: 5/16
16: 11/32
32: 27/64
64: 54/128
128: 99/256
256: 200/512
512: 397/1024

формат:

число: элементов/корзин

Casus ★★★★★ ()
Ответ на: комментарий от DRVTiny

Посмотрел я на это, но так и не понял, как пользоваться. Какие-то компиляции gcc с оптимизацией под sse4... О чём это, кто все эти люди? :) Но посмотрю обязательно ещё, должно наступить просветление.

Краткое содержание без претензий на полноту

1) Есть библиотека cmph (C Minimal Perfect Hash), которая позволяет для заданного в рантайме набора строк сделать совершенную хэш-функцию (т.е. без коллизий), по совместительству являющуюся минимальной (отображает N строк в числа от 0 до N-1). Это позволяет вместо любых хэш-таблиц использовать массивы, сгенерил функцию и пользуйся

2) Есть некий (похоже не вполне доделанный) модуль Perfect::Hash, автор которого задался целью поддержать кучу генераторов совершенных хэшей, а заодно и узнать, какой из них круче. Вот к этой части и относится цирк с конями и sse4. Однако единственный известный мне на вскидку генератор, работающий в рантайме - CMPH, так что можно было бы выдрать его поддержку из этого модуля и юзать у себя

Есть другие генераторы, gperf например, но их хорошо юзать когда у тебя набор ключей более менее постоянный, так что можно заранее сгенерить хэш-функцию и загрузить к себе в скрипт. Насколько я понимаю, именно этого хотел добиться автор Perfect::Hash, автоматически компилить XS-модули для заданного набора ключей.

Лучше бы сделал по-рабочекрестьянски обертку для CMPH, имхо

annulen ★★★★★ ()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.