何百万行ものファイルがあります (実際にはオンライン データ ストリームです。つまり、行ごとに受信しています)。各行は、並べ替えられていない (正と負の) 整数の配列で構成されており、制限はありません。各数値と長さが異なり、1 行に重複する値がある可能性があります。
を削除したいのですがduplicate lines(順序に関係なく 2 つの行が同じ値を持っている場合、それらは重複していると見なされます)、適切なハッシュ関数はありますか?
O(n)これを実行したいnのは行数です (各行の要素の最大可能数は一定であると想定できます。たとえば、各行に最大 100 要素があります)。
ここに投稿されたいくつかの質問をstackoverflowで読み、グーグルで検索しました。それらのほとんどは、配列が同じ長さであるか、整数が正であるか偶数であるか、ソートされている場合に関するものでした。一般的なケースでこれを解決しますか?
O(n)私の解決策：まず、ソートアルゴリズムを使用して各行をソートしますCounting sort。次に、それらを文字列にmd5入れ、ハッシュを使用してそれらをハッシュセットに入れます。セットにない場合はそのセットに入れ、既にリストにある場合は、同じハッシュ値を持つ配列をチェックします。
ソリューションの問題:Counting Sort数に制限がなく、衝突が可能であるため、 を使用した並べ替えには多くのスペースが必要です。