Algorithme non trivial pour calculer la médiane d'une fenêtre coulissante

J'ai besoin de calculer la médiane en cours d'exécution:

Entrée: , , vecteur . $n$ $k$ $(x_1, x_2, \dotsc, x_n)$
Sortie: vecteur , où est la médiane de . $(y_1, y_2, \dotsc, y_{n-k+1})$ $y_i$ $(x_i, x_{i+1}, \dotsc, x_{i+k-1})$

(Pas de tricherie avec des approximations; je voudrais avoir des solutions exactes. Les éléments $x_i$ sont de grands entiers.)

Il existe un algorithme trivial qui maintient un arbre de recherche de taille $k$ ; la durée totale d'exécution est $O(n \log k)$ . (Ici, un "arbre de recherche" fait référence à une structure de données efficace qui prend en charge les insertions, les suppressions et les requêtes médianes en temps logarithmique.)

Cependant, cela me semble un peu stupide. Nous apprendrons efficacement toutes les statistiques de commande dans toutes les fenêtres de taille $k$ , pas seulement les médianes. De plus, cela n'est pas trop attrayant dans la pratique, surtout si $k$ est grand (les grands arbres de recherche ont tendance à être lents, la surcharge de consommation de mémoire n'est pas anodine, l'efficacité du cache est souvent médiocre, etc.).

Pouvons-nous faire quelque chose de nettement mieux?

Y a-t-il des limites inférieures (par exemple, l'algorithme trivial est-il asymptotiquement optimal pour le modèle de comparaison)?

Edit: David Eppstein a donné une belle borne inférieure pour le modèle de comparaison! Je me demande s'il est néanmoins possible de faire quelque chose d'un peu plus intelligent que l'algorithme trivial?

Par exemple, pourrions-nous faire quelque chose dans ce sens: diviser le vecteur d'entrée en parties de taille $k$ ; trier chaque partie (en gardant une trace des positions d'origine de chaque élément); puis utiliser le vecteur trié par morceaux pour trouver efficacement les médianes en cours d'exécution sans structures de données auxiliaires? Bien sûr, ce serait toujours $O(n \log k)$ , mais dans la pratique, le tri des tableaux a tendance à être beaucoup plus rapide que la maintenance des arbres de recherche.

Edit 2: Saeed voulait voir quelques raisons pour lesquelles je pense que le tri est plus rapide que les opérations d'arbre de recherche. Voici des repères très rapides, pour $k = 10^7$ , $n = 10^8$ :

≈ 8s: tri de $n/k$ vecteurs avec $k$ éléments chacun
≈ 10s: trier un vecteur avec éléments $n$
≈ Années 80: insertions et suppressions dans une table de hachage de taille $n$ $k$
≈ 390s: insertions et suppressions dans un arbre de recherche équilibré de taille $n$ $k$

La table de hachage est là juste pour comparaison; il n'est d'aucune utilité directe dans cette application.

En résumé, nous avons presque un facteur 50 de différence dans les performances du tri par rapport aux opérations d'arborescence de recherche équilibrée. Et les choses empirent si nous augmentons . $k$

(Détails techniques: Données = nombres entiers aléatoires de 32 bits. Ordinateur = un ordinateur portable moderne typique. Le code de test a été écrit en C ++, en utilisant les routines de bibliothèque standard (std :: sort) et les structures de données (std :: multiset, std :: unsorted_multiset). J'ai utilisé deux compilateurs C ++ différents (GCC et Clang), et deux implémentations différentes de la bibliothèque standard (libstdc ++ et libc ++). Traditionnellement, std :: multiset a été implémenté comme un arbre rouge-noir hautement optimisé.)

ds.algorithms ds.data-structures lower-bounds Jukka Suomela
la source

Je ne pense pas que vous pourrez améliorer . La raison en est que si vous regardez une fenêtre , vous ne pouvez jamais exclure aucun des nombres d'être des médianes de la fenêtre future. Cela signifie qu'à tout moment, vous devez conserver au moins entiers dans une structure de données, et il ne semble pas se mettre à jour en moins de temps de journalisation.

n l o g k

$nlogk$

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

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

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

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

\frac{k}{2}

$\frac{k}{2}$

Votre algorithme trivial me semble être pas , est-ce que j'ai mal compris quelque chose? Et je pense qu'à cause de cela, vous avez un problème avec le grand , sinon le facteur logarithmique n'est rien dans les applications pratiques, il n'y a pas non plus de grande constante cachée dans cet algorithme.

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: Dans l'algorithme trivial, vous traitez les éléments un par un; à l'étape vous ajoutez à l'arbre de recherche et (si ) vous supprimez également de l'arbre de recherche. Il s'agit de étapes, chacune prenant du temps .

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

Vous voulez donc dire que vous avez un arbre de recherche équilibré et non un arbre de recherche occasionnel?

Saeed

@Saeed: Veuillez noter que dans mes repères, je n'ai même pas essayé de trouver des médianes. Je viens de faire insertions et suppressions dans un arbre de recherche de taille , et ces opérations sont garanties de prendre du temps . Il vous suffit d'accepter que les opérations d'arborescence de recherche sont très lentes en pratique, par rapport au tri. Vous le verrez facilement si vous essayez d'écrire un algorithme de tri qui fonctionne en ajoutant des éléments à une arborescence de recherche équilibrée - cela fonctionne certainement en temps , mais il sera ridiculement lent en pratique, et gaspillera également un beaucoup de mémoire.

n

$n$

n

$n$

k

$k$

O (\log k)

$O(\log k)$

O (n \log n)

$O(n \log n)$

Jukka Suomela

Réponses:

Voici une limite inférieure du tri. Étant donné un ensemble d'entrée de longueur à trier, créez une entrée pour votre problème médian en cours composé de copies d'un nombre inférieur au minimum de , puis lui-même, puis copies d'un nombre supérieur à le maximum de , et fixons . Les médianes de fonctionnement de cette entrée sont les mêmes que l'ordre de tri de . $S$ $n$ $n-1$ $S$ $S$ $n-1$ $S$ $k=2n-1$ $S$

Ainsi, dans un modèle de comparaison de calcul, un temps est requis. Peut-être que si vos entrées sont des nombres entiers et que vous utilisez des algorithmes de tri des nombres entiers, vous pouvez faire mieux. $\Omega(n\log n)$

David Eppstein
la source

Cette réponse me fait vraiment me demander si l'inverse est également vrai: étant donné un algorithme de tri efficace, obtenons-nous un algorithme médian efficace? (Par exemple, un algorithme de tri d'entiers efficace implique-t-il un algorithme médian de fonctionnement efficace pour les nombres entiers? Ou un algorithme de tri efficace IO fournit-il un algorithme médian de fonctionnement efficace IO?)

Jukka Suomela

Encore une fois, merci beaucoup pour votre réponse, cela m'a vraiment mis sur la bonne voie et a donné l'inspiration pour l'algorithme de filtrage médian basé sur le tri! En fin de compte, j'ai pu trouver un article de 1991 qui présentait essentiellement le même argument que ce que vous donnez ici, et Pat Morin a donné un pointeur vers un autre article pertinent de 2005; voir refs. [6] et [9] ici .

Jukka Suomela

Edit: Cet algorithme est maintenant présenté ici: http://arxiv.org/abs/1406.1717

Oui, pour résoudre ce problème, il suffit d'effectuer les opérations suivantes:

Trier vecteurs, chacun avec éléments. $n/k$ $k$
Faites un post-traitement en temps linéaire.

En gros, l'idée est la suivante:

Considérons deux blocs d'entrée adjacents, et , tous deux avec éléments; laisser les éléments soient et dans l'ordre d'apparition dans le vecteur d'entrée . $a$ $b$ $k$ $a_1, a_2, ..., a_k$ $b_1, b_2, ..., b_k$ $x$
Triez ces blocs et apprenez le rang de chaque élément dans le bloc.
Augmentez les vecteurs et avec des pointeurs prédécesseurs / successeurs afin qu'en suivant les chaînes de pointeurs, nous puissions parcourir les éléments dans un ordre croissant. De cette façon, nous avons construit des listes doublement liées $a$ $b$ $a'$ et . $b'$
Un par un, supprimer tous les éléments de la liste chaînée , dans l'ordre inverse d'apparition . Chaque fois que nous supprimons un élément, rappelez - vous quel était son successeur et prédécesseur au moment de la suppression . $b'$ $b_k, b_{k-1}, ..., b_1$
Maintenant, maintenez les "pointeurs médians" et qui pointent vers les listes et , respectivement. Initialisez au milieu de et initialisez à la fin de la liste vide . $p$ $q$ $a'$ $b'$ $p$ $a'$ $q$ $b'$
Pour chaque : $i$
- Supprimez de la liste (il s'agit de l' heure , supprimez simplement de la liste chaînée). Comparez avec l'élément pointé par pour voir si nous avons supprimé avant ou après . $a_i$ $a'$ $O(1)$ $a_i$ $p$ $p$
- Remettez à la liste dans sa position d'origine (c'est fois, nous avons mémorisé le prédécesseur et successeur de ). Comparer avec l'élément pointé par $b_i$ $b'$ $O(1)$ $b_i$ $b_i$ $q$ pour voir si nous avons ajouté l'élément avant ou après . $q$
- Mettez à jour les pointeurs et sorte que la médiane de la liste jointe soit soit en soit en . (C'est fois, suivez simplement les listes chaînées une ou deux étapes pour tout réparer. Nous garderons une trace du nombre d'éléments avant / après et dans chaque liste, et nous maintiendrons l'invariant que les deux et $p$ $q$ $a' \cup b'$ $p$ $q$ $O(1)$ $p$ $q$ $p$ pointer vers des éléments qui se rapprochent le plus possible de la médiane.) $q$

Les listes chaînées sont juste tableaux d'index éléments, elles sont donc légères (sauf que la localité d'accès à la mémoire est médiocre). $k$

Voici un exemple d'implémentation et de benchmarks:

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

Voici un graphique des temps de fonctionnement (pour ): $n \approx 2\cdot 10^6$

Bleu = tri + post-traitement, . $O(n \log k)$
Vert = maintenir deux tas, $O(n \log k)$ , implémentation depuis https://github.com/craffel/median-filter
Rouge = maintenir deux arbres de recherche, . $O(n \log k)$
Noir = maintenir un vecteur trié, . $O(n k)$
Axe X = taille de la fenêtre ( ). $\approx k/2$
Axe Y = durée de fonctionnement en secondes.
Données = entiers 32 bits et entiers aléatoires 64 bits, à partir de diverses distributions.

temps de course

Jukka Suomela
la source

Étant donné la limite de David, il est peu probable que vous puissiez faire mieux dans le pire des cas, mais il existe de meilleurs algorithmes sensibles à la sortie. Plus précisément, si dans le nombre de médianes dans le résultat, nous pouvons résoudre le problème dans le temps . $m$ $O(n \log m + m \log n)$

Pour ce faire, remplacez l'arbre binaire équilibré par un arbre binaire équilibré composé uniquement des éléments qui étaient des médianes dans le passé, plus deux tas de Fibonacci entre chaque paire de médianes précédentes (une pour chaque direction), plus les nombres pour que nous puissions localiser le tas Fibonacci qui contient un élément particulier dans la commande. Ne vous embêtez jamais à supprimer des éléments. Lorsque nous insérons un nouvel élément, nous pouvons mettre à jour notre structure de données en temps . Si les nouveaux dénombrements indiquent que la médiane se trouve dans l'un des tas de Fibonacci, il faut un supplémentaire pour extraire la nouvelle médiane. Ce $O(\log m)$ $O(\log n)$ $O(\log n)$ la charge n'a lieu qu'une fois par médiane.

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

Geoffrey Irving
la source

Oups, cela ne fonctionne pas comme écrit, car si vous ne supprimez pas les éléments, les décomptes ne refléteront pas la nouvelle fenêtre. Je ne sais pas si cela peut être corrigé, mais je laisserai la réponse au cas où il y aurait un moyen.

Geoffrey Irving

O (n \log m)

$O(n \log m)$

note complémentaire: la question n'est pas claire, la structure des données sous-jacentes n'est pas définie, nous savons juste quelque chose de très vague. comment voulez-vous améliorer quelque chose dont vous ne savez pas ce que c'est? comment voulez-vous comparer votre approche?

Saeed

Je m'excuse pour le travail incomplet. J'ai posé la question concrète nécessaire pour corriger cette réponse ici: cstheory.stackexchange.com/questions/21778/… . Si vous pensez que c'est approprié, je peux supprimer cette réponse jusqu'à ce que la question secondaire soit résolue.

Geoffrey Irving