Оптимизация алгоритма Ruby для группировки и подсчета цветов

Question

У меня, на первый взгляд, простая проблема, которую я хочу решить с помощью ruby, у меня есть куча цветов с соответствующими идентификаторами фотографий, например,

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

и я хочу обработать данные так, чтобы они были в этом формате:

2 фото для красного, зеленого
3 фото для красных
1 фотография для желтого

Несколько замечаний:

1. Фотографии / фотографии, соответствующие наибольшему количеству цветов, являются первыми в списке, если количество совпадающих цветов одинаково (как для красного и желтого выше), то сначала ставится наибольшее число.

2. Счетчик красного цвета равен 3, поскольку 2 фотографии имеют красный и зеленый цвета, а третья - только красный. Я не отображаю результат для зеленого цвета сам по себе, так как все зеленые фотографии учитываются с записью для красного и зеленого.

3. В конечном итоге мне нужно отображать только 5 лучших результатов независимо от размера набора данных.

Я написал алгоритм, который достигает этой цели (см. Ниже), но я был бы признателен за любые рекомендации о том, как я могу сделать это быстрее, а затем более элегантно. Скорость - это главное, я буду работать с большим количеством данных (порядка миллионов), затем, если это возможно, если это можно будет сделать более элегантным, что было бы неплохо - я не думаю, что я пишу элегантный код ruby, у меня есть c ++ background.

Мне известно о встраивании кода c и c ++ в ruby ​​для повышения производительности, но я бы очень хотел добиться этого только с помощью 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

Я публикую новый ответ, так как вы немного изменили спецификацию.

Это выполнялось в 1/3 вашего времени на небольшом наборе данных, давая тот же результат.

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

#assemble an array of photos, each photo being an array of sorted colors
photos = ARR.inject(Hash.new {|h,k| h[k] = []})  do |h,a| 
     h[a.first] &lt&lt a.last
     h
end.values.map{|v| v.sort!}

#count the occurrences of each combination
combination_counts = photos.uniq.inject(Hash.new(0)) {|h,comb| h[comb] = photos.count(comb); h}

#unique combinations
combinations = combination_counts.keys 

<strike>#find the 5 largest combinations
top_5 = (1..[combinations.size,5].min).map do 
          combinations.delete( combinations.max {|a,b| a.size &lt=> b.size} )
        end
</strike>
#find the top 5, plus extras in case of ties <b>(this replaces the above stricken code)</b>
top_set = []
next_photo = combinations.delete( combinations.max {|a,b| a.size &lt=> b.size} )
begin
  top_set &lt&lt next_photo 
  last_photo = next_photo
  next_photo = combinations.delete( combinations.max {|a,b| a.size &lt=> b.size} ) unless combinations.empty?
end while !combinations.empty? && (top_set.size &lt 5 || next_photo.size == last_photo.size)


#calculate frequency of the largest counts & sort
total_counts = top_set.inject(Hash.new {|h,k| h[k] = 0}) do |hash,combination|
  combination_counts.each{|k,v| hash[combination] += v if (combination & k) == combination}
  hash
end.sort_by { |s| [-1*s[0].length,-1*s[1]] }

total_counts[0..4].each do |l|
  puts l.inspect
end
# output for profiling.
puts "Time elapsed: #{Time.now - beginning} seconds."

Answer 2

См. Мой новый ответ , который отражает измененные спецификации

Если у вас> 1.8.7, вы можете использовать Array.combination. В противном случае вам нужно установить гем пермутации ruby:

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

Answer 3

Требуется 1.8.7+ для group_by

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

groups = a .
  group_by {|e|e[0]} .
  collect do |id, photos|
    [id, photos.inject([]){|all,(id,colour)| all << colour}.sort.uniq]
  end .
  group_by {|e|e[1]}

groups.each {|colours, list| groups[colours] = list.length}
h = Hash.new {|h,k| h[k]=[0,0]}

groups.each do |colours, count|
  colours.each do |colour|
    h[colour][0] += 1  # how many times a colour appears
    h[colour][1] += count  # how many photos the colour appears in
  end
end

h.each do |colour, (n,total)|
  groups.update({[colour] => total}) if n > 1
end

groups.each {|colours, count| puts "#{count} photos for #{colours.join ','}"}

выходы

2 photos for green,red
3 photos for red
1 photos for yellow