list現在、私は100万を持っており、integersそれぞれintegerを2000integer秒のブラックリストと照合します。これには約2分かかります。
for(int i = 0; i< MillionIntegerList.Length ; i++)
{
for(int blacklisted = 0; blacklisted < TwoThousandIntegerList.Length ; blacklisted++)
if(i==blacklisted)
i = 0; //Zero is a sentinel value
}
これにより、合計で2,000,000,000回の反復（ループ）が行われます。私が見ないより良い方法はありますか？ありがとう
MillionIntegerList現在、3つのオプションがあります。最初の2つは、ソートに依存しないという点でより一般的です（最初は指定されていませんでした）。大きなリストがすでにソートされている場合は、3番目が望ましいです。
オプション1
はい、LINQを使用してそれを行うためのより良い方法が間違いなくあります：
var common = MillionIntegerList.Intersect(TwoThousandIntegerList).ToList();
これは、内部でHashSet<int>ビルドを使用し、その中TwoThousandIntegerListの各要素を検索します。これは、毎回MillionIntegerList全体を調べるよりもはるかに効率的です。TwoThousandIntegerList
ブラックリストに載っていないものだけが必要な場合は、次のものが必要です。
var valid = MillionIntegerList.Except(TwoThousandIntegerList).ToList();
結果を1回だけ繰り返す必要がある場合は、ToList呼び出しを削除する必要があることに注意してください。結果を具体化するために呼び出しを含めたので、結果を複数回安価に調べることができます。Intersect反復しているだけの場合、またはの戻り値は結果をストリーミングExceptするだけなので、メモリ使用量の点ではるかに安価になります。
オプション2
LINQ to Objectsの実装の詳細に依存したくないが、それでもハッシュベースのアプローチが必要な場合：
var hashSet = new HashSet<int>(TwoThousandIntegerList);
hashSet.IntersectWith(MillionIntegerList);
// Now use hashSet
オプション3
大きなリストがソートされているという事実を利用するアプローチは間違いなく役に立ちます。
ブラックリストに登録されたリストを最初に並べ替えてもかまわないと仮定すると、次のようなストリーミング（および汎用）実装を作成できます。
// Note: to use this, you'd need to make sure that *both* sequences are sorted.
// You could either sort TwoThousandIntegerList in place, or use LINQ's OrderBy
// method.
public IEnumerable<T> SortedIntersect<T>(this IEnumerable<T> first,
IEnumerable<T> second) where T : IComparable<T>
{
using (var firstIterator = first.GetEnumerator())
{
if (!firstIterator.MoveNext())
{
yield break;
}
using (var secondIterator = second.GetEnumerator())
{
if (!secondIterator.MoveNext())
{
yield break;
}
T firstValue = firstIterator.Current;
T secondValue = secondIterator.Current;
while (true)
{
int comparison = firstValue.CompareTo(secondValue);
if (comparison == 0) // firstValue == secondValue
{
yield return firstValue;
}
else if (comparison < 0) // firstValue < secondValue
{
if (!firstIterator.MoveNext())
{
yield break;
}
firstValue = firstIterator.Current;
}
else // firstValue > secondValue
{
if (!secondIterator.MoveNext())
{
yield break;
}
secondValue = secondIterator.Current;
}
}
}
}
}
IComparer<T>（ Tが比較可能であることに依存する代わりに、必要に応じてをとることができます。）
大きなリストはソートされているため。小さなリストを (非常に迅速に) 並べ替えてから線形マージを実行すると、最良の結果が得られる場合があります。大規模な (および小規模な) リストの各項目を 1 回確認するだけで済み、バックグラウンドで Hashtable を作成する必要はありません。
これを行う方法については、MergeSortのマージ関数部分を参照してください。
私の意見では、必要なのはEnumerable.Exceptメソッド（IEnumerable、IEnumerable）です。
ここをチェックしてくださいhttp://msdn.microsoft.com/en-us/library/bb300779.aspx
あなたのアプローチには O(n*n) 時間が必要です。次の最適化を検討してください。
1)
整数が大きすぎない場合は、bool の配列を使用できます (たとえば、可能な最大の整数が 1000000 の場合は、bool[] b = new bool[1000000] を使用します)。数値 K をブラックリストに追加するには、b[K] = true を使用します。チェックは簡単です。これは O(n) で機能します。BitArray を使用することもできます
2)
整数は十分に大きくなる可能性があります。ブラックリストの保存には二分探索木を使用します (SortedSet など)。O(logN) の挿入および取得時間があります。つまり、全体として O(N*logN) です。構文は List (Add(int K), Contains(int K)) と同じで、重複は無視されます。
最良の解決策はブルーム フィルターを使用することだと思います。ブルーム フィルターが要素がブラックリストにある可能性があると言う場合、それが誤検知ではないかどうかを確認してください (ブラックリストの場合、O(Log(n)) で実行できます)。ソートされます）。このソリューションは時間効率が高く、追加のスペースをほとんど使用しないため、ハッシュセットを使用するよりもはるかに優れています。
これは、Google が Chrome のブラックリストに使用するソリューションです。
ソートされているので、長いリストでバイナリ検索を行うのはどうですか。
foreach(integer blacklisted in TwoThousandIntegerList)
{
integer i = MillionIntegerList.binarySearch(blacklisted)
if(i==blacklisted){
//Do your stuff
}
}
このソリューションのコストはO(m log n)時間のみです。ここで、m は小さなリストのサイズ、n は長いリストのサイズです。警告:MillionIntegerListこのソリューションでは、に重複する値がないことを前提としています。
そうでない場合は、連続したブロックにある必要があるため、繰り返しを繰り返すことができます。MillionInterListこのために、はレコードのリストであり、それぞれに と があるvalueと仮定しindexます。
foreach(integer blacklisted in TwoThousandIntegerList)
{
integer index = MillionIntegerList.binarySearch(blacklisted)
//Find the index of the first occurrence of blacklisted value
while(index > 0 && MillionIntegerList[index - 1].value == blacklisted){
--index;
}
while(MillionIntegerList[index].value == blacklisted){
//Do your stuff
++index;
}
}
このソリューションのコストはO(m log n + mk)です。ここで、kは で見つかったブラックリストに登録された整数あたりの重複の平均数です MillionInterList。
ブロックリストにはHashSetを使用します。
foreach(integer i in MillionIntegerList)
{
//check if blockedlist contains i
//do what ever you like.
}
Exceptリストのメソッドを使用します。これはうまくいきます