1Mエントリのリストがあり、これらのエントリの20,000のサブセットを除外したいと思います（2つのリストは、同じキー（文字列）を持つことで順序が異なります）。誰かがこれを行うためにCでクイック検索アルゴリズムを提案できますか？
20K IDのそれぞれを読み、毎回1Mのリストを調べる必要はありません。どんな提案も最も役に立ちます。
ありがとうございました。
質問する
90 次
3 に答える
2
使用したいのはハッシュセットです。ハッシュ セットは、要素がセット内に存在するかどうかを一定時間で基本的に記録するハッシュ テーブルの特殊なケースです。したがって、20,000 個の ID をハッシュ セットに挿入し、100 万個の文字列を実行して、それらがハッシュ セットに存在するかどうかを確認します。
参考までに、C でのハッシュ セットの実装を次に示します: https://github.com/avsej/hashset.c
実行時間は O(n) になります。これは、1M 文字列のチェックごとに一定の時間になるためです。
于 2013-03-15T23:28:30.693 に答える
0
最初に両方のリストを並べ替えます。次に、それらを一緒にトラバースし、リスト内のポインターの後ろにあるポインターをもう一方のポインターに進めます。
Cを使用する必要がありますか？これは Perl の仕事のように思えます。
于 2013-03-15T23:16:27.603 に答える
0
リストの検索を開始する前に、20,000 個のキーをハッシュ テーブルに含めます。次に、リスト内の各アイテムのキーについて、そのキーがハッシュ テーブルにある場合は、そのアイテムをリストから除外します。
于 2013-03-15T23:30:35.257 に答える