リストにリストが含まれているかどうかをすばやく見分けるにはどうすればよいですか？
https://stackoverflow.com/questions/4192961
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
複数の関連する質問がありますが、私のケースに固有のソリューションを探しています。 （通常）14の整数の配列があり、それぞれ1〜34の範囲があります。特定の静的リストの各INTがこの配列に少なくとも1回表示されるかどうかをすばやく見分けるにはどうすればよいですか？
参照のために、私は現在、このコードを使用しています。これは、可能な限り密接にスペックに似ているように書かれているため、確かに大幅に改善できます。
if (array.Count < 13) {
return;
}
var required = new int[] {
0*9 + 1,
0*9 + 9,
1*9 + 1,
1*9 + 9,
2*9 + 1,
2*9 + 9,
3*9 + 1,
3*9 + 2,
3*9 + 3,
3*9 + 4,
3*9 + 5,
3*9 + 6,
3*9 + 7,
};
IsThirteenOrphans = !required.Except (array).Any ();
必要なリストは動的ではありません。つまり、ランタイム中は常に同じになります。 LINQを使用することはオプションで、主な側面はパフォーマンスです。
編集：
- 入力配列はソートされていません。
- 入力値は複数回表示される場合があります。
- 入力配列には、少なくとも14個のアイテム、つまり必要な配列よりも1個多いです。
- 必要な配列は1つだけで、静的です。
- 必要な値は異なります。
- ヒストグラムの作成が安価であると仮定することができます。
アップデート： また、ソートされた入力配列のソリューションにも興味があります。
解決
アイデア1
いくつかと比較する必要がある場合 required リストでは、入力リストをソートしてから、繰り返して比較するだけです。しかし、ソートはもちろん速すぎませんが、遅すぎません。ただし、いくつかの必要なリストと比較すると、ソートのオーバーヘッドは迅速に償却される可能性があります。
配列がソートされたら、比較は些細なことです。
for(int i = 0; i < 14; i++)
if(arr[i] != required[i]) return false;
return true;
アイデア2
または、14の整数が明確/ユニークである場合、単に作成できます required ハッシュセットとします
input.Count(i => required.Contains(i)) == 14
しかし、それがソートよりも速いかどうかを実際にテストすることなく、私は知りません。
アイデア3
14 INTの順列の下で不変のクイックハッシュを計算し、それをの既知の値と比較します require. 。ハッシュマッチがより高価な比較を行う場合のみ。
//Prepare/precalculated
int[] hashes = new int[34];
Random random = new Random();
for(int i = 0; i < 34; i++)
hashes[i] = random.NextInt();
//On each list
int HashInts(int[] ints)
{
int result = 0;
foreach(int i in ints)
result += hashes[i - 1];
return result;
}
の価値の賢明な選択 hashes 少し改善するかもしれませんが、ランダムな値は問題ありません。
アイデア4
ヒストグラムを作成します：
int[] CreateHistogram(int[] ints)
{
int[] counts = new int[34];
foreach(int i in ints)
{
counts[i - 1]++;
}
return counts;
}
パフォーマンスがある場合、既存の配列を再利用することで作成する配列を避けることができます 本当 重要。
他のヒント
34+ビットの積分タイプが利用可能で、Cスタイルビット操作がある場合、変数リストからそのような整数Vを計算できます（リストがv [0]、v [1]、... （1 << V [0]）|（1 << V [1]）...ここで、1はVと同じタイプです）、静的リストのそのような整数を事前に定義し、類似して計算します。変数リストに静的リストが含まれているかどうかを確認するテスト（S＆〜V）== 0。
1つの可能性は、データの保存方法を変更することです。可能な値の範囲は1〜34に制限されているため、数字のリストを保存する代わりに、存在する各番号のカウントを保存できます。
int[] counts = new int[34];
リストに1つの1と2つの3がある場合、[0] == 1 && counts [2] = 2（1ベースのインデックスを使用することもできます（減算が少なくなります。）
リスト内の各INTが少なくとも1回表示されることを評価するために、各Xのアレイに順次インデックスを付け、すべてのカウント[x]> 0を確認するだけです。データの変換に関連するオーバーヘッドがあります。リストフォームですが、リストフォームのデータを頻繁に表示する必要がある場合は、それは問題です。このストレージ形式のもう1つの利点は、カウントを追加/削除すると、単一の配列要素が含まれないことです。リスト形式では、リストの中央に要素を削除するには、複数の要素のコピーが必要です。
高速な方法が必要な場合は、LINQを使用してはいけません。特定のリストアイテムがすべてBellow 35である場合は削除できます if (lst[i] < 35)ベローの回答トラバースリストはせいぜい1回、そして counting sort:
public bool FindExactMatch(int[] array, List<int> lst)
{
bool[] a34 = new bool[35];
foreach(var item in array)
{
a34[item] = true;
}
int exact = 0;
for (int i = 0; i < lst.Count; i++)
{
if (a34[lst[i]])
{
exact++;
if (exact == array.Length) return true;
a34[lst[i]] = false;
}
}
return false;
}
リストサイズが大きい場合、ソート付きリストの場合 lst.BinarySearch(array[i]) 14 * log（n） * c1がせいぜいかかりますが、実装がより速くなる可能性があり、自分の実装でバイナリ検索をテストしませんでしたが、min、max、sort in linqでバイナリ検索をテストしませんでしたあなた自身の（良い）実装よりも（4〜10時間）より遅いです。ソートされたリストサイズが小さい場合は、定数のように上記のようにアルゴリズムを使用することを好みます c1 上記のアルゴリズムでは小さく、バイナリ検索アルゴリズムで大きくなる可能性があります。
これは、必要な値が明確で静的であり、1〜34の間であるため、ビットワイズ操作の適切な候補のように見えます。アレイとして必要な保存の代わりに、const Ulongとして保存します。チェックする配列で、各値とビットワイズまたはビットワイズまたはビットワイズで左シフトによって入力された新しいウルングを作成します。
const ulong comparator = (1UL << 1) | (1UL << 9) | (1UL << 10) | (1UL << 18) | (1UL << 19) | (1UL << 27) | (1UL << 28) | (1UL << 29) | (1UL << 30) | (1UL << 31) | (1UL << 32) | (1UL << 33) | (1UL << 34);
public static bool ContainsDistinct13Values(int[] array)
{
ulong word = 0;
foreach (int i in array)
{
word |= (1UL << i);
}
return word == comparator;
}
編集：だから私はあなたの質問を理解し、おそらくいくつかの素晴らしい過剰なソリューションがあるでしょう。別の質問は、パフォーマンスがどれほど優れているかです。
static void Main(string[] args)
{
var required = new int[]
{
0*9 + 1,
0*9 + 9,
1*9 + 1,
1*9 + 9,
2*9 + 1,
2*9 + 9,
3*9 + 1,
3*9 + 2,
3*9 + 3,
3*9 + 4,
3*9 + 5,
3*9 + 6,
3*9 + 7,
};
precomputed = required.Select((x, i) => new { Value = x, Offset = (UInt16)(1 << i) }).ToDictionary(x => x.Value, x => x.Offset);
for (int i = 0; i < required.Length; i++)
{
precomputedResult |= (UInt16)(1 << i);
}
int[] array = new int[34]; // your array goes here..
Console.WriteLine(ContainsList(array));
Console.ReadKey();
}
// precompute dictionary
private static Dictionary<int, UInt16> precomputed;
// precomputed result
private static UInt16 precomputedResult = 0;
public static bool ContainsList(int[] values)
{
UInt16 result = 0;
for (int i = 0; i < values.Length; i++)
{
UInt16 v;
if (precomputed.TryGetValue(values[i], out v))
result |= v;
}
return result == precomputedResult;
}
アイテムを簡単にループして、アイテムが欠落していることを確認できます。あなたの例では、私はあなたが必要なアイテムがあるかどうかを知りたいと思っていることを理解しています。だからあなたは書くことができます
bool notContains = false;
foreach (var iddd in required)
{
foreach (var ar in array)
{
if (iddd == ar) notContains=true;
}
if (notContains == false) break;
}
これはあなたのアプローチよりもはるかに速いです。タイマーが追加された以下のコードをチェックしてください。あなたのアプローチには5ミリ秒かかりましたが、新しいものは0ミリ秒かかります
System.Diagnostics.Stopwatch aTimer = new System.Diagnostics.Stopwatch();
aTimer.Start();
var IsThirteenOrphans = !required.Except(array).Any();
aTimer.Stop();
System.Diagnostics.Stopwatch bTimer = new System.Diagnostics.Stopwatch();
bTimer.Start();
bool notContains = false;
foreach (var iddd in required)
{
foreach (var ar in array)
{
if (iddd == ar) notContains=true;
}
if (notContains == false) break;
}
bTimer.Stop();
