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
prev parent 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