Enumerable#group_by is O(n^2)

As a very quick test I did this (in a rails 2.2 app)

module Enumerable
  def old_group_by
    groups = []
    inject({}) do |grouped, element|
      index = yield(element)
      if group = grouped[index]
        group << element
      else
        group = [element]
        groups << [index, group]
        grouped[index] = group
      end
      grouped
    end
    groups
  end
end


require 'benchmark'
include Benchmark
array = (1..1000000).to_a; false

bmbm(5) do |x|
  x.report("current implementation") { array.group_by {|i| i % 13}}
  x.report("old implementation") { array.old_group_by {|i| i % 13}}
end

I get something like

current implementation 3.340000 0.030000 3.370000 ( 3.419125) old implementation 1.960000 0.020000 1.980000 ( 1.997561)

Varying the size of array the ratio of the two seems pretty constant, so to me at least the newer implementation is slower, but only by a constant factor. What testcase did you have that showed much worse results?

Hi Frederick. Thanks for picking this up!

Try it with more groups, by bumping up the i % 13 in your test code to a bigger value.

For i % 130:

current implementation 14.610000 0.100000 14.710000 ( 15.687624) old implementation 4.990000 0.040000 5.030000 ( 5.300712)

For i % 1300:

current implementation 128.240000 0.460000 128.700000 (130.583804) old implementation 5.410000 0.030000 5.440000 ( 5.639136)

You can see that it degrades very quickly as the number of groups goes up. This is because OrderedHash (as used by the current implementation) is O(n) for finding elements or inserting new elements.

Ah, O(n^2) in the number of groups - I'd interpreted the question as being O(n^2) in the size of the array

New OrderedHash implementation