Ruby: Sorting an array with another array

Question

let o1, o2, o3, o4 activerecord objects with

o1.kind = "att2"
o2.kind = "att3"
o3.kind = "att4"
o4.kind = "att1"

Let a = [o1, o2, o3, o4]

Let b = ['att1', 'att3', 'att4', 'att2']

I need to sort a with b so that the new order in a becomes:

a = [o4, o2, o3, o1]

I tried

a.sort_by do |element|
  b.index(element)
end

But how to sort by kind?

`a`, `b` are pretty bad names, even for an example, specially considering they are collections (so plural is more meaningful). — tokland, Aug 01 '13 at 15:37
Please don't select an answer so quickly, give time for people to improve their answers. Instead, give some feedback. — tokland, Aug 01 '13 at 15:39

score 6 · Answer 1 · answered Aug 01 '13 at 15:14

6

You need the index of element.kind, not element.

a.sort_by do |element|
  b.index(element.kind)
end

answered Aug 01 '13 at 15:14

mihai

37,072
9
60
86

+1 for simple, -1 for O(n^2) – tokland Aug 01 '13 at 15:36
2

The `O(n^2)` aspect is critical if this is going to be running against large sets of values for `a` and/or `b`, because it will cause it to run increasingly slower. – the Tin Man Aug 01 '13 at 15:40
fair enough...good point :) – mihai Aug 05 '13 at 08:10

tokland · Accepted Answer · 2013-08-01T18:55:51.687

4

O(n+m):

Hash[a.map { |o| [o.kind, o] }].values_at(*b)

edited Aug 01 '13 at 18:55

answered Aug 01 '13 at 15:36

tokland

66,169
13
144
170

I prefer this implementation even though it's slightly less pretty, since it is going to be O(n). – Chris Heald Aug 01 '13 at 15:43
@ChrisHeald: Is this pretty enough? `a.mash { |o| [o.kind, o] }.values_at(*b)` – tokland Aug 01 '13 at 15:45
I just mean that `sort_by` is self-descriptive, while this form is less obvious that it's supposed to be a sort. – Chris Heald Aug 01 '13 at 15:49
1

What the OP wants isn't really a sort, it's an associative lookup. I think the OP didn't know that though. – the Tin Man Aug 01 '13 at 15:59
@theTinMan: Good point. I think the most declarative code for this associative lookup could be a slightly modified version using a new abstraction: `a.to_hash_by(&:kind).values_at(*b)` or something similar, `categorize_by`?. – tokland Aug 01 '13 at 16:29

the Tin Man · Answer 3 · 2013-08-01T15:57:56.893

I'm using OpenStruct to imitate an Active Record result:

require 'ostruct'
o1, o2, o3, o4 = [*(1..4)].map{ OpenStruct.new }

o1.kind = "att2"
o2.kind = "att3"
o3.kind = "att4"
o4.kind = "att1"

a = [o1, o2, o3, o4]
b = ['att1', 'att3', 'att4', 'att2']

a_hash = Hash[a.map{ |e| [e.kind, e] }]
a_hash # => {"att2"=>#<OpenStruct kind="att2">, "att3"=>#<OpenStruct kind="att3">, "att4"=>#<OpenStruct kind="att4">, "att1"=>#<OpenStruct kind="att1">}

new_a_order = a_hash.values_at(*b)
new_a_order # => [#<OpenStruct kind="att1">, #<OpenStruct kind="att3">, #<OpenStruct kind="att4">, #<OpenStruct kind="att2">]

Benchmark time:

require 'benchmark'
require 'ostruct'

o1, o2, o3, o4 = [*(1..4)].map{ OpenStruct.new }

o1.kind = "att2"
o2.kind = "att3"
o3.kind = "att4"
o4.kind = "att1"

a = [o1, o2, o3, o4]
b = ['att1', 'att3', 'att4', 'att2']

def tokland(a_ary, b_ary)
  Hash[a_ary.map{ |e| [e.kind, e] }].values_at(*b_ary)
end

def bioneurlanet(a_ary, b_ary)
  b_ary.map { |att| a_ary.detect { |obj| obj.kind == att } }
end

def mihai(a_ary, b_ary)
  a_ary.sort_by do |element|
    b_ary.index(element.kind)
  end
end

N = 1_000_000
puts 'Ruby => ' + RUBY_VERSION
puts 'N => %d' % N

print 'tokland => ', tokland(a,b), "\n"
print 'bioneurlanet => ', bioneurlanet(a,b), "\n"
print 'mihai => ', mihai(a,b), "\n"


Benchmark.bm(12) do |x|
  x.report('tokland') { N.times { tokland(a,b) }}
  x.report('bioneurlanet') { N.times { bioneurlanet(a,b) }}
  x.report('mihai') { N.times { mihai(a,b) }}
end

Which outputs:

Ruby => 2.0.0
N => 1000000
tokland => [#<OpenStruct kind="att1">, #<OpenStruct kind="att3">, #<OpenStruct kind="att4">, #<OpenStruct kind="att2">]
bioneurlanet => [#<OpenStruct kind="att1">, #<OpenStruct kind="att3">, #<OpenStruct kind="att4">, #<OpenStruct kind="att2">]
mihai => [#<OpenStruct kind="att1">, #<OpenStruct kind="att3">, #<OpenStruct kind="att4">, #<OpenStruct kind="att2">]
                   user     system      total        real
tokland        2.890000   0.010000   2.900000 (  2.885242)
bioneurlanet   4.430000   0.000000   4.430000 (  4.434342)
mihai          3.180000   0.010000   3.190000 (  3.189240)

bioneuralnet · Answer 4 · 2013-08-01T15:27:22.723

2

This doesn't use sort_by, but it gets the result you want. Just a different way to think about the problem.

b.map { |att| a.detect { |obj| obj.kind == att } }

edited Aug 01 '13 at 15:27

answered Aug 01 '13 at 15:22

bioneuralnet

5,283
1
24
30

score 1 · Answer 5 · answered Aug 01 '13 at 17:08

1

I'd use a hash instead of an array for sorting:

b = {"att1"=>0, "att3"=>1, "att4"=>2, "att2"=>3}
a.sort_by { |e| b[e.kind] }

This is both, fast and plain.

You can convert an existing array with Hash[ary.each_with_index.to_a]

answered Aug 01 '13 at 17:08

Stefan

109,145
14
143
218

1

Yes, using the right container from the start really helps. – the Tin Man Aug 01 '13 at 18:04

Ruby: Sorting an array with another array

5 Answers5