Ruby: Comparant deux tableaux de hachages

Question

Je suis définitivement un débutant à ruby ​​(et en utilisant 1.9.1), donc toute aide est appréciée. Tout ce que j'ai appris sur Ruby a été d'utiliser google. J'essaie de comparer deux tableaux de hachages et en raison des tailles, ça prend beaucoup de temps et flirte avec le manque de mémoire. Toute aide serait appréciée.

J'ai une classe (ParseCSV) avec plusieurs méthodes (initialiser, ouvrir, comparer, enlever, sortir). La façon dont je l'ai travail est en ce moment comme suit (et cela ne passe les tests que j'ai écrit, tout en utilisant un ensemble de données beaucoup plus faible):

file1 = ParseCSV.new(“some_file”) 
file2 = ParseCSV.new(“some_other_file”) 

file1.open #this reads the file contents into an Array of Hash’s through the CSV library 
file1.strip #This is just removing extra hash’s from each array index. So normally there are fifty hash’s in each array index, this is just done to help reduce memory consumption. 

file2.open 
file2.compare(“file1.storage”) #@storage is The array of hash’s from the open method 

file2.output 

Maintenant que je suis aux prises avec est le comparer méthode. Travailler sur des ensembles de données plus petits n'est pas un gros problème et fonctionne assez vite. Cependant, dans ce cas, je compare environ 400 000 enregistrements (tous lus dans le tableau des hachages) contre un qui a environ 450 000 enregistrements. J'essaie d'accélérer ça. Je ne peux pas non plus exécuter la méthode strip sur file2. Voici comment je le fais maintenant:

def compare(x) 
    #obviously just a verbose message 
    puts "Comparing and leaving behind non matching entries" 

    x.each do |row| 
     #@storage is the array of hashes 
     @storage.each_index do |y|  
      if row[@opts[:field]] == @storage[y][@opts[:field]] 
       @storage.delete_at(y) 
      end 
     end 
    end 
end 

J'espère que cela a du sens. Je sais que le processus sera lent, car il faudra parcourir 400 000 lignes 440 000 fois chacune. Mais avez-vous d'autres idées pour l'accélérer et éventuellement réduire la consommation de mémoire?

Answer 1

Oui, ce sera O (n) au carré. Méchant.

Un meilleur pari serait d'utiliser la classe Set intégrée.

code ressemblerait à quelque chose comme:

require 'set' 

file1_content = load_file_content_into_array_here("some_file") 
file2_content = load_file_content_into_array_here("some_other_file") 

file1_set = Set[file1_content] 

unique_elements = file1_set - file2_content 

Cela suppose que les fichiers eux-mêmes ont un contenu unique. Devrait fonctionner dans le cas générique, mais peut avoir des bizarreries en fonction de ce que vos données ressemblent et comment vous l'analyser, mais aussi longtemps que les lignes peuvent être comparées avec == il devrait vous aider. Utiliser un ensemble sera BEAUCOUP plus rapide que faire une boucle imbriquée pour itérer sur le contenu du fichier.

(et oui, j'ai effectivement fait cela pour traiter les fichiers avec ~ 2 millions de lignes, donc il devrait être en mesure de gérer votre cas - éventuellement.Si vous faites de lourdes données de munging, Ruby ne peut pas être le meilleur choix de l'outil si)

Answer 2

Voici un script comparant deux façons de le faire: Votre original compare() et un new_compare(). Le paramètre new_compare utilise davantage les méthodes Enumerable intégrées. Comme ils sont implémentés en C, ils seront plus rapides.

J'ai créé une constante appelée Test :: SIZE pour tester les benchmarks avec différentes tailles de hachage. Résultats en bas. La différence est énorme.

require 'benchmark' 

class Test 
    SIZE = 20000 
    attr_accessor :storage 
    def initialize 
    file1 = [] 
    SIZE.times { |x| file1 << { :field => x, :foo => x } } 
    @storage = file1 
    @opts = {} 
    @opts[:field] = :field 
    end 

    def compare(x) 
    x.each do |row| 
     @storage.each_index do |y| 
     if row[@opts[:field]] == @storage[y][@opts[:field]] 
      @storage.delete_at(y) 
     end 
     end 
    end 
    end 

    def new_compare(other) 
    other_keys = other.map { |x| x[@opts[:field]] } 
    @storage.reject! { |s| other_keys.include? s[@opts[:field]] } 
    end 

end 

storage2 = [] 
# We'll make 10 of them match 
10.times { |x| storage2 << { :field => x, :foo => x } } 
# And the rest wont 
(Test::SIZE-10).times { |x| storage2 << { :field => x+100000000, :foo => x} } 

Benchmark.bm do |b| 
    b.report("original compare") do 
    t1 = Test.new 
    t1.compare(storage2) 
    end 
end 

Benchmark.bm do |b| 
    b.report("new compare") do 
    t1 = Test.new 
    t1.new_compare(storage2) 
    end 
end 

Résultats:

Test::SIZE = 500 
     user  system  total  real 
original compare 0.280000 0.000000 0.280000 ( 0.285366) 
     user  system  total  real 
new compare 0.020000 0.000000 0.020000 ( 0.020458) 

Test::SIZE = 1000 
    user  system  total  real 
original compare 28.140000 0.110000 28.250000 (28.618907) 
     user  system  total  real 
new compare 1.930000 0.010000 1.940000 ( 1.956868) 

Test::SIZE = 5000 
ruby test.rb 
     user  system  total  real 
original compare113.100000 0.440000 113.540000 (115.041267) 
     user  system  total  real 
new compare 7.680000 0.020000 7.700000 ( 7.739120) 

Test::SIZE = 10000 
     user  system  total  real 
original compare453.320000 1.760000 455.080000 (460.549246) 
     user  system  total  real 
new compare 30.840000 0.110000 30.950000 (31.226218)