Effiziente Möglichkeit zum Gruppieren, Sortieren und Zurückgeben der ersten N Ergebnisse

Ich habe einen Stream (oder eine lange Liste von Elementen, könnte Tausende oder Millionen sein), und ich muss die ersten N Gruppen (24 in meiner Situation) sortiert nach der Durchschnitt der Gruppe. So sind Elemente in der Form:Effiziente Möglichkeit zum Gruppieren, Sortieren und Zurückgeben der ersten N Ergebnisse

{groupId: 1, value: 10}, {groupId: 2, value: 4}, {groupId: 1: value: 2}

und bilden Gruppen:

{groupId: 1, average: 6}, {groupId: 2: average}

Klar, dass die naive Lösung ist iterieren, gruppieren, sortieren Gruppen von durchschnittlich und geben die ersten 24 Gruppen. Irgendeine Idee für eine Hochleistungslösung, die mit Millionen von Artikeln umgehen kann?

Quelle

2016-07-06 agori

Wenn Sie die Gruppen nach ihrem Durchschnitt sortieren möchten, gibt es keine Möglichkeit, die gesamte Liste zu durchlaufen. Aber selbst für "Millionen" sollte dies kein großes Problem darstellen. –

Hmm. Sie haben nicht gesagt, um welche Art von Daten es sich handelt. Vielleicht können Sie eine Micro-Batch-App wie Apache Spark oder Apache Storm verwenden –

@CaptainFogetti diese Daten stammen aus Lucene-Index, und ich versuche, einen Lucene Collector für meinen Anwendungsfall zu implementieren. – agori

Sie können nicht über die gesamte Liste iterieren, um jedes Mitglied einer bestimmten Gruppe zu erhalten. Sobald Sie jede Gruppe zur Verfügung mit seinem Mittelwert haben, können Sie folgendes tun:

Nehmen Sie die N ersten Gruppen in einen Vektor/Array.
Erstellen Sie einen Heap so aus dem Array, dass die Spitze des Heap die Gruppe mit dem maximalen Durchschnitt ist.
Für jede verbleibende Gruppe, vergleichen sie mit der Spitze des Haufens:
- Wenn die aktuelle Gruppe größer ist als die Spitze des Haufens ist, entsorgen Sie es
- Wenn sie kleiner ist, knallen die Spitze der N ersten Gruppen in einem Haufen Haufen und der aktuellen Gruppe einfügen

Am Ende Sie alle haben. Sie können sie in der richtigen Reihenfolge abrufen, indem Sie den letzten Schritt einer Heap-Sortierung anwenden und den von Ihnen abgerufenen Container umkehren (weil der Heap ein Max-Heap ist).

Gesamtkomplexität: (wobei K ist die Gesamtzahl von Gruppen und N oben definiert)

O (N + (KN) .ln (N) + N.ln (N) =O (N + K.ln (N))

Der Begriff N kommt von den ersten N Gruppen und die erste Max-Heap.
Der Begriff (K-N) .ln (N) stammt aus den Paaren der Operationen (oberste Gruppe löschen/aktuelle Gruppe einfügen) (maximal K - N von ihnen).
Der letzte Term (N.ln (N)) dient zum Sortieren des letzten Heaps.

Quelle

2016-07-06 12:46:42 Rerito

vielen Dank. Das ist mehr oder weniger das, was Solr tut, um gruppierte Ergebnisse zu sortieren, aber sie verwenden die Max-Funktion anstelle des Durchschnitts. Weißt du, ob diese Art der Sortierung (Sortierung nach ersten N-Elementen) einen Namen im Algorithmusfeld hat? – agori

@agori Nicht, dass ich weiß, aber dieses Problem ist sehr bekannt. Es gibt sogar eine bessere Lösung, die Sie in "Cracking the Coding Interview" IIRC finden können. – Rerito

Ich habe die von Guava implementierte Prioritätswarteschlange verwendet: 'MinMaxPriorityQueue.orderedBy (new MyComparator()) .maximumSize (groupOffset + this.topNGroups) .create();' – agori

Halten Sie einfach für jede Gruppe zwei Werte - Summe der Werte für diese Gruppe und Zähler. Am Ende dividiere die Summe nach Zähler, um den Durchschnitt für diese Gruppe zu erhalten.

Sie können die Informationen für eine begrenzte Anzahl von Gruppen nicht speichern, da jede Gruppe in einem bestimmten Moment eine Führungsrolle übernehmen kann.

Quelle

2016-07-06 08:50:27 MBo

Effiziente Möglichkeit zum Gruppieren, Sortieren und Zurückgeben der ersten N Ergebnisse

Antwort

Verwandte Themen