Was ist der beste Weg, um die meisten wiederkehrenden Werte in einem Satz zu finden? Ich würde gerne einen One-Pass-Algorithmus verwenden, unter der Annahme, dass die Werte aus der 1,2,3,4, .., m-Domäne stammen?Der beste Weg, um wiederkehrende Werte in einem Satz zu finden
Wenn ich einen Algorithmus schreiben müsste, wie würde ich das tun?
speichern sie in einer Hash-Tabelle mit einer Zählung, wie viele Male jeder gespeichert wurde (O (n)).
Dann Schleife durch die Eimer (O (n)).
Vielen Dank Mike für Ihren Kommentar ... –
Gern geschehen. Ich mag die einfachen. –
Was ist mit O (logn) ???? Gibt es eine Möglichkeit, O (log n) anstelle von O (n) zu erhalten? –
SELECT value
FROM table
GROUP BY
value
ORDER BY
COUNT(*) desc
LIMIT 1
Nun, ich weiß wie es in Form von SQL-Abfrage zu tun .. meine Frage ist, wenn ich einen psuedocode für die alogoritham, die dies in One-Pass-Algoritham (ein Tuple zu einer Zeit) tut, wie es tun? Angenommen, Sie haben Speicher nicht größer als log (m). –
Warum referenzieren Sie überhaupt SQL in Ihrer Frage? Es klingt, als würden Sie nach einem Allzweckalgorithmus für eine beliebige Datenstruktur fragen, die eine Relation darstellt. –
Ok ... sorry für die Kofusion ... ja das ist was ich frage ... danke .. –
SELECT value, COUNT(*) frequency
FROM table
GROUP BY value
ORDER BY COUNT(*) DESC
danke ... für Ihre Antwort –
Per Definition enthält ein Set nur eindeutige Werte. Daher sollte die Antwort die Menge selbst sein, die in konstanter Zeit "berechnet" werden kann. :-)
Ernsthaft, vorausgesetzt, dass Sie tatsächlich mit einem Heap, Liste, Vektor oder einer anderen Datenstruktur arbeiten, die Duplikate ermöglicht, ist wahrscheinlich die schnellste Möglichkeit, das Problem zu lösen, die Antwort von Mike Dunlavey, die ist eine Hashtabelle verwenden. Es gibt auch einige Techniken mit Bäumen, die Sie verwenden könnten, die sukzessive raffiniertere Schätzungen verwenden. Ich denke, ein solcher Ansatz wäre O (n log n) (nicht so gut wie die Hashtabellösung), obwohl er möglicherweise so niedrig wie O (log n) sein könnte, wenn Sie einen statistischen Fehler zulassen.
Vielen Dank für Ihren Kommentar. Werte sind nicht eindeutig. Die Tabelle wird Duplikate enthalten.Es ist nur so, dass die Werte aus der Domäne (1,2,3,4 ... m) stammen. –
Würde es Ihnen etwas ausmachen, Ihre Frage zu aktualisieren? "SQL-Frage" ist nicht sehr intuitiv. Etwas wie "Der beste Weg, um wiederkehrende Werte in SQL zu finden", wäre viel einfacher für die Menschen, Ihre Frage zu verstehen, auch ohne sie einzugeben. –
@Nimesh: Da die Kommentare zu der Antwort von @ Quassnoi anzeigen, dass dies überhaupt keine SQL-Frage ist, habe ich die "SQL" daraus entfernt. Roll meine Bearbeitung zurück, wenn du musst. (Aber ich würde ein paar Umformulierungen empfehlen, wenn die Frage jetzt nicht Ihre Bedürfnisse widerspiegelt. Die vorherige Version von Ihnen passte auch nicht zu Ihren Bedürfnissen.) – Tomalak
Vielen Dank für die Bearbeitung. Tomalak .. –