From: jmichel@... (Jean Michel) Date: 2001-01-03T08:40:07+09:00 Subject: [ruby-talk:8549] Re: speedup of anagram finder 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.