From: Joel VanderWerf <joelvanderwerf@...>
Date: 2013-08-26T13:12:26-07:00
Subject: [ruby-core:56813] Re: [ruby-trunk - Feature #8820][Open] Speed up Array#index

On 08/26/2013 12:57 PM, Eric Wong wrote:
> "trans (Thomas Sawyer)" <redmine@ruby-lang.org> wrote:
>>      def main
>>        n = 10000000  # ten million
>>        a = randPerm(100)
>>
>>        t0 = Time.now
>>
>>        n.times do |i|
>>          a.index(i)
>>        end
>>
>>        puts "%.5f" % [Time.now - t0]
>>      end
>>
>>      def randPerm(n)
>>        (0...n).sort_by{rand}
>>      end
>
> The performance of your code varies between runs because the
> ordering is always different and index is O(n) _worst_ case.
> call srand(0) before any rand calls to get a consistent seed.

The running time of this code won't vary much at all. The n=10000000 
setting is much higher than a.size, so most #index calls will return 
nil. The entire array is searched for almost all iterations.

Maybe the intent was for each iteration step to do this

   a.index(i%n)

?