Algorithmes de tri acceptant un comparateur aléatoire

22

Les algorithmes de tri génériques prennent généralement un ensemble de données à trier et une fonction de comparaison qui peut comparer deux éléments individuels. Si le comparateur est une relation d'ordre¹, la sortie de l'algorithme est une liste / tableau trié.

Je me demande si les algorithmes de tri se fait fonctionner avec un comparateur qui n'est pas une relation d'ordre (en particulier un qui renvoie un résultat aléatoire sur chaque comparaison). Par «travail», je veux dire ici qu'ils continuent de renvoyer une permutation de leur entrée et de fonctionner à leur complexité temporelle typiquement citée (par opposition à se dégrader toujours dans le pire des cas, ou à entrer dans une boucle infinie, ou des éléments manquants). L'ordre des résultats ne serait cependant pas défini. Encore mieux, la commande résultante serait une distribution uniforme lorsque le comparateur est un jeu de pièces.

D'après mon calcul mental approximatif, il semble qu'un tri par fusion serait bien avec cela et maintiendrait le même coût d'exécution et produirait un ordre aléatoire équitable. Je pense que quelque chose comme un tri rapide dégénérerait cependant, ne serait peut-être pas terminé et ne serait pas juste.

Quels autres algorithmes de tri (autres que le tri par fusion) fonctionneraient comme décrit avec un comparateur aléatoire?


  1. Pour référence, un comparateur est une relation d'ordre s'il est une fonction propre (déterministe) et satisfait les axiomes d'une relation d'ordre:

    • il est déterministe: compare(a,b)pour un particulier aet brenvoie toujours le même résultat.
    • c'est transitif: compare(a,b) and compare(b,c) implies compare( a,c )
    • c'est antisymétrique compare(a,b) and compare(b,a) implies a == b

(Supposons que tous les éléments d'entrée soient distincts, donc la réflexivité n'est pas un problème.)

Un comparateur aléatoire viole toutes ces règles. Il existe cependant des comparateurs qui ne sont pas des relations d'ordre mais qui ne sont pas aléatoires (par exemple, ils peuvent violer peut-être une seule règle et uniquement pour des éléments particuliers de l'ensemble).

edA-qa mort-ora-y
la source
(1) Qu'entendez-vous par stabilité de la fonction de comparaison? (2) «non stable» et «aléatoire» sont-ils synonymes?
Tsuyoshi Ito
"exécuter à leur complexité temporelle typiquement citée (par opposition à se dégrader dans le pire des cas" - la complexité temporelle typiquement citée est la pire des situations! "l'ordre serait un ordre aléatoire juste" - PAR "passable" vous voulez dire uniforme? Supposez-vous que le comparateur soit également uniforme?
Raphael
Peut-être pas dans la théorie formelle, mais dans la pratique (langages de programmation), beaucoup de choses sont citées en temps amorti. Par exemple, quicksort est souvent affiché comme mais est en fait O ( n 2 ) . O(logn)O(n2)
edA-qa mort-ora-y
4
@ edA-qamort-ora-y: (1) Vous voulez dire , pas O ( log n ) . (2) Ce n'est pas ce que signifie le « temps amorti »; vous voulez dire " heure prévue ", ou moins formellement, "heure typique". O(nlogn)O(logn)
JeffE
1
Personne n'a abordé la question (pour moi) la plus intéressante posée ci-dessus: quels algorithmes de tri (le cas échéant) ont la propriété que si le comparateur est un jeu de pièces, le résultat est une permutation uniforme.
Joe

Réponses:

13

Donc, fondamentalement, vous voulez savoir s'il existe un algorithme de tri qui ne se dégraderait pas de son cas moyen si on lui donnait une fonction de comparaison similaire à:

int Compare(object a, object b) { return Random.Next(-1,1); }

... où Random.Next () est une méthode qui produira un entier généré de façon aléatoire entre une limite inférieure et supérieure incluse incluse.

La réponse est en fait que la plupart des algorithmes de tri de base fonctionneront selon leur cas moyen, car ils obéissent à au moins l'une des deux conditions suivantes:

  1. Une comparaison entre deux éléments uniques n'est jamais effectuée deux fois dans le tri, et / ou
  2. Dans chaque itération du tri, la position correcte d'au moins un élément est déterminée et de sorte que cet élément n'est plus jamais comparé.

Par exemple, SelectionSort parcourt la sous-liste des éléments non triés, trouve l'élément "le moins" et / ou "le plus grand" (en comparant chacun au plus grand jusqu'à présent), le place dans sa position correcte et répète. Par conséquent, même avec un comparateur non déterministe, à la fin de chaque itération, l'algorithme aura trouvé une valeur qu'il pense être la plus petite ou la plus grande, l'échange avec l'élément dans la position qu'il essaie de déterminer, et ne considère jamais cet élément à nouveau, donc il obéit à la condition 2. Cependant, un A et un B peuvent être comparés plusieurs fois au cours de ce processus (comme l'exemple le plus extrême, considérez plusieurs passes de SelectionSort sur un tableau qui est trié dans l'ordre inverse) donc il viole la condition 1 .

MergeSort obéit à la condition 1 mais pas à la condition 2; lorsque les sous-tableaux sont fusionnés, les éléments du même sous-tableau (à gauche ou à droite) ne sont pas comparés les uns aux autres car il a déjà été déterminé que les éléments de ce côté du tableau sont en ordre entre eux; l'algorithme compare uniquement l'élément le moins non fusionné de chaque sous-tableau à l'autre pour déterminer celui qui est le moins important et devrait aller ensuite dans la liste fusionnée. Cela signifie que deux objets uniques A et B seront comparés l'un à l'autre au maximum une fois, mais l'index "final" d'un élément donné dans la collection complète n'est pas connu tant que l'algorithme n'est pas terminé.

InsertionSort n'obéit qu'à la condition 1 également, même si sa stratégie globale et sa complexité ressemblent davantage à SelectionSort. Chaque élément non trié est comparé aux éléments triés, le plus grand en premier, jusqu'à ce qu'il en trouve un de moins que l'élément examiné. l'élément est inséré à ce point, puis l'élément suivant est pris en compte. Le résultat est que l'ordre relatif de tout A et B est déterminé par une comparaison, et que d'autres comparaisons entre A et B ne sont jamais effectuées, mais la position finale d'un élément ne peut être connue que lorsque tous les éléments sont pris en compte.

QuickSort obéit aux deuxConditions. A chaque niveau, un pivot est choisi et agencé de telle sorte que le côté "gauche" contient des éléments inférieurs au pivot et le côté "droit" contient des éléments supérieurs au pivot. Le résultat de ce niveau est QuickSort (gauche) + pivot + QuickSort (droite) ce qui signifie essentiellement que la position de l'élément pivot est connue (un index supérieur à la longueur du côté gauche), le pivot n'est jamais comparé à aucun autre élément après qu'il a été choisi comme pivot (il peut avoir été comparé aux éléments de pivot précédents, mais ces éléments sont également connus et ne sont inclus dans aucun sous-réseau), ET les A et B qui se retrouvent sur les côtés opposés du pivot ne sont jamais par rapport. Dans la plupart des implémentations de QuickSort pur, le scénario de base est un élément, auquel cas son index actuel est son index final et aucune autre comparaison n'est effectuée.

Le seul type comparatif auquel je peux penser qui n'obéirait à aucune de ces conditions est un BubbleSort non optimisé. Si le tri n'accepte pas que les X éléments les plus importants soient à leur place après l'exécution de X passes et / ou utilise une passe de "double vérification" pour vérifier que la liste est triée, le tri ne sera considéré comme "terminé" que lorsque le comparateur aléatoire est retourné -1 ou 0 pour tous les deux éléments adjacents de la liste pendant une passe et donc aucun swap ont été réalisées (un événement qui, si vraiment aléatoire, qui se produirait avec une probabilité ; pour une relativement petite liste de 25 éléments, c'est une chance sur 2000, alors que pour 100 éléments la probabilité est de 3,7 * 10 -18(2/3)N1). Au fur et à mesure que la valeur absolue maximale du résultat du comparateur augmente, la probabilité pour une comparaison de retourner un résultat négatif ou nul diminue vers 0,5, ce qui rend la chance de terminer l'algorithme beaucoup moins probable (la chance de 99 pièces fait basculer toutes les têtes d'atterrissage , qui est essentiellement ce que cela se résume à, est de 1 sur 1,2 * 10 30 )

MODIFIER LONGTEMPS PLUS TARD: Il y a quelques "sortes" conçues spécifiquement comme exemples de ce qu'il ne faut pas faire qui incorporent un comparateur aléatoire; peut-être le plus célèbre est BogoSort. "Étant donné une liste, si la liste n'est pas en ordre, mélangez la liste et vérifiez à nouveau". Théoriquement, il finira par atteindre la bonne permutation des valeurs, tout comme le "BubbleSort non optimisé" ci-dessus, mais le cas moyen est le temps factoriel (N! / 2), et en raison du problème d'anniversaire (après suffisamment de permutations aléatoires, vous devenir plus susceptibles de rencontrer des permutations en double que des permutations uniques), il existe une possibilité non nulle que l'algorithme ne se termine jamais officiellement, l'algorithme est illimité dans le temps.

KeithS
la source
La condition 2 couvrirait-elle également le tri rapide? Ou serait-ce plutôt une troisième condition selon laquelle chaque itération est plus petite que la précédente.
edA-qa mort-ora-y
QuickSort serait, à mon avis, couvert par les deux conditions. Dans QuickSorts efficaces, vous choisissez le pivot, puis comparez chaque élément avec lui et permutez les éléments qui sont du mauvais «côté» du pivot. Une fois les éléments organisés, la fonction renvoie QuickSort (gauche) + pivot + QuickSort (droite) et le pivot n'est pas transmis aux niveaux inférieurs. Donc, les deux conditions sont vraies; vous ne comparez jamais un seul et un unique plus d'une fois, et vous avez déterminé l'index du pivot au moment où vous avez terminé d'organiser les autres éléments.
KeithS
Excellente réponse, mais je ne suis pas d'accord avec vous sur BubbleSort. Lors de l'utilisation d'un comparateur cohérent, à la i-ème itération, BubbleSort sait que les i-1 derniers éléments sont à leur place finale, et toute implémentation raisonnable de BubbleSort passera par moins d'éléments à chaque itération, donc elle devrait également s'arrêter après n itérations. .
Boris Trayvas
Après réflexion, j'aurais tendance à être d'accord avec vous; après X passes, les plus grandes valeurs X sont à leur place, vous pouvez donc réduire l'espace de problème à chaque passe et donc un algorithme efficace obéirait à la condition 2. Je modifierai
KeithS
Vous devez être prudent avec l'implémentation de Quicksort. On peut supposer qu'une recherche d'un élément non inférieur au pivot prendra fin lorsque nous rencontrerons le pivot ou un élément supérieur au pivot; ce ne serait pas nécessairement le cas.
gnasher729
10

Tout algorithme qui compare deux fois les deux mêmes éléments n'est pas un algorithme très intelligent, et en particulier un tel algorithme fonctionnerait moins bien que les algorithmes de tri les plus courants (fusion-tri, tri rapide, bulle-tri, insertion-tri). Tout algorithme qui compare des paires d'éléments au plus une fois a le même coût d'exécution (moyen) quel que soit le comportement de la fonction de comparaison, s'il est supérieur ou inférieur à des résultats également probables . Sinon, vous pouvez au moins garantir que l'algorithme de tri n'est pas pire que le temps d'exécution le plus défavorable, qui est inférieur àO(n2)

n


Edit: Le problème est plus intéressant que je le pensais, alors voici un autre commentaire:

comparecompare(x,y)=true1/2false1/2

insert x [] = [x]
insert x y:ys = if x < y then x:y:ys
                else y:insert x ys

sort_aux l e = match l with
                 [] -> e
                 x:xs -> sort_aux xs (insert x ys)

sort l = sort_aux l []

k=1nf(k)nlf(k)insertk:

compare

i=1ki2ii=1i2i=2

O(2n)O(n2)

Ce serait amusant de calculer les temps de fonctionnement moyens pour les différents autres algorithmes étant donné cette fonction de comparaison uniforme.

cody
la source
Quicksort peut répéter les comparaisons si le même élément est choisi comme pivot plusieurs fois (cela peut se produire plusieurs fois dans la liste).
Raphael
2
@Raphael: Mon choix de mots était mauvais: je voulais dire des comparaisons répétées entre les occurrences d'éléments, qui ne se produisent pas plus d'une fois dans Quicksort.
cody
1
@ Gilles: Je peux me tromper, mais je ne pense pas que la transitivité de la comparaison soit cruciale pour l' exécution de la plupart des algorithmes de tri; bien sûr, mais ce n’était pas l’objet de la question.
cody
@ Gilles: L'OP ne pose pas de question sur les algorithmes qui trient réellement. Il demande ce qui arrive aux algorithmes de tri standard lorsque toutes les comparaisons sont remplacées par des lancers de pièces. Les algorithmes résultants ne trient pas (sauf avec une faible probabilité), mais ce sont toujours des algorithmes bien définis.
JeffE
@JeffE Je le comprends maintenant. Ce n'est pas ainsi que j'ai lu la question au départ, mais étant donné les commentaires du demandeur, c'est ce que l'on voulait dire.
Gilles 'SO- arrête d'être méchant'
2

Mergesort avec un comparateur aléatoire juste n'est pas juste. Je n'ai pas de preuve, mais j'ai des preuves empiriques TRÈS solides. (Juste signifie uniformément distribué.)

module Main where

import Control.Monad
import Data.Map (Map)
import qualified Data.Map as Map
import System.Random (randomIO)

--------------------------------------------------------------------------------

main :: IO ()
main = do
  let xs = [0..9]
  xss <- replicateM 100000 (msortRand xs)
  print $ countFrequencies xss

msortRand :: [a] -> IO [a]
msortRand = msort (\_ _ -> randomIO)

countFrequencies :: (Ord a) => [[a]] -> [Map a Int]
countFrequencies [] = []
countFrequencies xss = foldr (\k m -> Map.insertWith (+) k 1 m) Map.empty ys : countFrequencies wss
  where
    ys = map head xss
    zss = map tail xss
    wss = if head zss == []
      then []
      else zss

--------------------------------------------------------------------------------

msort :: (Monad m) => (a -> a -> m Bool) -> [a] -> m [a]
msort (<) [] = return []
msort (<) [x] = return [x]
msort (<) xs = do
  ys' <- msort (<) ys
  zs' <- msort (<) zs
  merge (<) ys' zs'
  where
    (ys, zs) = split xs

merge :: (Monad m) => (a -> a -> m Bool) -> [a] -> [a] -> m [a]
merge (<) [] ys = return ys
merge (<) xs [] = return xs
merge (<) (x:xs) (y:ys) = do
  bool <- x < y
  if bool
    then liftM (x:) $ merge (<) xs (y:ys)
        else liftM (y:) $ merge (<) (x:xs) ys

split :: [a] -> ([a], [a])
split [] = ([], [])
split [x] = ([x], [])
split (x:y:zs) = (x:xs, y:ys)
  where
    (xs, ys) = split zs
Thomas Eding
la source
Haskell ou Caml est-il à la mode maintenant?
Yai0Phah
Je n'ai aucune idée. Mais Haskell est ma langue préférée, donc je l'ai programmée dedans; la correspondance des motifs a rendu cela plus facile.
Thomas Eding
0

Une réponse très connexe est trouvée dans All Sorts of Permutations (Functional Pearl) par Christiansen, Danilenko et Dylus. Ils exécutent un algorithme de tri dans la monade de liste , qui simule essentiellement le non-déterminisme, renvoyant toutes les permutations d'une liste d'entrée donnée. La propriété intéressante est que chaque permutation est retournée exactement une fois.

Citant le résumé:

...

Dans cet article, nous examinons la combinaison du non-déterminisme et du tri sous un angle différent: étant donné une fonction de tri, nous l'appliquons à un prédicat non déterministe pour obtenir une fonction qui énumère les permutations de la liste d'entrée. Nous allons au fond des propriétés nécessaires des algorithmes de tri et des prédicats en jeu et discutons des variations du non-déterminisme modélisé.

En plus de cela, nous formulons et prouvons un théorème indiquant que, quelle que soit la fonction de tri que nous utilisons, la fonction de permutation correspondante énumère toutes les permutations de la liste d'entrée. Nous utilisons des théorèmes libres, qui sont dérivés du type d'une fonction seule, pour prouver l'énoncé.

Petr Pudlák
la source