私は英語の単語（約50000語）のIspellリストを持っています。Perlでの私の宿題は、他の単語の部分文字列であるすべての文字列のリストをすばやく（1分未満のように）取得することです。私はすべての単語を比較する2つのforeachサイクルで解決策を試しましたが、いくつかの最適化を行っても、それでも遅すぎます。正しい解決策は、単語の配列に正規表現を巧妙に使用することかもしれないと思います。この問題を（Perlで）すばやく解決する方法を知っていますか？
質問する
269 次
3 に答える
2
私は、1つのスレッドを使用するだけで、コンピューター上でこれらすべてのサブストリングを約15秒で見つけることができる高速なソリューションを見つけました。基本的に、単語ごとに、可能なすべての部分文字列の配列を作成しました（「s」または「's」の末尾のみが異なる部分文字列を削除します）。
#take word and return list of all valid substrings
sub split_to_all_valid_subwords {
my $word = $_[0];
my @split_list;
my ($i, $j);
for ($i = 0; $i < length($word); ++$i){
for ($j = 1; $j <= length($word) - $i; ++$j){
unless
(
($j == length($word)) or
($word =~ m/s$/ and $i == 0 and $j == length($word) - 1) or
($word =~ m/\'s$/ and $i == 0 and $j == length($word) - 2)
)
{
push(@split_list, substr($word, $i, $j));
}
}
}
return @split_list;
}
次に、部分文字列のすべての候補のリストを作成し、単語と交差させます。
my @substring_candidates;
foreach my $word (@words) {
push( @substring_candidates, split_to_all_valid_subwords($word));
}
#make intersection between substring candidates and words
my %substring_candidates=map{$_ =>1} @substring_candidates;
my %words=map{$_=>1} @words;
my @substrings = grep( $substring_candidates{$_}, @words );
現在、部分文字列には、他のいくつかの単語の部分文字列であるすべての単語の配列があります。
于 2012-12-12T14:36:52.783 に答える
1
foo|bar|bazPerl の正規表現は、コンパイルされた正規表現の長さの特定の制限まで、Aho-Corasick マッチなどのパターンを最適化します。あなたの 50000 語はおそらくその長さを超えますが、より小さなグループに分けることができます。(実際、長さによって分割し、長さ N の単語のみをチェックして、長さ 1 から N-1 の単語が含まれていることを確認したいでしょう。)
別の方法として、Perl コードに Aho-Corasick を実装することもできます。これは楽しいことです。
于 2012-12-11T16:38:42.800 に答える
1
アップデート
Ondra は彼の答えで美しい解決策を提供しました。問題を考えすぎて最適化手法に失敗した例として、私の投稿をここに残します。
私の最悪のケースは、入力内の他のどの単語とも一致しない単語に対して発生します。その場合、それは 2 次になります。これOPT_PRESORTは、ほとんどの単語の最悪のケースを宣伝する試みでした。はOPT_CONSECUTIVE、アルゴリズムの主要部分の項目の総数を削減する線形複雑性フィルターでしたが、複雑さを考慮すると一定の要素にすぎません。ただし、Ondras アルゴリズムでは依然として有用であり、2 つの連続した単語を比較するよりも分割リストを作成する方がコストがかかるため、数秒節約できます。
以下のコードを更新して、可能な最適化として ondras アルゴリズムを選択しました。ゼロスレッドとプリソート最適化と組み合わせることで、最大のパフォーマンスが得られます。
私がコーディングしたソリューションを共有したいと思います。入力ファイルを指定すると、同じ入力ファイル内の他の単語の部分文字列であるすべての単語が出力されます。したがって、それは ysth のアイデアの反対を計算しますが、私は彼の答えから最適化 #2 のアイデアを取り入れました。必要に応じて無効にできる主な最適化は、次の 3 つです。
- マルチスレッド「単語 A はリスト L にありますか?単語 B は L にありますか?」という
質問 簡単に並列化できます。 - すべての単語を長さで事前に並べ替えて、
可能なすべての長さについて、特定の長さより長いすべての単語のリストを指す配列を作成します。長い単語の場合、これにより可能な単語の数が大幅に削減されますが、長さnの 1 つの単語が長さ 1 から長さnまでのすべてのリストに表示されるため、かなりのスペースが犠牲になります。 連続する単語のテスト
私の/usr/share/dict/wordsでは、ほとんどの連続する行は非常によく似ています。Abby Abby's例えば。最初の単語に一致するすべての単語は 2 番目の単語にも一致するため、すぐに最初の単語を一致する単語のリストに追加し、さらにテストするために 2 番目の単語のみを保持します。これにより、テスト ケースで約 30% の単語が節約されました。最適化 2 の前にこれを行うため、これにより多くのスペースも節約されます。もう 1 つのトレードオフは、出力がソートされないことです。
スクリプト自体の長さは約 120 行です。表示する前に、各サブについて説明します。
頭
これは、マルチスレッド用の標準的なスクリプト ヘッダーです。ああ、これを実行するには perl 5.10 以降が必要です。構成定数は、最適化の動作を定義します。そのフィールドにマシンのプロセッサの数を追加します。OPT_MAX変数は処理したい単語の数を取ることができますが、これは最適化が行われた後に評価されるため、簡単な単語はすでにOPT_CONSECUTIVE最適化によって捕捉されています。そこに何かを追加すると、スクリプトが一見遅くなります。$|++ステータスの更新がすぐに表示されるようにします。私は実行されたexit後。main
#!/usr/bin/perl
use strict; use warnings; use feature qw(say); use threads;
$|=1;
use constant PROCESSORS => 0; # (false, n) number of threads
use constant OPT_MAX => 0; # (false, n) number of words to check
use constant OPT_PRESORT => 0; # (true / false) sorts words by length
use constant OPT_CONSECUTIVE => 1; # (true / false) prefilter data while loading
use constant OPT_ONDRA => 1; # select the awesome Ondra algorithm
use constant BLABBER_AT => 10; # (false, n) print progress at n percent
die q(The optimisations Ondra and Presort are mutually exclusive.)
if OPT_PRESORT and OPT_ONDRA;
exit main();
main
メイン ロジックをカプセル化し、マルチスレッドを実行します。入力がソートされている場合、 の出力n words will be matchedは入力単語数よりかなり少なくなります。一致した単語をすべて選択したら、それらを STDOUT に出力します。すべてのステータス更新などは STDERR に出力されるため、出力に干渉しません。
sub main {
my @matching; # the matching words.
my @words = load_words(\@matching); # the words to be searched
say STDERR 0+@words . " words to be matched";
my $prepared_words = prepare_words(@words);
# do the matching, possibly multithreading
if (PROCESSORS) {
my @threads =
map {threads->new(
\&test_range,
$prepared_words,
@words[$$_[0] .. $$_[1]] )
} divide(PROCESSORS, OPT_MAX || 0+@words);
push @matching, $_->join for @threads;
} else {
push @matching, test_range(
$prepared_words,
@words[0 .. (OPT_MAX || 0+@words)-1]);
}
say STDERR 0+@matching . " words matched";
say for @matching; # print out the matching words.
0;
}
load_words
これにより、コマンド ライン引数として指定された入力ファイルからすべての単語が読み取られます。ここでOPT_CONSECUTIVE最適化が行われます。$last単語は、一致する単語のリストに入れられるか、後で一致する単語のリストに入れられます。は、単語が word の部分文字列-1 != index($a, $b)かどうかを決定します。$b$a
sub load_words {
my $matching = shift;
my @words;
if (OPT_CONSECUTIVE) {
my $last;
while (<>) {
chomp;
if (defined $last) {
push @{-1 != index($_, $last) ? $matching : \@words}, $last;
}
$last = $_;
}
push @words, $last // ();
} else {
@words = map {chomp; $_} <>;
}
@words;
}
prepare_words
これは入力単語を「吹き飛ばし」、長さの後にそれらを各スロットに並べ替えます。したがって、スロット 1 にはすべての単語が含まれます。この最適化が選択されていない場合、これはノーオペレーションであり、入力リストをそのまま渡します。
sub prepare_words {
if (OPT_ONDRA) {
my $ondra_split = sub { # evil: using $_ as implicit argument
my @split_list;
for my $i (0 .. length $_) {
for my $j (1 .. length($_) - ($i || 1)) {
push @split_list, substr $_, $i, $j;
}
}
@split_list;
};
return +{map {$_ => 1} map &$ondra_split(), @_};
} elsif (OPT_PRESORT) {
my @prepared = ([]);
for my $w (@_) {
push @{$prepared[$_]}, $w for 1 .. length $w;
}
return \@prepared;
} else {
return [@_];
}
}
test
$wこれは、単語が他の単語の部分文字列であるかどうかをテストします。$wbl前のサブルーチンによって作成されたデータ構造を指します: 単語のフラット リスト、または長さで並べ替えられた単語のいずれかです。次に、適切なアルゴリズムが選択されます。実行時間のほぼすべてがこのループに費やされます。を使用すると、正規表現を使用するよりもはるかに高速indexです。
sub test {
my ($w, $wbl) = @_;
my $l = length $w;
if (OPT_PRESORT) {
for my $try (@{$$wbl[$l + 1]}) {
return 1 if -1 != index $try, $w;
}
} else {
for my $try (@$wbl) {
return 1 if $w ne $try and -1 != index $try, $w;
}
}
return 0;
}
divide
$itemsこれは、アイテムを$parcelsバケットに公平に分配することを保証するアルゴリズムをカプセル化したにすぎません。アイテムの範囲の境界を出力します。
sub divide {
my ($parcels, $items) = @_;
say STDERR "dividing $items items into $parcels parcels.";
my ($min_size, $rest) = (int($items / $parcels), $items % $parcels);
my @distributions =
map [
$_ * $min_size + ($_ < $rest ? $_ : $rest),
($_ + 1) * $min_size + ($_ < $rest ? $_ : $rest - 1)
], 0 .. $parcels - 1;
say STDERR "range division: @$_" for @distributions;
return @distributions;
}
test_range
これはtest、入力リスト内の各単語を呼び出し、マルチスレッド化されたサブです。grepコード (最初の引数として指定) が true を返す入力リスト内のすべての要素を選択します。またthread 2 at 10%、完了を待つのがずっと簡単になるようなステータスメッセージを定期的に出力します。これは心理的な最適化です;-)。
sub test_range {
my $wbl = shift;
if (BLABBER_AT) {
my $range = @_;
my $step = int($range / 100 * BLABBER_AT) || 1;
my $i = 0;
return
grep {
if (0 == ++$i % $step) {
printf STDERR "... thread %d at %2d%%\n",
threads->tid,
$i / $step * BLABBER_AT;
}
OPT_ONDRA ? $wbl->{$_} : test($_, $wbl)
} @_;
} else {
return grep {OPT_ONDRA ? $wbl->{$_} : test($_, $wbl)} @_;
}
}
呼び出し
bashを使用して、次のようなスクリプトを呼び出しました
$ time (head -n 1000 /usr/share/dict/words | perl script.pl >/dev/null)
1000入力したい行数、dict/words使用した単語リスト/dev/null、出力リストを格納する場所 (この場合は出力を破棄) はどこですか。ファイル全体を読み取る必要がある場合は、次のように引数として渡すことができます
$ perl script.pl input-file >output-file
timeスクリプトが実行された時間を示すだけです。2 つの低速プロセッサと 50000 ワードを使用した場合、私の場合は 2 分強で実行されました。これは実際には非常に優れています。
更新: Ondra + Presort 最適化、およびスレッドなしで、現在は 6 ～ 7 秒程度です。
さらなる最適化
更新: より良いアルゴリズムによって克服されます。このセクションはもはや完全に有効ではありません。
マルチスレッドはひどいです。かなりのメモリを割り当て、正確には高速ではありません。これは、データの量を考えると驚くべきことではありません。を使うことも考えましたThread::Queueが、それは $@* のように遅いです! したがって、完全にノーゴーです。内部ループtestが下位レベルの言語でコーディングされている場合、indexビルトインを呼び出す必要がないため、パフォーマンスが向上する可能性があります。Cをコーディングできる場合は、Inline::Cモジュールを見てください。スクリプト全体を低言語でコーディングすると、配列へのアクセスも高速になります。Java のような言語を使用すると、マルチスレッド化の負担も軽減されます (そしてコストも削減されます)。
于 2012-12-12T06:01:05.893 に答える