Ich möchte Entropie und gegenseitige Informationen im leistungskritischen Code sehr oft berechnen. Als Zwischenschritt muss ich die Anzahl der Vorkommen jedes Wertes zählen. Zum Beispiel:
%Vor%Natürlich sind die offensichtlichen Wege, dies zu tun, entweder ein assoziatives Array oder das Sortieren des Eingangsarrays unter Verwendung eines "Standard" -Sortieralgorithmus wie Schnellsortierung. Für kleine ganze Zahlen, wie Bytes, ist der Code derzeit spezialisiert, um ein einfaches altes Array zu verwenden.
Gibt es einen cleveren Algorithmus, um dies effizienter zu tun als eine Hash-Tabelle oder ein "Standard" -Sortieralgorithmus, wie eine assoziative Array-Implementierung, die Updates gegenüber Einfügungen stark begünstigt, oder einen Sortieralgorithmus, der glänzt, wenn Ihre Daten ein Viele Krawatten?
Hinweis: Ganzzahlige Ganzzahlen sind nur ein Beispiel für einen möglichen Datentyp. Ich möchte hier eine einigermaßen generische Lösung implementieren, da aber Ganzzahlen und Strukturen, die nur ganze Zahlen enthalten, häufige Fälle sind, würde ich mich für spezielle Lösungen interessieren, wenn sie extrem effizient sind.
Bitte erzählen Sie mehr über Ihre Daten.
In jedem Fall schlage ich folgende Idee vor: einen Mergesort, der so modifiziert wurde, dass er Duplikate zählt.
Das heißt, Sie arbeiten nicht in Zahlen, sondern in Paaren (Zahl, Häufigkeit) (Sie könnten dafür eine clevere, speichereffiziente Darstellung verwenden, zum Beispiel zwei Arrays anstelle eines Arrays von Paaren etc.).
Sie beginnen mit [(x1,1), (x2,1), ...] und führen einen Mergesort wie üblich aus, aber wenn Sie zwei Listen zusammenführen, die mit demselben Wert beginnen, fügen Sie den Wert in die Ausgabe ein Liste mit ihrer Summe von Vorkommen. In Ihrem Beispiel:
%Vor%Dies könnte sehr verbessert werden, indem man einige clevere Tricks anwendet, um das Array zu initialisieren (man erhält ein Array von Wert: Vorkommenspaaren, das viel kleiner ist als das Original, aber die Summe des 'Vorkommens' für jeden 'Wert' ist gleich der Anzahl der Vorkommen von 'Wert' im ursprünglichen Array. Teilen Sie das Array beispielsweise in fortlaufende Blöcke auf, deren Werte sich um nicht mehr als 256 oder 65536 unterscheiden, und verwenden Sie ein kleines Array zum Zählen von Vorkommen innerhalb jedes Blocks. Tatsächlich kann dieser Trick auch in späteren Zusammenführungsphasen angewendet werden.
Hashing ist im Allgemeinen besser skalierbar, wie eine andere Antwort zeigt. Für viele mögliche Verteilungen (und viele Fälle im wirklichen Leben, in denen Subarrays zufällig sortiert werden, je nachdem, wie das gesamte Array zusammengesetzt wurde), timsort ist oft "übernatürlich gut" (näher an O (N) als an O (N log N)) - Ich habe gehört, dass es wahrscheinlich zum Standard wird / Standard-Sortieralgorithmus in Java bei einigen relativ nahen Zukunftsdaten (seit Jahren der Standard-Sortieralgorithmus in Python).
Es gibt keine wirklich gute Möglichkeit, solche Probleme anzugehen, es sei denn, es werden Benchmarks für eine Auswahl von Fällen erstellt, die für das tatsächliche Arbeitsaufkommen repräsentativ sind (mit dem offensichtlichen Risiko, dass Sie eine Stichprobe tatsächlich auswählen) voreingenommen / nicht repräsentativ - das ist kein geringes Risiko, wenn Sie versuchen, eine Bibliothek zu erstellen, die von vielen externen Benutzern außerhalb Ihrer Kontrolle verwendet wird.
Bei einem Array von ganzen Zahlen wie im Beispiel wäre es am effizientesten, ein Array von int s zu haben und es basierend auf Ihren Werten zu indizieren (wie Sie es bereits tun).
Wenn Sie das nicht können, kann ich mir keine bessere Alternative als eine Hashmappe vorstellen. Sie brauchen nur einen schnellen Hashalgorithmus. Sie können nicht besser als O (n) Leistung, wenn Sie alle Ihre Daten verwenden möchten. Ist es eine Option, nur einen Teil der Daten zu verwenden, die Sie haben?
(Beachten Sie, dass das Sortieren und Zählen asymptotisch langsamer ist (O (n * log (n))) als die Verwendung einer hashmapbasierten Lösung (O (n)).)
Tags und Links algorithm language-agnostic performance data-structures statistics