从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"

这就是我的做法：

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

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

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

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

Answer 1

关键操作是搜索现有值。Array#includes?在这种情况下是非常低效的：它需要遍历所有先前的行（对于重复的行，不是全部，但通常是其中的一半）。每一行都这样做O(N²)。

您需要可以快速搜索的其他数据结构。Crystal具有Set由哈希表支持的类型。

可能甚至有更好的数据结构和算法可以解决此问题，但SetCrystal的标准库中提供了该数据结构，应该已经做了很多改进。