2

给定 n 个 csv 文件，它们的大小加起来为 100 GB，我需要根据以下规则和条件删除重复的行：

  • csv 文件编号为 1.csv 到 n.csv，每个文件大小约为 50MB。
  • 第一列是一个字符串键，如果它们的第一列相同，则认为 2 行是重复的。
  • 我想通过将副本保留在以后的文件中来删除副本（2.csv 被认为晚于 1.csv）

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

  • 将所有文件合并为一个大文件

    cat *.csv > one.csv

  • 对csv进行排序

    sort one.csv >one_sorted.csv

  • 目前不知道如何消除重复。uniq有一个跳过前 N 个字段的 -f 标志，但在我的情况下，我想跳过除前 1 个字段之外的所有字段。

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

4

4 回答 4

2

这是一种使用方法GNU awk：

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

解释：读取一个按数字排序的文件，我们将每个文件的第一列添加到一个关联数组，其值为整行。这样，保留的副本就是最新文件中出现的副本。完成后，循环遍历数组的键并打印出值。确实提供了通过和函数的GNU awk排序能力，但是将输出传递给使事情更容易阅读，并且可能更快更有效。asort()asorti()sort

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

awk -F, '{ array[$1]=$0 } END { for (i in array) print array[i] | "sort -nk 1" }' $(ls -v *.csv)
于 2012-10-15T03:28:27.983 回答
1

如果你能把这些行保留在内存中

如果足够多的数据可以放入内存，那么steve的awk解决方案非常简洁，无论您是通过内部管道写入命令，还是简单地将未修饰的输出通过管道传输到shell 级别。sortawkawksort

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

如果密钥适合内存

如果您无法在内存中容纳足够多的数据，那么前面的任务就会困难得多，并且至少需要对文件进行两次扫描。我们需要假设，pro tem，您至少可以将每个键放在内存中，并计算该键出现的次数。

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

（这假设您可以存储键和计数两次；另一种方法是icount（仅）在两次扫描中使用，在扫描 1 中递增，在扫描 2 中递减，当计数减为零时打印值。）

我可能会为此使用 Perl 而awk不是awk.

连钥匙都不配？

如果您甚至无法将键及其计数放入内存中怎么办？那么您将面临一些严重的问题，尤其是因为脚本语言可能无法像您希望的那样干净利落地向您报告内存不足的情况。在证明有必要之前，我不会尝试过这座桥。如果有必要，我们需要一些关于文件集的统计数据来了解可能的情况：

  • 记录的平均长度。
  • 不同键的数量。
  • 对于 N = 1, 2, ... max中的每一个，具有 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' 循环并显式执行所有读取（您可以将 BEGIN 替换为 END 并获得相同的结果）。该逻辑在许多方面都基于 Perl 逻辑。awk在带有 BSD和 GNU的 Mac OS X 10.7.5 上测试awk。有趣的是，GNUawk坚持在closeBSDawk没有的调用中使用括号。在第close()一个循环中调用是必要的，以使第二个循环完全工作。第二个循环中的close()调用是为了保持对称和整洁——但当您在一次运行中处理几百个文件时，它们也可能是相关的。

于 2012-10-15T05:10:11.000 回答
0

我的回答是基于史蒂夫的

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

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

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

注意：如果您在同一个文件中有重复项（即，如果您在同一个文件中有同一个键的多个实例），这将不起作用

于 2012-10-15T05:03:17.290 回答
0

关于您的排序计划，对单个文件进行排序然后合并它们可能更实际，而不是连接然后排序。使用该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。

于 2012-10-15T05:56:55.743 回答