perl - 打印 10GB 文件的唯一行

Question

我有一个包含 2 亿行的 10GB 文件。我需要获取此文件的唯一行。

我的代码：

 while(<>) {
     chomp;
     $tmp{$_}=1;
 }
 #print...

我只有2GB内存。我怎么解决这个问题？

score 5 · Accepted Answer

正如我对大卫的回答所评论的那样，数据库是要走的路，但一个不错的可能是DBM::Deep因为它是纯 Perl 并且易于安装和使用；它本质上是一个绑定到文件的 Perl 哈希。

use DBM::Deep;
tie my %lines, 'DBM::Deep', 'data.db';

while(<>) {
    chomp;
    $lines{$_}=1;
}

这基本上是您已经拥有的，但哈希现在是一个与文件（此处为 data.db）相关联的数据库，而不是保存在内存中。

score 5 · Accepted Answer

在大多数情况下，您可以将该行作为键存储在哈希中。但是，当你变得这么大时，这真的不是很有效。在这种情况下，您最好使用数据库。

要尝试的一件事是曾经包含在 Unix (BDB) 中的伯克利数据库。现在，它显然归甲骨文所有。

Perl 可以使用BerkeleyDB模块与 BDB 数据库通信。事实上，您甚至可以将 Perl 哈希绑定到 BDB 数据库。完成此操作后，您可以使用普通 Perl 哈希来访问和修改数据库。

BDB 非常健壮。比特币使用它，SpamAssassin 也使用它，因此它很可能可以处理您必须创建的数据库类型以查找重复行。如果您已经安装了 DBD，那么编写一个程序来处理您的任务应该不会花那么长时间。如果它不起作用，你就不会在这上面浪费太多时间。

我能想到的唯一另一件事是使用 SQL 数据库，它会更慢且更复杂。

附录

可能是我想多了……

我决定尝试一个简单的哈希。这是我的程序：

#! /usr/bin/env perl
use strict;
use warnings;
use feature qw(say);
use autodie;

use constant DIR => "/usr/share/dict";

use constant WORD_LIST => qw(words web2a propernames connectives);

my %word_hash;
for my $count (1..100) {
    for my $file (WORD_LIST) {
        open my $file_fh, "<", DIR . "/$file";
        while (my $word = <$file_fh>) {
            chomp $word;
            $word_hash{"$file-$word-$count"} = $word;
        }
    }
}

读入的文件总共包含大约 313,000 行。我这样做了 100 次以获得包含 31,300,000 个键的散列。它几乎是低效的。每把钥匙都是独一无二的。内存量将是巨大的。然而...

有效。尽管该程序效率极低，但运行大约需要 10 分钟，并且最大容量约为 6 GB。但是，其中大部分都在虚拟内存中。奇怪的是，即使它正在运行、吞噬内存并占用 98% 的 CPU，我的系统并没有真正减慢那么多。我想问题真的是你期待什么样的表现？如果运行大约 10 分钟对您来说不是什么大问题，并且您不希望经常使用此程序，那么可能会为了简单起见并使用简单的哈希。

我现在正在从 Oracle 下载 DBD，对其进行编译和安装。我将使用 DBD 尝试相同的程序，看看会发生什么。

使用 BDB 数据库

完成这项工作后，我想如果你安装了 MySQL，使用 Perl DBI 会更容易。我不得不：

从 Oracle 下载 Berkeley DB，您需要一个 Oracle 帐户。我不记得我的密码，并告诉它给我发电子邮件。一直没收到邮件。我花了 10 分钟试图记住我的电子邮件地址。
下载后，必须对其进行编译。找到了为 Mac 编译的方向，看起来很简单。
运行 CPAN 崩溃。最终发现 CPAN 正在寻找/usr/local/BerkeleyDB并将其安装为/usr/local/BerkeleyDB.5.3. 创建链接解决了这个问题。

总而言之，安装 BerkeleyDB 大约需要 1/2 小时。安装后，修改我的程序非常简单：

#! /usr/bin/env perl
use strict;
use warnings;
use feature qw(say);
use autodie;

use BerkeleyDB;

use constant {
    DIR       => "/usr/share/dict",
    BDB_FILE  => "bdb_file",
};

use constant WORD_LIST => qw(words web2a propernames connectives);

unlink BDB_FILE if -f BDB_FILE;

our %word_hash;
tie %word_hash, "BerkeleyDB::Hash",
    -Filename => BDB_FILE,
    -Flags    => DB_CREATE
        or die qq(Cannot create DBD_Database file ") . BDB_FILE . qq("\n);

for my $count (1..10) {
    for my $file (WORD_LIST) {
        open my $file_fh, "<", DIR . "/$file";
        while (my $word = <$file_fh>) {
            chomp $word;
            $word_hash{"$file-$word-$count"} = $word;
        }
    }
}

我所要做的就是添加几行。

运行该程序令人失望。它不是更快，而是慢得多。它花了 2 多分钟，而使用纯哈希只需要 13 秒。

但是，它使用的内存要少得多。虽然旧程序吞噬了千兆字节，但 BDB 版本几乎不使用兆字节。相反，它创建了一个 20MB 的数据库文件。

但是，在虚拟机和廉价内存的时代，它有什么成就吗？在虚拟内存和良好内存处理之前的过去，如果程序使用了所有内存（内存以兆字节而不是千兆字节为单位），它会导致计算机崩溃。现在，如果您的程序需要比可用内存更多的内存，则只需为其提供虚拟内存。

所以，最后，使用伯克利数据库并不是一个好的解决方案。我在编程时间中节省的任何东西tie都浪费在了安装过程中。而且，它很慢。

使用 BDB 只需使用 DBD 文件而不是内存。现代操作系统也会这样做，而且速度更快。当操作系统会为您处理它时，为什么要这样做？

使用数据库的唯一原因是您的系统确实没有所需的资源。2 亿行是一个大文件，但现代操作系统可能会接受它。如果您的系统确实没有资源，请在另一个系统上使用 SQL 数据库，而不是 DBD 数据库。

score 5 · Accepted Answer

如果您不关心保留顺序，我敢打赌以下解决方案比以前发布的解决方案（例如 DBM::Deep）更快：

sort -u file

score 4 · Accepted Answer

您可能会考虑为每一行计算一个哈希码，并跟踪（哈希、位置）映射。为此，您不需要复杂的散列函数（甚至是大散列）；事实上，如果主要关注的是内存使用，“更小”比“更独特”要好。即使是 CRC，或总结字符的代码，也可以。关键不是在这个阶段保证唯一性——只是将候选匹配从 2 亿个缩小到几十个。

对于每一行，计算哈希值并查看是否已有映射。如果你这样做了，那么对于映射到该哈希的每个位置，读取该位置的行并查看这些行是否匹配。如果他们中的任何一个这样做，请跳过该行。如果没有，或者您没有该哈希的任何映射，请记住 (hash, position) 然后打印该行。

请注意，我说的是“位置”，而不是“行号”。为了在不到一年的时间内完成这项工作，您几乎可以肯定必须能够找到线路的权利，而不是找到线路#1392499 的方式。

score 3 · Accepted Answer

如果您不关心时间/IO 限制，也不关心磁盘限制（例如，您还有 10 GB 空间），您可以执行以下愚蠢算法：

1）读取文件（听起来它有 50 个字符行）。扫描时，记住最长的行长度$L。

2) 分析前 3 个字符（如果您知道 char #1 是相同的 - 比如说"["- 分析位置 N 中可能有更多不同字符的 3 个字符）。

3) 对于每个包含 3 个字符 $XYZ 的行，将该行附加到文件 3char.$XYZ 中，并将该文件中的行数记录在一个散列中。

4）当您的整个文件以这种方式拆分时，您应该有一大堆（如果文件仅是 AZ，则为 26^3）较小的文件，并且最多 4 个文件，每个文件 >2GB。

5) 将原始文件移动到“已处理”目录中。

6）对于每个大文件（> 2GB），选择接下来的3个字符位置，并重复步骤#1-#5，新文件为6char.$XYZABC

7) 起泡、冲洗、重复。您最终将获得以下两个选项之一：

8a）一堆较小的文件，每个文件都在 2GB 以下，所有这些文件都具有相互不同的字符串，并且每个（由于其大小）都可以通过您问题中的标准“存储到哈希”解决方案单独处理。

8b）或者，大多数文件都较小，但是，$L在重复步骤 7 处理 >2GB 的文件时，您已经耗尽了所有字符，并且您仍然有 1-4 个大文件。你猜怎么着——因为那些最多 4 个大文件在位置 1..$L 的文件中具有相同的字符，因此它们也可以在您的问题中使用“存储到哈希”方法进行处理，因为它们不会尽管它们的大小，但包含多个不同的行！

请注意，在最坏的情况下，这可能需要10GB * L / 3磁盘空间，但如果您将步骤#5 从“移动”更改为“删除”，则只需要 20GB 磁盘空间。

瞧。完毕。

作为一种替代方法，考虑散列你的行。我不是散列专家，但您应该能够将一行压缩为 <5 倍行大小恕我直言的散列。

如果您想对此有所了解，您将在第一遍对字符序列进行频率分析，然后以这种方式进行压缩/编码。

score 1 · Accepted Answer

如果你有更多的处理器并且至少有 15GB 的可用空间并且你的存储速度足够快，你可以试试这个。这将并行处理它。

split --lines=100000 -d 4 -d input.file
find . -name "x*" -print|xargs -n 1 -P10 -I SPLITTED_FILE sort -u SPLITTED_FILE>unique.SPLITTED_FILE
cat unique.*>output.file
rm unique.* x*

score 0 · Accepted Answer

您可以将文件分成 10 个 1 GB 的文件，然后一次读取一个文件，对该文件中的行进行排序，并在排序后将其写回。打开所有 10 个文件并将它们合并回一个文件（确保以正确的顺序合并它们）。打开输出文件以保存唯一行。然后一次一行地读取合并文件，保留最后一行进行比较。如果最后一行和当前行不匹配，则写出最后一行，并将当前行保存为最后一行进行比较。否则从合并文件中获取下一行。这将为您提供一个包含所有独特行的文件。

执行此操作可能需要一段时间，但如果您的内存有限，那么将文件分解并处理其中的一部分将起作用。

写出文件时可能会进行比较，但这会有点复杂。

score 0 · Accepted Answer

0

为什么要为此使用 perl？posix外壳：

sort | uniq

完了，我们去喝啤酒吧。

于 2012-04-05T04:50:14.867 回答

perl - 打印 10GB 文件的唯一行

8 回答 8

附录

使用 BDB 数据库

Related

Reference