从许多csv文件中删除dup

给定.csv文件的大小加起来可达100 GB，我需要根据以下规则和条件删除重复的行：

csv文件编号为1.csv到n.csv，每个文件的大小约为50MB
第一列是字符串键，如果两行的第一列相同，则视为dup
我想通过将重复数据块保存在以后的文件中来删除重复数据块(2.csv被认为晚于1.csv)

我的算法如下，我想知道是否有更好的算法。

将所有文件合并为一个巨大的文件
```
cat *.csv > one.csv
```
对csv 进行排序
```
sort one.csv >one_sorted.csv
```
不知道在这一点上如何消除重复。uniq有一个-f标志，它跳过前N个字段，但在我的情况下，我想跳过除前1个字段之外的所有字段。

我需要帮助完成最后一步(消除排序文件中的重复数据)。还有更有效的算法吗？

以下是使用GNU awk:的一种方法

awk -F, '{ array[$1]=$0 } END { for (i in array) print array[i] }' $(ls -v *.csv)

说明：读取一个数字排序的文件glob，我们将每个文件的第一列添加到一个关联数组中，该数组的值为整行。通过这种方式，保留的副本就是最新文件中出现的副本。完成后，循环遍历数组的键并打印出值。GNU awk确实通过asort()和asorti()函数提供了排序功能，但将输出管道传输到sort会使内容更易于阅读，而且可能更快、更高效。

如果你需要对第一列进行数字排序，你可以这样做：

awk -F, '{ array[$1]=$0 } END { for (i in array) print array[i] | "sort -nk 1" }' $(ls -v *.csv)

如果可以将行保存在内存中

如果内存中能容纳足够的数据，那么steve的awk解决方案就相当简洁了，无论您是通过awk中的管道写入sort命令，还是简单地通过在shell级别将未修饰的awk的输出管道写入到sort。

如果您有100GiB的数据，可能有3%的重复，那么您需要能够在内存中存储100GiB数据。这是很多主要的记忆。64位系统可能使用虚拟内存来处理它，但运行速度可能相当慢。

如果钥匙适合记忆

如果你不能在内存中放入足够的数据，那么接下来的任务就要困难得多，需要至少对文件进行两次扫描。我们需要假设，暂时来说，你至少可以将每个键放入内存中，并计算出该键出现的次数。

扫描1：读取文件。
- 计算每个键在输入中出现的次数
- 在awk中，使用icount[$1]++
扫描2：重新读取文件。
- 计算每个键出现的次数；ocount[$1]++
- 如果是icount[$1] == ocount[$1]，则打印该行

(这假设您可以存储两次密钥和计数；另一种选择是在两次扫描中都使用icount(仅)，在扫描1中递增，在扫描2中递减，当计数减为零时打印值。)

我可能会使用Perl而不是awk，如果只是因为用Perl重读文件比用awk更容易的话。

连钥匙都装不下

如果你连钥匙和它们的计数都记不住了怎么办？然后您将面临一些严重的问题，尤其是因为脚本语言可能无法像您希望的那样干净地向您报告内存不足的情况。除非证明有必要，否则我不会试图跨过这座桥。如果有必要，我们需要一些关于文件集的统计数据，以了解可能的情况：

记录的平均长度
不同键的数目
N=1、2、…中每一个出现N次的不同键的数量最大
钥匙的长度
钥匙数量加上可装入存储器的计数

可能还有其他一些。。。所以，正如我所说，在证明有必要之前，我们不要试图穿过那座桥。

Perl解决方案

示例数据

$ cat x000.csv
abc,123,def
abd,124,deg
abe,125,deh
$ cat x001.csv
abc,223,xef
bbd,224,xeg
bbe,225,xeh
$ cat x002.csv
cbc,323,zef
cbd,324,zeg
bbe,325,zeh
$ perl fixdupcsv.pl x???.csv
abd,124,deg
abe,125,deh
abc,223,xef
bbd,224,xeg
cbc,323,zef
cbd,324,zeg
bbe,325,zeh
$

注意没有千兆字节规模的测试！

fixdupcsv.pl

这使用了"向上计数，向下计数"的技术。

#!/usr/bin/env perl
#
# Eliminate duplicate records from 100 GiB of CSV files based on key in column 1.
use strict;
use warnings;
# Scan 1 - count occurrences of each key
my %count;
my @ARGS = @ARGV;   # Preserve arguments for Scan 2
while (<>)
{
$_ =~ /^([^,]+)/;
$count{$1}++;
}
# Scan 2 - reread the files; count down occurrences of each key.
# Print when it reaches 0.
@ARGV = @ARGS;      # Reset arguments for Scan 2
while (<>)
{
$_ =~ /^([^,]+)/;
$count{$1}--;
print if $count{$1} == 0;
}

"while (<>)"表示法会破坏@ARGV(因此，在执行其他操作之前会复制到@ARGS)，但这也意味着，如果将@ARGV重置为原始值，它将再次运行文件。在Mac OS X 10.7.5上使用Perl 5.16.0和5.10.0进行了测试。

这是Perl；TMTOWTDI。您可以使用：

#!/usr/bin/env perl
#
# Eliminate duplicate records from 100 GiB of CSV files based on key in column 1.
use strict;
use warnings;
my %count;
sub counter
{
my($inc) = @_;
while (<>)
{
$_ =~ /^([^,]+)/;
$count{$1} += $inc;
print if $count{$1} == 0;
}
}
my @ARGS = @ARGV;   # Preserve arguments for Scan 2
counter(+1);
@ARGV = @ARGS;      # Reset arguments for Scan 2
counter(-1);

可能也有压缩循环主体的方法，但我发现其中的内容相当清晰，并且更喜欢清晰而不是极端简洁。

调用

您需要以正确的顺序向fixdupcsv.pl脚本提供文件名。由于文件编号从1.csv到大约2000.csv，因此不要按字母数字顺序列出它们，这一点很重要。其他答案建议ls -v *.csv使用GNUls扩展选项。如果有，那是最好的选择。

perl fixdupcsv.pl $(ls -v *.csv)

如果这不可用，那么你需要对名称进行数字排序：

perl fixdupcsv.pl $(ls *.csv | sort -t. -k1.1n)

Awk解决方案

awk -F, '
BEGIN   {
for (i = 1; i < ARGC; i++)
{
while ((getline < ARGV[i]) > 0)
count[$1]++;
close(ARGV[i]);
}
for (i = 1; i < ARGC; i++)
{
while ((getline < ARGV[i]) > 0)
{
count[$1]--;
if (count[$1] == 0) print;
}
close(ARGV[i]);
}
}'

这忽略了awk固有的"read"循环，并显式执行所有读取(您可以用END替换BEGIN，得到相同的结果)。该逻辑在许多方面都紧密地基于Perl逻辑。在Mac OS X 10.7.5上测试了BSDawk和GNUawk。有趣的是，GNUawk在对close的调用中坚持使用括号，而BSDawk没有。close()调用在第一个循环中是必要的，以使第二个循环工作。第二个循环中的close()调用是为了保持对称性和整洁性，但当您在一次运行中处理几百个文件时，它们也可能是相关的。

我的答案是基于steve的

awk -F, '!count[$1]++' $(ls -rv *.csv)

{print $0}隐含在awk语句中。

本质上，awk只打印$1包含该值的第一行。由于.csv文件是按相反的自然顺序列出的，这意味着对于具有相同值$1的所有行，只打印最新文件中的一行。

注意：如果您在同一文件中有重复项(即，如果您在相同文件中有相同密钥的多个实例)，则将不起作用。

关于您的排序计划，对单个文件进行排序，然后合并它们可能更实用，而不是连接然后排序。使用sort程序排序的复杂性可能是O(n log(n))。如果说每个50MB文件有200000行，而每个文件有2000行，那么n大约是4亿行，而n log(n) ~ 10^10则是。如果将R记录的F个文件分别处理，则排序成本为O(F*R*log(R))，合并成本为O(F*R*log(R))。这些成本足够高，单独排序不一定更快，但这个过程可以分解成方便的块，因此可以更容易地进行检查。这里有一个小规模的例子，假设逗号可以用作排序键的分隔符。(如图所示，包含逗号的以引号分隔的键字段将是排序的问题。)请注意，-s告诉sort进行稳定排序，使具有相同排序键的行按遇到的顺序排列。

for i in $(seq 1 8); do sort -t, -sk1,1 $i.csv > $i.tmp; done
sort -mt, -sk1,1 [1-8].tmp > 1-8.tmp

或者如果更加谨慎可能会保存一些中间结果：

sort -mt, -sk1,1 [1-4].tmp > 1-4.tmp
sort -mt, -sk1,1 [5-8].tmp > 5-8.tmp
cp 1-4.tmp 5-8.tmp /backup/storage
sort -mt, -sk1,1 1-4.tmp 5-8.tmp > 1-8.tmp

此外，在合并之后进行单独排序的一个优点是可以轻松地在多个处理器或系统之间划分工作负载。

在对所有文件进行排序并合并(例如，文件X)后，编写一个awk程序非常简单，该程序在BEGIN从X读取一行并将其放入变量L中。此后，每次从X读取行时，如果$0的第一个字段与L不匹配，它就会写出L并将L设置为$0。但如果$0与L匹配，则会将L设置为$0。在END，它写出L.

如果可以将行保存在内存中

如果钥匙适合记忆

连钥匙都装不下

Perl解决方案

fixdupcsv.pl

调用

Awk解决方案

相关内容

最新更新

热门标签：