Am effizientesten Weg, um das 99. Perzentil eines Datensatzes zu berechnen

Ich habe 100 Integer in meiner Datenbank. Ich sortiere sie in aufsteigender Reihenfolge. Gerade jetzt für das 99. Perzentil nehme ich die 99. Nummer nach dem Sortieren.Am effizientesten Weg, um das 99. Perzentil eines Datensatzes zu berechnen

nach einer bestimmten Zeit t, eine neue Nummer kommen in die Datenbank und eine ältere Nummer verworfen wird. Der aktuelle Code nehmen Sie einfach die 100 Integer und sortieren sie alle wieder.

Da gibt es 99 Zahlen, die durch die Menge der ursprünglichen 100 ganzen Zahlen geteilt werden und die Menge von 100 ganzen Zahlen nach der Zeit t. Gibt es eine effizientere Methode zur Berechnung des 99. Perzentils, 95. Perzentils, 90. Perzentils und so weiter?

PS: All dies unter MySQL-Datenbank erfolgt

Quelle

2016-09-08 Laughing Day

Wenn Sie eine Datenbank verwenden, d. H. MySQL, glaube ich nicht, dass Sie die Effizienz nicht über die Verwendung eines Index hinaus steigern können. Andere haben vielleicht bessere Ideen. Wenn Sie Ihre eigene sortierte Datenstruktur codieren, optimieren Sie Code-Einfügungen und -Löschungen mithilfe einer binären Suchsuche. – mba12

Sorry, ich habe vergessen zu erwähnen, dass alles unter MySQL-Datenbank erfolgt. –

(@ mba12: 'Ich glaube nicht, dass du nicht in der Lage sein wirst ...' - bitte versuche, mehrfache Negationen zu vermeiden.) – greybeard

Nennen wir N die Größe des Array A (hier N = 100) und Sie suchen das K -te kleinste Element (nach einigen Änderungswünsche).

Die einfachste Lösung ist wahrscheinlich eine Art von modifizierter Einfügesortierung: Sie behalten ein (sortiertes) Array der N-K+1 größten Elemente (nennen wir es B).

ein Element Discard e: zu Fuß durch B (z.B. während B[i] < e) (*). Wenn B[i] = e, alle Elemente < i nach rechts verschieben.
Fügen Sie ein Element e: Holen Sie sich den unteren Index i, so dass B[i] > e. Verschiebe alle Elemente >= i nach rechts und setze B[i] := e.
Holen Sie sich die K -te kleinere Element: zurück B[0].

Zeitkomplexität: O(N-K) pro Anfrage.

(*) Eigentlich könnten Sie den Suchschritt mit der binären Suche beschleunigen, aber es wird nicht die gesamte zeitliche Komplexität ändern.

Wenn N-K sehr groß ist, wäre es interessant stattdessen Binärbäume zu verwenden (mit einer O(log(N-K)) Zeitkomplexität pro Anfrage). Aber angesichts der tatsächlichen Größe Ihrer Datensätze (und Ihrer Programmiersprache) wird es nicht "gewinnbringend" sein.

Quelle

2016-09-08 23:29:45 md5

Ich muss MySQL verwenden, obwohl –

@LaughingDay: Ich weiß nicht, MySQL, aber es sieht aus wie es gibt ein Konzept von [Schleifen] (https://dev.mysql.com/doc/refman/5.7/en/loop .html) und Sie können Arrays mit [temporären Tabellen] emulieren (http://stackoverflow.com/questions/12176709/how-can-i-simulate-an-array-variable-in-mysql). Die erste Lösung ist in den meisten gängigen Programmiersprachen nur ~ 10 Zeilen lang, in MySQL sollte es auch nicht so schwer sein, sie zu programmieren. – md5

Was ist, wenn der Datensatz sehr groß ist und das Hinzufügen und Entfernen von Werten häufig ist? Wenn Sie dann jedes Mal eine temporäre Tabelle behalten, würde das die Leistung beeinträchtigen und viel Speicherplatz beanspruchen, nein? –

Wenn Ihre Daten zufällig verteilt sind, könnten Sie versuchen, die Position zu erraten durch eine lineare Verteilung angenommen wird.

guessPosition = NewNumber * (Max-Min)/100

Und dann von diesem Punkt aus einen Galopp Suche machen.

Und wenn gefunden, legen Sie es an der richtigen Stelle ein.

Quelle

2016-09-08 22:26:42 Surt

Wie mache ich das in MySql? –

Am effizientesten Weg, um das 99. Perzentil eines Datensatzes zu berechnen

Antwort

Verwandte Themen