From: Lars Christensen <larschbelunktumdk@...>
Date: 2009-08-11T23:12:49+09:00
Subject: Re: How to define doubles: Array-to-hash

On Mon, Aug 10, 2009 at 1:17 AM, 7stud --<bbxx789_05ss@yahoo.com> wrote:
> Your code doesn't produce the desired result, the op wanted an efficient
> solution, and this:

Actually, he wanted the "most efficient".

This is faster than the inject/hash method:

    result = []
    lastv = nil
    count = 1
    original.sort.each do |v|
      if v == lastv
        count += 1
      else
        result.push(lastv, count) if lastv
        count = 1
        lastv = v
      end
    end
    result.push(lastv, count)
    hash = Hash[*result]

This is O(n logn+n) while the inject method should be theoretically be
O(n) (assuming that Hash tables lookups/insertions are constant-time
and inject is linear). However, its significantly faster (250%) on
1.8.6-mswin32 and a little faster (50%) on 1.9.1-mingw32, even on
large arrays (millions of elements). Anyone who can explain why?