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

最低悬的果实？Array用and替换你对andArray#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)。

两者之间的简单测试用例（查找两个文件之间的公共行）产生：

$ 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行。在 10,000 行时，include仍然需要 5 秒，而key?全部需要 29 毫秒。

200 万行，key?耗时不到 4 秒。我认为我不能等待Array#include?实施完成。

于 2013-03-07T09:10:59.937 回答
1

当您想要检测额外的 id 时，您离最佳解决方案并不远。您可以通过构建 Set 来加快查找速度，而不是将旧的 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) 中有一个错误。

于 2013-03-07T09:05:52.427 回答
0

看看Diffy，这是一个很酷的用于计算文件之间差异的 gem。

于 2013-03-07T09:09:51.570 回答