Sur des fenêtres plus petites, le n log n
tri peut fonctionner. Existe-t-il de meilleurs algorithmes pour y parvenir?
algorithms
median
miku
la source
la source
Réponses:
C'est une mauvaise forme de trier un tableau pour calculer une médiane. (Médianes et autres quantiles) sont généralement calculées en utilisant le QuickSelect algorithme, avec complexes.O ( n )
Vous pouvez également consulter ma réponse à une récente question connexe ici .
la source
Voici un article décrivant un algorithme possible. Code source inclus et application assez sérieuse (détection des ondes gravitationnelles basée sur l'interférométrie laser), vous pouvez donc vous attendre à ce qu'il soit bien testé.
la source
Si vous êtes prêt à tolérer une approximation, il existe d'autres méthodes. Par exemple, une approximation est une valeur dont le rang est à une certaine distance (spécifiée par l'utilisateur) de la vraie médiane. Par exemple, la médiane a un rang (normalisé) 0,5, et si vous spécifiez un terme d'erreur de 10%, vous voudriez une réponse dont le rang se situe entre 0,45 et 0,55.
Si une telle réponse est appropriée, il existe de nombreuses solutions qui peuvent fonctionner sur des fenêtres coulissantes de données. L'idée de base est de conserver un échantillon des données d'une certaine taille (environ 1 / terme d'erreur) et de calculer la médiane de cet échantillon. On peut montrer qu'avec une probabilité élevée, quelle que soit la nature de l'entrée, la médiane résultante satisfait les propriétés que j'ai mentionnées ci-dessus.
Ainsi, la principale question est de savoir comment maintenir un échantillon courant des données d'une certaine taille, et il existe de nombreuses approches pour cela, y compris la technique connue sous le nom d'échantillonnage de réservoir. Par exemple, cet article: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.24.7136
la source
Si vous conservez une fenêtre de données de longueur k en tant que liste triée à double lien, alors, au moyen d'une recherche binaire (pour insérer chaque nouvel élément au fur et à mesure qu'il est déplacé dans la fenêtre) et d'un tableau circulaire de pointeurs (pour localiser immédiatement les éléments qui doivent être supprimés), chaque décalage de la fenêtre nécessite O (log (k)) effort pour insérer un élément, seulement O (1) effort pour supprimer l'élément déplacé hors de la fenêtre, et seulement O (1) effort pour trouver la médiane (car chaque fois qu'un élément est inséré ou supprimé dans la liste, vous pouvez mettre à jour un pointeur sur la médiane en O (1)). L'effort total pour traiter un tableau de longueur N est donc O ((nk) log (k)) <= O (n log (k)). C'est mieux que n'importe quelle autre méthode proposée jusqu'à présent et ce n'est pas une approximation, c'est exact.
la source
Comme vous l'avez mentionné, le tri serait
O(n·log n)
pour une fenêtre de longueurn
. Faire ce déplacement en ajoute un autrel=vectorlength
faisant le coût totalO(l·n·log n)
.Le moyen le plus simple de le faire est de garder une liste ordonnée des n derniers éléments en mémoire lors du passage d'une fenêtre à la suivante. Étant donné que la suppression / l'insertion d'un élément de / dans une liste ordonnée sont les deux,
O(n)
cela entraînerait des coûtsO(l·n)
.Pseudocode:
la source
Voici une solution O (1) pour trouver la médiane actuelle, et O (log n) pour ajouter un nouveau numéro http://www.dsalgo.com/RunningMedian.php
la source
Si vous pouvez vivre avec une estimation au lieu de la vraie médiane, l' algorithme Remedian (PDF) est un passage avec de faibles exigences de stockage et une précision bien définie.
la source
J'ai utilisé cette bibliothèque C ++ RunningStats dans une application intégrée. C'est la bibliothèque de statistiques en cours d'exécution la plus simple que j'ai trouvée à ce jour.
Depuis le lien:
la source