Ruby Array Sort 2 different ways

Question

I have an array of objects that I am trying to sort by several criteria. Most comparisons are just <=> for their hashes, so using sort_by is very fast, but one of them is more complicated.

An array of football teams, and currently it is sorted as follows:

 teams.sort_by { |item| [item.points, item.goal_dif, item.goals] } 

However, if, finally, 2 teams have the same values ​​in these three fields, I want the tie-break to be the function that I did, a_beat_b(teamA, teamB) .

I tried using Array.sort , but it is very slow compared to sort_by for the first ones ... My implementation was like this:

teams.sort ( |a,b| [a.points, a.goals_dif, a.goals] <=> [b.points, b.goals_dif, b.goals])
This was very slow compared to sort_by. Functions for points, goals, and goals require some simple queries, but they are bogged down if they need to do hundreds.

I'm not very good at Ruby, so I don’t know where to place a_beats_b there. (It returns 1, 0, or -1 if the bit drawn or played before B is repeated)

Answer 1

I tried using Array.sort , but it is very slow compared to sort_by for those who are a little bit in the beginning

This is because sort calls this block several times. Here is an example to show what happens under the hood: (sorting "apple" , "pear" and "fig" by length)

 def length(str) puts "calculating #{str.inspect}.length" str.length end array = %w{apple pear fig} array.sort { |a, b| length(a) <=> length(b) } #=> ["fig", "pear", "apple"] 

The output from our length method:

 calculating "apple".length calculating "pear".length calculating "apple".length calculating "fig".length calculating "pear".length calculating "fig".length 

As you can see, length is called several times during sorting. Imagine these are database queries.

sort_by , on the other hand, calls the block once for each element, creating an internal mapping:

 array.sort_by { |a| length(a) } #=> ["fig", "pear", "apple"] 

Output:

 calculating "apple".length calculating "pear".length calculating "fig".length 

For expensive operations (like database queries) this is much faster. But it is also less flexible - you cannot dynamically compare a and b .

However, you can save the results of your (expensive) operation, for example, using a hash: (this is called memoization )

 hash = Hash.new { |h, k| h[k] = length(k) } 

And use the hash in sort :

 array.sort { |a, b| hash[a] <=> hash[b] } # calculating "apple".length # calculating "pear".length # calculating "fig".length #=> ["fig", "pear", "apple"] 

After sorting, our hash looks like this:

 hash #=> {"apple"=>5, "pear"=>4, "fig"=>3} 

As applied to your code, something like this should work:

 hash = Hash.new { |h, k| h[k] = [k.points, k.goal_dif, k.goals] } teams.sort { |a, b| hash[a] == hash[b] ? a_beats_b(a, b) : hash[a] <=> hash[b] } 

Answer 2

sort implementation with a_beats_b enabled:

 teams.sort do |a, b| result = [a.points, a.goals_dif, a.goals] <=> [b.points, b.goals_dif, b.goals] result.zero? ? a_beats_b(a, b) : result end 

Answer 3

Here's another approach, which, although somewhat complex, has been developed to increase efficiency. The method uses the following steps.

• Convert each instance of Team into an array containing an instance and an array of three elements, on which low-cost sorting will be performed.
• Use Enumerate # sort_by to sort arrays using three-element arrays.
• Use Enumerable # chunk to group two-element arrays with equal three-element arrays.
• Match each element of the selected array with the Team instance in the two-element array.
• Use List # flat_map to match each selected group of Team instances after sorting by a_beat_b(a, b) (if only the group contains only one command, of course).

code

 def sort_em(teams) teams.map { |t| [t, [t.points, t.goal_dif, t.goals]] }. sort_by(&:last). chunk(&:last). map { |_,tied_teams| tied_teams.map(&:first) }. flat_map { |tied_teams| (tied_teams.size == 1) ? tied_teams.first : tied_teams.sort { |a,b| a_beat_b(a, b) } } end 

Example

 class Team attr_reader :name, :points, :goal_dif, :goals def initialize(name, points, goal_dif, goals) @name, @points, @goal_dif, @goals = name, points, goal_dif, goals end end teams = [Team.new("bluebirds", 233, 25, 130), Team.new("eagles", 233, 18, 105), Team.new("jays", 233, 25, 130), Team.new("owls", 160, 12, 105), Team.new("sparrows", 233, 18, 105) ] #=> [#<Team:0x007ff2f900e5a8 @name="bluebirds", @points=233, @goal_dif=25, @goals=130>, # #<Team:0x007ff2f900e530 @name="eagles", @points=233, @goal_dif=18, @goals=105>, # #<Team:0x007ff2f900e4b8 @name="jays", @points=233, @goal_dif=25, @goals=130>, # #<Team:0x007ff2f900e440 @name="owls", @points=160, @goal_dif=12, @goals=105>, # #<Team:0x007ff2f900e3c8 @name="sparrows", @points=233, @goal_dif=18, @goals=105>] def a_beat_b(a, b) a.name.size <=> b.name.size end sort_em(teams) #=> [#<Team:0x007ff2fa845630 @name="owls", @points=160, @goal_dif=12, @goals=105>, # #<Team:0x007ff2fa845720 @name="eagles", @points=233, @goal_dif=18, @goals=105>, # #<Team:0x007ff2fa8455b8 @name="sparrows", @points=233, @goal_dif=18, @goals=105>, # #<Team:0x007ff2fa8456a8 @name="jays", @points=233, @goal_dif=25, @goals=130>, # #<Team:0x007ff2fa8457e8 @name="bluebirds", @points=233, @goal_dif=25, @goals=130>] 

Explanation

Following are the steps.

 a = teams.map { |t| [t, [t.points, t.goal_dif, t.goals]] } #=> [[#<Team:0x007ff2fa8457e8 @name="bluebirds", @points=233, @goal_dif=25, @goals=130>, # [233, 25, 130]], # [#<Team:0x007ff2fa845720 @name="eagles", @points=233, @goal_dif=18, @goals=105>, # [233, 18, 105]], # [#<Team:0x007ff2fa8456a8 @name="jays", @points=233, @goal_dif=25, @goals=130>, # [233, 25, 130]], # [#<Team:0x007ff2fa845630 @name="owls", @points=160, @goal_dif=12, @goals=105>, # [160, 12, 105]], # [#<Team:0x007ff2fa8455b8 @name="sparrows", @points=233, @goal_dif=18, @goals=105>, # [233, 18, 105]]] b = a.sort_by(&:last) #=> [[#<Team:0x007ff2fa845630 @name="owls", @points=160, @goal_dif=12, @goals=105>, # [160, 12, 105]], # [#<Team:0x007ff2fa845720 @name="eagles", @points=233, @goal_dif=18, @goals=105>, # [233, 18, 105]], # [#<Team:0x007ff2fa8455b8 @name="sparrows", @points=233, @goal_dif=18, @goals=105>, # [233, 18, 105]], # [#<Team:0x007ff2fa8457e8 @name="bluebirds", @points=233, @goal_dif=25, @goals=130>, # [233, 25, 130]], # [#<Team:0x007ff2fa8456a8 @name="jays", @points=233, @goal_dif=25, @goals=130>, # [233, 25, 130]] # ] c = b.chunk(&:last) #=> #<Enumerator: #<Enumerator::Generator:0x007ff2fa81dc20>:each> 

To find out what values ​​are generated by the enumerator c , we can convert it to an array.

 c.to_a #=> [[[160, 12, 105], # [[#<Team:0x007ff2fa845630 @name="owls",@points=160,@goal_dif=12,@goals=105>, # [160, 12, 105] # ] # ] # ], # [[233, 18, 105], # [[#<Team:0x007ff2fa845720 @name="eagles",@points=233,@goal_dif=18,@goals=105>, # [233, 18, 105] # ], # [#<Team:0x007ff2fa8455b8 @name="sparrows",@points=233,@goal_dif=18,@goals=105>, # [233, 18, 105] # ] # ], # [[233, 25, 130], # [[#<Team:0x007ff2fa8457e8 @name="bluebirds",@points=233,@goal_dif=25,@goals=130>, # [233, 25, 130] # ], # [#<Team:0x007ff2fa8456a8 @name="jays", @points=233,@goal_dif=25,@goals=130>, # [233, 25, 130] # ] # ] # ] # ] 

 d = c.map { |_,tied_teams| tied_teams.map(&:first) } #=> [[#<Team:0x007ff2fa845630 @name="owls", @points=160, @goal_dif=12, @goals=105>], # [#<Team:0x007ff2fa845720 @name="eagles", @points=233, @goal_dif=18, @goals=105>, # #<Team:0x007ff2fa8455b8 @name="sparrows", @points=233, @goal_dif=18, @goals=105> # ], # [#<Team:0x007ff2fa8457e8 @name="bluebirds", @points=233, @goal_dif=25, @goals=130>, # #<Team:0x007ff2fa8456a8 @name="jays", @points=233, @goal_dif=25, @goals=130> # ] # ] d.flat_map { |tied_teams| (tied_teams.size == 1) ? tied_teams.first : tied_teams.sort { |a,b| a_beat_b(a, b) } } #=> [#<Team:0x007ff2fa845630 @name="owls", @points=160, @goal_dif=12, @goals=105>, # #<Team:0x007ff2fa845720 @name="eagles", @points=233, @goal_dif=18, @goals=105>, # #<Team:0x007ff2fa8455b8 @name="sparrows", @points=233, @goal_dif=18, @goals=105>, # #<Team:0x007ff2fa8456a8 @name="jays", @points=233, @goal_dif=25, @goals=130>, # #<Team:0x007ff2fa8457e8 @name="bluebirds", @points=233, @goal_dif=25, @goals=130> # ] 

Answer 4

Depending on the size and const of the sort function, this might be the approach:

 # First group the teams by standard sort: groups = teams.group_by{|a| [a.points, a.goals_dif, a.goals] } # For each group that has ties. Run the slow sorter on them: groups.each{ |_,val| val.sort!{|teamA,teamB| a_beat_b(teamA, teamB)} if val.size > 1 } # Finally run sort on the keys of the group by: groups.sort.flat_map(&:last)