Как найти, какие элементы в массиве MASSIVE появляются более одного раза?

Это очень простой вопрос; какие элементы отображаются в списке более одного раза?

Проблемы решены. Но ждать! Что делать, если массив ДЕЙСТВИТЕЛЬНО большой:

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

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

Мы говорим от 10 000 до 10 000 000 строк на файл, сотни файлов.

Ответы

Ответ 1

Что-то вроде

items = 30_000_000

array = items.times.map do
  rand(10_000_000)
end

puts "Done with seeding"
puts
puts "Checking what items appear more than once. Size: #{array.size}"
puts

t1 = Time.now
def more_than_once(array)
  counts = Hash.new(0)
  array.each do |item|
    counts[item] += 1
  end

  counts.select do |_, count|
    count > 1
  end.keys
end

res = more_than_once(array)
t2 = Time.now


p res.size
puts "Took #{t2 - t1}"

работает для вас?

Продолжительность около 40 секунд на моей машине.

Ответ 2

Вот еще два решения с сравнительным сравнением этих и методов @Pascal.

Использовать наборы

require 'set'

def multi_set(arr)
  s1 = Set.new
  arr.each_with_object(Set.new) { |e, smulti| smulti.add(e) unless s1.add?(e) }.to_a
end

arr = ["mike", "mike", "mike", "john", "john", "peter", "clark"]    
multi(arr)
  #=> ["mike", "john"]

s1 строится для включения всех отдельных элементов arr. s1.add?(e) возвращает nil, если s1 уже содержит e, и в этом случае e добавляется к smulti, если smulti уже не содержит этот элемент. (См. Установить # добавить?.) smulti возвращается методом.

Использовать Array#difference

Array#difference - это метод, который я предложил добавить к ядру Ruby. См. Также мой ответ здесь.

class Array
  def difference(other)
    h = other.each_with_object(Hash.new(0)) { |e,h| h[e] += 1 }
    reject { |e| h[e] > 0 && h[e] -= 1 }
  end
end

def multi_difference(arr)
  arr.difference(arr.uniq).uniq
end

Benchmark

def more_than_once(arr)
  counts = Hash.new { |hash, key| hash[key] = 0 }
  arr.each do |item|
    counts[item] += 1
  end
  counts.select do |_, count|
    count > 1
  end.keys
end

require 'fruity'

items = 30_000_000
arr = items.times.map { rand 10_000_000 }

compare do 
  Pascal     { more_than_once(arr) }
  Set        { multi_set(arr) }
  Difference { multi_difference(arr) }
end

Running each test once. Test will take about 4 minutes.
Pascal is faster than Set by 19.999999999999996% ± 10.0%
Set is faster than Difference by 30.000000000000004% ± 10.0%

Конечно, difference, если часть ядра Ruby будет закодирована на C и оптимизирована.