[prev in list] [next in list] [prev in thread] [next in thread] 

List:       kmail-devel
Subject:    Re: KMMsgDict slowness
From:       Ingo =?iso-8859-1?q?Kl=F6cker?= <ingo.kloecker () epost ! de>
Date:       2002-01-01 22:39:19
[Download RAW message or body]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On Tuesday 01 January 2002 22:42, Michael Häckel wrote:
> On Tuesday 01 January 2002 22:22, Ingo Klöcker wrote:
> > JFYI, maybe you already know this. The prime number (which is equal
> > to the number of entries in the hash table) should be chosen so
> > that the number of messages equals about 70-80 % of the number of
> > hash table entries because if the hash table is filled more then 80
> > % there are too many collisions and this results in a performance
> > loss.
>
> But a bigger hash table needs more RAM.

Nowadays time is more expensive than RAM. ;-)

I just looked the following up.
Let m = <number of messages>, N = <size of the hash table> and a = m/N. 
Then for an ideal hashing algorithm the average cost C_ins for 
inserting an element in the hash table is
C_ins = (N+1) / (N+1-m)
which is approximately
1 / (1-a)
and the average cost C_sea+ for an successful search is approximately
C_sea+ ~= - ( ln (1-a) ) / a .

So for a = 0.5 we get C_ins ~= 2 and C_sea+ ~= 1.4,
for a = 0.6 we get C_ins ~= 2.5 and C_sea+ ~= 1.5,
for a = 0.7 we get C_ins ~= 3.3 and C_sea+ ~= 1.7,
for a = 0.8 we get C_ins ~= 5 and C_sea+ ~= 2.0,
for a = 0.9 we get C_ins ~= 10 and C_sea+ ~= 2.5.

So especially C_ins grows very fast if the ratio a is in the 
neighborhood of 1.0. Therefore a hash table should never be filled to 
more than 90 %. Too save some RAM we could probably try to keep the 
ratio a between 75 % and 85 %. But then we need some more prime 
numbers. I'll calculate some tomorrow.

Regards,
Ingo
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.0.6 (GNU/Linux)
Comment: For info see http://www.gnupg.org

iD8DBQE8MjqoGnR+RTDgudgRAvAUAJ9NAKhIHX8ROXOoqUv56GLCa4s9agCgr1cS
5IHNfckpQSsGo3QNIjwz0G4=
=f0TT
-----END PGP SIGNATURE-----
_______________________________________________
kmail Developers mailing list
kmail@mail.kde.org
http://mail.kde.org/mailman/listinfo/kmail
[prev in list] [next in list] [prev in thread] [next in thread]