algorithm - 超大字符串子集的比较

Question

每天有一个文件，从 2000000 到 4000000 个字符串，其中包含一行一行的唯一 15 符号数字，如下所示:

850025000010145
401115000010152
400025000010166
770025555010152
512498004158752

从今年年初开始，您相应地拥有一定数量的此类文件。所以我必须将今天文件的每一行与年初的所有先前文件进行比较，并仅返回所有已检查文件中以前从未遇到过的数字。

我应该使用哪种语言和算法？如何实现？

Answer 1

除了简单的脚本(即 bash、Windows 批处理、Powershell 等)之外，您无需编写任何代码即可执行此操作。有一些标准工具可以快速处理这类事情。

首先，您有一些包含 200 万到 400 万个数字的文件。处理所有这些文件很困难，因此您要做的第一件事就是创建一个经过排序的组合文件。最简单的方法是将所有文件连接成一个文件，对其进行排序，然后删除重复项。例如，使用 GNU/Linux cat 和 sort 命令:

cat file1 file2 file3 file4 > combined
sort -u combined > combined_sort

(-u 删除重复项)

该方法的问题是您最终需要对一个非常大的文件进行排序。图 400 万行 15 个字符，每行加上换行符，以及将近 100 天的文件，您正在处理 7 GB 的文件。全年的数据量为 25 GB。这需要很长时间。

因此，改为对每个单独的文件进行排序，然后合并它们:

sort -u file1 >file1_sort
sort -u file2 >file2_sort
...
sort -m -u file1 file2 file3 > combined_sorted

-m 开关合并已经排序的文件。

现在您所拥有的是到目前为止您看到的所有标识符的排序列表。您想将今天的文件与那个文件进行比较。首先，对今天的文件进行排序:

sort -u today >today_sort

现在，您可以比较文件并只输出与今天文件不同的文件:

comm -2 -3 today_sort combined_sort

-2 表示抑制仅出现在第二个文件中的行，-3 表示抑制两个文件共有的行。因此，您将得到的是 today_sort 中不存在于 combined_sort 中的行。

现在，如果您打算每天都这样做，那么您需要获取 comm 命令的输出并将其与 combined_sort 合并，这样您就可以明天使用那个组合文件。这样您就不必每天都重建 combined_sort 文件。所以:

comm -2 -3 today_sort combined_sort > new_values

然后:

sort -m combined_sort new_values > combined_sort_new

你可能想用日期命名文件，所以你有 combined_sort_20140401 和 combined_sort_20140402 等

因此，如果您从年初开始并希望每天都这样做，您的脚本将类似于:

sort -u $todays_file > todays_sorted_file
comm -2 -3 todays_sorted_file $old_combined_sort > todays_uniques
sort -m $old_combined_sort todays_sorted_file > $new_combined_sort

$todays_file、$old_combined_sort 和 $new_combined_sort 是您在命令行上传递的参数。所以，如果脚本被称为“daily”:

daily todays_file.txt all_values_20140101 all_values_20140102