ruby - Ruby 颜色分组统计算法优化

Question

我有一个表面上看起来很简单的问题，我想用 ruby 来解决，我有一堆颜色和相关的照片 ID，例如

[[1,"red"],[1,"green"],[2,"red"],[3,"yellow"],[4,"green"],[4,"red"]]

我希望处理数据，使其成为这种格式:

红色、绿色2张照片
3张照片为红色
1 张照片为黄色

一些注意事项:

1. 匹配最多颜色的照片/照片在列表中排在第一位，如果匹配的颜色数量相同(如上面的红色和黄色)，则将最高数量放在第一位。

   <

2. 红色的计数为 3，因为 2 张照片有红色和绿色，而第三张只有红色。我不会单独显示绿色的结果，因为所有绿色照片都包含红色和绿色条目。

3. 最终，无论数据集有多大，我只需要显示前 5 个结果。

我已经编写了一个实现此目标的算法(见下文)，但我将不胜感激有关如何使其更快、更优雅的任何指导。速度是首要考虑因素，我将对大量数据(百万级订单)进行操作，然后如果可能的话，如果它可以变得更优雅，那会很好——我不认为我写的是优雅的 ruby​​ 代码，我有一个c++背景。

我知道在 ruby​​ 中嵌入 c 和 c++ 代码以提高性能，但我真的很想只使用 ruby​​ 来实现这一点。

非常感谢

beginning = Time.now

ARR = [[1,"red"],[1,"green"],[2,"red"],[3,"yellow"],[4,"red"],[4,"green"],[4,"yellow"],[5,"green"],[5,"red"],[6,"black"]]

# Group the colours by their id.
groups = ARR.group_by {|x| x[0]}

# output for profiling.
puts "After Group BY: #{Time.now - beginning} seconds."

# Remove the id's, as they are no longer useful. Sort the colours alphabetically.
sorted_groups = []
groups.each do |i,j|
  sorted_groups << j.map!{ |x|  x[1]}.sort
end

# Order the colours, so the group containing the most colours comes first.
# Do a secondary sort alphabetically, so that all identical groups are next to each other. 
sorted_groups_in_order = sorted_groups.sort_by { |s| [s.length,s] }.reverse

# Traverse the groups in order to find the index that marks the position of results_to_return unique groups.
# This is to make subsequent processing more efficient, as it will only operate on a smaller subset.
results_to_return = 5
temp = sorted_groups_in_order[0]
combination_count = 0
index = 0

sorted_groups_in_order.each do |e|
 combination_count +=1 if e != temp
 break if combination_count == results_to_return

 index += 1
 temp = e
end

# Iterate through the subset, and count the duplicates.
tags_with_count = Hash.new(0)
sorted_groups_in_order[0..index].each do |v|
  tags_with_count.store(v,tags_with_count[v]+1)
end

# Sort by the number of colours in each subset, the most colours go first.
tags_with_count = tags_with_count.sort { |q,w| w[0].size <=> q[0].size }

# if colour subsets are found in colour supersets, then increment the subset count to reflect this.
tags_with_count.reverse.each_with_index do |object,index|
  tags_with_count.reverse.each_with_index do |object2,index2|
    if (index2 < index) && (object[0]&object2[0] == object2[0])
      object2[1] += object[1]
    end
  end
end

# Sort by the number of colours in each subset, the most colours go first.
# Perform a secondary sort by the count value.
tags_with_count = tags_with_count.sort_by { |s| [s[0].length,s[1]] }.reverse

# print our results.
tags_with_count.each do |l|
  puts l.inspect
end

# output for profiling.
puts "Time elapsed: #{Time.now - beginning} seconds."

Answer 1

查看我的 new answer反射(reflect)修改后的规范

假设您有 > 1.8.7，您可以使用 Array.combination。否则你需要安装 ruby​​ 置换 gem:

http://permutation.rubyforge.org/

然后。 . .

data = [[1,"red"],[1,"green"],[2,"red"],[3,"yellow"],[4,"green"],[4,"red"]]

 # get a hash mapping photo_id to colors
colors_by_photo_id = data.inject(Hash.new {|h,k| h[k] = []})  do |h,a| 
     h[a.first] << a.last
     h
end

 # could use inject here, but i think this is more readable
total_counts = Hash.new{|h,k| h[k] = 0}

 # add up the sum for all combinations
colors_by_photo_id.values.each do |color_array|
  1.upto(color_array.size).each do |i|
     color_array.combination(i){|comb| total_counts[comb.sort] += 1}
  end
end

>> total_counts
=> {["green", "red"]=>2, ["red"]=>3, ["yellow"]=>1, ["green"]=>2}

 # or if you want the output sorted:
>> total_counts.to_a.sort_by{|a,c| -c}
=> [[["red"], 3], [["green", "red"], 2], [["green"], 2], [["yellow"], 1]]