Michael Glass wrote: > The answer to 'but why' use the Goedel numbering scheme is: > > gn(UV) = gn(U) * gn(V) > > Concatenation in string-land becomes multiplication in number-land. > > In other words, you need to compute the signature of each > string in the dataset exactly once. After that it's just > one multiply per test.
Good point! And, of course, my test case won't show the advantage since it doesn't have this precomputation loop. It's not the concatenation versus multiply per se, but rather the fact that the Goedel numbering computation can be done (nearly) linearly with the input (leaving only a multiplication, as you note) while the string signature form can't even be started until the two state names are paired. > Your other solutions are computing the signatures of concatenated > strings about (N^2)/2 times. > > The overall performance of both should be O(N^2). 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!) -- -- Steve Wampler [EMAIL PROTECTED] The gods that smiled upon your birth are laughing now. -- fortune cookie ------------------------------------------------------------------------- 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
