En minimum = head . sort El sort ne sera pas fait complètement, parce qu'il ne sera pas fait à l'avance . Le site sort ne sera fait qu'autant que nécessaire pour produire le tout premier élément, demandé par head .
Dans le cas de mergesort, par exemple, au départ n Les numéros de la liste seront comparés par paires, puis les gagnants seront mis par paires et comparés ( n/2 ), puis les nouveaux gagnants ( n/4 ), etc. En tout, O(n) comparaisons pour produire l'élément minimal.
mergesortBy less [] = []
mergesortBy less xs = head $ until (null.tail) pairs [[x] | x <- xs]
where
pairs (x:y:t) = merge x y : pairs t
pairs xs = xs
merge (x:xs) (y:ys) | less y x = y : merge (x:xs) ys
| otherwise = x : merge xs (y:ys)
merge xs [] = xs
merge [] ys = ys
Le code ci-dessus peut être complété pour étiqueter chaque nombre qu'il produit avec le nombre de comparaisons qui ont été effectuées pour le produire :
mgsort xs = go $ map ((,) 0) xs where
go [] = []
go xs = head $ until (null.tail) pairs [[x] | x <- xs] where
....
merge ((a,b):xs) ((c,d):ys)
| (d < b) = (a+c+1,d) : merge ((a+1,b):xs) ys -- cumulative
| otherwise = (a+c+1,b) : merge xs ((c+1,d):ys) -- cost
....
g n = concat [[a,b] | (a,b) <- zip [1,3..n] [n,n-2..1]] -- a little scrambler
En l'exécutant pour plusieurs longueurs de liste, nous constatons que c'est en effet ~ n :
*Main> map (fst . head . mgsort . g) [10, 20, 40, 80, 160, 1600]
[9,19,39,79,159,1599]
Pour voir si le code de tri lui-même est ~ n log n nous le modifions de façon à ce que chaque numéro produit n'entraîne que son propre coût, et le coût total est alors trouvé par sommation sur l'ensemble de la liste triée :
merge ((a,b):xs) ((c,d):ys)
| (d < b) = (c+1,d) : merge ((a+1,b):xs) ys -- individual
| otherwise = (a+1,b) : merge xs ((c+1,d):ys) -- cost
Voici les résultats pour des listes de différentes longueurs,
*Main> let xs = map (sum . map fst . mgsort . g) [20, 40, 80, 160, 320, 640]
[138,342,810,1866,4218,9402]
*Main> map (logBase 2) $ zipWith (/) (tail xs) xs
[1.309328,1.2439256,1.2039552,1.1766101,1.1564085]
Ce qui précède montre ordres de croissance empiriques pour les longueurs croissantes de la liste, n qui diminuent rapidement, comme c'est le cas dans les cas suivants ~ n log n les calculs. Voir aussi cet article de blog . Voici une vérification rapide de la corrélation :
*Main> let xs = [n*log n | n<- [20, 40, 80, 160, 320, 640]] in
map (logBase 2) $ zipWith (/) (tail xs) xs
[1.3002739,1.2484156,1.211859,1.1846942,1.1637106]
éditer : L'évaluation paresseuse peut être considérée métaphoriquement comme une sorte d'idiome producteur/consommateur. 1 avec un stockage indépendant de mémorisation comme intermédiaire. Toute définition de la production que nous écrivons, définit un producteur qui produira sa production, petit à petit, au fur et à mesure de la demande de son ou ses consommateurs - mais pas avant. Ce qui est produit est mémorisé, de sorte que si un autre consommateur consomme la même production à un rythme différent, il accède au même stockage, rempli précédemment.
Lorsqu'il ne reste plus de consommateurs faisant référence à un élément de stockage, celui-ci est mis au rebut. Parfois, grâce à des optimisations, le compilateur est capable de supprimer complètement le stockage intermédiaire, éliminant ainsi l'homme du milieu.
1 voir aussi : Générateurs simples et évaluation paresseuse par Oleg Kiselyov, Simon Peyton-Jones et Amr Sabry.
