[retroforth] Re: Faster find
- From: Chris Walton <chris.r.walton@xxxxxxxxx>
- To: retroforth@xxxxxxxxxxxxx
- Date: Thu, 27 Jan 2005 15:33:03 -0800
On Thu, 27 Jan 2005 22:25:13 +0100, Helmar Wodtke <helmwo@xxxxxx> wrote:
> retroforth@xxxxxxxxxxxxx schrieb am 27.01.05 21:28:47:
> >
> > Dear all,
> >
> > Some days ago I suggested a faster find, and gave that a try. Well, I'm
> > still
> > novice with fasm, so I would like to ask for your comments. Expect (quite)
> > some errors in my attempt below.
> Hi again,
>
> I wrote a small testing program in perl:
> -----------------------------
> #! /usr/bin/perl
> use strict;
>
> my @nodes = {};
>
> sub insert {
> my $word = shift;
> my $p = 0;
> for (split('', $word)) {
> my $q = $nodes[$p]->{$_};
> if (not defined $q) {
> $q = $nodes[$p]->{$_} = scalar @nodes;
> $nodes[$q] = {};
> }
> $p = $q;
> }
> }
>
> my $input = join('', <>);
> insert $1 while $input =~ /(\S+)/g;
>
> print "Used nodes: ", scalar @nodes, "\n";
> ----------------------------
>
> It says that the wordset of Retro 7.4 only would eat up half of the space
> you've reserved for it. At my opinion this is too much space for the
> dictionary.
Yessir, that is too much.
I think such a system is only worth using for something like Quest32
or Win32forth or something that have several thousands of words in the
dictionary. And even there, I believe they should seriously rethink
their strategy there. It would be nicer if the source is just
recompiled when needed, that keeps everything small and nice and
allows for a simpler and smaller dictionary.
If I may recommend something, possibly allocation the dictionary space
as 4 arrays in the fashion of colorforth. You can probably put a
significant amount of letters in 8 bytes, so just compare 2 pairs of
numbers instead of comparing the string which is much slower. Also,
this is MUCH smaller.
A processor-dependent optimization might use MMX for the compare.
I love retroforth, I love colorforth. They are more alike than you
might like to think :). Both beautiful.
-- Chris
> Bis dann,
> Helmar
> helmwo@xxxxxx
>
>
> -- Binary/unsupported file stripped by Ecartis --
> -- Type: application/x-pkcs7-signature
> -- File: smime.p7s
> -- Desc: S/MIME Cryptographic Signature
>
>
--
I F34R N0N3 F0R F0RTH SH4LL GUID3 M3
Other related posts:
