Ruby Array Sortuj 2 różne sposoby

Question

Mam szereg obiektów, które próbuję posortować według wielu kryteriów. Większość porównań to po prostu wykonanie <=> na swoich skrótach, więc używanie sort_by jest bardzo szybkie, ale jedno z nich jest bardziej złożone.

tablica jest drużyn piłkarskich, a to obecnie klasyfikowane tak:

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

Jednakże w przypadku, w ostatnich 2 zespoły mają identyczne wartości na tych 3 obszarach, chcę tiebreaker być funkcja które zrobiłem, a_beat_b(teamA, teamB).

Próbowałem za pomocą Array.sort, ale to jest bardzo powolny w porównaniu do sort_by dla tych pierwszych kilku ... mój wdrożenia było tak:

teams.sort (|a,b| [a.points, a.goals_dif, a.goals] <=> [b.points, b.goals_dif, b.goals])
To był bardzo powolny w porównaniu do sort_by. Funkcje punktów, target_dif i celów wymagają prostych zapytań, ale grzęźnie, jeśli musi setki.

Nie jestem zbyt dobry w Ruby, więc nie wiem, gdzie umieścić mój a_beats_b. (Zwraca 1, 0 lub -1 jeśli beat, zwrócił lub utracone do B, repsectively)

Answer 1

Próbowałem za pomocą Array.sort, ale jest to bardzo powolny w porównaniu do sort_by dla tych pierwszych kilku

to dlatego sort nazywa danego bloku kilka razy. Oto przykład, aby pokazać, co dzieje się pod maską: (sortowanie "apple", "pear" i "fig" według długości)

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"] 

Wyjście z naszej length metoda:

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

Jak widać, length nazywa wiele razy podczas sortowania. Wyobraź sobie, że są to zapytania do bazy danych.

sort_by z drugiej strony wywołuje blok raz dla każdego elementu, budowanie wewnętrznego mapowania:

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

wyjściowa:

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

dla drogich operacji (takich zapytań do bazy danych), jest znacznie szybciej. Ale jest także mniej elastyczny - nie można już dynamicznie porównywać wartości a i b.

Można jednak zapisać wyniki swojej (drogie) operacji, na przykład za pomocą skrótu: (nazywa się to memoization)

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

i użyj skrótu ciągu sort:

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

Po sortowaniu nasz skrót wygląda następująco:

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

Zastosowana do kodu, coś jak to powinno działać:

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

Realizacja sort z a_beats_b obejmowały:

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

Oto inne podejście, że choć trochę skomplikowane, został zaprojektowany dla wydajności. Metoda wykorzystuje następujące kroki.

• konwersji każdego Team na przykład na tablicy zawierającej tablicę wystąpienie i trzech elementów w którym tani sortowania do wykonania.
• Użyj Enumerable#sort_by, aby posortować tablice według tablic trzyelementowych.
• Skorzystaj z Enumerable#chunk, aby pogrupować dwuelementowe macierze, które mają równe, trój elementowe tablice.
• Mapuj każdy element tablicy z kawałkami na instancję Team w tablicy dwuelementowej.
• Użyj Enumerable#flat_map do odwzorowania każdej porcji grupy instancji Team po posortowaniu według metody a_beat_b(a, b) (chyba że grupa zawiera tylko jeden zespół, oczywiście).

kod

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 

Przykład

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>] 

Objaśnienie

Kroki są następujące.

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> 

Aby zobaczyć, jakie wartości są generowane przez moduł wyliczający c możemy przekonwertować go na tablicy.

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

W zależności od wielkości i const funkcji sortowania może być to podejście:

# 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)