haskell longueur d'exécution O (1) ou O (n)

Question

Je travaillais sur une affectation Haskell et j'essayais de trouver des façons de rendre mon code plus rapide. Par exemple, ma fonction factorielle ci-dessous trouve le nombre de diviseurs d'un nombre entier. Cependant, il m'est apparu que je pouvais rendre mon code plus rapide en évitant d'utiliser la "longueur".

factors :: Int -> Int 
factors x = go 1 
    where 
    go :: Int -> Int 
    go i 
     | i == x  = 1 
     | mod x i == 0 = 1 + go (i + 1) 
     | otherwise  = go (i + 1) 

Je me demande si la fonction de longueur d'Haskell est O (n) comme strlen() en C ou O (1) comme String.length() en Java.

De même, y a-t-il un meilleur ou plus efficace d'écrire mon code?

Answer 1

Du point de vue théorique, on ne peut pas savoir si length est θ (n), nous savons qu'il est O (n), mais il est techniquement possible que Haskell met en œuvre plus rapide pour les listes connues.

Depuis un compilateur Haskell pourrait être libre d'implémenter une liste comme ils le veulent. Mais néanmoins il n'a pas d'importance, puisque dans ce cas générant la liste en premier lieu prendra θ (n).

Notez que même si le compilateur utilise une structure de données plus dédié, Haskell est paresseux, de sorte que votre compréhension de la liste ne donne pas lieu à une liste complète, mais plus dans une fonction qui peut générer une liste paresseusement.

Enfin, si nous évaluions la compréhension de la liste avec impatience, il faudrait à nouveau O (n) pour d'abord générer la liste en premier lieu. Donc, même si l'obtention de la longueur était très rapide, la génération de la liste nécessiterait O (n) comme limite inférieure. Donc, quelle que soit l'efficacité de length, l'algorithme va encore évoluer linéairement avec l'entrée.

Votre propre implémentation utilise à nouveau O (n) (et n'est pas très sûr pour être honnête). Néanmoins, vous pouvez facilement speedup la factorisation d'un nombre à O (sqrt n):

factors :: Int -> Int 
factors x = go 1 
    where 
    go :: Int -> Int 
    go i | i2 > x = 0 
     | i2 == x = 1 
     | mod x i == 0 = 2 + go (i+1) 
     | otherwise = go (i + 1) 
     where i2 = i*i 

nous énumérons ici de 1 à sqrt (n). Chaque fois que nous trouvons un facteur a, nous savons qu'il y a un co -facteur b = x/a. Tant que a n'est pas égal à sqrt (x), nous savons que ceux-ci sont différents. Dans le cas a est égal à sqrt (x), nous savons que a est égal à b et ainsi nous comptons cela comme un. Cela étant dit, il y a certainement des moyens plus rapides de le faire. C'est un sujet avec beaucoup de recherche qui a donné des algorithmes plus efficaces. Je ne suggère pas que ce qui précède est le plus rapide, mais c'est certainement une énorme amélioration en termes de complexité temporelle.

Answer 2

La construction de la liste avec la compréhension de liste prend déjà O(n).Par conséquent, il n'y a pas beaucoup de surcharge lors de l'utilisation d'une fonction de longueur qui devrait avoir la complexité O(n) dans le pire des cas.

Answer 3

De même, y a-t-il un meilleur ou plus efficace d'écrire mon code?

La factorisation en nombre entier est l'un des problèmes les plus connus. Il y a sûrement beaucoup d'algorithmes qui ont été proposés pour cela, même si je ne suis pas assez expert pour faire une recommandation (CS.SE est proche, et peut aider à cela, si nécessaire). Aucune de ces propositions n'est un temps polynomial, mais cela ne les empêche pas d'être plus rapide que l'approche triviale.

Même sans regarder la littérature, quelques optimisations simples peuvent être trouvées.

• Le code original scanne toute la liste [1..x], mais ce n'est pas nécessaire. Nous pourrions nous arrêter à sqrt x, car après il n'y a plus de diviseurs.

• Encore plus: après que nous trouvons un diviseur m, on pourrait diviser par xm (autant de fois que possible), et récursif avec ce nouveau numéro. Par exemple. si x = 1000 après que nous essayons m=2, nous calculons 1000 -> 500 -> 250 -> 125, puis trouvons les nouveaux diviseurs (plus grands que 2) dans 125. Notez comment cela a rendu le nombre beaucoup plus petit.

Je quitterai la mise en œuvre des stratégies dans ce Haskell comme un exercice :-P

Answer 4

Willem Van Onsem arrive en tête avec un étrange, et je pense pas facilement défendable l'argument (que, dans un certain sens « théorique » nous pouvons ne connaissez pas la complexité de length puisque le compilateur est libre d'optimiser les structures de code et de données). Laissant de côté la question de savoir si c'est même correct ou une contradiction enfouie, je ne pense pas que ce soit une façon très fructueuse d'aborder ce genre de problème.

Vous pouvez en effet déduire la complexité des length (et bien d'autres fonctions) juste en regardant la définition de [a]:

Prelude> :info [] 
data [] a = [] | a : [a] -- Defined in ‘GHC.Types’ 

Les listes sont définis inductivement; vous pouvez voir à partir de cette définition (qui est presque juste normal haskell) qu'au niveau supérieur une liste est soit le constructeur [] ou :. Il est évident que length doit se répéter n fois sur cette structure et devrait donc être O (n).

Il est très important de pouvoir raisonner au moins de manière intuitive de cette manière, en particulier sur les listes qui sont omniprésentes. par exemple. rapide quelle est la complexité de (!!)?

Si vous voulez faire un plongeon profond dans le raisonnement formel sur la complexité du temps en présence de la paresse, alors vous aurez besoin de ramasser "Structures de données purement fonctionnelles" par Okasaki.