0

私の現在のスクリプト：

old_ids = []
File.open("missing.txt","w") do |result|
  File.open('query_result.csv', "r") do |old_copy| 
    old_copy.each_line do |line|
      old_ids << line.chomp.to_i #add exisiting ids to array
    end
  end

  File.open('item_info', "r") do |new_copy|
    new_copy.each_line do |line|
      if !old_ids.include? line.split("\t")[0].chomp.to_i #find all ids in new file that do not exist in old file and add them to missing.txt
         result.puts line.split("\t")[0].chomp.to_i
         puts "Adding #{line.split("\t")[0].chomp.to_i}"
          end
        end
      end
    end

これをより効率的にリファクタリングするにはどうすればよいでしょうか。私が解析したファイルには約 260 万件のレコードが含まれているため、書かれているように、実行には非常に長い時間がかかります。

4

3 に答える 3

2

最も低いハンギングフルーツ? andの使用をArrayandArray#includeに置き換えます。HashHash#key?

old_ids = {}
File.open("missing.txt","w") do |result|
  File.foreach('query_result.csv') do |line|
    id = line.chomp.to_i
    old_ids[id] = id
  end

  File.foreach('item_info') do |line|
    id = line.split("\t")[0].chomp.to_i
    unless old_ids.key?(id)
      result.puts id
      puts "Adding #{id}"
    end
  end
end

理由は単純です。Array#include?与えられた値を探すたびに配列全体をスキャンし、全体として O(n 2 ) の複雑さを与えます。Hash#key?一方、 は、指定された値のハッシュを計算し、ルックアップを実行して、指定されたキーがハッシュ テーブルに存在するかどうかを確認します。償却された時間の複雑さは O(n) に近づきます。

2 つの間の単純なテスト ケース (2 つのファイル間の共通行を見つける) は、次の結果をもたらします。

$ time ruby include.rb
real    2m51.409s
user    2m51.246s
sys     0m0.138s

対

$ time ruby key.rb
real    0m0.092s
user    0m0.082s
sys     0m0.009s

これは、それぞれ 2 16行の 2 つのファイルです。10,000 行でincludeも 5 秒key?かかりますが、29 ミリ秒かかります。

200万行key?で4秒以下。Array#include?実装が完了するのを待つことはできないと思います。

于 2013-03-07T09:10:59.937 に答える
1

追加の ID を検出したいので、最適なソリューションからそれほど遠くありません。古い ID を配列に入れるのではなく、セットを作成することで検索を高速化できます。それはより速いです。

old_ids = Set.new
File.open("missing.txt","w") do |result|
  File.open('query_result.csv', "r") do |old_copy| 
    old_copy.each_line do |line|
      old_ids.add(line.chomp.to_i) #add exisiting ids to Set
    end
  end

  File.open('item_info', "r") do |new_copy|
    new_copy.each_line do |line|
      if !old_ids.include? line.split("\t")[0].chomp.to_i #test if the id exists in the Set old_ids
         result.puts line.split("\t")[0].chomp.to_i
         puts "Adding #{line.split("\t")[0].chomp.to_i}"
        end
      end
    end
  end
end

ファイルの例がないとテストできません。コード (old_wmt_ids) に 1 つのエラーがありました。

于 2013-03-07T09:05:52.427 に答える
0

Diffyを見てください。これは、ファイル間の差分を計算するためのクールな gem です。

于 2013-03-07T09:09:51.570 に答える