Wie kann ich feststellen schnell, wenn eine Liste eine Liste 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 ganze Zahlen, die jeweils im Bereich von 1 bis 34. Wie kann ich schnell erkennen, ob jeder int in einem bestimmten, statische Liste mindestens einmal erscheint in diesem Array?

Als Referenz Ich bin derzeit mit diesem Code, der geschrieben wurde, die Spezifikation so nah wie möglich zu ähneln, so dass es sicherlich erheblich verbessert werden kann:

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

Die erforderliche Liste ist nicht dynamisch, das heißt, es wird immer die gleiche während der Laufzeit sein. Mit Linq optional ist, ist der Hauptaspekt Leistung.

Bearbeiten:

• Der Eingabe-Array nicht sortiert ist.
• Eingabewerte mehrmals erscheinen.
• Die Eingangsanordnung mindestens 14 Elemente enthalten, das heißt 1 mehr als die erforderliche Array.
• Es gibt nur 1 erforderlich Array und es ist statisch.
• Die Werte in erforderlich sind verschieden.
• Sie können davon ausgehen, dass ein Histogramm billig zu erstellen.

Update:. Ich bin auch in einer Lösung für eine sortierte Eingabearray interessiert

Answer 1

Idea 1
Wenn Sie mit mehreren required Listen vergleichen müssen dann könnten Sie die Eingabeliste sortieren und dann einfach vergleichen sie durch Iterieren. Aber Sortierung ist natürlich nicht zu schnell, aber nicht zu langsam auch nicht. Aber wenn Sie mit mehreren erforderlichen Listen der Aufwand für Sortierung vergleichen könnte schnell amortisieren.

Sobald das Array sortiert Vergleich ist trivial:

for(int i = 0; i < 14; i++)
  if(arr[i] != required[i]) return false;

return true;

Idea 2
Oder wenn die 14 ganze Zahlen sind verschieden / einzigartig Sie einfach required ein HashSet machen und tun

input.Count(i => required.Contains(i)) == 14

Aber ich weiß nicht, ohne es wirklich zu testen, ob das ist schneller als das Sortieren.

Idea 3
Berechnen eines Hash-Schnell die unter Permutationen über die 14 ints invariant ist, und vergleichen es mit dem bekannten Wert von require. Nur wenn die Hash-Matches, die teurer Vergleich tun.

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

Eine kluge Wahl von Werten für hashes könnte es ein wenig verbessern, aber zufällige Werte sollten in Ordnung sein.

Idea 4
Erstellen Sie ein Histogramm:

int[] CreateHistogram(int[] ints)
{
  int[] counts = new int[34];
  foreach(int i in ints)
  {
    counts[i - 1]++;
  }

  return counts;
}

Sie können das Array durch die Wiederverwendung eines vorhandenen Array erstellen vermeiden, wenn die Leistung ist wirklich wichtig.

Answer 2

Wenn Sie ein 34+ integraler Typ verfügbar Bit und C-Stil Operationen biß, dann könnte man so eine ganze Zahl V aus der Variablenliste berechnen (wenn die Liste v [0], v [1], ... dann ist V (1 << v [0]) | (1 << v [1]), ..., wo 1 von der gleichen Art wie V ist) und haben eine solche vordefinierte Ganzzahl S für die statische Liste analog berechnet. Der Test, um zu sehen, ob die statische Liste in der Variablenliste enthalten ist, ist dann (S & ~ V) == 0.

Answer 3

Eine Möglichkeit ist es, die Art und Weise zu ändern, dass Sie die Daten speichern. Da der Bereich der möglichen Werte auf 1-34 beschränkt ist, sondern eine Liste von Zahlen zu speichern, müssen Sie die Zählungen jeder Zahl vorhanden speichern können:

int[] counts = new int[34];

Wenn Ihre Liste hat eine 1 und zwei 3s, dann zählt [0] == 1 && zählt [2] = 2 (Sie abwechselnd 1-basierte Indizierung verwenden könnten, wenn die Dinge machen schneller (weniger Subtraktionen.))

Nun zu bewerten, dass jeder int in einer Liste mindestens einmal erscheint, geben Sie einfach Index in das Array sequentiell für jeden x und stellen Sie sicher, dass alle Zählungen [x]> 0: Es wird Overhead mit der Transformation der Daten aus den Zählungen in Verbindung gebracht werden Form in die Liste Form, aber das nur ein Problem, wenn Sie auch die Daten in der Form einer Liste sehen müssen häufig. Ein weiterer Vorteil dieses Speicherformat besteht darin, dass das Hinzufügen / Entfernen zu Zählungen wird nie mehr als ein einzelne Array-Element beinhaltet; in der Liste Form bringt eine Kopie von mehreren Elementen ein Element in der Mitte der Liste zu entfernen.

Answer 4

Wenn Sie schnellen Art und Weise wollen Sie nicht Linq verwenden sollten, wenn ein gegebenes Listenelement all unten 35 ist, können Sie if (lst[i] < 35) entfernen Der Balg Antwort Querungs Liste höchstens einmal, und verhält sich wie 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;
}

für sortierte Liste, wenn Listengröße ist groß, dass man lst.BinarySearch(array[i]) tun kann, die 14 * log nimmt (n) * c1 höchstens, und ich denke, es ist auch leistungsfähig genug ist, wenn Sie es schneller geworden sein implementieren kann, und ich habe nicht Test binäre Suche mit meiner eigenen Implementierung, aber Min, Max, Sort in Linq ist langsamer als (zwischen 4 und 10 Mal), um Ihre eigene (gut) Umsetzung. Und wenn sortierte Liste der Größe klein ist, bevorzugen i-Algorithmus zu verwenden, wie oben, weil Konstante c1 ist in obigen Algorithmus klein und können in binären Suchalgorithmus größer sein.

Answer 5

Das sieht wie ein guter Kandidat für die bitweise Operationen, da die Werte in erforderlich sind verschieden, statisch, und zwischen 1 und 34. Anstelle des Sparens als Array erforderlich, speichern Sie sie als const ulong. In Ihrem Arrays zu überprüfen, erstellen Sie eine neue ulong bevölkert von Linksverschiebung jeder Wert und bit- oder.

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

Answer 6

Edit: Also ich Ihre Frage verstanden und haben wahrscheinlich einige schöne Über komplizierte Lösung. Eine andere Frage ist, wie gut die Leistung hat.

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

Answer 7

Sie könnten leicht Schleife durch die Elemente und finden Sie heraus gibt es ein fehlendes Element. Durch Ihr Beispiel verstehe ich Sie wollte nur wissen, ob es einen Eintrag aus erforderlich ist, ist in Reihe fehlt. so könnte man schreiben

bool notContains = false;

foreach (var iddd in required)
{
    foreach (var ar in array)
    {
        if (iddd == ar) notContains=true;
    }

    if (notContains == false) break;
}

Das ist viel schneller als Ihr Ansatz. Schauen Sie sich den Code unten mit Timer hinzugefügt. Ihr Ansatz dauerte 5 ms, aber die neue nehmen 0 ms

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