Steve Wampler wrote:
> I'm tempted to try and measure the
> performance of both approaches by writing two versions of the
> getClassSignature() method - one with Goedel numbering and the other using
> the 'characters in lexical order' to see if there's a performance benefit
> either way, but my instinct is that (at least for this puzzle) either solution
> is so fast as to be indistinguishable in performance. So I'd have to find
> a puzzle (maybe feed the program /usr/dict/web2 instead of the names of
> states)
> where we could see the difference...
I figured out a quick way: simply add a bunch of calls of getStates() into the
same list. (Note that the test code rejects Michael's repudiation of the New
World Order and allows the new states of "York New", "New Kory", etc. to
co-exist
despite being anagrams of each other - SNN is not FOX, and accepts the New World
Order and welcomes our new Overlords).
With all the lines in getStates() uncommented, this pushed the times of the
code up into a range that allows some measure of the difference in the two
signature techniques. After 30 runs of each type, it appears as though the
"string" version of getClassSignature() is ~3% faster than the Godel numbering.
For this data set and this algorithm. I'm quite certain one could devise a test
that reverses this result.
Here's the string version (slightly better than the one poster earlier):
# Build a signature identifying the equivalence class for state pair s.
# (All the letters in alphabetic order).
procedure getClassSignature(s)
every (ns := "") ||:= (upto(c := !(cset(s)--' '), s), c)
return ns
end
and the Goedel numbering (yes, I should use Godel, I've just gotten used to
typing Goedel) stolen directly from Michael's code:
# Build a signature identifying the equivalence class for state pair s.
# (Godelization).
procedure getClassSignature(s)
static xlate
local p, i, z
initial {
xlate := table(1)
p := create prime()
every i := 1 to 26 do {
xlate[&lcase[i]] := xlate[&ucase[i]] := @p
}
}
z := 1
every z *:= xlate[!s]
return z
end
Incidently, I discovered (learning something new all the time!) that linking
in 'factors' (to get prime()) links in 'numbers', which replaces the min() and
max() functions with procedures. This broke my code, where I had replaced:
if state1 << state2 then statePair := state1||":"||state2
else statePair := state2||":"||state1
with:
statePair := min(state1, state2)||":"||max(state1,state2)
While the functions work with strings, the procedures only work with numerics.
--
Steve Wampler -- [EMAIL PROTECTED]
The gods that smiled on your birth are now laughing out loud.
-------------------------------------------------------------------------
Take Surveys. Earn Cash. Influence the Future of IT
Join SourceForge.net's Techsay panel and you'll get the chance to share your
opinions on IT & business topics through brief surveys-and earn cash
http://www.techsay.com/default.php?page=join.php&p=sourceforge&CID=DEVDEV
_______________________________________________
Unicon-group mailing list
[EMAIL PROTECTED]
https://lists.sourceforge.net/lists/listinfo/unicon-group
