Steve Wampler wrote:
I'll back the pre-computation into my code (with the Godelization)
and compare. (Though I'm sure the results will show gn() to be
faster!)
Yep. By quite a bit. This is on a different machine than before,
so you can only compare these two values with each other and not
with the original:
String form of signature computation: ~ 1.85s
Godel form of signature computation (with precompute): ~ 0.75s
(Again with larger input sets than the original).
The new version is attached. (It could be sped up more by adding a
prepass through the states to precompute gn(state). This version
computes gn(state) only if it hasn't been computed already, which
costs two extra table lookups in the (n^2)/2 part of the algorithm.
It feels cleaner to me, however.)
Thanks for pointing that advantage of using Goedel numbers out, Michael!
--
Steve Wampler [EMAIL PROTECTED]
The gods that smiled upon your birth are laughing now. -- fortune cookie
link factors
procedure main()
local min, max
st := &time
equivClasses := table()
statePairs := table()
every put(states := [], map(!getStates())) # Make case insignificant
min := proc("min",0)
max := proc("max",0)
# Pass one builds a table of equivalence classes (all state pairs in the
# same equivalence class have the same characters in them)
# It also does a little bookkeeping to avoid work later.
every (state1 := |get(states)) & (state2 := !states) do {
if state1 ~== state2 then {
statePair := min(state1, state2)||":"||max(state1,state2)
signature := getClassSignature(state1, state2)
/equivClasses[signature] := set()
insert(equivClasses[signature], statePair)
statePairs[statePair] := set(state1, state2)
}
}
# Pass two produces all valid state pair couples in each equivalence class.
every equivClass := !equivClasses do {
while delete(equivClass, lastPair := ?equivClass) do {
every *(statePairs[lastPair] ** # Ensure no duplicated state
statePairs[pair := !equivClass]) = 0 do {
write(lastPair," and ", pair)
}
}
}
write(&errout, "Time: ", (&time-st)/1000.0)
end
# Build a signature identifying the equivalence class for state pair s.
# (Godelization).
procedure getClassSignature(s1, s2)
state G
initial G := table()
/G[s1] := gn(s1)
/G[s2] := gn(s2)
return G[s1]*G[s2]
end
# Compute the Godel number for a string (also saves it into a table
procedure gn(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
procedure getStates()
return ["Alabama", "Alaska", "Arizona", "Arkansas", "California",
"Colorado", "Connecticut", "Delaware", "Florida", "Georgia",
"Hawaii", "Idaho", "Illinois", "Indiana", "Iowa", "Kansas",
"Kentucky", "Louisiana", "Maine", "Maryland", "Massachusetts",
"Michigan", "Minnesota", "Mississippi", "Missouri", "Montana",
"Nebraska", "Nevada", "New Hampshire", "New Jersey",
"New Mexico", "New York", "North Carolina", "North Dakota",
"Ohio", "Oklahoma", "Oregon", "Pennsylvania", "Rhode Island",
"South Carolina", "South Dakota", "Tennessee", "Texas", "Utah",
"Vermont", "Virginia", "Washington", "West Virginia",
# "NeW kORy", "nEW KorY", "Wen Kory", "York New", "Kory New",
# "York New", "York New", "New Kory", "Wen Kory", "Kory New",
"Wisconsin", "Wyoming"]
end
-------------------------------------------------------------------------
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
