Ruby: Как найти элемент в массиве, который встречается чаще всего?

Question

[1, 1, 1, 2, 3].mode
=> 1

['cat', 'dog', 'snake', 'dog'].mode
=> dog

Answer 1

Сначала создайте хеш, отображающий каждое значение в массиве на его частоту ...

arr = [1, 1, 1, 2, 3]

freq = arr.inject(Hash.new(0)) { |h,v| h[v] += 1; h }
#=> {1=>3, 2=>1, 3=>1}

… затем используйте таблицу частот, чтобы найти элемент с самой высокой частотой:

arr.max_by { |v| freq[v] }
#=> 1

Answer 2

Хотя я обожаю решение grep за его элегантность и за напоминание (или обучение) о методе в Enumerable, который я забыл (или полностью упустил из виду), он медленный, медленный, медленный. Я согласен на 100%, что создание метода Array#mode - хорошая идея, однако, это Ruby, нам не нужна библиотека функций, которые работают с массивами, мы можем создать миксин, который добавляет необходимые функции в сам класс Array.

Но альтернатива inject (Hash) использует сортировку, в которой мы на самом деле не нуждаемся: мы просто хотим получить значение с наибольшим вхождением.

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

require 'benchmark'

class Array
  def mode1
    sort_by {|i| grep(i).length }.last
  end
  def mode2
    freq = inject(Hash.new(0)) { |h,v| h[v] += 1; h }
    sort_by { |v| freq[v] }.last    
  end
  def mode3
    freq = inject(Hash.new(0)) { |h,v| h[v] += 1; h }
    max = freq.values.max                   # we're only interested in the key(s) with the highest frequency
    freq.select { |k, f| f == max }         # extract the keys that have the max frequency
  end
end

arr = Array.new(1_000) { |i| rand(100) }    # something to test with

Benchmark.bm(30) do |r|
  res = {}
  (1..3).each do |i|
    m = "mode#{i}"
    r.report(m) do
      100.times do
        res[m] = arr.send(m).inspect
      end
    end
  end
  res.each { |k, v| puts "%10s = %s" % [k, v] }
end

А вот вывод из примера запуска.

                                user     system      total        real
mode1                          34.375000   0.000000  34.375000 ( 34.393000)
mode2                           0.359000   0.000000   0.359000 (  0.359000)
mode3                           0.219000   0.000000   0.219000 (  0.219000)
     mode1 = 41
     mode2 = 41
     mode3 = [[41, 17], [80, 17], [72, 17]]

«Оптимизированный» режим3 занимал 60% времени предыдущего рекордсмена. Обратите также внимание на несколько записей с самой высокой частотой.

EDIT

Через несколько месяцев я заметил ответ Нилеша , который предложил это:

def mode4
  group_by{|i| i}.max{|x,y| x[1].length <=> y[1].length}[0]
end

Он не работает с 1.8.6 из коробки, потому что эта версия не имеет Array # group_by. ActiveSupport имеет его для разработчиков Rails, хотя кажется, что он на 2-3% медленнее, чем mode3 выше. Однако использование (превосходного) backports драгоценного камня дает 10-12% прироста , а также дает целую кучу дополнений 1.8.7 и 1.9.

Вышеуказанное относится только к 1.8.6 - и в основном только в случае установки в Windows. Поскольку он у меня установлен, вот что вы получаете от IronRuby 1.0 (в .NET 4.0):

==========================   IronRuby   =====================================
(iterations bumped to **1000**)    user     system      total        real
mode1 (I didn't bother :-))
mode2                           4.265625   0.046875   4.312500 (  4.203151)
mode3                           0.828125   0.000000   0.828125 (  0.781255)
mode4                           1.203125   0.000000   1.203125 (  1.062507)

Так что, если производительность является сверхкритической, сравните параметры вашей версии и ОС Ruby. YMMV .

Answer 3

array.max_by { |i| array.count(i) }

Answer 4

Майк: я нашел более быстрый метод. Попробуйте это:

  class Array
    def mode4
      group_by{|i| i}.max{|x,y| x[1].length <=> y[1].length}[0]
    end
  end

Результат теста:

                                    user     system      total        real
mode1                          24.340000   0.070000  24.410000 ( 24.526991)
mode2                           0.200000   0.000000   0.200000 (  0.195348)
mode3                           0.120000   0.000000   0.120000 (  0.118200)
mode4                           0.050000   0.010000   0.060000 (  0.056315)
     mode1 = 76
     mode2 = 76
     mode3 = [[76, 18]]
     mode4 = 76

Answer 5

arr = [ 1, 3, 44, 3 ]
most_frequent_item = arr.uniq.max_by{ |i| arr.count( i ) }
puts most_frequent_item
#=> 3

Не нужно даже думать о частотных сопоставлениях.

Answer 6

Это дубликат этого вопроса: Ruby - уникальные элементы в массиве

Вот решение этого вопроса:

group_by { |n| n }.values.max_by(&:size).first

Эта версия кажется даже быстрее, чем ответ Nilesh C. Вот код, который я использовал для тестирования (OS X 10.6 Core 2 2,4 ГГц МБ).

Благодарность Майку Вудхаусу за (исходный) код оценки:

class Array
   def mode1
     group_by { |n| n }.values.max_by(&:size).first
   end
   def mode2
     freq = inject(Hash.new(0)) { |h,v| h[v] += 1; h }
     max = freq.values.max                   # we're only interested in the key(s) with the highest frequency
     freq.select { |k, f| f == max }         # extract the keys that have the max frequency
   end
end

arr = Array.new(1_0000) { |i| rand(100000) }    # something to test with

Benchmark.bm(30) do |r|
    (1..2).each do |i| r.report("mode#{i}") { 100.times do arr.send("mode#{i}").inspect; end }; end
end

А вот и результаты теста:

                                user     system      total        real
mode1                           1.830000   0.010000   1.840000 (  1.876642)
mode2                           2.280000   0.010000   2.290000 (  2.382117)
 mode1 = 70099
 mode2 = [[70099, 3], [70102, 3], [51694, 3], [49685, 3], [38410, 3], [90815, 3], [30551, 3], [34720, 3], [58373, 3]]

Как видите, эта версия работает примерно на 20% быстрее с учетом игнорирования связей. Мне также нравится краткость, я лично использую это как есть, без повязок обезьяны повсюду. :)

Answer 7

, если вы пытаетесь избежать изучения #inject (чего не следует делать ...)

words = ['cat', 'dog', 'snake', 'dog']
count = Hash.new(0)

words.each {|word| count[word] += 1}
count.sort_by { |k,v| v }.last

но если бы я прочитал этот ответ раньше, теперь я бы ничего не знал о #inject и man, вам нужно знать о # inject.

Answer 8

Вот еще одна версия, которая дает вам связи в зависимости от режима:

def mode
  group_by {|x| x}.group_by {|k,v| v.size}.sort.last.last.map(&:first)
end

Другими словами, сгруппируйте значения, затем сгруппируйте эти пары kv по количеству значений, затем отсортируйте эти kv пары, возьмите последнюю (наибольшую) размерную группу и затем раскрутите ее значения. Мне нравится group_by.

Answer 9

idx = {}
[2,2,1,3,1].each { |i| idx.include?(i) ? idx[i] += 1 : idx[i] = 1}

Это просто простой индексатор. Вы можете заменить массив [2,2,1 ..] любым идентификатором, основанным на символах / строках, это не сработает с объектами, вам нужно внести немного больше сложности, но это достаточно просто.

Перечитывая ваши вопросы, это решение несколько перегружено, так как оно собирается возвращать вам индекс всех вхождений, а не только одного из них.

Answer 10

def mode(array)

    count = []  # Number of times element is repeated in array
    output = [] 
    array.compact!
    unique = array.uniq
    j=0

    unique.each do |i|
        count[j] = array.count(i)
        j+=1
    end
    k=0
    count.each do |i|
        output[k] = unique[k] if i == count.max
        k+=1
    end  

    return output.compact.inspect
end

p mode([3,3,4,5]) #=> [3]

p mode([1,2,3]) #=> [1,2,3]

p mode([0,0,0,0,0,1,2,3,3,3,3,3]) #=> [0,3]

p mode([-1,-1,nil,nil,nil,0]) #=> [-1]

p mode([-2,-2,3,4,5,6,7,8,9,10,1000]) #=> [-2]