たとえば、さまざまなクライアントから送信されたファイルを処理するアプリケーションがあります。クライアントは毎日大量のファイルを送信し、それらのファイルのコンテンツをシステムにロードします。ファイルの形式は同じです。与えられている唯一の制約は、同じファイルを2回実行することは許可されていないということです。
特定のファイルを実行したかどうかを確認するには、ファイルのチェックサムを作成して別のファイルに保存します。したがって、新しいファイルを取得したら、そのファイルのチェックサムを作成し、実行して保存した他のファイルのチェックサムと比較できます。
これまでに実行したすべてのファイルのすべてのチェックサムを含むファイルは、非常に大きくなっています。検索と比較には時間がかかりすぎます。
注：アプリケーションは、データベースとしてフラットファイルを使用します。rdbmsなどの使用を提案しないでください。現時点では不可能です。
重複ファイルをチェックする別の方法があると思いますか？
それらを別の場所に保管します。クライアントが処理のためにファイルをアップロードするディレクトリと、それらのファイルが保存される別のディレクトリを用意します。
それとも、クライアントが同じファイルを複数回アップロードできる状況ですか? その場合は、毎回完全な比較を行う必要があります。
また、チェックサムを使用すると、2 つのファイルが異なるという確信が得られますが (チェックサムによっては、非常に高い信頼性が得られます)、100% 保証されるわけではありません。可能なマルチバイトストリームの事実上無限の宇宙を取り、それらを32バイトのチェックサムに減らして、一意性を保証することはできません。
また、階層化されたディレクトリ構造を検討してください。たとえば、ファイルfoobar.txtは path を使用して保存されます/f/fo/foobar.txt。これにより、特定のファイルのディレクトリをスキャンするコスト (線形操作) が最小限に抑えられます。
また、チェックサムを保持する場合、これを階層化に使用できます/1/21/321/myfile.txt(構造に最下位桁を使用します。この場合のチェックサムは 87654321 になる可能性があります)。
いいえ。すべてのファイルを比較する必要があります。厳密には、新しい各ファイルの内容を、既に表示されているすべてのファイルと比較する必要があります。これはチェックサムまたはハッシュ関数で概算できますが、インデックスに既にリストされている新しいファイルを見つけた場合は、ハッシュとチェックサムが衝突する可能性があるため、確実に完全な比較を行う必要があります。
したがって、ファイルをより効率的に保存する方法に行き着きます。
berkleydb、memcached、voldemortなどの専門的なソフトウェアに任せることをお勧めします。
自分でロールバックする必要がある場合は、バイナリ検索 ( qsort 、 bsearch など) の背後にある原則を見ることができます。
表示されたチェックサムのリスト (および上記の再確認のための完全なファイルへのパス) を並べ替えた形式で保持している場合は、バイナリ検索を使用して検索できます。ただし、それぞれの新しいアイテムを正しい順序で挿入するコストはますます高くなります。
ハッシュの数が多い場合の軽減策の 1 つは、ハッシュをビンソートすることです。たとえば、ハッシュの最初のバイトに対応する 256 個のビンを用意します。明らかに、そのバイトコードで始まるハッシュのリストを検索して挿入するだけでよく、ストレージから最初のバイトを省略します。
(各ビンで) 数億のハッシュを管理している場合は、各ハッシュのメイン リストと「最近の」リストがあるように、2 フェーズの並べ替えを検討できます。最近のリストがあるしきい値、たとえば 100000 アイテムに達すると、メイン リスト (O(n)) にマージして最近のリストをリセットします。
新しいドキュメントを以前のすべてのドキュメントと比較する必要があります。これを行う効率的な方法は、ハッシュを使用することです。
ただし、すべてのハッシュを 1 つの順序付けられていないリストに格納する必要はありません。また、次のステップが完全なデータベースである必要もありません。代わりに、ハッシュの最初の数字または 2 桁に基づくディレクトリ、次の 2 桁に基づくファイル、およびハッシュのソートされたリストを含むファイルを作成できます。(または同様のスキーム - ファイルが大きくなりすぎたときにレベルを上げて、適応させることもできます)
この方法では、一致するものを検索するために、いくつかのディレクトリ ルックアップと、それに続くファイル内のバイナリ検索が必要になります。
何度も繰り返す場合 (同じファイルが同時に送信される場合) は、Look-aside キャッシュも使用する価値があります。
チェックサムを作成した後、名前としてチェックサムを使用してディレクトリを作成し、そこにファイルを配置します。そこにすでにファイルがある場合は、新しいファイルを既存のファイルと比較します。
そうすれば、1つ（またはいくつか）のファイルをチェックするだけで済みます。
また、ファイルにヘッダー（1行）を追加して、内容を説明することをお勧めします。作成日、クライアントのIPアドレス、いくつかのビジネスキー。ヘッダーは、この1行を読み取っている重複を検出できるように選択する必要があります。
[編集]多くのエントリを持つディレクトリ（この場合はチェックサムディレクトリ）があると、一部のファイルシステムが機能しなくなります。これが問題になる場合は、チェックサムの最初の2文字を親ディレクトリの名前として使用して、2番目のレイヤーを作成します。必要に応じて繰り返します。
次のレベルから2つの文字を切り落とさないでください。このように、チェックサムを手動でカットしなくても、問題が発生した場合にチェックサムでファイルを簡単に見つけることができます。
提案やRDBMSを行わないように求めているにもかかわらず、SQLiteを提案します。インデックスを使用してすべてのチェックサムを1つのテーブルに格納すると、検索が非常に高速になり、SQLiteの統合はまったく問題になりません。
ウィルが彼のより長い答えで指摘したように、すべてのハッシュを単一の大きなファイルに保存するのではなく、単にそれらをいくつかのファイルに分割する必要があります。
英数字形式のハッシュがであるとしましょうpIqxc9WI。そのハッシュをpI_hashes.db（最初の2文字に基づいて）という名前のファイルに保存します。
新しいファイルが到着したら、ハッシュを計算し、最初の2文字を取得して、CHARS_hashes.dbファイルでのみルックアップを実行します。
他の人が述べているように、チェックサムを格納するための異なるデータ構造を持つことが正しい方法です。とにかく、RDBMSの方法を使いたくないとおっしゃっていましたが、sqliteを試してみませんか？ファイルのように使用でき、非常に高速です。使い方も非常に簡単です。ほとんどの言語にはsqliteサポートも組み込まれています。たとえば、Pythonでは40行未満のコードで済みます。
私があなたの状況と要件を正しく理解していれば、システムを再設計する必要があると思います.
明確にするために、私は、クライアントが 1 日を通してファイルを送信し、ファイル名が無関係であると想定し、ファイルを受信したときにその [i]内容[/i] が間違っていないことを確認する必要があるという前提で作業しています。別のファイルの内容と同じです。
その場合、すべてのファイルを他のすべてのファイルと比較する必要があります。それは本当に避けられないことであり、あなたは現時点で管理できる最善を尽くしています. 少なくとも、チェックサムを回避する方法を求めることは、間違った質問をすることです。着信ファイルを、今日すでに処理されているファイルのコーパス全体と比較する必要があり、チェックサムを比較する方が、ファイル全体を比較するよりもはるかに高速になります。ボディ（後者のメモリ要件は言うまでもありません...）。
ただし、おそらくチェックをいくらか高速化できます。処理済みのチェックサムをtrieのようなものに保存すると、特定のファイル (チェックサムではなく) が既に処理されているかどうかをすばやく確認できます。32 文字のハッシュの場合、潜在的に他のすべてのファイルと比較するのではなく、そのファイルが既に処理されているかどうかを確認するために、最大 32 回のルックアップを行う必要があります。これは事実上、線形検索ではなく、既存のチェックサムのバイナリ検索です。
少なくとも、チェックサム ファイルを適切なデータベース ファイルに移動する必要があります (まだ移動していないと仮定します) - 4GB の制限がある SQLExpress はここでは十分ではないかもしれません。次に、各チェックサムとともに、ファイル名、ファイル サイズ、および受信した日付を保存し、ファイル サイズとチェックサムにインデックスを追加し、同じサイズのファイルのチェックサムのみに対してクエリを実行します。ただし、ウィルが言うように、重複をチェックする方法はとにかく保証されていません。