56ee28134dd0776825445e3551979b14

require "benchmark"
data_set = []
10000.times do
data_set << [rand(10), rand(10), rand(10)]
end
Benchmark.measure do
data_set.sort_by_multiple(:ascending, :descending, :ascending) { |o| o }
end
# => #<Benchmark::Tms:0x2135ce8 @cutime=0.0, @label="", @stime=0.0, @real=1.84591794013977, @utime=1.81, @total=1.81, @cstime=0.0>
Benchmark.measure do
data_set.sort_by_multiple(:ascending, :ascending, :ascending) { |o| o }
end
# => #<Benchmark::Tms:0x207cab8 @cutime=0.0, @label="", @stime=0.0, @real=0.0400059223175049, @utime=0.0399999999999996, @total=0.0399999999999996, @cstime=0.0>

Obviously, there's a lot of potential for optimizing this method. Suggestions?

module Enumerable
  # Sorts the enumeration by mapping the
  # values in the enumeration through the given block.
  #
  # The method takes a tuple of Symbols which indicate the sort direction
  # for each value returned by the block.
  #
  # The block must return a tuple of the same size as the direction tuple.
  def sort_by_multiple(*directions, &block)
    # Performance optimization
    if directions.all? { |d| d == :ascending || d == :asc }
      return self.sort_by(&block)
    end
    sorted = ((self.collect do |obj|
      [block.call(obj), obj]
    end).sort do |a, b|
      if !a[0].kind_of?(Array) || !b[0].kind_of?(Array)
        raise TypeError,
          "The block must return values of type Array."
      elsif a[0].size != directions.size || b[0].size != directions.size
        raise ArgumentError,
          "Size mismatch between block return value and " +
          "directions parameter: " +
          "#{a[0].inspect}, #{b[0].inspect}, #{directions.inspect}"
      else
        result = 0
        directions.each_with_index do |direction, index|
          value_a = a[0][index]
          value_b = b[0][index]
          if direction == :descending || direction == :desc
            result = value_b <=> value_a
          elsif direction == :ascending || direction == :asc
            result = value_a <=> value_b
          else
            raise ArgumentError,
              "Direction must be one of: :ascending, :descending, " +
              "was: #{direction.inspect}."
          end
          break if result != 0
        end
        result
      end
    end).collect do |pair|
      pair[1]
    end
    sorted
  end
end

Refactorings

No refactoring yet !

56ee28134dd0776825445e3551979b14

Sporkmonger

September 5, 2008, September 05, 2008 13:38, permalink

No rating. Login to rate!

Minor improvement.

module Enumerable
  # Sorts the enumeration by mapping the
  # values in the enumeration through the given block.
  #
  # The method takes a tuple of Symbols which indicate the sort direction
  # for each value returned by the block.
  #
  # The block must return a tuple of the same size as the direction tuple.
  def sort_by_multiple(*directions, &block)
    raise LocalJumpError, "No block given." if block == nil
    # Performance optimization
    if directions.all? { |d| d == :ascending || d == :asc }
      return self.sort_by(&block)
    elsif directions.all? { |d| d == :descending || d == :desc }
      return self.sort_by(&block).reverse
    end
    sorted = ((self.collect do |obj|
      [block.call(obj), obj]
    end).sort do |a, b|
      if !a[0].kind_of?(Array) || !b[0].kind_of?(Array)
        raise TypeError,
          "The block must return values of type Array."
      elsif a[0].size != directions.size || b[0].size != directions.size
        raise ArgumentError,
          "Size mismatch between block return value and " +
          "directions parameter: " +
          "#{a[0].inspect}, #{b[0].inspect}, #{directions.inspect}"
      else
        result = 0
        directions.each_with_index do |direction, index|
          value_a = a[0][index]
          value_b = b[0][index]
          if direction == :descending || direction == :desc
            result = value_b <=> value_a
          elsif direction == :ascending || direction == :asc
            result = value_a <=> value_b
          else
            raise ArgumentError,
              "Direction must be one of: :ascending, :descending, " +
              "was: #{direction.inspect}."
          end
          break if result != 0
        end
        result
      end
    end).collect do |pair|
      pair[1]
    end
    sorted
  end
end
56ee28134dd0776825445e3551979b14

Sporkmonger

September 5, 2008, September 05, 2008 13:41, permalink

No rating. Login to rate!

Some specs:

require File.dirname(__FILE__) + '/../spec_helper'

describe Enumerable, "when sorting in multiple directions" do
  it "should correctly sort the array" do
    result = [
      [1,2,3],
      [3,2,1],
      [1,1,1],
      [2,3,1],
      [3,2,3]
    ].sort_by_multiple(
      :ascending, :descending, :ascending
    ) { |o| o }
    result.should == [
      [1,2,3],
      [1,1,1],
      [2,3,1],
      [3,2,1],
      [3,2,3]
    ]
  end

  it "should correctly sort the array" do
    result = [
      [1,2,3],
      [3,2,1],
      [1,1,1],
      [2,3,1],
      [3,2,3]
    ].sort_by_multiple(
      :descending, :ascending, :ascending
    ) { |o| o }
    result.should == [
      [3,2,1],
      [3,2,3],
      [2,3,1],
      [1,1,1],
      [1,2,3]
    ]
  end

  it "should correctly sort the array" do
    result = [
      [1,2,3],
      [3,2,1],
      [1,1,1],
      [2,3,1],
      [3,2,3]
    ].sort_by_multiple(
      :ascending, :ascending, :ascending
    ) { |o| o }
    result.should == [
      [1,1,1],
      [1,2,3],
      [2,3,1],
      [3,2,1],
      [3,2,3]
    ]
  end

  it "should correctly sort the array" do
    result = [
      [1,2,3],
      [3,2,1],
      [1,1,1],
      [2,3,1],
      [3,2,3]
    ].sort_by_multiple(
      :descending, :descending, :descending
    ) { |o| o }
    result.should == [
      [3,2,3],
      [3,2,1],
      [2,3,1],
      [1,2,3],
      [1,1,1]
    ]
  end
end
56ee28134dd0776825445e3551979b14

Sporkmonger

September 5, 2008, September 05, 2008 14:04, permalink

No rating. Login to rate!

Another minor improvement.

module Enumerable
  # Sorts the enumeration by mapping the
  # values in the enumeration through the given block.
  #
  # The method takes a tuple of Symbols which indicate the sort direction
  # for each value returned by the block.
  #
  # The block must return a tuple of the same size as the direction tuple.
  def sort_by_multiple(*directions, &block)
    raise LocalJumpError, "No block given." if block == nil
    # Performance optimization
    if directions.all? { |d| d == :ascending || d == :asc }
      return self.sort_by(&block)
    elsif directions.all? { |d| d == :descending || d == :desc }
      return self.sort_by(&block).reverse
    end
    unless (directions.all? do |d|
      d == :ascending || d == :asc || d == :descending || d == :desc
    end) then
      raise ArgumentError,
        "Directions must all be one of: :ascending, :descending, " +
        "was: #{directions.inspect}."
    end
    sorted = ((self.collect do |obj|
      [block.call(obj), obj]
    end).sort do |a, b|
      if !a[0].kind_of?(Array) || !b[0].kind_of?(Array)
        raise TypeError,
          "The block must return values of type Array."
      elsif a[0].size != directions.size || b[0].size != directions.size
        raise ArgumentError,
          "Size mismatch between block return value and " +
          "directions parameter: " +
          "#{a[0].inspect}, #{b[0].inspect}, #{directions.inspect}"
      else
        result = 0
        directions.each_with_index do |direction, index|
          result = a[0][index] <=> b[0][index]
          next if result == 0
          result = -result if direction == :descending || direction == :desc
          break
        end
        result
      end
    end).collect do |pair|
      pair[1]
    end
    sorted
  end
end
A8d3f35baafdaea851914b17dae9e1fc

Adam

September 5, 2008, September 05, 2008 15:57, permalink

1 rating. Login to rate!

This is quite a bit faster on my system.

require "activesupport"

class Sorter < ActiveSupport::OrderedHash
  def initialize(array, &block)
    block ||= lambda { |element| element }
    super(array.map { |element| block.call(element).clone }.group_by { |element| element.delete_at(0) })
  end
  
  def sort(*directions)
    keys.sort(&method(directions.shift)).inject([]) do |result,key|
      next [ result, key ].flatten if self[key].flatten.empty?
      
      Sorter.new(self[key]).sort(*directions).each do |array|
        result << [ key, *array ].flatten
      end
      
      result
    end
  end
  
  private
    def ascending(a, b)
      a <=> b
    end
    
    def descending(a, b)
      b <=> a
    end
end
module Enumerable
  def sort_by_multiple(*directions, &block)
    Sorter.new(self, &block).sort(*directions)
  end
end
56ee28134dd0776825445e3551979b14

Sporkmonger

September 5, 2008, September 05, 2008 17:18, permalink

No rating. Login to rate!

Adam,

Interesting, but I couldn't get it to pass my specs:

TypeError in 'Enumerable when sorting in multiple directions should correctly sort the array'
can't convert Hash into Integer
From line #6.

A8d3f35baafdaea851914b17dae9e1fc

Adam

September 5, 2008, September 05, 2008 17:29, permalink

No rating. Login to rate!

How strange. It passes all your specs here. Using ActiveSupport 2.1 and Ruby 1.8.5.

56ee28134dd0776825445e3551979b14

Sporkmonger

September 5, 2008, September 05, 2008 17:31, permalink

No rating. Login to rate!

>> ActiveSupport::OrderedHash.new({})
=> TypeError: can't convert Hash into Integer

A8d3f35baafdaea851914b17dae9e1fc

Adam

September 5, 2008, September 05, 2008 18:11, permalink

1 rating. Login to rate!

That error is normal under that circumstance. OrderedHash works with arrays, not hashes.

>> ActiveSupport::OrderedHash.new([[1,2], [3,4]])
=> [[1, 2], [3, 4]]

However, there shouldn't be a Hash going into the class from the specs you posted.

56ee28134dd0776825445e3551979b14

Sporkmonger

September 5, 2008, September 05, 2008 18:47, permalink

No rating. Login to rate!

Enumerable#group_by returns a Hash.

A8d3f35baafdaea851914b17dae9e1fc

Adam

September 5, 2008, September 05, 2008 18:59, permalink

No rating. Login to rate!

Are you using Ruby 1.9 by any chance? Otherwise you should be getting an OrderedHash. Here's the relevant code from ActiveSupport:

module Enumerable
  # Ruby 1.8.7 introduces group_by, but the result isn't ordered. Override it.
  remove_method(:group_by) if [].respond_to?(:group_by) && RUBY_VERSION < '1.9'
 
  def group_by
    inject ActiveSupport::OrderedHash.new do |grouped, element|
      (grouped[yield(element)] ||= []) << element
      grouped
    end
  end unless [].respond_to?(:group_by)

  ...
56ee28134dd0776825445e3551979b14

Sporkmonger

September 5, 2008, September 05, 2008 19:21, permalink

No rating. Login to rate!

Adding in a call to Hash#to_a on the return value of Enumerable#group_by made it work. However, while it passes the original specs, it should also pass this additional spec, which it does not:

(Basically, thou shalt not flatten indiscriminately.)

it "should correctly sort the array" do
    result = [
      [[1],2,[3]],
      [[3],2,[1]],
      [[1],1,[1]],
      [[2],3,[1]],
      [[3],2,[3]]
    ].sort_by_multiple(
      :ascending, :descending, :ascending
    ) { |o| o }
    result.should == [
      [[1],2,[3]],
      [[1],1,[1]],
      [[2],3,[1]],
      [[3],2,[1]],
      [[3],2,[3]]
    ]
  end
56ee28134dd0776825445e3551979b14

Sporkmonger

September 5, 2008, September 05, 2008 19:25, permalink

No rating. Login to rate!

This is the fix for the offending line, (line #6):

super((array.map { |element| block.call(element).clone }.group_by { |element| element.delete_at(0) }).to_a)

Your refactoring





Format Copy from initial code

or Cancel