Evaluation paresseuse et complexité temporelle

Je regardais autour de Non-Trivial Lazy Evaluation de stackoverflow, ce qui m’a conduit à la présentation de Keegan McAllister: Why learn Haskell . Dans la diapositive 8, il montre la fonction minimale, définie comme suit:

minimum = head . sort 

et déclare que sa complexité est O (n). Je ne comprends pas pourquoi la complexité est dite linéaire si le sorting par remplacement est O (nlog n). Le sorting référencé dans la publication ne peut pas être linéaire, car il ne suppose rien sur les données, comme cela serait requirejs par les méthodes de sorting linéaire, telles que le sorting par comptage.

L’évaluation paresseuse joue-t-elle un rôle mystérieux ici? Si oui, quelle est l’explication derrière cela?

    Au minimum = head . sort minimum = head . sort , le sort ne se fera pas complètement, car il ne sera pas fait au préalable . Le sort ne sera fait que pour produire le premier élément exigé par la head .

    Par exemple, lors de la fusion, les n premiers chiffres de la liste seront comparés par paires, puis les gagnants seront jumelés et comparés ( n/2 numéros), 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 xy : pairs t pairs xs = xs merge (x:xs) (y:ys) | less yx = 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 marquer chaque numéro qu'il produit avec un certain nombre de comparaisons entrant dans sa production:

     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 .... gn = 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 voyons que c'est bien ~ 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 sorting lui-même est ~ n log n , nous le modifions de manière à ce que chaque nombre produit ne comporte que son propre coût, et le coût total est ensuite calculé par sommation sur la liste sortingée entière:

      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 les 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 des ordres de croissance empiriques pour des longueurs croissantes de liste, n , qui diminuent rapidement, comme le montrent généralement ~ n log n calculs de ~ n log n . Voir aussi ce billet de blog . Voici un test de corrélation rapide:

     *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] 

    edit: L'évaluation paresseuse peut être considérée de manière métaphorique comme une sorte de langage producteur / consommateur 1 , avec un stockage indépendant de la mémorisation en tant qu'intermédiaire. Toute définition productive que nous écrivons définit un producteur qui produira sa sortie, bit par bit, au fur et à mesure des demandes de ses consommateurs - mais pas avant. Tout ce qui est produit est mémorisé, de sorte que si un autre consommateur consum la même sortie à un rythme différent, il accède au même stockage, rempli précédemment.

    Lorsqu'il ne rest plus de consommateurs faisant référence à un élément de stockage, les déchets sont collectés. Parfois, avec les optimisations, le compilateur est capable de supprimer complètement le stockage intermédiaire, ce qui élimine les intermédiaires.

    1 voir aussi: Simple Generators v. Lazy Evaluation par Oleg Kiselyov, Simon Peyton-Jones et Amr Sabry.

    Supposons que minimum' :: (Ord a) => [a] -> (a, [a]) est une fonction qui retourne le plus petit élément d’une liste avec la liste avec cet élément supprimé. Clairement, cela peut être fait en O (n) temps. Si vous définissez ensuite sort comme

     sort :: (Ord a) => [a] -> [a] sort xs = xmin:(sort xs') where (xmin, xs') = minimum' xs 

    alors l’évaluation paresseuse signifie que dans (head . sort) xs seul le premier élément est jamais calculé. Cet élément est, comme vous le voyez, simplement (le premier élément de) la paire minimum' xs , qui est calculée en temps O (n).

    Bien entendu, comme le souligne delnan, la complexité dépend de la mise en œuvre du sort .

    Vous avez un bon nombre de réponses qui abordent les spécificités de la head . sort head . sort Je vais juste append quelques statuts supplémentaires.

    Avec une évaluation rapide, les complexités informatiques de divers algorithmes se composent de manière simple. Par exemple, la plus petite limite supérieure (LUB) pour f . g f . g doit être la sum des LUB pour f et g . Ainsi, vous pouvez traiter f et g comme des boîtes noires et raisonner exclusivement en fonction de leurs LUB.

    Avec une évaluation paresseuse, cependant, f . g f . g peut avoir une LUB meilleure que la sum des LUBs de f et g . Vous ne pouvez pas utiliser le raisonnement par boîte noire pour prouver le LUB; vous devez parsingr les implémentations et leur interaction.

    Ainsi, le fait souvent cité que la complexité de l’évaluation paresseuse est beaucoup plus difficile à raisonner qu’à évaluer avec empressement. Pensez à ce qui suit. Supposons que vous essayiez d’améliorer les performances asymptotiques d’un morceau de code dont la forme est f . g f . g . Dans un langage enthousiaste, il existe une stratégie évidente que vous pouvez suivre pour faire ceci: choisir le plus complexe de f et g et améliorer celui-ci en premier. Si vous y réussissez, vous réussissez au f . g f . g tâche.

    Dans un langage paresseux, en revanche, vous pouvez avoir ces situations:

    • Vous améliorez le plus complexe de f et g , mais f . g f . g ne s’améliore pas (ou même empire ).
    • Vous pouvez améliorer f . g f . g de manière à ne pas aider (ou même à aggraver ) f ou g .

    L’explication dépend de l’implémentation du sort , et pour certaines implémentations, ce ne sera pas vrai. Par exemple, avec un sorting par insertion qui insère à la fin de la liste, l’évaluation différée n’aide pas. Alors choisissons une implémentation à regarder, et pour simplifier, utilisons le sorting de sélection:

     sort [] = [] sort (x:xs) = m : sort (delete m (x:xs)) where m = foldl (\xy -> if x < y then x else y) x xs 

    La fonction utilise clairement le temps O (n ^ 2) pour sortinger la liste, mais comme head n'a besoin que du premier élément de la liste, le sort (delete x xs) n'est jamais évalué!

    Ce n’est pas si mystérieux. Quelle quantité de liste devez-vous sortinger pour fournir le premier élément? Vous devez trouver l’élément minimal, ce qui peut facilement être fait en temps linéaire. En fait, pour certaines implémentations de sort évaluation paresseuse le fera pour vous.

    Une façon intéressante de voir cela en pratique est de suivre la fonction de comparaison.

     import Debug.Trace import Data.List myCmp xy = trace (" myCmp " ++ show x ++ " " ++ show y) $ compare xy xs = [5,8,1,3,0,54,2,5,2,98,7] main = do print "Sorting entire list" print $ sortBy myCmp xs print "Head of sorted list" print $ head $ sortBy myCmp xs 

    Tout d’abord, notez la manière dont la sortie de la liste entière est entrelacée avec les messages de trace. Deuxièmement, notez comment les messages de trace sont similaires lors du calcul de la tête.

    Je viens de lancer ceci via Ghci, et ce n’est pas exactement O (n): il faut 15 comparaisons pour trouver le premier élément, pas le 10 qui devrait être requirejs. Mais c’est encore moins que O (n log n).

    Edit: comme Vitus le souligne ci-dessous, prendre 15 comparaisons au lieu de 10 n’est pas la même chose que de dire que ce n’est pas O (n). Je voulais juste dire que cela prend plus que le minimum théorique.

    Inspiré par la réponse de Paul Johnson, j’ai tracé les taux de croissance des deux fonctions. J’ai d’abord modifié son code pour imprimer un caractère par comparaison:

     import System.Random import Debug.Trace import Data.List import System.Environment rs n = do gen <- newStdGen let ns = randoms gen :: [Int] return $ take n ns cmp1 xy = trace "*" $ compare xy cmp2 xy = trace "#" $ compare xy main = do n <- fmap (read . (!!0)) getArgs xs <- rs n print "Sorting entire list" print $ sortBy cmp1 xs print "Head of sorted list" print $ head $ sortBy cmp2 xs 

    En comptant les caractères * et # , nous pouvons échantillonner le nombre de comparaisons à des points régulièrement espacés (excusez mon python):

     import matplotlib.pyplot as plt import numpy as np import envoy res = [] x = range(10,500000,10000) for i in x: r = envoy.run('./sortCount %i' % i) res.append((r.std_err.count('*'), r.std_err.count('#'))) plt.plot(x, map(lambda x:x[0], res), label="sort") plt.plot(x, map(lambda x:x[1], res), label="minimum") plt.plot(x, x*np.log2(x), label="n*log(n)") plt.plot(x, x, label="n") plt.legend() plt.show() 

    Lancer le script nous donnerait le graphique suivant:

    Les taux de croissance

    La pente de la ligne inférieure est ..

     >>> import numpy as np >>> np.polyfit(x, map(lambda x:x[1], res), deg=1) array([ 1.41324057, -17.7512292 ]) 

    ..1.41324057 (en supposant que c'est une fonction linéaire)