从 CSV 中删除重复项——性能问题

Question

我有一个 CSV 文件，可能如下所示：

foo,bar,glib
"a","1","A"
"b","1","B"
"a","2","C"
"b","1","D"

我正在遍历该 CSV 文件，并希望删除 foo 和 bar 相同的所有重复行，即我生成的文件应如下所示：

foo,bar,glib
"a","1","A"
"b","1","B"
"a","2","C"

我就是这样做的：

require "csv"

File.open("input.csv") do |infile|
  reader = CSV.new(infile, header=true)
  File.open("output.csv", "w") do |outfile|
    printed_tuples = Array(Tuple(String, String)).new
    CSV.build(outfile) do |writer|
      while reader.next
        next if printed_tuples.includes?({reader.row["foo"], reader.row["bar"]})
        printed_tuples << {reader.row["foo"], reader.row["bar"]}
        writer.row reader.row.to_a
      end
    end
  end
end

真正的 CSV 文件要大得多（386280 行和 17 列），而且速度太慢以至于几乎无法使用。

具有讽刺意味的是，我正在重写 python 脚本，因为我曾希望获得更好的性能，但现在 python 版本要快得多。

有人对如何加快速度有任何指示吗？

Answer 1

关键操作正在搜索现有值。 Array#includes? 在这种情况下效率很低：它需要遍历所有以前的行（对于重复行，它不是全部，但通常是一半）。对每一行执行此操作，即 O(N²).

您需要一种可以更快搜索的不同数据结构。 Crystal 有一个 Set 类型，由散列 table.

支持

对于这个问题可能有更好的数据结构和算法，但是 Set 在 Crystal 的标准库中可用并且应该已经有了很大的改进。

从 CSV 中删除重复项——性能问题

Removing duplicates from CSV -- performance problems

performance

crystal-lang