Existe-t-il un moyen de mesurer le tri d'une liste?

161

Existe-t-il un moyen de mesurer le tri d'une liste?

Je veux dire, il ne s'agit pas de savoir si une liste est triée ou non (booléen), mais quelque chose comme un rapport de «tri», quelque chose comme le coefficient de corrélation dans les statistiques.

Par exemple,

  • Si les éléments d'une liste sont dans l'ordre croissant, son taux serait de 1,0

  • Si la liste est triée par ordre décroissant, son taux serait de -1,0

  • Si la liste est presque triée par ordre croissant, son taux serait de 0,9 ou une valeur proche de 1.

  • Si la liste n'est pas triée du tout (aléatoire), son taux serait proche de 0

J'écris une petite bibliothèque à Scala pour m'entraîner. Je pense qu'un taux de tri serait utile, mais je ne trouve aucune information sur quelque chose comme ça. Peut-être que je ne connais pas les termes adéquats pour le concept.

Josell
la source
4
Serait-ce utilisé pour déterminer l'algorithme idéal pour trier la liste? Par exemple, pour les valeurs proches de 0, QuickSort serait idéal, mais les valeurs à chaque extrémité de l'échelle (presque triées ou presque inversées), MergeSort serait beaucoup plus rapide, car QC passe à O (N ^ 2) dans ces cas.
Darrel Hoffman
8
+1 pour "ratio of sortess"
0x499602D2
1
@Fuhrmanator La version stochastique de l'algorithme n'a pas besoin d'effectuer un tri pour arriver à une estimation probabiliste du tri. Ce n'est que si vous souhaitez obtenir une mesure exacte dont vous avez besoin pour effectuer un tri.
Timothy Shields
1
Premier instinct sarcastique mais drôle: vous pouvez trier par insertion la liste et voir combien de temps cela prend, puis comparer cela au temps qu'il faut pour trier (la liste maintenant triée) et inversement.
kqr

Réponses:

142

Vous pouvez simplement compter le nombre d'inversions dans la liste.

Inversion

Une inversion dans une séquence d'éléments de type Test une paire d'éléments de séquence qui apparaissent dans le désordre selon un ordre <sur l'ensemble des T's.

De Wikipedia :

Formellement, laissez A(1), A(2), ..., A(n)être une séquence de nnombres.
Si i < jet A(i) > A(j), alors la paire (i,j)est appelée une inversion de A.

Le numéro d'inversion d'une séquence est une mesure courante de son tri.
Formellement, le nombre d'inversion est défini comme étant le nombre d'inversions, c'est-à-dire

définition

Pour rendre ces définitions plus claires, considérez l'exemple de séquence 9, 5, 7, 6. Cette séquence a les inversions (0,1), (0,2), (0,3), (2,3) et le numéro d'inversion 4 .

Si vous voulez une valeur entre 0et 1, vous pouvez diviser le nombre d'inversion par N choose 2.

Pour créer réellement un algorithme pour calculer ce score en fonction du tri d'une liste, vous avez deux approches:

Approche 1 (déterministe)

Modifiez votre algorithme de tri préféré pour garder une trace du nombre d'inversions qu'il corrige pendant son exécution. Bien que cela ne soit pas trivial et ait des implémentations variables en fonction de l'algorithme de tri que vous choisissez, vous vous retrouverez avec un algorithme qui n'est pas plus cher (en termes de complexité) que l'algorithme de tri avec lequel vous avez commencé.

Si vous empruntez cette voie, sachez que ce n'est pas aussi simple que de compter les «swaps». Mergesort, par exemple, est le pire des cas O(N log N), mais s'il est exécuté sur une liste triée par ordre décroissant, il corrigera toutes les N choose 2inversions. Ce sont des O(N^2)inversions corrigées dans les O(N log N)opérations. Ainsi, certaines opérations doivent inévitablement corriger plus d'une inversion à la fois. Vous devez être prudent avec votre mise en œuvre. Remarque: vous pouvez le faire avec O(N log N)complexité, c'est juste délicat.

En relation: calcul du nombre «d'inversions» dans une permutation

Approche 2 (stochastique)

  • Échantillonner au hasard des paires (i,j), oùi != j
  • Pour chaque paire, déterminez si list[min(i,j)] < list[max(i,j)](0 ou 1)
  • Calculer la moyenne de ces comparaisons puis normaliser par N choose 2

Personnellement, j'opterais pour l'approche stochastique à moins que vous n'ayez une exigence d'exactitude - ne serait-ce que parce qu'elle est si facile à mettre en œuvre.


Si vous voulez vraiment une valeur ( z') entre -1(triée par ordre décroissant) et 1(triée par ordre croissant), vous pouvez simplement mapper la valeur ci-dessus ( z), qui se situe entre 0(triée par ordre croissant) et 1(triée par ordre décroissant), à cette plage en utilisant cette formule :

z' = -2 * z + 1
Timothy Shields
la source
2
C'est un peu fascinant pour moi que le tri d'une liste soit (généralement) O (n * logn), et la méthode naïve / évidente de calcul des inversions est O (n ^ 2). Je me demande s'il existe de meilleurs algorithmes pour calculer le nombre d'inversions?
Mark Bessey
5
Il y a quelques approches intéressantes dans cette question SO: stackoverflow.com/questions/6523712/... Fondamentalement, elles reviennent à trier le tableau afin de déterminer combien d'inversions il y a.
Mark Bessey
4
J'ai pensé naïvement que vous pouviez simplement compter les paires adjacentes qui sont dans le désordre. Mais cela sous-dénombrera gravement: 1 2 3 1 2 3 n'a qu'une seule inversion adjacente, mais elle est inversée à 50% par la mesure la plus correcte.
Barmar le
2
@Barmar Je pense que la liste 1 2 3 1 2 3 serait qualifiée de triée ;-)
scunliffe
2
@TimothyShields, eh bien, non, ce n'est pas le cas. Mais je ne vais pas insister sur ce point. Juste une suggestion pour ajouter une définition non formelle plus accessible aux moins enclins symboliquement.
Chris Calo
24

La mesure traditionnelle du tri d'une liste (ou d'une autre structure séquentielle) est le nombre d'inversions.

Le nombre d'inversions est le nombre de paires (a, b) st indice de a <b ET b <<a. À ces fins, <<représente la relation de commande que vous choisissez pour votre tri particulier.

Une liste entièrement triée n'a pas d'inversions, et une liste complètement inversée a le nombre maximum d'inversions.

Marcin
la source
5
Techniquement, 5 4 3 2 1est entièrement trié car l'ordre n'est pas spécifié, mais je suis pédant :-)
paxdiablo
7
@paxdiablo Cela dépend de la définition de <.
Marcin
@paxdiablo, eh bien, on pourrait mesurer le tri par la distance entre le nombre d'inversions et le plus proche de 0 ou n choose 2.
huon
17

Vous pouvez utiliser la corrélation réelle.

Supposons qu'à chaque élément de la liste triée, vous attribuez un rang entier à partir de zéro. Notez qu'un graphique de l'indice de position des éléments en fonction du rang ressemblera à des points en ligne droite (corrélation de 1,0 entre la position et le rang).

Vous pouvez calculer une corrélation sur ces données. Pour un tri inversé, vous obtiendrez -1 et ainsi de suite.

Kaz
la source
1
Je suis désolé, mais cela laisse trop d’explications, comme la façon dont vous attribuez les nombres entiers.
Marcin
2
Vous avez besoin de la liste triée pour affecter les entiers; alors ce n'est qu'une énumération des éléments.
Kaz
1
Exactement ce que j'allais suggérer. Déterminez la corrélation entre la position de l'objet dans la liste d'origine et sa position dans la liste triée. La mauvaise nouvelle est que les routines de corrélation s'exécutent probablement en O (n ^ 2); la bonne nouvelle est qu'ils sont probablement prêts à l'emploi pour votre environnement.
Peter Webb
2
Ouais, juste le rho de Spearman en.wikipedia.org/wiki/…
Lucas
Je suis curieux ... est-ce que cette approche équivaut à mettre à l'échelle le nombre d'inversions?
Clayton Stanley
4

Il y a eu d'excellentes réponses, et j'aimerais ajouter un aspect mathématique pour être complet:

  • Vous pouvez mesurer le degré de tri d'une liste en mesurant dans quelle mesure elle est corrélée à une liste triée. Pour ce faire, vous pouvez utiliser la corrélation de rang (la plus connue étant celle de Spearman ), qui est exactement la même que la corrélation habituelle, mais elle utilise le rang des éléments dans une liste au lieu des valeurs analogiques de ses éléments.

  • De nombreuses extensions existent, comme un coefficient de corrélation (+1 pour le tri exact, -1 pour l'inversion exacte)

  • Cela vous permet d'avoir des propriétés statistiques pour cette mesure, comme le théorème de limite centrale permutationnelle, qui vous permet de connaître la distribution de cette mesure pour les listes aléatoires.

Meduz
la source
3

En dehors du nombre d'inversion, pour les listes numériques, la distance quadratique moyenne de l'état trié est imaginable:

#! ruby
d = -> a { a.zip( a.sort ).map { |u, v| ( u - v ) ** 2 }.reduce( :+ ) ** 0.5 }

a = 8, 7, 3, 4, 10, 9, 6, 2, 5, 1
d.( a ) #=> 15.556
d.( a.sort ) #=> 0.0
d.( a.sort.reverse ) # => 18.166 is the worrst case
Boris Stitnicky
la source
Je pense que c'est le carré de la fonction de corrélation standard, voir en.wikipedia.org/wiki/Correlation_ratio . Et s'applique également aux listes non numériques; les deux valeurs comparées sont la position de l'objet dans les deux listes.
Peter Webb
Je suis un simplet. Je ne sais même pas ce qu'est le rapport de corrélation. Quand j'ai lu cet article de Wikipédia, tout en haut, on me demande ce qu'est la «dispersion statistique», puis «l'écart type», puis «variation», puis «coefficient de corrélation interclasse». J'ai appris tout cela, plusieurs fois, et plusieurs fois, je l'ai encore oublié. Dans ma réponse pragmatique, je mesure simplement la distance entre les deux vecteurs avec le théorème de Pythagore, dont je me souviens de l'école élémentaire, c'est tout.
Boris Stitnicky
1

Je ne suis pas sûr de la "meilleure" méthode, mais une méthode simple serait de comparer chaque élément avec celui qui le suit, en incrémentant un compteur si élément2> élément 1 (ou ce que vous voulez tester), puis divisez par le nombre total d'éléments. Cela devrait vous donner un pourcentage.

user2369405
la source
1

Je compterais les comparaisons et les diviserais par le nombre total de comparaisons. Voici un exemple simple de Python .

my_list = [1,4,5,6,9,-1,5,3,55,11,12,13,14]

right_comparison_count = 0

for i in range(len(my_list)-1):
    if my_list[i] < my_list[i+1]: # Assume you want to it ascending order
        right_comparison_count += 1

if right_comparison_count == 0:
    result = -1
else:
    result = float(right_comparison_count) / float((len(my_list) - 1))

print result
Ibrahim
la source
0

Que diriez-vous quelque chose comme ça?

#!/usr/bin/python3

def sign(x, y):
   if x < y:
      return 1
   elif x > y:
      return -1
   else:
      return 0

def mean(list_):
   return float(sum(list_)) / float(len(list_))

def main():
   list_ = [ 1, 2, 3, 4, 6, 5, 7, 8 ]
   signs = []
   # this zip is pairing up element 0, 1, then 1, 2, then 2, 3, etc...
   for elem1, elem2 in zip(list_[:-1], list_[1:]):
      signs.append(sign(elem1, elem2))

   # This should print 1 for a sorted list, -1 for a list that is in reverse order
   # and 0 for a run of the same numbers, like all 4's
   print(mean(signs))

main()
Dstromberg
la source
2
Cela ne compte que les inversions adjacentes. Si vous regardez les autres réponses, vous verrez que cela est insuffisant.
Konrad Rudolph
1
@KonradRudolph: Je pense que cette réponse satisfait la question posée. Le fait que d'autres réponses soient plus complètes ne signifie pas que celle-ci est insuffisante; cela dépend des exigences du PO.
LarsH
0

Si vous prenez votre liste, calculez les rangs des valeurs dans cette liste et appelez la liste des rangs Yet une autre liste, Xqui contient les entiers de 1à length(Y), vous pouvez obtenir exactement la mesure de tri que vous recherchez en calculant le coefficient de corrélation ,, rentre les deux listes.

r = \frac{\sum ^n _{i=1}(X_i - \bar{X})(Y_i - \bar{Y})}{\sqrt{\sum ^n _{i=1}(X_i - \bar{X})^2} \sqrt{\sum ^n _{i=1}(Y_i - \bar{Y})^2}} 

Pour une liste entièrement triée ,, r = 1.0pour une liste triée inversement r=-1.0, et le rvarie entre ces limites pour différents degrés de tri.

Un problème possible avec cette approche, en fonction de l'application, est que le calcul du rang de chaque élément de la liste équivaut à le trier, il s'agit donc d'une opération O (n log n).

Simon
la source
Mais cela n'ignorera pas la forme de la courbe. Si son tableau est trié, mais, par exemple, contient des valeurs augmentant de façon exponentielle, la corrélation sera petite là où il veut qu'elle soit 1,0.
Lee Daniel Crocker
@LeeDanielCrocker: Oui, c'est un bon point. J'ai modifié ma réponse pour résoudre ce problème en classant les valeurs.
Simon