From: albert.bachmann@gmx.de
Subject: [Shootout] Spellcheck.adb
Date: 25 Apr 2005 14:30:42 -0700
Date: 2005-04-25T14:30:42-07:00 [thread overview]
Message-ID: <1114464642.518876.137610@f14g2000cwb.googlegroups.com> (raw)
Dear newsgroup,
on http://shootout.alioth.debian.org/ I discovered that the Ada entry
for the "spellcheck" benchmark produces an error according to the
information on that website. The specification for this benchmark can
be found here:
http://shootout.alioth.debian.org/benchmark.php?test=spellcheck&lang=all&sort=fullcpu
Since I am new to Ada I decided that it might be a good idea to
implement a solution and see how it performs. Finally I came up with a
naive program that performs not very well in comparison to other
language implementations. I produced a naive implementation in C++ as
well which solves the problem in less than half the time. The entry for
C++ at the Shootout takes half the time of my naive solution.
Now what I'd like to ask you is how I can speed up my Ada solution? As
I said I'm a novice and certainly there is a huge optimization
potential here. Here is the output of 'time':
Ada:
real 0m0.742s
user 0m0.720s
sys 0m0.009s
C++:
real 0m0.217s
user 0m0.192s
sys 0m0.008s
First I post the C++ solution since it is much shorter and easy to
understand:
#include <map>
#include <string>
#include <fstream>
#include <iostream>
using namespace std;
int main()
{
map<string, bool> dict;
string key;
ifstream in("spellcheck-dict.txt");
while (getline(in, key))
dict[key] = true;
while (cin >> key)
{
if (!dict[key])
cout << key << endl;
}
}
And now spellcheck.adb:
with ada.text_io;
with ada.integer_text_io;
with gnat.htable;
use ada;
procedure spellcheck is
subtype word is string(1 .. 128);
subtype index is natural range 0 .. 2760;
file : text_io.file_type;
item : word;
item_offset : natural;
no_item : constant boolean := false;
function hash(item : word) return index is
a : constant positive := 127;
h : index := 0;
begin
for i in item'range loop
h := (a * h + character'pos(item(i))) mod index'last;
end loop;
return h;
end hash;
package dictionary is new gnat.htable.simple_htable(header_num =>
index,
element => boolean,
no_element => no_item,
key => word,
hash => hash,
equal => "=");
begin
text_io.open(file, text_io.in_file, "spellcheck-dict.txt");
while text_io.end_of_file(file) = false loop
text_io.get_line(file, item, item_offset);
strings.fixed.delete(item, item_offset + 1, item'last);
dictionary.set(item, true);
end loop;
while text_io.end_of_file = false loop
text_io.get_line(item, item_offset);
strings.fixed.delete(item, item_offset + 1, item'last);
if dictionary.get(item) = no_item then
text_io.put_line(item);
null;
end if;
end loop;
text_io.close(file);
end spellcheck;
Regards,
Albert
next reply other threads:[~2005-04-25 21:30 UTC|newest]
Thread overview: 23+ messages / expand[flat|nested] mbox.gz Atom feed top
2005-04-25 21:30 albert.bachmann [this message]
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
replies disabled
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox