sorte de court-circuiter

Question

Je comprends que:

head (map (2**) [1..999999])

Est-ce que ne fait évaluer 2 ** 1, et aucun des autres, mais le livre que je lis dit:

head (sort somelist)

aura seulement besoin de trouver le plus petit élément de la liste, parce que c'est tout ce qui est utilisé. Comment cela marche-t-il? Pour autant que je peux dire, ce serait impossible avec les algorithmes de tri que je connais (comme le tri à bulles).

La seule façon que je peux penser que cela fonctionnerait est si l'algorithme de tri devait passer par la liste entière à la recherche de l'élément le plus petit, puis récursif sur la liste sans cet élément. Pour moi, cela semble vraiment lent.

Est-ce comment la fonction de tri fonctionne, ou est-il un autre algorithme de tri, je ne sais pas, qui permettrait de court-circuit comme il est?

Answer 1

  

aura seulement besoin de trouver le plus petit élément de la liste, parce que c'est tout ce qui est utilisé.

... devrait vraiment dire que la fonction n'a besoin que de faire la quantité minimale de travail que l'algorithme de tri nécessite pour trouver le plus petit élément.

Par exemple, si nous utilisons quicksort comme notre algorithme de tri sous-jacent, alors head . quicksort est équivalente à la optimal algorithme de sélection connu sous le nom « QuickSelect », ce qui est le pire cas linéaire. De plus, nous pouvons mettre en œuvre k -quickselect simplement par take k . quicksort.

Wikipedia note dans son article sur des algorithmes de sélection (je souligne):

  

Parce que le soutien linguistique pour le tri est plus omniprésent, l'approche simpliste du tri suivie par l'indexation est préféré dans de nombreux environnements, malgré son désavantage de la vitesse. En effet, pour les langues paresseux, cette approche simpliste peut même vous obtenir la meilleure complexité possible pour le k plus petit / plus trié (avec un maximum / minimum comme un cas particulier) si votre tri est assez paresseux.

Quicksort fonctionne bien dans ce scénario, alors que le tri par défaut dans Haskell (tri par fusion) ne compose pas tout à fait aussi bien, comme il le fait plus de travail que nécessaire de renvoyer chaque élément de la liste triée. Comme ce poste sur la liste de diffusion Haskell Notes:

  

quicksort paresseux est capable de produire le lot de la   des premiers éléments plus petits k en

     

O (n + k log k) de temps total [1]

     

alors que les besoins de mergesort paresseux

     

O (n + k log n) du temps total [2]

Pour plus que vous pourriez vous lire ce billet de blog .

Answer 2

Si vous créez une fonction de comparaison qui trace ses arguments, comme celui-ci dans la ligne de commande de GHCi:

> :module + Data.List Debug.Trace
> let myCompare x y = trace ("\tCmp " ++ show x ++ " " ++ show y) $ compare x y

vous pouvez voir le comportement vous:

> sortBy myCompare "foobar"

"     Cmp 'f' 'o'
      Cmp 'o' 'b'
      Cmp 'f' 'b'
      Cmp 'a' 'r'
      Cmp 'b' 'a'
a     Cmp 'b' 'r'
b     Cmp 'f' 'o'
      Cmp 'f' 'r'
f     Cmp 'o' 'o'
      Cmp 'o' 'r'
o     Cmp 'o' 'r'
or"

Haskell évalue la chaîne paresseuse, un caractère à la fois. La colonne de gauche est en cours d'impression lorsque chaque caractère est trouvée, avec la colonne de droite enregistrant les comparaisons nécessaires, comme imprimé par « trace ».

Notez que si vous compilez cela, surtout avec Optimisations, vous pourriez obtenir un résultat différent. L'Optimiseur gère un analyseur qui remarquera la rigueur sans doute que la chaîne entière est imprimé, il serait plus efficace d'évaluer avec empressement.

Ensuite, essayez

> head $ sortBy myCompare "foobar"

      Cmp 'f' 'o'
      Cmp 'o' 'b'
      Cmp 'f' 'b'
      Cmp 'a' 'r'
      Cmp 'b' 'a'
'a'

Si vous voulez comprendre comment cela fonctionne, regardez le code source de la fonction de tri et d'évaluer « sorte « foobar » » manuellement sur papier.

qsort [] = []
qsort (x:xs) = qsort less ++ [x] ++ qsort greater
   where (less, greater) = partition (< x) xs

   qsort ('f':"oobar")
 = qsort ('b':"a") ++ "f" ++ qsort ('o':"or")
 = ("a" ++ "b") ++ "f" ++ qsort ('o':"or")

Et maintenant, nous avons fait assez pour constater que « a » est le premier élément du résultat sans avoir à évaluer l'autre appel à « qsort ». J'ai omis la comparaison réelle parce que son caché à l'intérieur de l'appel à « partition ». En fait, la « partition » est aussi paresseux, donc en fait n'a pas été évalué pour autant que je l'ai montré l'argument à l'autre « qsort » il.

Answer 3

L'algorithme que vous venez de décrire a un nom spécifique: « sorte de sélection ». Il est O (n ² ) il est donc pas tout à fait la chose la plus rapide que vous pourriez faire. Cependant, si vous voulez que les premiers éléments « k » dans le tableau trié, la complexité serait O (kn) qui est bien si « k » est assez petit (comme votre exemple).

Notez que vous utilisez une fonction pure dans un langage fonctionnel. Le compilateur est susceptible d'être en mesure de générer du code Optimisée pour sort dans les deux cas en regardant les fonctions sont ainsi composées. Il peut facilement déduire que vous voulez que l'élément minimum lorsque vous rédigez head et sort.