7
\$\begingroup\$

Ruby's built-in sorts are unstable. The stable_sort gem monkey-patches Ruby's built-in library to have stable sorts which include nearly all the functionality of the built-in sorts, but with the addition of stability.

The built-in sort method can take a block:

a.sort do |x, y|
  x.length <=> y.length
end

However, the gem's #stable_sort_by method cannot take a block (as of version 1.1). I am adding that capability. By simply replacing "sort" with "stable_sort", the above sort would become stable:

a.stable_sort do |x, y|
  x.length <=> y.length
end

The code that needs improvement

My implementation is ugly, and not performant: It creates a temporary array of the same size as the original. Here is the monkey-patch that adds Enumerable#stable_sort:

module Enumerable

  def stable_sort_by
    return to_enum(:stable_sort_by) if !block_given?
    sort_by.with_index{ |e, index| [yield(e), index] }
  end

  def stable_sort
    if block_given?
      # Add indices
      a = map.with_index do |e, i|
        [e, i]
      end
      # Use built-in sort.  When two elements compare the same,
      # compare the indices to break the tie
      a.sort! do |(a, i), (b, j)|
        result = yield(a, b)
        if result == 0
          i <=> j
        else
          result
        end
      end
      # Remove the indices 
      a.map(&:first)
    else
      stable_sort_by { |x| x }
    end
  end

end

Supporting code

The rspec test:

describe Enumerable do

  KeyValue = Struct.new(:key, :value) do
    def <=> (other)
      self.key <=> other.key
    end
  end

  let (:array) { [KeyValue.new(1, 1), KeyValue.new(1, 2), KeyValue.new(1, 3), KeyValue.new(1, 4), KeyValue.new(0, 10)] }
  let (:expectation) { [KeyValue.new(0, 10), KeyValue.new(1, 1), KeyValue.new(1, 2), KeyValue.new(1, 3), KeyValue.new(1, 4)] }

  describe "#stable_sort (Array)" do
    it 'sorts stably' do
      expect(array.stable_sort.to_s).to eq expectation.to_s
    end
  end

  describe "#stable_sort (Array) (with block)" do
    it 'sorts stably' do
      array = ['a', 'c', 'bd', 'fe', 'b']
      sorted = array.stable_sort do |a, b|
        a.length <=> b.length
      end
      expect(sorted).to eq ['a', 'c', 'b', 'bd', 'fe']
    end
  end

end

The benchmark:

require "benchmark"

def iterate
  100.times { yield }
end

Benchmark.bm(16) do |x|
  Random.srand(0)
  a = Array.new(10000) { rand(100) }
  x.report("sort") do
    iterate { a.sort }
  end
  x.report("sort {}") do
    iterate { a.sort { |a, b| a <=> b } }
  end
  x.report("stable_sort") do
    iterate { a.stable_sort }
  end
  x.report("stable_sort {}") do
    iterate { a.stable_sort { |a, b| a <=> b } }
  end
end

And benchmark results:

                       user     system      total        real
sort               0.110000   0.010000   0.120000 (  0.119809)
sort {}            0.800000   0.000000   0.800000 (  0.798593)
stable_sort        2.800000   0.000000   2.800000 (  2.801303)
stable_sort {}     2.060000   0.010000   2.070000 (  2.062832) <--- 

The question

Can stable_sort (benchmark "stable_sort {}") be made more more performant? Can it be made cleaner?

Copyright notice

Portions of the above code are derived from the stable_sort gem which is is Copyright (c) 2013 by Naoyoshi Aikawa and released under the MIT License.

\$\endgroup\$
  • \$\begingroup\$ Would it be possible to use sort_by using the index in the block_given? part? \$\endgroup\$ – Mark Thomas Jun 27 '17 at 12:46
  • \$\begingroup\$ @MarkThomas I don't know how to make that work. The trouble is that the block given to #stable_sort_by doesn't return a comparable object--instead, it does the actual comparison. #sort_by needs something comparable. \$\endgroup\$ – Wayne Conrad Jun 27 '17 at 12:59
  • \$\begingroup\$ I'm guessing most of your excess time is from the unnecessary copy. Have you tried just writing your own merge sort instead? The gains from avoiding the copy may outweigh the losses from sorting in ruby rather than relying on the built-in sort in C. You could test the hypothesis fairly quickly, anyway: stackoverflow.com/questions/21121075/… \$\endgroup\$ – Jonah Jun 28 '17 at 1:24
  • \$\begingroup\$ @Jonah I would be astonished if any pure-Ruby sort could beat the copy-plus-built-in sort. Still, I hadn't thought about implementing the sort in Ruby, so that's a good idea to have. \$\endgroup\$ – Wayne Conrad Jun 28 '17 at 15:31
  • 1
    \$\begingroup\$ @WayneConrad: Actually, at least Rubinius, JRuby, and especially TruffleRuby can do some amazing optimizations. TruffleRuby in particular has been known to beat hand-optimized YARV C extensions. \$\endgroup\$ – Jörg W Mittag Jul 3 '17 at 12:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.