用两种不同的方式对Ruby数组进行排序

Question

我有一个对象数组，想要按照多个条件进行排序。大部分比较只需要使用它们的哈希值来执行<=>操作，因此使用sort_by非常快，但其中一个比较更为复杂。

这个数组是足球队的数组，目前正在按以下方式进行排序：

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

然而，如果最后有两个或以上的团队在这三个领域上具有相同的价值，我希望使用我制作的函数a_beat_b（teamA，teamB）来解决平局问题。 我尝试使用Array.sort，但与sort_by相比，它非常缓慢...我的实现如下所示：

teams.sort（| a，b | [a.points，a.goals_dif，a.goals] <=> [b.points，b.goals_dif，b.goals]）

对于points，goals_dif和goals的函数需要一些简单的查询，但是如果要进行数百次查询，则会陷入困境。 我不太擅长Ruby，所以不确定在哪里放置a_beats_b。 （它返回1、0或-1，如果A打败了B，则分别为平局或输给B）

- Andre

---

你的 a_beat_b 实现是什么样子的？当你说“无法正确编写代码”时，你的意思是什么？ - Matt

a_beat_b 类似于 <=>，如果 A 队在本次比赛中击败了 B 队，则返回1；如果是平局，则返回0；如果 B 赢了，则返回-1。 Array.sort 的代码如下：teams.sort (|a,b| [a.points, a.goals_dif, a.goals] <=> [b.points, b.goals_dif, b.goals]) 我不知道将我的函数放在哪里。 我会编辑进去的。 - Andre

Array#sort 是正确的答案。你应该检查数组是否相同，然后有条件地使用 a_beat_b 来执行更昂贵的比较。如果我们不知道你如何尝试实现 Array#sort，我们就无法真正帮助你。 - user229044

我已经进行了编辑，不确定如何编写排序函数来使用我的函数。 - Andre

关于速度慢的问题：points，goals_dif和goals这些方法是否效率低下？ - Stefan

他们只是简单地对两个查询进行求和，速度相当快，但如果它们被频繁调用，所有的数据库访问都会使其变慢。 - Andre

Answer 1

我尝试使用Array.sort，但与sort_by相比，它非常慢，特别是在前几个元素时。

这是因为sort会多次调用给定的块。以下是一个示例，展示了底层发生的情况：（按长度对"apple"、"pear"和"fig"进行排序）

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

我们的length方法的输出：

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

正如您所看到的，length在排序过程中被调用多次。想象一下这些是数据库查询。

另一方面，sort_by对每个元素调用一次块，构建一个内部映射：

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

输出：

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

对于一些昂贵的操作（如数据库查询），这样做会更快。但是它也不那么灵活 - 你不能动态地比较 a 和 b 了。

然而，你可以通过使用哈希表来存储你 (昂贵) 操作的结果：(这被称为 记忆化)

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

在 sort 中使用哈希：

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

排序后，我们的哈希表如下所示：

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

应用到你的代码中，类似这样应该可以工作：

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

- Stefan

---

哇，我真的得学习一下你在那里做的事情。我已经知道排序函数之间的区别了，但这里有很多厉害的东西。不管怎样，这就是答案。谢谢！ - Andre

Answer 2

包含 a_beats_b 的 sort 实现：

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

- Aleksei Matiushkin

---

那个 result.zero? 看起来很不错！这段代码肯定是有效的，但是那个 sort 比 sort_by 还要慢得多，它需要超过 5 秒，而 sort_by 只需要大约 1 秒。如果这是唯一可能的方法，我会接受这个答案。 - Andre

Answer 3

这是另一种方法，虽然有些复杂，但设计的效率很高。该方法使用以下步骤：

• 将每个Team实例转换为一个包含实例和三元素数组的数组，用于进行廉价排序。
• 使用Enumerable#sort_by按三元素数组对数组进行排序。
• 使用Enumerable#chunk将具有相等三元素数组的二元素数组分组。
• 将每个分块数组元素映射到两个元素数组中的Team实例。
• 使用Enumerable#flat_map在经过方法a_beat_b(a, b)排序后（除非该组只包含一个团队）映射每个分块的Team实例组。

代码

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

示例

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

解释

具体步骤如下。

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> 

为了查看枚举器 c 生成的值，我们可以将其转换为数组。

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

- Cary Swoveland

Answer 4

根据排序函数的大小和常量，这可能是一种方法：

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

- hirolau