Nichttrivialer Algorithmus zur Berechnung eines Gleitfenstermedians

Ich muss den laufenden Median berechnen:

Eingabe: $n$ , $k$ , Vektor $(x_1, x_2, \dotsc, x_n)$ .
Ausgabe: Vektor $(y_1, y_2, \dotsc, y_{n-k+1})$ , wobei $y_i$ der Median von $(x_i, x_{i+1}, \dotsc, x_{i+k-1})$ .

(Kein Schummeln mit Näherungen; ich hätte gerne genaue Lösungen. Elemente sind große ganze Zahlen.) $x_i$

Es gibt einen einfachen Algorithmus, der einen Suchbaum der Größe . Die Gesamtlaufzeit beträgt . (Hier bezieht sich ein "Suchbaum" auf eine effiziente Datenstruktur, die Einfügungen, Löschungen und mittlere Abfragen in logarithmischer Zeit unterstützt.) $k$ $O(n \log k)$

Das kommt mir allerdings etwas blöd vor. Wir werden effektiv alle Ordnungsstatistiken in allen Fenstern der Größe lernen , nicht nur die Mediane. Darüber hinaus ist dies in der Praxis nicht allzu attraktiv, insbesondere wenn groß ist (große Suchbäume sind in der Regel langsam, der Overhead beim Speicherverbrauch ist nicht trivial, die Cache-Effizienz ist oft schlecht usw.). $k$ $k$

Können wir etwas wesentlich besser machen?

Gibt es Untergrenzen (z. B. ist der Trivialalgorithmus für das Vergleichsmodell asymptotisch optimal)?

Edit: David Eppstein gab eine schöne Untergrenze für das Vergleichsmodell! Ich frage mich, ob es trotzdem möglich ist, etwas Klügeres als den trivialen Algorithmus zu tun.

Könnten wir zum Beispiel etwas in diese Richtung tun: Teilen Sie den Eingabevektor in Teile der Größe ; sortiere jeden Teil (verfolge die ursprünglichen Positionen jedes Elements); und dann den stückweise sortierten Vektor verwenden, um die laufenden Mediane ohne zusätzliche Datenstrukturen effizient zu finden? Natürlich wäre dies immer noch , aber in der Praxis ist das Sortieren von Arrays in der Regel viel schneller als das Verwalten von Suchbäumen. $k$ $O(n \log k)$

Bearbeiten 2: Saeed wollte einige Gründe sehen, warum das Sortieren meiner Meinung nach schneller ist als Suchbaumoperationen. Hier sind sehr schnelle Benchmarks für , : $k = 10^7$ $n = 10^8$

≈ 8s: Sortieren von Vektoren mit jeweils Elementen $n/k$ $k$
≈ 10s: Sortierung eines Vektors mit Elementen $n$
≈ 80s: Einfügungen und Löschungen in einer Hash-Tabelle der Größe $n$ $k$
≈ 390s: Einfügungen und Löschungen in einem ausgeglichenen Suchbaum der Größe $n$ $k$

Die Hash-Tabelle dient nur zum Vergleich. Es ist in dieser Anwendung nicht direkt von Nutzen.

Zusammenfassend lässt sich sagen, dass sich die Sortierleistung im Vergleich zu ausgeglichenen Suchbaumoperationen um fast den Faktor 50 unterscheidet. Und es wird noch schlimmer, wenn wir erhöhen . $k$

(Technische Details: Daten = zufällige 32-Bit-Ganzzahlen. Computer = ein typischer moderner Laptop. Der Testcode wurde in C ++ unter Verwendung der Standard-Bibliotheksroutinen (std :: sort) und Datenstrukturen (std :: multiset, std :: unsorted_multiset). Ich habe zwei verschiedene C ++ - Compiler (GCC und Clang) und zwei verschiedene Implementierungen der Standardbibliothek (libstdc ++ und libc ++) verwendet. Traditionell wurde std :: multiset als hochoptimierter Rot-Schwarz-Baum implementiert.)

ds.algorithms ds.data-structures lower-bounds Jukka Suomela
quelle

Ich glaube nicht , Sie in der Lage sein zu verbessern

. Der Grund dafür ist, wenn Sie an einem Fenster schauen

n l o g k

$nlogk$

x_{t}, . . ., x_{t + k - 1}

$x_t,...,x_{t+k-1}$ , können Sie niemals eine der Zahlen

als Median des zukünftigen Fensters. Dies bedeutet, dass Sie in jeder Zeit mindestens

x_{t + \frac{k}{2}}, . . ., x_{t + k - 1}

$x_{t+\frac{k}{2}},...,x_{t+k-1}$

Ganzzahlen in einer Datenstruktur, und die Aktualisierung scheint nicht kürzer als die Protokollierungszeit zu sein.

\frac{k}{2}

$\frac{k}{2}$

Ihr trivialer Algorithmus scheint für mich

nicht

, habe ich etwas falsch verstanden? Und ich denke deswegen hast du ein Problem mit big

, sonst ist der logarithmische Faktor in praktischen Anwendungen nichts, und es gibt keine große versteckte Konstante in diesem Algorithmus.

O ((n - k) \cdot k \cdot \log k)

$O((n-k)\cdot k \cdot \log k)$

O (n \log k)

$O(n \log k)$

k

$k$

Saeed

@ Saeed: Im einfachen Algorithmus verarbeiten Sie Elemente nacheinander. In Schritt

fügen Sie

zum Suchbaum hinzu und (wenn

) entfernen Sie auch

aus dem Suchbaum. Dies sind

Schritte, von denen jeder eine Zeit von

i

$i$

x_{i}

$x_i$

i > k

$i > k$

x_{i - k}

$x_{i-k}$

n

$n$

O (\log k)

$O(\log k)$

Jukka Suomela

Sie meinen also, Sie haben einen ausgeglichenen Suchbaum, keinen zufälligen Suchbaum?

Saeed

@ Saeed: Bitte beachten Sie, dass ich in meinen Benchmarks nicht einmal versucht habe, Mediane zu finden. Ich habe gerade

Einfügungen und

Löschungen in einem Suchbaum der Größe

, und diese Operationen werden garantiert

Zeit in Anspruch nehmen . Sie müssen nur akzeptieren, dass Suchbaumoperationen in der Praxis im Vergleich zur Sortierung sehr langsam sind. Sie werden dies leicht erkennen, wenn Sie versuchen, einen Sortieralgorithmus zu schreiben, der durch Hinzufügen von Elementen zu einem ausgeglichenen Suchbaum funktioniert - dies funktioniert sicherlich in

n

$n$

n

$n$

k

$k$

O (\log k)

$O(\log k)$

-Zeit, ist aber in der Praxis lächerlich langsam und verschwendet auch viel der Erinnerung.

O (n \log n)

$O(n \log n)$

Jukka Suomela

Antworten:

Hier ist eine Untergrenze für das Sortieren. Erstellen Sie für einen zu sortierenden Eingabesatz der Länge eine Eingabe für Ihr laufendes Medianproblem, die aus Kopien einer Zahl kleiner als das Minimum von , dann aus selbst und dann aus Kopien einer Zahl größer als besteht das Maximum von und setze . Die laufenden Mediane dieser Eingabe stimmen mit der sortierten Reihenfolge von . $S$ $n$ $n-1$ $S$ $S$ $n-1$ $S$ $k=2n-1$ $S$

Also in einem Vergleichsmodell der Berechnung, Zeit erforderlich. Wenn es sich bei Ihren Eingaben möglicherweise um Ganzzahlen handelt und Sie Ganzzahl-Sortieralgorithmen verwenden, können Sie dies besser tun. $\Omega(n\log n)$

David Eppstein
quelle

Diese Antwort lässt mich wirklich fragen, ob auch die Umkehrung zutrifft: Erhalten wir bei einem effizienten Sortieralgorithmus einen effizient ausgeführten Median-Algorithmus? (Bedeutet ein effizienter Ganzzahl-Sortieralgorithmus beispielsweise einen effizient ausgeführten Median-Algorithmus für Ganzzahlen? Oder liefert ein IO-effizienter Sortieralgorithmus einen IO-effizient ausgeführten Median-Algorithmus?)

Jukka Suomela,

Nochmals vielen Dank für Ihre Antwort, es hat mich wirklich auf den richtigen Weg gebracht und mich zu dem sortierungsbasierten Medianfilter-Algorithmus inspiriert! Am Ende konnte ich einen Artikel aus dem Jahr 1991 finden, der im Grunde das gleiche Argument enthielt wie Sie, und Pat Morin gab einen Hinweis auf einen anderen relevanten Artikel aus dem Jahr 2005; siehe refs. [6] und [9] hier .

Jukka Suomela

Bearbeiten: Dieser Algorithmus wird jetzt hier vorgestellt: http://arxiv.org/abs/1406.1717

Ja, um dieses Problem zu lösen, ist es ausreichend, die folgenden Vorgänge auszuführen:

Sortieren Sie Vektoren mit jeweils Elementen. $n/k$ $k$
Führen Sie eine zeitlineare Nachbearbeitung durch.

Grob gesagt lautet die Idee:

Man betrachte zwei benachbarte Eingangsblöcke und , beide mit Elementen; lassen Sie die Elemente sein , und in der Reihenfolge des Auftretens im Eingabevektor . $a$ $b$ $k$ $a_1, a_2, ..., a_k$ $b_1, b_2, ..., b_k$ $x$
Sortieren Sie diese Blöcke und lernen Sie den Rang jedes Elements innerhalb des Blocks.
Erweitern Sie die Vektoren und mit Vorgänger- / Nachfolgerzeigern, sodass wir die Elemente in aufsteigender Reihenfolge durchlaufen können, indem wir den Zeigerketten folgen. Auf diese Weise haben wir doppelt verknüpfte Listen und konstruiert . $a$ $b$ $a'$ $b'$
Einer nach dem anderen, löschen Sie alle Elemente aus der verknüpften Liste , in der umgekehrten Reihenfolge des Erscheinens . Wenn wir ein Element löschen, merken Sie sich, was zum Zeitpunkt des Löschens sein Nachfolger und Vorgänger war . $b'$ $b_k, b_{k-1}, ..., b_1$
Behalten Sie nun die "Medianzeiger" und , die auf die Listen und . Initialisiere bis zum Mittelpunkt von und initialisiere bis zum Ende der leeren Liste . $p$ $q$ $a'$ $b'$ $p$ $a'$ $q$ $b'$
Für jedes : $i$
- Löschen Sie aus der Liste (dies ist Mal, löschen Sie es einfach aus der verknüpften Liste). Vergleichen Sie mit dem Element, auf das um festzustellen, ob wir vor oder nach gelöscht haben . $a_i$ $a'$ $O(1)$ $a_i$ $p$ $p$
- Setzen Sie wieder in die Liste an seiner ursprünglichen Position (dies ist Mal, wir haben den Vorgänger und Nachfolger von auswendig gelernt ). Vergleichen Sie mit dem Element, auf das , um , ob wir das Element vor oder nach hinzugefügt haben . $b_i$ $b'$ $O(1)$ $b_i$ $b_i$ $q$ $q$
- Update Zeiger und , so dass der Medianwert der verbundenen Liste ist entweder auf oder . (Dies ist Mal. Folgen Sie einfach den verknüpften Listen in ein oder zwei Schritten, um alles zu reparieren. Wir werden verfolgen, wie viele Elemente vor / nach und in jeder Liste sind, und wir werden die Invariante beibehalten, dass beide und auf Elemente zeigen, die so nah wie möglich am Median liegen.) $p$ $q$ $a' \cup b'$ $p$ $q$ $O(1)$ $p$ $q$ $p$ $q$

Die verknüpften Listen sind nur Element-Arrays von Indizes, daher sind sie leichtgewichtig (mit der Ausnahme, dass die Lokalität des Speicherzugriffs schlecht ist). $k$

Hier ist eine Beispielimplementierung und Benchmarks:

https://github.com/suomela/median-filter

Hier ist eine Darstellung der Laufzeiten (für ): $n \approx 2\cdot 10^6$

Blau = Sortieren + Nachbearbeitung, $O(n \log k)$ .
Grün = Erhalte zwei Haufen, $O(n \log k)$ , Implementierung von https://github.com/craffel/median-filter
Rot = zwei Suchbäume pflegen, $O(n \log k)$ .
Schwarz = Beibehaltung eines sortierten Vektors, $O(n k)$ .
X - Achse = Fenstergröße ( $\approx k/2$ ).
Y-Achse = Laufzeit in Sekunden.
Daten = 32-Bit-Ganzzahlen und zufällige 64-Bit-Ganzzahlen aus verschiedenen Verteilungen.

Laufzeiten

Jukka Suomela
quelle

In Anbetracht von Davids Grenzen ist es unwahrscheinlich, dass Sie einen besseren Worst-Case-Fall erzielen können, aber es gibt bessere ausgangssensitive Algorithmen. Insbesondere wenn in der Anzahl der Mediane im Ergebnis ist, können wir das Problem in der Zeit lösen . $m$ $O(n \log m + m \log n)$

$O(\log m)$ $O(\log n)$ $O(\log n)$ Die Aufladung erfolgt nur einmal pro Median.

$O(n \log m + m \log k)$

Geoffrey Irving
quelle

Hoppla, dies funktioniert nicht wie geschrieben, da die Anzahl der Elemente nicht das neue Fenster widerspiegelt, wenn Sie keine Elemente löschen. Ich bin nicht sicher, ob es behoben werden kann, aber ich werde die Antwort hinterlassen, falls es einen Weg gibt.

Geoffrey Irving

O (n \log m)

$O(n \log m)$

Randnotiz: Frage ist nicht klar, untergeordnete Datenstruktur ist nicht definiert, wir wissen nur etwas sehr vages. Wie wollen Sie etwas verbessern, von dem Sie nicht wissen, was es ist? Wie wollen Sie Ihren Ansatz vergleichen?

Saeed

Ich entschuldige mich für die unvollständige Arbeit. Ich habe hier die konkrete Frage gestellt, die zur Behebung dieser Antwort erforderlich ist: cstheory.stackexchange.com/questions/21778/… . Wenn Sie es für angebracht halten, kann ich diese Antwort entfernen, bis die zweite Frage geklärt ist.

Geoffrey Irving