Mảng Ruby Sắp xếp theo 2 cách khác nhau

Question

Tôi có một mảng đối tượng mà tôi đang cố sắp xếp theo nhiều tiêu chí. Hầu hết các so sánh chỉ bằng cách thực hiện <=> trên băm của chúng, vì vậy việc sử dụng sort_by rất nhanh, nhưng một trong số chúng phức tạp hơn.

Mảng là của đội bóng, và nó hiện đang được sắp xếp như thế này:

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

Tuy nhiên, trong trường hợp ở 2 đội cuối cùng có giá trị giống nhau trên những 3 lĩnh vực, tôi muốn các sợi giây là một chức năng mà tôi đã tạo, a_beat_b(teamA, teamB).

tôi đã cố gắng sử dụng Array.sort, nhưng nó rất chậm so với sort_by cho những người đầu tiên vài ... thực hiện của tôi là như thế này:

teams.sort (|a,b| [a.points, a.goals_dif, a.goals] <=> [b.points, b.goals_dif, b.goals])
Đó là rất chậm so với sort_by. Các hàm cho các điểm, goal_dif và các mục tiêu yêu cầu một số truy vấn đơn giản, nhưng nó bị sa lầy nếu nó phải làm hàng trăm.

Tôi không giỏi Ruby, vì vậy, không chắc chắn nên đặt a_beats_b vào đó ở đâu. (Nó trả về 1, 0 hoặc -1 nếu A nhịp, thu hút hoặc bị mất đến B, repsectively)

Answer 1

Tôi đã cố gắng sử dụng Array.sort, nhưng nó rất chậm so với sort_by cho những người đầu tiên số

Điều này là do số sort gọi khối đã cho nhiều lần. Dưới đây là một ví dụ cho thấy những gì đang xảy ra dưới mui xe: (sắp xếp "apple", "pear" và "fig" theo chiều dài)

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

Output từ phương pháp length của chúng tôi:

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

Như bạn thấy, length được gọi là nhiều lần trong khi sắp xếp. Hãy tưởng tượng rằng đây là những truy vấn cơ sở dữ liệu.

sort_by mặt khác gọi là khối một lần cho mỗi phần tử, xây dựng một bản đồ nội bộ:

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

Output:

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

Đối với hoạt động tốn kém (như truy vấn cơ sở dữ liệu), đây là nhiều nhanh hơn. Nhưng nó cũng ít linh hoạt hơn - bạn không thể tự động so sánh a và b nữa.

Bạn tuy nhiên có thể lưu trữ các kết quả của (đắt tiền) hoạt động của bạn, ví dụ bằng cách sử dụng một hash: (điều này được gọi là memoization)

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

Và sử dụng các hash trong sort:

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

Sau khi sắp xếp, giá trị băm của chúng tôi trông giống như sau:

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

Áp dụng cho mã của bạn, một cái gì đó như thế này sẽ hoạt động:

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

Thực hiện sort với a_beats_b bao gồm:

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

Đây là một cách tiếp cận khác, trong khi hơi phức tạp, được thiết kế để có hiệu quả. Phương pháp này sử dụng các bước sau.

• Chuyển đổi từng mảng Team thành một mảng chứa thể hiện và mảng ba phần tử mà sắp xếp không tốn kém.
• Sử dụng Enumerable#sort_by để sắp xếp mảng theo mảng ba phần tử.
• Sử dụng Enumerable#chunk để nhóm các mảng hai phần tử có mảng ba phần tử bằng nhau.
• Ánh xạ từng phần tử mảng vào ví dụ Team trong mảng hai phần tử.
• Sử dụng Enumerable#flat_map để ánh xạ từng nhóm chunked Team trường hợp sau khi được sắp xếp theo phương pháp a_beat_b(a, b) (trừ khi nhóm chỉ chứa một nhóm).

Mã

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 

Ví dụ

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

Giải thích

Các bước thực hiện như sau.

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> 

Để xem giá trị nào được tạo bởi điều tra c, chúng tôi có thể chuyển đổi giá trị đó thành một mảng.

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

Tùy thuộc vào kích thước và const của hàm sắp xếp này có thể là một cách tiếp cận:

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