[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [elmo-users] box_selection a sprawa polska
From: |
rzyjontko |
Subject: |
Re: [elmo-users] box_selection a sprawa polska |
Date: |
Wed, 23 Apr 2003 17:47:03 -0000 |
User-agent: |
elmo/0.6 |
W swoim poprzednim liście napisałeś:
>
> > Tutaj mamy dużą szansę zrobić to milion razy lepiej niż u konkurencji.
>
> Jak prawie wszystko do tej pory :) Tak czuję, że wisi jeszcze nade
> mną przyspieszenie addressbooka.
Pomyślałem sobie, że się pochwalę. Elmo ma prawdopodobnie jedną z
najbardziej wyżyłowanych implementacji tablic hashujących. Siedziałem
trochę przy tym i okazało się, że przy wypełnieniu = 140% średnia
długość niepustej listy = 1.6, albo coś koło tego. To jeszcze o
niczym nie świadczy bo to mógł być przypadek. Trzebaby przebadać dużo
większą próbkę, ale stawiam na to, że oczekiwana długość listy w
trakcie działania programu nie przekracza 2.5.
Wniosek: tablice hashujące w elmo działają w czasie stałym z *małą*
stałą, a tablice hashujące w mutt'cie działają w czasie liniowym (to z
powodu stałego rozmiaru tablicy).
Ale to co robi pine, to już jest dramat! Zajrzałem do źródeł i
przeczytałem tam coś takiego:
"This is a standard hash function that should be as evenly
distributed as possible. I haven't done much research to find a
good one."
No to gratulacje. Patrzymy w kod, a tam się okazuje, że pomijane są
białe znaki, litery są przekształcane na małe, a funkcja po prostu
dosumowuje wartość znaku przesuniętą o różne wartości (co ósmy znak
tak samo).
---- ----
rzyjontko <rzyj # plusnet () pl>
http://www.student.ii.uni.wroc.pl/~rzyj/
---- ----