From: David Alan Black Date: 2001-01-03T10:38:43+09:00 Subject: [ruby-talk:8551] Re: speedup of anagram finder On Wed, 3 Jan 2001, Jean Michel wrote: > In article , > David Alan Black wrote: > >Hello -- > > > >My benchmark results for this, on the first 10K words of /usr/dict/words > >(lowercased), are: > > user system total real > > histogram 5.650000 0.010000 5.660000 ( 5.658936) > > unpack 2.270000 0.000000 2.270000 ( 2.276009) > > histogram 5.530000 0.000000 5.530000 ( 5.523607) > > unpack 2.120000 0.000000 2.120000 ( 2.123110) > > Yes, I made a mistake in benchmarking, now my results agree with yours. > I guess actually the interpretive overhead is indeed too high, and any > solution which uses a primitive (like sort) will be faster than any loop > even if the algorithm embodied by the loop is superior... > > I think trying to optimize too much in an interpreted language leads > to perverse algorithms after a while (that is, algorithms which are > theoretically inferior but do better because they happen to call a > convenient primitive). To get a fast algorithm here, the best is to > implement yourself sort for strings in the kernel, written in C. Then no > pack, no unpack just this call to sort... But this is like a special > anagram-primitive in the kernel, a bit silly. Of course the best > approach would be to speed up execution of .each loops until perverse > algorithms are no more tempting. I rather like the idea of a String#sort_bytes method. I imagine it might be useful for things other than anagrams (not sure what things, but anyway). It certainly speeds things up: user system total real unpack 10.800000 0.000000 10.800000 ( 10.794349) sorted 6.180000 0.000000 6.180000 ( 6.182574) (that's for all of /usr/dict/words), even with a fairly rough-cut C implementation. David -- David Alan Black home: dblack@candle.superlink.net work: blackdav@shu.edu Web: http://pirate.shu.edu/~blackdav