リストに複製のみが含まれているかどうかをすばやく見分けるにはどうすればよいですか？

StackOverflow https://stackoverflow.com/questions/4185766

質問

複数の関連する質問がありますが、私のケースに固有のソリューションを探しています。 （通常）14の整数の配列があります。各INTが正確に2回表示されるかどうか（つまり、7ペアがある）かどうかをすばやく見分けるにはどうすればよいですか？値範囲は1〜35です。ここでの主な側面はパフォーマンスです。

参照のために、これが私の現在のソリューションです。それは、スペックを可能な限り密接に、そしてパフォーマンスを念頭に置くことなく似ていると書かれていたので、私は確かに大幅に改善できると確信しています。

var pairs = Array
    .GroupBy (x => x)
    .Where (x => x.Count () == 2)
    .Select (x => x.ToList ())
    .ToList ();
IsSevenPairs = pairs.Count == 7;

LINQの使用はオプションです。それが速い限り、私はどのように気にしません:)

編集： intがn> 1で2n回表示されるという特別なケースがあります。この場合、チェックはする必要があります 不合格, 、つまり、7つの異なるペアが必要です。

編集：結果AniとJonのソリューションを小さな変更でテストし、ターゲットアプリの複数のベンチマーク実行中にANIがマシンに約2倍のJonのスループットを持っていることがわかりました（Win7-64のコア2デュオ）。 INTの配列を生成するには、それぞれのチェックと同じ長さが必要なので、結果に満足しています。皆さんありがとう！

役に立ちましたか？

解決

明らかに、linqは提供しません 最適な ここでの解決策は、あなたの現在のLINQソリューションを改善します。

// checks if sequence consists of items repeated exactly once
bool isSingleDupSeq = mySeq.GroupBy(num => num)
                           .All(group => group.Count() == 2);

// checks if every item comes with atleast 1 duplicate
bool isDupSeq = mySeq.GroupBy(num => num)
                     .All(group => group.Count() != 1);

あなたが言及する特定のケース（0-31）については、より高速で配列ベースのソリューションを次に示します。可能な数値の範囲が大きい場合、それはあまりうまくスケーリングしません（この場合、ハッシュソリューションを使用してください）。

// elements inited to zero because default(int) == 0
var timesSeenByNum = new int[32];

foreach (int num in myArray)
{
    if (++timesSeenByNum[num] == 3)
    {
        //quick-reject: number is seen thrice
        return false;
    }
}

foreach (int timesSeen in timesSeenByNum)
{
    if (timesSeen == 1)
    {
        // only rejection case not caught so far is
        // if a number is seen exactly once
        return false;
    }
}

// all good, a number is seen exactly twice or never
return true;

編集：Jon Skeetが指摘したように、バグを修正しました。また、彼のアルゴは賢くて、 おそらく もっと早く。

他のヒント

まあ、あなたの正確な要件を考えると、私たちは少し賢くなることができます。このようなもの：

public bool CheckForPairs(int[] array)
{
    // Early out for odd arrays.
    // Using "& 1" is microscopically faster than "% 2" :)
    if ((array.Length & 1) == 1)
    {
        return false;
    }

    int[] counts = new int[32];
    int singleCounts = 0;
    foreach (int item in array)
    {
        int incrementedCount = ++counts[item];
        // TODO: Benchmark to see if a switch is actually the best approach here
        switch (incrementedCount)
        {
            case 1:
                singleCounts++;
                break;
            case 2:
                singleCounts--;
                break;
            case 3:
                return false;
            default:
                throw new InvalidOperationException("Shouldn't happen");
        }
    }
    return singleCounts == 0;
}

基本的に、これはあなたがまだ持っている人のない価値の数を追跡し、それが3つの種類を見つけた場合、「早い段階」を持っています。

（これがANIのインクリメントのアプローチよりも速いか遅くなるか、その後比類のないペアをチェックするかどうかはわかりません。）

ゼロに初期化された32の整数要素の配列を作成します。それを「ビリー」と呼びましょう。

入力配列の各要素について、1のビリー[要素]を増やします。

最後に、ビリーに0または2のみが含まれているかどうかを確認します。

ほぼ確実に、14ペアしか持っていない場合はほぼ確実に過剰になりますが、32枚の可能な値しかありませんが、一般的な場合は次のようなことができます。

bool onlyPairs = yourArray.ContainsOnlyPairs();

// ...

public static class EnumerableExtensions
{
    public static bool ContainsOnlyPairs<T>(this IEnumerable<T> source)
    {
        var dict = new Dictionary<T, int>();

        foreach (T item in source)
        {
            int count;
            dict.TryGetValue(item, out count);

            if (count > 1)
                return false;

            dict[item] = count + 1;
        }

        return dict.All(kvp => kvp.Value == 2);
    }
}

アイテムの範囲が0〜31の場合、32の1ビットフラグをUINT32に保存できます。各アイテムを使用してマスク=（1 shlアイテム）を計算することをお勧めし、「オル」、 'xor'ing、またはマスク値を追加した場合に何が起こるかを確認します。有効なケースと無効なケースの結果を見てください。オーバーフローを避けるために、追加にUINT64を使用することをお勧めします（UINT32は2つの31、30、または8つの29がある場合はオーバーフローする可能性があるため）。

このCodesNipetが新しい視点を与えることができると思います（速度を測定しませんでした）。

int[] array = { 0, 1, 2, 3, 1, 1, 3, 5, 1, 2, 7, 31 }; // this is your sample array

uint[] powOf2 = {
    1, 2, 4, 8,
    16, 32, 64, 128,
    256, 512, 1024, 2048,
    4096, 8192, 16384, 32768,
    65536, 131072, 262144, 524288,
    1048576, 2097152, 4194304, 8388608,
    16777216, 33554432, 67108864, 134217728,
    268435456, 536870912, 1073741824, 2147483648
               };

uint now;
uint once = 0;
uint twice = 0;
uint more = 0;

for (int i = 0; i < array.Length; i++)
{
    now = powOf2[array[i]];

    more |= twice & now;
    twice ^= (once & now) & ~more;
    twice ^= more;
    once |= now;
}

変数「2回」に2倍の値を持つことができます。もちろん、32未満の値に対してのみ機能します。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top