Wie kann ich feststellen schnell, wenn eine Liste nur Duplikate enthält?

Question

Es gibt mehrere ähnliche Fragen, aber ich bin für eine Lösung, die spezifisch für meinen Fall suchen. Es gibt eine Reihe von (in der Regel) 14 Zahlen. Wie kann ich feststellen, schnell, wenn jeder int genau doppelt erscheint (das heißt, es sind 7 Paare)? Der Wertebereich reicht von 1 bis 35. Der Hauptaspekt hier Leistung ist.

Als Referenz, das ist meine aktuelle Lösung. Es wurde geschrieben, die Spezifikation so nah wie möglich zu ähneln und ohne Leistung im Verstand, so dass ich sicher bin, ist, erheblich verbessert werden kann:

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

Linq ist optional. Ich interessiere mich nicht wie, so lange wie es ist schnell:)

Bearbeiten: Dort wird der Sonderfall ist, dass ein int 2n mal mit n erscheint> 1. In diesem Fall wird die Prüfung sollte nicht , dh es sollte 7 verschiedene Paare sein .

Bearbeiten: Ergebnis Getestet habe ich Ani und Jons Lösungen mit kleinen Modifikationen und während mehrere Benchmark läuft in dem Ziel App gefunden, dass Ani hat etwa doppelt Jons Durchsatz auf meinem Rechner (einige Core 2 Duo auf Win7-64). Die Erzeugung des Arrays von Ints bereits etwa so lang wie die entsprechenden Kontrollen erfolgt, also bin ich mit dem Ergebnis zufrieden. Danke, alle!

Answer 1

Natürlich LINQ nicht bieten die optimal Lösung hier, obwohl ich Ihre aktuelle LINQ Lösung verbessern würde:

// 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);

Für den speziellen Fall, dass Sie erwähnen (0-31), hier ist eine schnelle, Array-basierte Lösung. Es ist nicht sehr gut skalieren, wenn die Bandbreite der möglichen Zahlen groß ist (eine Hashing-Lösung in diesem Fall verwendet werden).

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

EDIT: Fehler behoben Wie von Jon Skeet. Ich mag auch darauf hinweisen, dass sein algo ist intelligenter und wahrscheinlich schneller.

Answer 2

Nun, Ihre genauen Anforderungen gegeben, können wir ein bisschen klüger sein. So etwas wie folgt aus:

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

Im Grunde hält diese verfolgen, wie viele ungepaarte Werte, die Sie noch haben, und hat eine „early out“, wenn es jemals einen Drilling findet.

(Ich weiß nicht, ob dies ohne Weiteres schneller sein oder langsamer als Ani Ansatz des Inkrementierens und dann für nicht ausgeglichene Paare Überprüfung danach.)

Answer 3

würde ich ein Array aus 32 ganzzahligen Elementen erzeugt, auf Null initialisiert. Nennen wir es "billy".

Für jedes Element des Eingangsfeldes, würde ich erhöhen billy [element] von 1.

Am Ende, ob billy enthält nur 0 oder 2.

Answer 4

Mit ziemlicher Sicherheit übertrieben, wenn man nur habe 14-ish Paare und nur 32-ish mögliche Werte, aber im allgemeinen Fall könnten Sie so etwas tun:

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

Answer 5

Wenn der Bereich der Artikel 0-31 ist, können Sie speichern 32 Ein-Bit-Flags in einem Uint32. Ich würde vorschlagen, jedes Element und Compute mask = (1 SHL Artikel) nehmen, und sehen, was passiert, wenn Sie versuchen, ‚ODER-Verknüpfung‘ XOR-Verknüpfung oder das Hinzufügen der Maskenwerte. Schauen Sie sich die Ergebnisse für gültige und ungültige Fälle. Um zu vermeiden, Überlauf, möchten Sie vielleicht einen uint64 für den Zusatz verwenden (da ein uint32 überlaufen könnte, wenn es zwei 31 ist, oder vier 30er Jahre oder acht 29s).

Answer 6

Ich denke, (nie die Geschwindigkeit gemessen) dieses codesnipet kann Ihnen einen neuen Blickwinkel:

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

können Sie sich die verdoppelten Werte in den Variablen „zweimal“; Natürlich funktioniert es nur für Werte kleiner als 32;