From: gotoken@... (GOTO Kentaro)
Date: 2000-12-28T16:30:37+09:00
Subject: [ruby-talk:8162] Re: speedup of anagram finder

Helo ---

In message "[ruby-talk:8152] Re: speedup of anagram finder"
    on 00/12/28, David Alan Black <dblack@candle.superlink.net> writes:
>>    1. Initialize block variables before the block.
>>    2. Use destructive method!
>>    3. `x.size > 0' ==> `not x.empty?'
>>    4. `x.size > n' ==> `x[n]'
>>    5. `a = x[0]'   ==> `a, = x'
>
>I assume that #2 is because many non-destructive methods call their
>destructive equivalents, so for instance Array#flatten makes a copy of
>the object and then calls Array#flatten! on it.  Or is there another
>reason?  And is this something that can be depended on permanently?

Not permanently but true in the almost all cases.  Additionally,
nobang always creates a new object and they yield GC, which takes
unexpectedly much time cost often.

However, I like also method-chain because it doesn't fragment my
thought streams but needs nobang :-(

>About #4: it breaks on this:
>
>   a = [1,2,false]
>   a.size > 2       => true
>   a[2]             => false

Oh, yes. I didn't assume boolean arrays. #4 is not general one.

>I keep finding that "for x in y" benchmarks faster than #each.
>I wish it didn't, because I like #each.  Further research
>required....

Interesting!
                      user     system      total        real
   each          10.945312   0.000000  10.945312 ( 11.007231)
   for            8.242188   0.007812   8.250000 (  8.274486)

Why I got such result?

>Would there be any disadvantage here to using "[]" instead of
>Array.new?  It seems to be a lot faster.

Hmm, Array.new refer the constant `Array' and it maybe takes much
time.  On the other hand, `[]' is compiled on the parse stage.

With

  def arraynew; Array.new end
  def arrayliteral; [] end

I got by 1000_000 times iterations:

                      user     system      total        real
   arraynew       9.289062   0.000000   9.289062 (  9.345590)
   arrayliteral   5.078125   0.000000   5.078125 (  5.079134)

>Speaking of which....  I found that storing the hash keys as
>strings, in the following manner:
>
>      (anagrams[key.join] ||= []) .push word
>
>sped things up quite a bit.  I'm not sure why that would be, exactly,
>but it did seem to be the case.  (Combining it into one line is just
>to avoid doing two joins or creating a new variable.)  Yet more
>further research....

I'm guessing the times to search symbol are unexpectedly taken. 

>			 user     system      total        real
>   david             4.600000   0.000000   4.600000 (  4.591789)
>   gotoken           6.290000   0.030000   6.320000 (  6.329997)
>
>
>Much of the speed david() picked up seems to be from "key.join".

I didn't hit on that! 

# Ah, time trial is enjoyable :-)

-- Gotoken