VO
голое железо не я первый помянул
Size: a a a
2020 January 11
AP
ладно, я в любом случае потерялся
VO
я только сказал что мало кто задумывается что с одним значением хэш-бакета может быть дофига разных элементов.
AP
я только сказал что мало кто задумывается что с одним значением хэш-бакета может быть дофига разных элементов.
я не спорил и даже скорее подтвердил это
VO
даже в случае если хэш-бакетов примерно равно количеству улементов к хэше. причем дофига -- это порядка 8, что ли, не помню уже
AP
я тестировал перловый хеш. его функция очень мало коллизий даёт, поэтому количество бакетов растёт по степеням двойки от числа элементов
VO
приведенная мной цифра -- это для такого случая
AP
т.е. когда количество элементов превышает очередную степень двойки, то хеш перестраивается на следующую
AT
Да нарисуйте вы микробенчи и померяйтесь
AP
зачем? я уже всё для себя выяснил
VO
вот тут правильно не бенчи, а мат анализ. но он сложный, да.
AT
Что хэш медленне массива? ))
VO
я -- про количество коллизий.
AP
вот мы тут в большинстве своём уже все сеньоры, а всё равно было о чёмо поговрить/поспорить. так что я не вижу ничего плохого в поднятии этого вопроса на собеседовании хоть для джуна, хоть для сеньора
VO
а вот кстати, интересный вопрос. (может и не про перл). если у нас число строкой задется -- что быстрее будет -- atoi и по индексу и хэш-функцию и из хэша?
VO
число будем считать достаточно большим (длинным)
AT
А это зависит
# /bin/time perl -le 'for my $j (1e9..1e9+100) { my @a; for(my $i = 0;$i < 100000; ++$i) { $a[rand()*1e8] = $i } }'
14.86user 0.04system 0:14.91elapsed
/bin/time perl -le 'for my $j (1e9..1e9+100) { my %h; for(my $i = 0;$i < 100000; ++$i) { $h{rand()*1e8} = $i } }'
9.71user 0.01system 0:09.72elapsed
# /bin/time perl -le 'for my $j (1e9..1e9+100) { my @a; for(my $i = 0;$i < 100000; ++$i) { $a[rand()*1e8] = $i } }'
14.86user 0.04system 0:14.91elapsed
/bin/time perl -le 'for my $j (1e9..1e9+100) { my %h; for(my $i = 0;$i < 100000; ++$i) { $h{rand()*1e8} = $i } }'
9.71user 0.01system 0:09.72elapsed
AP
а вот кстати, интересный вопрос. (может и не про перл). если у нас число строкой задется -- что быстрее будет -- atoi и по индексу и хэш-функцию и из хэша?
видимо, не про перл. функция atoi примерно сравнима, скорее всего, с функцией вычисления хеша. но сам способ хранения массива даёт преимущества
VO
ну вот все же не совсем сравнима. всяких ветвлений поболее будет
VO
а дальше уже ньюансы, да...