0

2 つの utf-8 テキスト ファイルが必要です。ファイルの各行には文字列があり、Ü、Ö、ą、ę などの言語固有の文字を含めることができます。文字列はランダムな順序と長さで、繰り返すことができます。最初のファイルには、少なくとも 3 mln の行があります (1 mld の行を簡単に超える可能性があります)。2 番目のファイルは小さく、通常は約 40 万行になります (ただし、はるかに大きくなる可能性があります)。

ファイル 1 のエントリを含む新しいファイルを作成し、ファイル 2 に表示されるエントリを削除し、すべての繰り返しエントリを作成する必要があります。

現在、両方のファイルを並べ替えて、繰り返しエントリを削除しています。次に、2番目のファイルに表示されるかどうかを確認しながら、それらを新しいファイルに書き込みます。

これを行うより速い方法はありますか？

編集

メモリが問題です。この文字列をメモリにコピーせず、ファイルを操作します。私の友人は、メモリにコピーするのではなく、ファイル ストリームで作業することを提案しました。この後、実行時間は大幅に短縮されます。

コンピュータの管理者は、データベースをインストールしたくありません。

ループで次のようにコードルーンをソートした後：

if stringFromFile1 < stringFromFile2 then writeToFile3 and get next stringFromFile1
else if stringFromFile1 == stringFromFile2 then dropStringFromFile1 and get next stringFromFile1
else if stringFromFile1 > stringFromFile2 then get next stringFromFile2 and go to line 1
4

3 に答える 3

0

考えられる最適化はいくつかあります。

Roman Saveljev が示唆したように、トライ構造をメモリに保持できます。データのエントロピーによっては、メモリに簡単に収まります。

2 番目のファイルがソートされると、バイナリ検索を実行してレコードが存在するかどうかを確認できます (まだ行っていない場合)。

ブルーム フィルターをメモリに保持して、複製されていないレコードを簡単にチェックして、毎回ディスクにアクセスすることを避けることもできます。

于 2012-08-03T18:54:46.500 に答える
0

私の提案は、ファイル 2 を前処理し、そこからツリー構造を形成することです。たとえば、次のようなファイル 2 があるとします。

bad
bass
absent

次に、ツリー構造は次のようになります。

BEGIN -> b -> a -> d -> END
|             |
|             + -> s -> s -> END
|
+-> a -> b -> s -> e -> n -> t -> END

END単語の区切り記号を指定します (スペース、改行など)

次に、ファイル 1 をファイル ストリームに開き、バイトごとに読み取ります。ファイルの先頭に到達するか、区切り文字の後に次の文字を選択すると、ツリーのウォークが開始されます。ストリームされたバイトを使用して に移動できる場合はEND、一致する単語が見つかったことを意味し、それを破棄する必要があります。そうでない場合、単語は一意であり、削除する必要はありません。一意であることが判明した場合、単語をツリー構造に追加して、それ以上の繰り返しを破棄する必要があります。

ツリー構造はかなりの量のメモリを必要としますが、何らかの配列で一意の単語を保持するよりも少なくなります。

于 2012-08-03T08:26:49.857 に答える
0

ハッシュ セットなどの利用可能なデータ構造がある場合は、ファイルを反復処理して各行を追加するだけです。セットは繰り返しを許可せず、ハッシュセットは、要素が既に存在するかどうかを確認する一定の方法を提供する必要があります (少なくとも Java では、addメソッドは要素が存在するかどうかを確認し、存在しない場合は、アイテムを定数のセットに追加します)時間）。

両方のファイルを確認したら、ハッシュ セットを繰り返し処理し、その内容をファイルに保存できます。これにより、線形時間で実行できるアルゴリズムが提供されます。

言及するのを忘れました：メモリ消費に制限がないことを前提としています。その場合は、各行のハッシュを主キーとして使用して、各行をデータベースに保存してみてください。2 つの主キーを持つ要素の挿入は失敗するはずなので、データベースに一意の文字列があることを確認してください。挿入が完了したら、データベースから値を取得してファイルに保存できます。

于 2012-08-03T07:34:18.387 に答える