9

関連する質問は複数ありますが、自分のケースに固有の解決策を探しています。（通常）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のマシンでのJonのスループットが約2倍であることがわかりました（Win7-64の一部のCore 2 Duo）。intの配列の生成には、それぞれのチェックと同じくらいの時間がかかるので、結果に満足しています。皆さんありがとう！

4

6 に答える 6

10

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

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のアプローチよりも速いか遅いかはわかりません。）

于 2010-11-15T15:22:21.070 に答える
6

明らかに、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;

編集：JonSkeetによって指摘されたバグを修正しました。彼のアルゴはより賢く、おそらくより速いことも指摘しておきます。

于 2010-11-15T15:19:50.857 に答える
0

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

入力配列の要素ごとに、billy[element]を1ずつ増やします。

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

于 2010-11-15T15:23:12.880 に答える
0

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);
    }
}
于 2010-11-15T15:25:03.240 に答える
0

項目の範囲が0〜31の場合、32個の1ビットフラグをuint32に格納できます。各アイテムを取得してmask=（1 SHL item）を計算し、「または」、「xor」、またはマスク値を追加しようとするとどうなるかを確認することをお勧めします。有効なケースと無効なケースの結果を確認します。オーバーフローを回避するには、加算にuint64を使用することをお勧めします（31が2つ、30が4つ、または29が8つある場合、uint32がオーバーフローする可能性があるため）。

于 2010-11-15T16:02:55.347 に答える
0

私は（速度を測定したことはありませんが）このコードニペットはあなたに新しい視点を与えることができると思います：

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;
}

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

于 2010-11-15T16:23:32.943 に答える