メモリに収まらない非常に大きなデータセットがあり、データセットには何百万ものレコードがあり、重複行を削除したいとします (実際には重複から 1 行を保持します)。
空間と時間の複雑さの点で最も効率的なアプローチは何ですか?
私が思ったこと：
1.ブルームフィルターを使用して、それがどのように実装されているかはわかりませんが、副作用に偽陽性があると思います。その場合、それが本当に重複しているかどうかをどのように見つけることができますか?
2.ハッシュ値を使用する場合、この場合、重複する値が少ない場合、一意のハッシュ値の数が多くなり、メモリに問題が発生する可能性があります。
並べ替えやインデックス作成を行わずに重複アイテムを削除する必要があるため、削除するたびにデータセット全体をスキャンすることになり、パフォーマンスの点で耐え難いほどコストがかかります。それを考えると、これまたはデータベースの外部ソートを考えるかもしれません。出力データセットの順序を気にしない場合。レコードまたはレコードのキーのハッシュに従って、入力データセットのサブセットを格納する「n」個のファイルを作成します。ハッシュを取得し、「n」によるモジュロを取得して、コンテンツを保存するための適切な出力ファイルを取得します。現在、すべての出力ファイルのサイズが小さいため、削除操作は非常に高速です。出力ファイルには、通常のファイル、または sqlite/berkeley db を使用できます。ただし、sqlite/bdb をお勧めします。出力ファイルへのすべての書き込みをスキャンしないようにするために、すべての出力ファイルにフロントエンド ブルーム フィルターを設定できます。ブルームフィルターはそれほど難しくありません。多くのライブラリが利用可能です。「n」の計算は、メイン メモリに依存します。「n」には悲観的で大きな値を使用してください。作業が完了したら、すべての出力ファイルを 1 つのファイルに連結します。