Optimisation help needed
Martin DeMello
acyclic word graph) files, as produced by Graham Toal's program at
http://www.gtoal.com/wordgames/dawgutils/
Essentially a dawg is a variant of a trie, with a fixed-length (4 byte)
record containing a letter, a pointer to another node (the root of a
subtree of words starting with the current prefix), and bits flagging
the end of node and end of word markers for the current record
(see http://www.wutka.com/dawg.html)
The problem is that this is a very C-oriented data structure - a node is
stored as a consecutive series of records, which you read until you find
the letter you're looking for or you come to the end of node marker. The
pointer is likewise just an offset into the contiguous memory block the
dawg occupies (or into the file, but slurping the whole thing into
memory is one of the first optimisations I tried). All this ends up
being horribly inefficient in ruby - indeed, the bottleneck is the
get_children function, which I've implemented thus:
def children(index)
eon = eil
a = nil
until(eon)
a = memoized_read_record(index)
yield a
eon = a.eon?
index += 1
end
end
The entire code, and the dawg file I'm using to test it are up on
http://rubyforge.org/frs/?group_id=562 - could people please take a look
at it and see what I can do without dropping into C? (It could be that
my anagram algorithm is naive too - suggestions welcomed)
martin
linus sellberg
> at it and see what I can do without dropping into C? (It could be that
> my anagram algorithm is naive too - suggestions welcomed)
One of the most efficient algorithms for finding anagrams sorts both the
grammar and the word you want to find anagrams for before it starts to
compare anything.
(that is, bar => abr)
Robert Klemme
"Martin DeMello" <martin...@yahoo.com> schrieb im Newsbeitrag
news:3G3Td.487016$6l.245954@pd7tw2no...
This is what I came up with so far - it's cleaner but unfortunately not
faster. Interestingly enough the StrinIO variant is slower...
Have to go to bed now. HTH
robert
Robert Klemme
"Robert Klemme" <bob....@gmx.net> schrieb im Newsbeitrag
news:384iaaF...@individual.net...
Ha, I must've been totally blind. Try this version instead!
You probably can make it even faster if you marshal the dictionary once
you've read it.
Good night
robert
Martin DeMello
That doesn't extend itself well to anagrams with wildcards, though.
DAWGs are nice for those.
martin
Martin DeMello
>
> Ha, I must've been totally blind. Try this version instead!
>
> You probably can make it even faster if you marshal the dictionary once
> you've read it.
Thanks - looks a lot more rubyish than mine, too! Will test it out when
I get home.
martin
Robert Klemme
There we some errors still. I did a bit of fixing and tidying up. Most
interesting I find the simplification achieved by "EOW =
DawgNode.new.freeze".
Have fun
robert
Martin DeMello
>
> There we some errors still. I did a bit of fixing and tidying up. Most
> interesting I find the simplification achieved by "EOW =
> DawgNode.new.freeze".
Subtle problem:
current.children[char] = eoword ? DawgNode::EOW : nodes[ptr]
doesn't work because a node could be both EOW *and* have children. But
looks like a very nice clean approach on the whole - will happily
replace my old code with this.
martin
Martin DeMello
(And yes, it turned out to be a very small fix - merely adding the eow
attribute back to every node and saying
if char != 0
current.children[char] = nodes[ptr]
current.eow = eoword
end
plus a few supporting changes elsewhere.)
martin
Martin DeMello
>
> (And yes, it turned out to be a very small fix - merely adding the eow
> attribute back to every node and saying
>
> if char != 0
> current.children[char] = nodes[ptr]
> current.eow = eoword
> end
My turn to be too sleepy for this :) Of course it's a bit more tricky
than that.
current.children[char].eow = eoword if ptr > 1
seems to work; I'll bang on it some more in the morning.
martin