我有一个10GB的文件,有2亿行.我需要获得此文件的唯一行.
我的代码:
while(<>) {
chomp;
$tmp{$_}=1;
}
#print...
我只有2GB的内存.我怎么解决这个问题？
在大多数情况下,您可以将该行存储为哈希中的键.但是,当你得到这么大的时候,这真的不是很有效率.在这种情况下,您最好使用数据库.
要尝试的一件事是Berkeley数据库,它包含在Unix(BDB)中.现在,它显然归Oracle所有.
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千兆字节.但是,大部分都是在虚拟内存中.奇怪的是,即使它正在运行,吞噬内存,占用98%的CPU,我的系统并没有真正放慢这么多.我想这个问题真的是你期待什么类型的表现？如果运行大约10分钟对你来说并不是一个问题,并且你不希望经常使用这个程序,那么可能只是为了简单并使用简单的哈希.
我现在正在从Oracle下载DBD,编译它并安装它.我将使用DBD尝试相同的程序,看看会发生什么.
完成工作后,我认为如果安装了MySQL,使用Perl DBI会更容易.我不得不:
/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的数据库文件.
但是,在虚拟机和廉价内存的这些日子里,它做到了什么？在虚拟内存和良好内存处理之前的过去,如果程序使用了所有内存(并且内存以兆字节而不是千兆字节为单位),则程序会使计算机崩溃.现在,如果您的程序需要的内存多于可用内存,那么它只会被赋予虚拟内存.
因此,最后,使用Berkeley数据库并不是一个好的解决方案.无论我通过使用节省了多少编程时间tie都浪费在安装过程中.而且,它很慢.
使用BDB只是使用DBD文件而不是内存.现代操作系统也会这样做,而且速度更快.为什么操作系统会为您处理它？
使用数据库的唯一原因是您的系统确实没有所需的资源.2亿行是一个大文件,但现代操作系统可能会好起来的.如果您的系统确实没有资源,请在另一个系统上使用SQL数据库,而不是DBD数据库.
正如我对David的回答所评论的那样,数据库是可行的方法,但是一个很好的数据库可能是DBM::Deep因为它的纯Perl并且易于安装和使用; 它本质上是一个绑定到文件的Perl哈希.
use DBM::Deep;
tie my %lines, 'DBM::Deep', 'data.db';
while(<>) {
chomp;
$lines{$_}=1;
}
这基本上就是你已经拥有的,但哈希现在是一个绑定到文件的数据库(这里是data.db),而不是保存在内存中.
如果您不关心保留订单,我敢打赌以下内容比以前发布的解决方案更快(例如DBM :: Deep):
sort -u file
如果您不关心时间/IO 限制，也不关心磁盘限制（例如您还有 10 GB 空间），您可以执行以下愚蠢的算法：
1）读取文件（听起来有50个字符行）。扫描时，记住最长的线长度$L。
2) 分析前 3 个字符（如果您知道 char #1 是相同的 - 比如说"["- 分析位置 N 中可能有更多不同字符的 3 个字符）。
3) 对于每行包含 3 个字符 $XYZ 的行，将该行附加到文件 3char.$XYZ 中，并在哈希中保留该文件中的行数。
4) 当你的整个文件以这种方式分割时，你应该有一大堆（如果文件仅是 AZ，则 26^3）较小的文件，并且最多 4 个每个 >2GB 的文件。
5) 将原始文件移动到“Processed”目录中。
6) 对于每个大文件 (>2GB)，选择接下来的 3 个字符位置，并重复步骤 #1-#5，新文件为 6char.$XYZABC
7）起泡沫，冲洗，重复。最终您将得到以下两个选项之一：
8a）一堆较小的文件，每个文件都在 2GB 以下，所有这些文件都有相互不同的字符串，并且每个文件（由于其大小）都可以通过问题中的标准“存储到散列”解决方案单独处理。
8b) 或者，大多数文件都较小，但是，您$L在对 >2GB 文件重复步骤 7 时已耗尽所有字符，并且仍然有 1-4 个大文件。猜猜看 - 由于这些最多 4 个大文件在位置 1..$L 的文件中具有相同的字符，因此也可以使用问题中的“存储到散列”方法来处理它们，因为它们不会尽管其大小，但包含多个不同的线条！
请注意，这可能需要（在最坏的发行版中）10GB * L / 3磁盘空间，但如果将步骤 #5 从“移动”更改为“删除”，则仅需要 20GB 磁盘空间。
瞧。完毕。
作为一种替代方法，请考虑对您的行进行哈希处理。我不是散列专家，但您应该能够将一行压缩为 <5 倍行大小的散列（恕我直言）。
如果您想对此感兴趣，您将在第一次通过时对字符序列进行频率分析，然后以这种方式进行压缩/编码。