comp.lang.ada
 help / color / mirror / Atom feed
From: "Dmitry A. Kazakov" <mailbox@dmitry-kazakov.de>
Subject: Re: [Shootout] Spellcheck.adb
Date: Wed, 27 Apr 2005 10:40:09 +0200
Date: 2005-04-27T10:40:09+02:00	[thread overview]
Message-ID: <162n63ifx5jhn$.x4a2jtiveto0.dlg@40tude.net> (raw)
In-Reply-To: nIybe.50781$Of5.32614@nntpserver.swip.net

On Tue, 26 Apr 2005 23:50:12 +0200, David Sauvage wrote:

> Dmitry A. Kazakov wrote:
>> ...
>> The above is approximately five times faster on my computer under FC3.
>> Probably, because it does not use hash tables?
> 
> GNAT.Spitbol.Table generic use hash tables (i wonder if it could be 
> called an hashed table maps method?), may be people would like to have a 
> look on it's hash function (see #1)
> 
> The published shootout Ada spellcheck using GNAT.Spitbol.Table :
> real    0m0.120s
> user    0m0.083s
> sys     0m0.007s
> 
> (i run all the programs several times before each post ;-), so i get 
> fresh time average each post)
> 
> I try using the Tables generic package implementation (see #2) instead 
> of GNAT.Spitbol.Table generic on the shootout Ada spellcheck 
> implementation, which gave me  :
> real    0m0.271s
> user    0m0.197s
> sys     0m0.014s

Aha, now it is how it must be! (:-))

Hash table should be slower than sorted arrays on natural dictionaries. But
because it is allocated in advance (40_000 items), that should give it an
advantage over a dynamically allocated sorted array, when sizes of the
dictionary and of the text are close:

1 x malloc + n x string compare >> n x (hash + integer compare),
though string compare < hash + integer compare

when n ~ 1 two times looks OK.

[I can't stop wondering how badly wrong the benchmarks were designed]

BTW, you can try to use streams in the second part of your code. That
should bring another 10ms or so.

-- 
Regards,
Dmitry A. Kazakov
http://www.dmitry-kazakov.de



      reply	other threads:[~2005-04-27  8:40 UTC|newest]

Thread overview: 23+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2005-04-25 21:30 [Shootout] Spellcheck.adb albert.bachmann
2005-04-25 21:57 ` Spellcheck.adb Albert Bachmann
2005-04-25 23:27 ` [Shootout] Spellcheck.adb Marius Amado Alves
2005-04-26 18:04 ` Spellcheck.adb Matthew Heaney
2005-04-26 19:36 ` [Shootout] Spellcheck.adb David Sauvage
2005-04-26 20:50   ` Spellcheck.adb Albert Bachmann
2005-04-27 15:11     ` Spellcheck.adb Matthew Heaney
2005-04-27 22:49       ` Spellcheck.adb Albert Bachmann
2005-04-27 23:35         ` Spellcheck.adb Marius Amado Alves
2005-04-27 23:58           ` Spellcheck.adb Albert Bachmann
2005-04-28  0:19             ` Spellcheck.adb Marius Amado Alves
2005-04-29 10:22               ` Spellcheck.adb Albert Bachmann
2005-04-28  0:58             ` Spellcheck.adb Matthew Heaney
2005-04-29 10:19               ` Spellcheck.adb Albert Bachmann
2005-04-28  0:41         ` Spellcheck.adb Matthew Heaney
2005-04-28 21:20           ` Spellcheck.adb Simon Wright
2005-04-29 10:05           ` Spellcheck.adb Albert Bachmann
2005-04-29 12:35             ` Spellcheck.adb Matthew Heaney
2005-04-26 21:21   ` Spellcheck.adb Albert Bachmann
2005-04-26 22:04     ` Spellcheck.adb David Sauvage
2005-04-26 20:36 ` [Shootout] Spellcheck.adb Dmitry A. Kazakov
2005-04-26 21:50   ` David Sauvage
2005-04-27  8:40     ` Dmitry A. Kazakov [this message]
replies disabled

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox