Wie funktioniert "GROUP BY" mathematisch?

Question

Ich habe eine Datenstruktur von Schlüsselwertpaaren und ich möchte "GROUP BY" Wert implementieren. Beide Schlüssel und Werte sind Zeichenfolgen.

Also was ich getan habe war, dass ich jedem Wert (String) eine eindeutige "Primzahl" gegeben habe. Dann habe ich für jeden Schlüssel die Multiplikation aller Primzahlen gespeichert, die mit verschiedenen Werten eines bestimmten Schlüssels verknüpft sind. Also wenn Schlüssel "Anirudh" ​​Werte "x", "y", "z" hat, dann speichere ich die Zahl M (Schlüssel) = 2 * 3 * 5 = 30. Später, wenn ich eine Gruppe mit einem bestimmten Wert "x" (sagen wir) machen möchte, dann iteriere ich einfach über alle Schlüssel und teile die M (Schlüssel) durch die Primzahl, die mit "x" verknüpft ist. Ich überprüfe dann, ob der Rest 0 ist und wenn er Null ist, dann ist dieser bestimmte "Schlüssel" ein Teil der Gruppe um für den Wert "x".

Ich weiß, dass dies der komischste Weg ist, es zu tun. Manche Leute sortieren die Schlüsselwertpaare (sortiert nach Werten). Ich hätte auch eine andere Tabelle (Hash-Tabelle) erstellen können, die bereits nach "Werten" gruppiert ist. Ich möchte also eine bessere Methode kennen als meine (es müssen viele sein). In meiner Methode als die Anzahl der eindeutigen Werte für einen bestimmten Schlüssel erhöht sich auch das Produkt der Primzahl (das zu exponentiell).

Answer 1

Ihre Methode führt immer O (n) durch, um Gruppenmitglieder zu finden, da Sie alle Elemente der Sammlung durchlaufen müssen, um Elemente zu finden, die zur Zielgruppe gehören. Ihre Methode birgt auch das Risiko, dass allgemeine Integer-Grenzen überschritten werden (32, 64 Bit), wenn Sie viele Elemente haben, da Sie möglicherweise eine große Anzahl von Primzahlen multiplizieren, um Ihren Schlüssel zu bilden.

Sie werden es effizienter und sicherlich vorhersehbarer finden, eine Bitmaske zu verwenden, um Gruppenzugehörigkeiten nach diesem Ansatz zu verfolgen. Wenn Sie 16 Gruppen haben, können Sie das mit einer 16-Bit-Kurzform unter Verwendung einer Bitmaske darstellen. Mit Primes, wie Sie vorschlagen, würden Sie eine ganze Zahl mit genügend Bits benötigen, um die Nummer 32589158477190044730 zu halten (die ersten 16 Primzahlen multipliziert), die 65 Bits erfordern würde.

Andere Ansätze zur Gruppierung sind auch O (n) für die erste Iteration (schließlich muss jedes Element mindestens einmal für die Gruppenzugehörigkeit getestet werden). Wenn Sie jedoch dazu neigen, die gleichen Gruppenprüfungen zu wiederholen, sind die anderen Methoden, auf die Sie verweisen (z. B. das Führen einer Listen- oder Hashtabelle pro Zielgruppe), viel effizienter, weil nachfolgende Gruppenmitgliedschaftstests 0 (1) sind.

So direkt Ihre Frage zu beantworten:

• Wenn es mehrere Anfragen für Gruppenmitgliedschaft (Wiederholung einiger Gruppen) sind, jede Lösung, die die Gruppen speichert (einschließlich denen, die Sie in Ihrer Frage vorschlagen) wird eine bessere Leistung als deine Methode.
• Wenn es keine Wiederholung Anfragen für Gruppenmitgliedschaft sind, gibt es keinen Vorteil für die Gruppenmitgliedschaft zu speichern

Da Wiederholungsanfragen wahrscheinlich auf Ihre Frage basiert scheinen:

• Verwenden einer Struktur, wie ein Listen Sie eine Gruppen-ID aus, um eine Gruppenmitgliedschaft zu speichern, wenn Sie den Speicher tauschen möchten, um mehr Geschwindigkeit zu erhalten.
• Verwenden Sie ein angemessen breites Bit-Array, um die Gruppenmitgliedschaft zu speichern, wenn Sie mit der Geschwindigkeit arbeiten möchten, um weniger Speicher zu verwenden.

Answer 2

Wenn ich keine Ahnung habe, was hier gefragt wird, klingt das ähnlich (aber viel rechenintensiver) als ein Bitvektor oder eine Summe von Potenzen von 2. Der erste Wert ist "1", der zweite ist "2" , dritte ist "4" und so weiter. Wenn Sie "7" haben, wissen Sie, dass es "erste" + "zweite" + "dritte" ist.