cod*_*ter 23 linux bash perl awk grep
我有两个文件,file1.txt和file2.txt. file1.txt有大约14K线,file2.txt约有20亿. 每行file1.txt有一个字段f1,而file2.txt有3个字段,f1through f3,分隔符|.
我想找到的所有行file2.txt那里f1的file1.txt比赛f2中file2.txt(或上线的任何位置,如果我们不想花费额外的时间分割的数值file2.txt).
file1.txt(约14K行,未排序):
foo1
foo2
...
bar1
bar2
...
file2.txt(约20亿行,未排序):
date1|foo1|number1
date2|foo2|number2
...
date1|bar1|number1
date2|bar2|number2
...
预期产量:
date1|foo1|number1
date2|foo2|number2
...
date1|bar1|number1
date2|bar2|number2
...
这是我尝试过的,似乎需要几个小时才能运行:
fgrep -F -f file1.txt file2.txt > file.matched
我想知道是否有更好,更快的方法使用常见的Unix命令或小脚本执行此操作.
zdi*_*dim 18
Perl解决方案.[见下面的注释.]
对第一个文件使用哈希.当您逐行读取大文件时,通过正则表达式提取字段(捕获第一个图案||)或split(获取第二个单词)并打印它exists.它们的速度可能略有不同(时间).在defined不需要在正则表达式检查而split使用//(定义-或),该短路.
use warnings;
use strict;
# If 'prog smallfile bigfile' is the preferred use
die "Usage: $0 smallfile bigfile\n" if @ARGV != 2;
my ($smallfile, $bigfile) = @ARGV;
open my $fh, '<', $smallfile or die "Can't open $smallfile: $!";
my %word = map { chomp; $_ => 1 } <$fh>;
open $fh, '<', $bigfile or die "Can't open $bigfile: $!";
while (<$fh>)
{
exists $word{ (/\|([^|]+)/)[0] } && print;
# Or
#exists $word{ (split /\|/)[1] // '' } && print;
}
close $fh;
避免if分支和使用短路更快,但只是很少.在数十亿行上,这些调整加起来但又不过分.逐行读取小文件可能(或可能不是)稍快一点,而不是如上所述在列表上下文中,但这不应该是显而易见的.
更新 写入以STDOUT保存两个操作,我反复计时它比写入文件快一点.这种用法也与大多数UNIX工具一致,所以我改为写入STDOUT.接下来,exists不需要进行测试,丢弃它可以节省一个操作.但是,我一直用它来获得更好的运行时间,同时它也更好地传达了目的.我总是把它留在里面.感谢ikegami的评论.
注意通过下面的基准测试, 注释掉的版本比另一个快约50%.给出这些是因为它们不同,一个找到第一个匹配而另一个找到第二个字段.我保持这种方式作为一种更通用的选择,因为这个问题很模糊.
一些比较(基准)[更新为写入STDOUT,请参阅上面的"更新"]
HåkonHægland在答案中进行了广泛的分析,为大多数解决方案提供了一个时间表.这是另一个考虑因素,对上述两个解决方案进行基准测试,OP自己的答案,以及发布的答案fgrep,预计会很快并在问题和许多答案中使用.
我以下列方式构建测试数据.对于两个文件,大致如图所示的少数几行的长度用随机字构成,因此在第二个字段中匹配.然后我用数据样本填充这个"种子",使用不匹配的行,以便模拟OP引用的大小和匹配之间的比率:对于小文件中的14K行,大文件中有1.3M行,产生126K匹配.然后重复写入这些样本以构建完整数据文件作为OP,shuffle-ed每次使用List :: Util.
下面比较的所有运行产生106_120上述文件大小的匹配(diff-ed用于检查),因此匹配频率足够接近.它们通过使用调用完整程序进行基准测试my $res = timethese(60 ...).cmpthese($res)v5.16 的结果是
Rate regex cfor split fgrep
regex 1.05/s -- -23% -35% -44%
cfor 1.36/s 30% -- -16% -28%
split 1.62/s 54% 19% -- -14%
fgrep 1.89/s 80% 39% 17% --
优化的C程序排fgrep在首位的事实并不令人惊讶." 正则表达式 "落后于" 分裂 " 的滞后可能是由于启动引擎进行少量匹配的开销很多次.考虑到不断发展的正则表达式引擎优化,这可能会因Perl版本而异.我包括@codeforester的答案(" CFOR因为它自称是最快的,其')20%背后的非常相似的’滞后分裂 "可能是由于分散的小的低效率(见这个答案下面留言).†
这并没有什么不同,虽然硬件和软件以及数据细节之间确实存在差异.我在不同的Perls和机器上运行它,显着的区别是在某些情况下fgrep确实快了一个数量级.
OP的非常慢的经历fgrep令人惊讶.鉴于他们引用的运行时间比上面的要慢一些,我猜想有一个旧系统要"责备".
尽管这完全基于I/O,但是将它放在多个内核上会产生并发效益,而且我预计会有一个很好的加速,最多可达几个.
†唉,评论被删除了(？).总之:不需要使用的标量(成本),一个的if分公司,defined中,printf而不是print(慢!).这对20亿线的效率至关重要.
Håk*_*and 14
我试图对这里介绍的一些方法进行比较.
首先,我创建了一个Perl脚本来生成输入文件file1.txt和file2.txt.为了比较一些解决方案,我确保file1.txt只有单词才会出现在第二个字段中file2.txt.也是为了能够使用join@GeorgeVasiliou提出的解决方案,我排序file1.txt和file2.txt.目前,我仅基于75个随机单词生成输入文件(取自https://www.randomlists.com/random-words).file1.txt其余70个单词中使用的这75个单词中只有5 个被用来填补字段file2.txt.可能有必要大幅增加单词数以获得真实的结果(根据OP,原始file1.txt包含14000个单词).在下面的测试中,我使用了file2.txt1000000(100万)行.该脚本还生成regexp1.txt@BOC的grep解决方案所需的文件.
gen_input_files.pl:
#! /usr/bin/env perl
use feature qw(say);
use strict;
use warnings;
use Data::Printer;
use Getopt::Long;
GetOptions ("num_lines=i" => \my $nlines )
or die("Error in command line arguments\n");
# Generated random words from site: https://www.randomlists.com/random-words
my $word_filename = 'words.txt'; # 75 random words
my $num_match_words = 5;
my $num_file2_lines = $nlines || 1_000_000;
my $file2_words_per_line = 3;
my $file2_match_field_no = 2;
my $file1_filename = 'file1.txt';
my $file2_filename = 'file2.txt';
my $file1_regex_fn = 'regexp1.txt';
say "generating $num_file2_lines lines..";
my ( $words1, $words2 ) = get_words( $word_filename, $num_match_words );
write_file1( $file1_filename, $words2 );
write_file2(
$file2_filename, $words1, $words2, $num_file2_lines,
$file2_words_per_line, $file2_match_field_no
);
write_BOC_regexp_file( $file1_regex_fn, $words2 );
sub write_BOC_regexp_file {
my ( $fn, $words ) = @_;
open( my $fh, '>', $fn ) or die "Could not open file '$fn': $!";
print $fh '\\|' . (join "|", @$words) . '\\|';
close $fh;
}
sub write_file2 {
my ( $fn, $words1, $words2, $nlines, $words_per_line, $field_no ) = @_;
my $nwords1 = scalar @$words1;
my $nwords2 = scalar @$words2;
my @lines;
for (1..$nlines) {
my @words_line;
my $key;
for (1..$words_per_line) {
my $word;
if ( $_ != $field_no ) {
my $index = int (rand $nwords1);
$word = @{ $words1 }[$index];
}
else {
my $index = int (rand($nwords1 + $nwords2) );
if ( $index < $nwords2 ) {
$word = @{ $words2 }[$index];
}
else {
$word = @{ $words1 }[$index - $nwords2];
}
$key = $word;
}
push @words_line, $word;
}
push @lines, [$key, (join "|", @words_line)];
}
@lines = map { $_->[1] } sort { $a->[0] cmp $b->[0] } @lines;
open( my $fh, '>', $fn ) or die "Could not open file '$fn': $!";
print $fh (join "\n", @lines);
close $fh;
}
sub write_file1 {
my ( $fn, $words ) = @_;
open( my $fh, '>', $fn ) or die "Could not open file '$fn': $!";
print $fh (join "\n", sort @$words);
close $fh;
}
sub get_words {
my ( $fn, $N ) = @_;
open( my $fh, '<', $fn ) or die "Could not open file '$fn': $!";
my @words = map {chomp $_; $_} <$fh>;
close $fh;
my @words1 = @words[$N..$#words];
my @words2 = @words[0..($N - 1)];
return ( \@words1, \@words2 );
}
接下来,我创建了一个solutions包含所有测试用例的子文件夹:
$ tree solutions/
solutions/
??? BOC1
? ??? out.txt
? ??? run.sh
??? BOC2
? ??? out.txt
? ??? run.sh
??? codeforester
? ??? out.txt
? ??? run.pl
? ??? run.sh
[...]
这里的文件out.txt是每个解决方案的greps输出.脚本run.sh运行给定测试用例的解决方案.
BOC1 :@BOC提出的第一个解决方案
grep -E -f regexp1.txt file2.txt
BOC2 :@BOC建议的第二个解决方案:
LC_ALL=C grep -E -f regexp1.txt file2.txt
codeforester:@codeforester接受的Perl解决方案(参见来源)
codeforester_orig :@codeforested提供的原始解决方案:
fgrep -f file1.txt file2.txt
dawg:使用@dawg提出的字典和分割线的Python解决方案(参见源代码)
gregory1 :@gregory建议的使用Gnu Parallel的解决方案
parallel -k --pipepart -a file2.txt --block "$block_size" fgrep -F -f file1.txt
请参阅下面有关如何选择的说明$block_size.
hakon1:Perl解决方案由@HåkonHægland提供(参见来源).此解决方案需要在第一次运行代码时编译c扩展.它不需要重新编译时file1.txt或file2.txt变化.注意:在初始运行时用于编译c扩展的时间不包括在下面显示的运行时间中.
ikegami:解决方案使用组装的正则表达式并使用grep -P@ikegami给出的.注意:组装的regexp被写入一个单独的文件regexp_ikegami.txt,因此生成regexp的运行时不包含在下面的比较中.这是使用的代码:
regexp=$(< "regexp_ikegami.txt")
grep -P "$regexp" file2.txt
inian1 :@Inian使用的第一个解决方案 match()
awk 'FNR==NR{
hash[$1]; next
}
{
for (i in hash) if (match($0,i)) {print; break}
}' file1.txt FS='|' file2.txt
inian2 :@Inian使用的第二个解决方案 index()
awk 'FNR==NR{
hash[$1]; next
}
{
for (i in hash) if (index($0,i)) {print; break}
}' file1.txt FS='|' file2.txt
inian3:@Inian仅检查$2字段的第三个解决方案:
awk 'FNR==NR{
hash[$1]; next
}
$2 in hash' file1.txt FS='|' file2.txt
inian4:由@Inian(基本相同,第四soultion codeforester_orig用LC_ALL):
LC_ALL=C fgrep -f file1.txt file2.txt
inian5:由@Inian(同第五溶液inian1,但用LC_ALL):
LC_ALL=C awk 'FNR==NR{
hash[$1]; next
}
{
for (i in hash) if (match($0,i)) {print; break}
}' file1.txt FS='|' file2.txt
inian6:同inian3但是LC_ALL=C.感谢@GeorgeVasiliou的建议.
jjoao:由@JJoao提出的编译flex生成的C代码(参见源代码).注意:每次file1.txt更改时都必须重新编译exectuable .用于编译可执行文件的时间不包括在下面显示的运行时间中.
oliv:@oliv提供的Python脚本(参见源代码)
Vasiliou:join按照@GeorgeVasiliou的建议使用:
join --nocheck-order -11 -22 -t'|' -o 2.1 2.2 2.3 file1.txt file2.txt
Vasiliou2:同Vasiliou但是LC_ALL=C.
zdim:使用@zdim提供的Perl脚本(参见源代码).注意:这使用regexp搜索版本(而不是拆分线解决方案).
zdim2:zdim除了它使用split函数而不是regexp搜索字段之外file2.txt.
我用Gnu并行实验了一下(参见gregory1上面的解决方案)来确定我的CPU的最佳块大小.我有4个核心,目前似乎最佳选择是将文件(file2.txt)分成4个相同大小的块,并在4个处理器中的每一个上运行单个作业.这里可能需要更多测试.因此,对于第一个file2.txt20M的测试案例,我设置$block_size为5M(参见gregory1上面的解决方案),而对于下面给出的更真实的情况,其中file2.txt268M,使用$block_size了67M.
该解决方案BOC1,BOC2,codeforester_orig,inian1,inian4,inian5,和gregory1所有使用松散匹配.这意味着来自的词语file1.txt不必完全匹配在#2的字段中file2.txt.接受了线上任何地方的比赛.由于这种行为使得将它们与其他方法进行比较变得更加困难,因此还引入了一些修改过的方法.前两个方法调用BOC1B并BOC2B使用了修改过的regexp1.txt文件.原始regexp1.txt中的线条在表格\|foo1|foo2|...|fooN\|上与任何场边界处的单词匹配.修改后的文件regexp1b.txt仅使用表单将匹配锚定到字段#2 ^[^|]*\|foo1|foo2|...|fooN\|.
然后的改性方法的其余部分codeforester_origB,inian1B,inian4B,inian5B,和gregory1B使用修改file1.txt.修改后的文件不是每行一个文字,而是在表单上每行file1b.txt使用一个正则表达式:
^[^|]*\|word1\|
^[^|]*\|word2\|
^[^|]*\|word3\|
[...]
此外,fgrep -f被grep -E -f这些方法所取代.
这是用于运行所有测试的脚本.它使用Bash time命令记录每个脚本花费的时间.请注意,time命令返回三个不同的时代呼唤real,user和sys.首先我使用user+ sys,但是在使用Gnu并行命令时意识到这是不正确的,所以下面报告的时间现在是real返回的部分time.有关返回的不同时间的详细信息,请参阅此问题time.
第一次测试运行时file1.txt包含5行,并file2.txt包含1000000行.这是run_all.pl脚本的前52行,其余部分可在此处获得.
run_all.pl
#! /usr/bin/env perl
use feature qw(say);
use strict;
use warnings;
use Cwd;
use Getopt::Long;
use Data::Printer;
use FGB::Common;
use List::Util qw(max shuffle);
use Number::Bytes::Human qw(format_bytes);
use Sys::Info;
GetOptions (
"verbose" => \my $verbose,
"check" => \my $check,
"single-case=s" => \my $case,
"expected=i" => \my $expected_no_lines,
) or die("Error in command line arguments\n");
my $test_dir = 'solutions';
my $output_file = 'out.txt';
my $wc_expected = $expected_no_lines; # expected number of output lines
my $tests = get_test_names( $test_dir, $case );
my $file2_size = get_file2_size();
my $num_cpus = Sys::Info->new()->device( CPU => () )->count;
chdir $test_dir;
my $cmd = 'run.sh';
my @times;
for my $case (@$tests) {
my $savedir = getcwd();
chdir $case;
say "Running '$case'..";
my $arg = get_cmd_args( $case, $file2_size, $num_cpus );
my $output = `bash -c "{ time -p $cmd $arg; } 2>&1"`;
my ($user, $sys, $real ) = get_run_times( $output );
print_timings( $user, $sys, $real ) if $verbose;
check_output_is_ok( $output_file, $wc_expected, $verbose, $check );
print "\n" if $verbose;
push @times, $real;
#push @times, $user + $sys; # this is wrong when using Gnu parallel
chdir $savedir;
}
say "Done.\n";
print_summary( $tests, \@times );
以下是运行测试的输出:
$ run_all.pl --verbose
Running 'inian3'..
..finished in 0.45 seconds ( user: 0.44, sys: 0.00 )
..no of output lines: 66711
Running 'inian2'..
..finished in 0.73 seconds ( user: 0.73, sys: 0.00 )
..no of output lines: 66711
Running 'Vasiliou'..
..finished in 0.09 seconds ( user: 0.08, sys: 0.00 )
..no of output lines: 66711
Running 'codeforester_orig'..
..finished in 0.05 seconds ( user: 0.05, sys: 0.00 )
..no of output lines: 66711
Running 'codeforester'..
..finished in 0.45 seconds ( user: 0.44, sys: 0.01 )
..no of output lines: 66711
[...]
[@Vasiliou获得的结果显示在中间栏中.]
|Vasiliou
My Benchmark |Results | Details
-------------------------------|---------|----------------------
inian4 : 0.04s |0.22s | LC_ALL fgrep -f [loose]
codeforester_orig : 0.05s | | fgrep -f [loose]
Vasiliou2 : 0.06s |0.16s | [LC_ALL join [requires sorted files]]
BOC1 : 0.06s | | grep -E [loose]
BOC2 : 0.07s |15s | LC_ALL grep -E [loose]
BOC2B : 0.07s | | LC_ALL grep -E [strict]
inian4B : 0.08s | | LC_ALL grep -E -f [strict]
Vasiliou : 0.08s |0.23s | [join [requires sorted files]]
gregory1B : 0.08s | | [parallel + grep -E -f [strict]]
ikegami : 0.1s | | grep -P
gregory1 : 0.11s |0.5s | [parallel + fgrep -f [loose]]
hakon1 : 0.14s | | [perl + c]
BOC1B : 0.14s | | grep -E [strict]
jjoao : 0.21s | | [compiled flex generated c code]
inian6 : 0.26s |0.7s | [LC_ALL awk + split+dict]
codeforester_origB : 0.28s | | grep -E -f [strict]
dawg : 0.35s | | [python + split+dict]
inian3 : 0.44s |1.1s | [awk + split+dict]
zdim2 : 0.4s | | [perl + split+dict]
codeforester : 0.45s | | [perl + split+dict]
oliv : 0.5s | | [python + compiled regex + re.search()]
zdim : 0.61s | | [perl + regexp+dict]
inian2 : 0.73s |1.7s | [awk + index($0,i)]
inian5 : 18.12s | | [LC_ALL awk + match($0,i) [loose]]
inian1 : 19.46s | | [awk + match($0,i) [loose]]
inian5B : 42.27s | | [LC_ALL awk + match($0,i) [strict]]
inian1B : 85.67s | | [awk + match($0,i) [strict]]
Vasiliou Results : 2 X CPU Intel 2 Duo T6570 @ 2.10GHz - 2Gb RAM-Debian Testing 64bit- kernel 4.9.0.1 - no cpu freq scaling.
然后我创建了一个更现实的案例,file1.txt有100个单词,file2.txt有1000万行(268Mb文件大小).我从字典中提取了1000个随机单词,然后/usr/share/dict/american-english使用shuf -n1000 /usr/share/dict/american-english > words.txt这些单词中提取的100个单词file1.txt,然后file2.txt以与上述第一个测试用例相同的方式构造.请注意,字典文件是UTF-8编码的,我从中删除了所有非ASCII字符words.txt.
然后我运行测试,没有前一种情况下的三种最慢的方法.即inian1,inian2和inian5被排斥在外.以下是新结果:
gregory1 : 0.86s | [parallel + fgrep -f [loose]]
Vasiliou2 : 0.94s | [LC_ALL join [requires sorted files]]
inian4B : 1.12s | LC_ALL grep -E -f [strict]
BOC2B : 1.13s | LC_ALL grep -E [strict]
BOC2 : 1.15s | LC_ALL grep -E [loose]
BOC1 : 1.18s | grep -E [loose]
ikegami : 1.33s | grep -P
Vasiliou : 1.37s | [join [requires sorted files]]
hakon1 : 1.44s | [perl + c]
inian4 : 2.18s | LC_ALL fgrep -f [loose]
codeforester_orig : 2.2s | fgrep -f [loose]
inian6 : 2.82s | [LC_ALL awk + split+dict]
jjoao : 3.09s | [compiled flex generated c code]
dawg : 3.54s | [python + split+dict]
zdim2 : 4.21s | [perl + split+dict]
codeforester : 4.67s | [perl + split+dict]
inian3 : 5.52s | [awk + split+dict]
zdim : 6.55s | [perl + regexp+dict]
gregory1B : 45.36s | [parallel + grep -E -f [strict]]
oliv : 60.35s | [python + compiled regex + re.search()]
BOC1B : 74.71s | grep -E [strict]
codeforester_origB : 75.52s | grep -E -f [strict]
在grep基础的解决方案正在寻找对全行的匹配,所以在这种情况下,它们包含一些虚假的比赛:方法codeforester_orig,BOC1,BOC2,gregory1,inian4,和oliv提取1087609个线条勾勒出1000万线,而其他方法从中提取正确的997993行file2.txt.
我在我的Ubuntu 16.10笔记本电脑上测试了这个(Intel Core i7-7500U CPU @ 2.70GHz)
整个基准研究可在此处获得.
你尝试过Awk这样可以加速一些事情:
awk 'FNR==NR{hash[$1]; next}{for (i in hash) if (match($0,i)) {print; break}}' file1.txt FS='|' file2.txt
(或)使用下面Benjamin W.的评论所建议的index()功能Awk
awk 'FNR==NR{hash[$1]; next}{for (i in hash) if (index($0,i)) {print; break}}' file1.txt FS='|' file2.txt
(或)Ed Morton在评论中建议的更直接的正则表达匹配,
awk 'FNR==NR{hash[$1]; next}{for (i in hash) if ($0~i) {print; break}}' file1.txt FS='|' file2.txt
是你所需要的全部.我猜这会有更快,但不完全确定有百万+条目的文件.这里的问题在于沿线任何地方的可能性匹配.如果在任何特定列中都有相同的内容(例如$2单独说),则可以采用更快的方法
awk 'FNR==NR{hash[$1]; next}$2 in hash' file1.txt FS='|' file2.txt
您还可以通过locale在系统中使用该设置来加快速度.从这个精彩的StéphaneChazelas关于这个主题的答案中解释,你可以通过将locale传递LC_ALL=C给本地运行的命令来快速加速.
在任何GNU基于系统上,默认为locale
$ locale
LANG=en_US.UTF-8
LC_CTYPE="en_US.UTF-8"
LC_NUMERIC="en_US.UTF-8"
LC_TIME="en_US.UTF-8"
LC_COLLATE="en_US.UTF-8"
LC_MONETARY="en_US.UTF-8"
LC_MESSAGES="en_US.UTF-8"
LC_PAPER="en_US.UTF-8"
LC_NAME="en_US.UTF-8"
LC_ADDRESS="en_US.UTF-8"
LC_TELEPHONE="en_US.UTF-8"
LC_MEASUREMENT="en_US.UTF-8"
LC_IDENTIFICATION="en_US.UTF-8"
LC_ALL=
使用一个变量LC_ALL,您可以将所有LC_类型变量一次设置为指定的区域设置
$ LC_ALL=C locale
LANG=en_US.UTF-8
LC_CTYPE="C"
LC_NUMERIC="C"
LC_TIME="C"
LC_COLLATE="C"
LC_MONETARY="C"
LC_MESSAGES="C"
LC_PAPER="C"
LC_NAME="C"
LC_ADDRESS="C"
LC_TELEPHONE="C"
LC_MEASUREMENT="C"
LC_IDENTIFICATION="C"
LC_ALL=C
那么这会产生什么影响呢？
简单地说,使用locale C它时默认使用服务器的基本Unix/Linux语言ASCII.基本上当你有grep什么东西时,默认情况下你的语言环境将被国际化并设置为UTF-8,它可以代表Unicode字符集中的每个字符,以帮助显示世界上任何一个写入系统,目前不仅仅是110,000唯一的字符,而ASCII每个字符都是以单字节序列编码,其字符集不包括128唯一字符.
所以它转换为这个,当grep在UTF-8字符集中编码的文件上使用时,它需要将每个字符与十万个唯一字符中的任何一个匹配,但只是128在ASCII,所以使用你的fgrepas
LC_ALL=C fgrep -F -f file1.txt file2.txt
此外,同样可以适应Awk,因为它使用regex与match($0,i)调用的匹配,设置C区域设置可以加速字符串匹配.
LC_ALL=C awk 'FNR==NR{hash[$1]; next}{for (i in hash) if (match($0,i)) {print; break}}' file1.txt FS='|' file2.txt
假设:1.您希望仅在本地工作站上运行此搜索.2.你有多个核心/ cpus来利用并行搜索.
parallel --pipepart -a file2.txt --block 10M fgrep -F -f file1.txt
根据上下文进行一些进一步的调整:A.使用LANG = C禁用NLS(这已在另一个答案中提到)B.使用-m标志设置最大匹配数.
注意:我猜测file2是〜4GB且10M块大小没问题,但您可能需要优化块大小以获得最快的运行速度.
一小段Perl代码解决了该问题。这是采取的方法：
file1.txt在哈希中file2.txt逐行读取，解析并提取第二个字段这是代码：
#!/usr/bin/perl -w
use strict;
if (scalar(@ARGV) != 2) {
printf STDERR "Usage: fgrep.pl smallfile bigfile\n";
exit(2);
}
my ($small_file, $big_file) = ($ARGV[0], $ARGV[1]);
my ($small_fp, $big_fp, %small_hash, $field);
open($small_fp, "<", $small_file) || die "Can't open $small_file: " . $!;
open($big_fp, "<", $big_file) || die "Can't open $big_file: " . $!;
# store contents of small file in a hash
while (<$small_fp>) {
chomp;
$small_hash{$_} = undef;
}
close($small_fp);
# loop through big file and find matches
while (<$big_fp>) {
# no need for chomp
$field = (split(/\|/, $_))[1];
if (defined($field) && exists($small_hash{$field})) {
printf("%s", $_);
}
}
close($big_fp);
exit(0);
我使用file1.txt中的14K行和file2.txt中的130M行来运行上述脚本。它在大约13秒内完成了126K场比赛。这是time相同的输出：
real 0m11.694s
user 0m11.507s
sys 0m0.174s
我运行了@Inian的awk代码：
awk 'FNR==NR{hash[$1]; next}{for (i in hash) if (match($0,i)) {print; break}}' file1.txt FS='|' file2.txt
它比Perl解决方案慢得多，因为它使file2.txt中的每一行循环14K次-这确实很昂贵。它在处理了592K条记录file2.txt并产生了40K条匹配的线后中止。这是花了多长时间：
awk: illegal primary in regular expression 24/Nov/2016||592989 at 592989
input record number 675280, file file2.txt
source line number 1
real 55m5.539s
user 54m53.080s
sys 0m5.095s
使用@Inian的其他awk解决方案可以消除循环问题：
time awk -F '|' 'FNR==NR{hash[$1]; next}$2 in hash' file1.txt FS='|' file2.txt > awk1.out
real 0m39.966s
user 0m37.916s
sys 0m0.743s
time LC_ALL=C awk -F '|' 'FNR==NR{hash[$1]; next}$2 in hash' file1.txt FS='|' file2.txt > awk.out
real 0m41.057s
user 0m38.475s
sys 0m0.904s
awk 鉴于我们不必编写整个程序来做到这一点，因此在这里给人留下了深刻的印象。
我也运行了@oliv的Python代码。完成这项工作大约花了15个小时，看起来效果不错。构建大型正则表达式的效率不及使用哈希查找的效率。这里的time输出：
real 895m14.862s
user 806m59.219s
sys 1m12.147s
我试图按照建议使用parallel。但是，fgrep: memory exhausted即使块大小很小，它也会因错误而失败。
令我惊讶的是，这fgrep完全不适合这样做。22小时后我终止了它，并产生了约10万次匹配。 我希望fgrep可以选择强制将其内容-f file保留在哈希中，就像Perl代码所做的那样。
我没有检查join方法-我不需要排序文件的额外开销。而且，由于fgrep性能不佳，我认为join这样做不会比Perl代码更好。
感谢大家的关注和回应。
| 归档时间： |
|
| 查看次数： |
6306 次 |
| 最近记录： |