Algorithmuskomplexitätsanalyse für Implementierungen funktionaler Programmiersprachen

Ich habe heute gelernt, dass sich die Algorithmusanalyse basierend auf dem Rechenmodell unterscheidet. Daran habe ich noch nie gedacht oder gehört.

Ein Beispiel, das mir von User @chi weiter veranschaulicht wurde, war:

Betrachten Sie zB die Aufgabe: gegeben return . Im RAM kann dies in gelöst werden, da der Array-Zugriff zeitlich konstant ist. Mit TMs müssen wir die gesamte Eingabe scannen, also ist es $(i,x_1 ,…,x_n )$ $x_i$ $O(1)$ $O(n)$

Das lässt mich über funktionale Sprachen nachdenken; Nach meinem Verständnis sind "funktionale Sprachen eng mit dem Lambda-Kalkül verbunden" (aus einem Kommentar von Yuval Filmus hier ). Wenn funktionale Sprachen auf Lambda-Berechnungen basieren, aber auf RAM-basierten Maschinen ausgeführt werden, wie kann dann die Komplexitätsanalyse für Algorithmen durchgeführt werden, die mit rein funktionalen Datenstrukturen und Sprachen implementiert wurden?

Ich hatte keine Gelegenheit, rein funktionale Datenstrukturen zu lesen, aber ich habe mir die Wikipedia-Seite für das Thema angesehen, und es scheint, dass einige der Datenstrukturen herkömmliche Arrays ersetzen durch:

"Arrays können durch Karten- oder Direktzugriffslisten ersetzt werden, die eine rein funktionale Implementierung zulassen, aber die Zugriffs- und Aktualisierungszeit ist logarithmisch."

In diesem Fall wäre das Rechenmodell anders, richtig?

complexity-theory algorithm-analysis computability computation-models lambda-calculus Abdul
quelle

Ich bin definitiv kein Experte in diesem Thema, aber ich glaube, ich habe gehört, dass 1) eine lisp-ähnliche Maschine (mit einem eigenen Kostenmodell) RAM-Programme mit einem zusätzlichen Faktor ( simulieren kann (dies scheint leicht zu beweisen zu sein) ) und 2) ob dieser Faktor wirklich benötigt wird, ist noch ein offenes Problem. Ferner kann argumentiert werden, dass das Zuweisen von O (1) -Kosten zum Array-Zugriff im RAM-Modell zu großzügig ist. In der Hardware muss der Speicherzugriff Gatter durchlaufen, wobei die Größe des physischen Speichers ist.

O (\log n)

$O(\log n)$

O (\log n)

$O(\log n)$

n

$n$

Chi

Beachten Sie auch, dass praktisch alle realen FP-Sprachen Arrays in irgendeiner Form mit einer garantierten -Zugriffszeit haben (wie in imperativen Sprachen). Dies wird normalerweise gelöst, indem sie als Sprachprimitiv hinzugefügt werden.

O (1)

$O(1)$

Chi

Ein Beispiel für ein anderes Rechenmodell wäre die Anzahl der Beta-Reduktionen, die an einem Lambda-Kalkül-Term durchgeführt werden. In FP verwenden wir eher ein RAM-Modell, das als Lambda-Kalkül verkleidet ist, wenn das Sinn macht

Kurt Mueller

@KurtMueller Beachten Sie, dass wir einen Lambda-Term der Größe nur nach Reduktionen erhalten können. Dies macht das Kostenmodell zum Zählen der Beta-Anzahl unrealistisch. Ein wohl besserer Weg könnte sein, jeden Schritt nach der Größe der vorliegenden Begriffe abzuwägen. Dies ist jedoch nicht das einzig mögliche Modell: Die optimale Bewertung von Lambda-Begriffen wendet Beta nicht auf naive Weise an und bevorzugt einige ausgefeiltere Grafikreduktionsmaschinen. In diesem Fall wäre es wahrscheinlich nicht angemessen, die Betas zu zählen.

O (2^{n})

$O(2^n)$

O (n)

$O(n)$

Chi

Beachten Sie, dass Sie auch wissen müssen, ob Ihre funktionale Sprache eifrig oder faul / streng oder nicht streng ist. Ich bin kürzlich auf eine Situation gestoßen, in der ein realer Algorithmus in Haskell polynomisch war (nicht streng), die naive Übersetzung in OCaml (streng) jedoch exponentiell war.

Eric Lippert

Antworten:

Dies hängt von der Semantik Ihrer funktionalen Sprache ab. Sie können keine Algorithmusanalyse für Programmiersprachen isoliert durchführen, da Sie nicht wissen, was die Anweisungen tatsächlich bedeuten. Die Spezifikation für Ihre Sprache muss eine ausreichend detaillierte Semantik enthalten. Wenn Ihre Sprache alles in Bezug auf die Lambda-Rechnung spezifiziert, benötigen Sie ein Kostenmaß für Reduzierungen (sind sie O (1) oder hängen sie von der Größe des Begriffs ab, den Sie reduzieren?).

Ich denke, dass die meisten funktionalen Sprachen dies nicht so tun und stattdessen nützlichere Aussagen wie "Funktionsaufrufe sind O (1), an den Kopf einer Liste anhängen ist O (1)" liefern, solche Dinge.

adrianN
quelle

Ich glaube, ich verstehe Ihre Antwort irgendwie (das Missverständnis ist höchstwahrscheinlich auf mein Unverständnis in der Lambda-Rechnung zurückzuführen): Sie sagen, Sie müssen die Analyse grundsätzlich von Fall zu Fall (Fall ist Sprache) durchführen, anstatt a allgemeiner Weg, weil bestimmte Operationen pro Sprache unterschiedliche Bedeutungen haben. Ist mein Verständnis richtig?

Abdul

Ja. Ihr Sprachdesigner muss Ihnen sagen, was die Dinge, die Sie in der Sprache schreiben können, tatsächlich bedeuten, bevor Sie die Laufzeit eines Algorithmus analysieren können.

AdrianN

"Sie können keine Algorithmusanalyse für isolierte Programmiersprachen durchführen" - bezog sich dies auf FP-Sprachen oder Sprachen im Allgemeinen? Wenn es sich auf das frühere bezog, wie können wir dann die Analyse in der Schule so allgemein durchführen, dh die Analyse über Java-, C / C ++ - und Python-Probleme hinweg durchführen? Liegt es daran, dass sie sich alle sehr ähnlich sind? Oder liegt es daran, dass die zugrunde liegenden Datenstrukturen und ADTs alle gleich sind und auch auf die gleiche Weise implementiert werden? Oder schließlich ist es , weil diese Kurse einfach aus Gründen der Erziehung sind, und nicht unbedingt zu müssen streng genau?

Abdul

Dies gilt für alle Programmiersprachen. Um genau zu sein, müssen Sie zuerst ein Maschinenmodell reparieren, z. B. den Arbeitsspeicher und (eine kleine Handvoll) Anweisungen, die es unterstützt. Sie können Programme nur mit diesen Anweisungen analysieren. Dann können Sie sich eine Zuordnung Ihrer Programmiersprache zu diesem Maschinenmodell vorstellen. Anschließend können Sie Programme in der Programmiersprache analysieren. Überprüfen Sie für eine sehr strenge Behandlung, wie Knuth dies in The Art of Computer Programming tut. Vieles davon kann aufgrund von Big-O-Versteckkonstanten vereinfacht werden.

AdrianN