Analyse de complexité d'algorithmes sur les implémentations de langages de programmation fonctionnels

J'ai appris aujourd'hui que l'analyse d'algorithme diffère en fonction du modèle de calcul. C'est quelque chose auquel je n'ai jamais pensé ni entendu parler.

Un exemple qui m'a été donné, qui l'a illustré davantage, par l'utilisateur @chi était:

Par exemple, considérons la tâche: étant donné retournent . En RAM, cela peut être résolu dans car l'accès au tableau est à temps constant. En utilisant des MT, nous devons analyser toute l'entrée, donc c'est $(i,x_1 ,…,x_n )$ $x_i$ $O(1)$ $O(n)$

Cela me fait me poser des questions sur les langages fonctionnels; D'après ma compréhension, «les langages fonctionnels sont intimement liés au calcul lambda» (d'après un commentaire de Yuval Filmus ici ). Donc, si les langages fonctionnels sont basés sur le calcul lambda, mais qu'ils fonctionnent sur des machines basées sur la RAM, quelle est la bonne façon d'effectuer une analyse de complexité sur des algorithmes implémentés à l'aide de structures de données et de langages purement fonctionnels?

Je n'ai pas eu l'occasion de lire les structures de données purement fonctionnelles mais j'ai regardé la page Wikipedia pour le sujet, et il semble que certaines des structures de données remplacent les tableaux traditionnels par:

"Les tableaux peuvent être remplacés par une carte ou une liste d'accès aléatoire, qui admet une implémentation purement fonctionnelle, mais le temps d'accès et de mise à jour est logarithmique."

Dans ce cas, le modèle de calcul serait différent, n'est-ce pas?

complexity-theory algorithm-analysis computability computation-models lambda-calculus Abdul
la source

Je ne suis certainement pas un expert sur ce sujet, mais je crois avoir entendu dire que 1) une machine semblable à du lisp (avec son propre modèle de coût) peut simuler des programmes RAM avec un facteur supplémentaire

(cela semble facile à prouver) , et 2) la question de savoir si ce facteur est vraiment nécessaire reste un problème ouvert. De plus, on peut soutenir que l'attribution d'un coût O (1) à l'accès à la matrice dans le modèle RAM est trop généreuse. Dans le matériel, l'accès à la mémoire doit traverser

portes

où

est la taille de la mémoire physique.

O (\log n)

$O(\log n)$

O (\log n)

$O(\log n)$

n

$n$

chi

Gardez également à l'esprit que pratiquement tous les langages FP du monde réel ont des tableaux sous une forme quelconque, avec un temps d'accès

garanti (comme dans les langages impératifs). Ceci est généralement résolu en les ajoutant en tant que primitive de langue.

O (1)

$O(1)$

chi

Un exemple d'un modèle de calcul différent serait le nombre de réductions bêta effectuées sur un terme de calcul lambda. En FP, nous utilisons davantage un modèle de bélier déguisé en calcul lambda, si cela a du sens

Kurt Mueller

@KurtMueller Notez que nous pouvons obtenir un terme lambda de taille

après seulement

réductions de bête. Cela rend le modèle de coût du comptage du nombre de bêta irréaliste. Un meilleur argument pourrait être de peser chaque étape par la taille des termes en question. Pourtant, ce n'est pas le seul modèle possible: l'évaluation optimale des termes lambda n'applique pas la bêta de manière naïve, préférant des machines de réduction de graphes plus sophistiquées. Dans ce cas, il ne serait probablement pas approprié de compter les bêtas.

O (2^{n})

$O(2^n)$

O (n)

$O(n)$

chi

Notez que vous devez également savoir si votre langage fonctionnel est empressé ou paresseux / strict ou non strict. J'ai récemment rencontré une situation où un algorithme du monde réel était polynomial dans Haskell (non strict) mais la traduction naïve en OCaml (stricte) était exponentielle.

Eric Lippert

Réponses:

Cela dépend de la sémantique de votre langage fonctionnel. Vous ne pouvez pas faire une analyse d'algorithme sur les langages de programmation isolément, car vous ne savez pas ce que signifient réellement les instructions. La spécification de votre langue doit fournir une sémantique suffisamment détaillée. Si votre langue spécifie tout en termes de calcul lambda, vous avez besoin d'une mesure des coûts pour les réductions (sont-ils O (1) ou dépendent-ils de la taille du terme que vous réduisez?).

Je pense que la plupart des langages fonctionnels ne le font pas de cette façon et fournissent plutôt des instructions plus utiles comme "les appels de fonction sont O (1), en ajoutant à la tête d'une liste est O (1)", des choses comme ça.

adrianN
la source

Je crois que je comprends en quelque sorte votre réponse (le malentendu est probablement dû à mon manque de compréhension dans le calcul lambda): Vous dites que vous devez essentiellement faire l'analyse au cas par cas (le cas étant la langue), plutôt que de manière générale, car certaines opérations ont des significations différentes par langue. Ma compréhension est-elle correcte?

Abdul

Oui. Votre concepteur de langage doit vous dire ce que signifient réellement les choses que vous pouvez écrire dans la langue avant d'analyser le temps d'exécution d'un algorithme.

adrianN

"Vous ne pouvez pas faire une analyse d'algorithme sur les langages de programmation de manière isolée" - cela faisait-il référence aux langages FP ou aux langages en général? Si cela faisait référence au précédent, comment pouvons-nous analyser les algorithmes à l'école de manière aussi générale, c'est-à-dire analyser les problèmes Java, C / C ++, Python? Est-ce parce qu'ils sont tous très similaires? Ou est-ce parce que les structures de données et les ADT sous-jacents sont tous les mêmes et mis en œuvre de la même manière? Ou enfin, est-ce parce que ces cours sont simplement à des fins éducatives et n'ont pas nécessairement besoin d'être strictement précis?

Abdul

C'est vrai pour tous les langages de programmation. Pour être strictement correct, vous devez d'abord corriger un modèle de machine, par exemple la RAM et (une petite poignée) d'instructions qu'il prend en charge. Vous pouvez uniquement effectuer une analyse sur des programmes en utilisant uniquement ces instructions. Ensuite, vous pouvez penser à un mappage de votre langage de programmation sur ce modèle de machine. Ensuite, vous pouvez analyser des programmes dans le langage de programmation. Pour un traitement très rigoureux, vérifiez comment Knuth le fait dans The Art of Computer Programming. Une grande partie de cela peut être simplifiée en raison des constantes masquantes big-O.

adrianN