Wie wird die Komplexität von Algorithmen für funktionale Sprachen modelliert?

38

Die Komplexität des Algorithmus ist so ausgelegt, dass sie unabhängig von Details auf niedrigeren Ebenen ist. Sie basiert jedoch auf einem zwingenden Modell, z. B. dem Array-Zugriff und dem Ändern eines Knotens in einem Baum. Dies ist in reinen Funktionssprachen nicht der Fall. Die Haskell-Liste benötigt für den Zugriff eine lineare Zeit. Zum Ändern eines Knotens in einem Baum muss eine neue Kopie des Baums erstellt werden.

Sollte es dann eine alternative Modellierung der Algorithmuskomplexität für funktionale Sprachen geben?

wsaleem
quelle
3
Dies könnte das sein, wonach Sie suchen.
Aristu
1
Ihre Frage könnte hier beantwortet werden: cs.stackexchange.com/q/18262/755 . Insbesondere unterscheidet sich die Zeitkomplexität in einer rein funktionalen Sprache von der Zeitkomplexität in einer imperativen Sprache um höchstens ein Verhältnis von für einige geeignete Annahmen über die Fähigkeiten beider Sprachen. O(logn)
DW
3
GHC Haskell unterstützt veränderbare Arrays und Bäume und so weiter. So können Sie den Array-Zugriff durchführen und Baumknoten in O (1) -Zeit mithilfe von "Status-Threads" (den STMonaden) ändern .
Tanner Swett
1
@ BobJarvis Hängt ab. Ist eine Liste ein abstrakter Datentyp für Sie oder ziehen Sie speziell verknüpfte Listen in Betracht?
Raphael
1
Welchen Zweck suchen Sie für die Modellierung der algorithmischen Komplexität? Suchen Sie etwas, das mathematisch rein ist, oder etwas, das praktisch ist? Für einen praktischen Wert sollte darauf geachtet werden, ob Ihnen ein Speicher zur Verfügung steht oder nicht, aber aus mathematisch puristischer Sicht sollten die Fähigkeiten der Implementierung keine Rolle spielen.
Cort Ammon

Antworten:

34

Wenn Sie davon ausgehen, dass der -calculus ein gutes Modell für funktionale Programmiersprachen ist, könnte man meinen: Der -calculus hat eine scheinbar einfache Vorstellung von Zeitkomplexität: Zählen Sie einfach die Anzahl der -Reduktionsschritte .λλβ(λx.M)NM[N/x]

Aber ist das ein gutes Maß für die Komplexität?

Um diese Frage zu beantworten, sollten wir zunächst klären, was wir unter Komplexitätsmaß verstehen. Eine gute Antwort liefert die These von Slot und van Emde Boas : Jedes gute Komplexitätsmaß sollte eine polynomielle Beziehung zum kanonischen Begriff der Zeitkomplexität haben, der mit Turing-Maschinen definiert wird. Mit anderen Worten, es sollte ein ‚angemessen‘ kodiert sein von Kalkül Bezug auf Turingmaschinen, wie für ein Polynom , ist es der Fall , dass für jeden Term der Größe: reduziert sich auf einen Wert in -Reduktionsschritten genau dann, wenn sich auf einen Wert in reduzierttr(.)λpM|M|Mp(|M|) βtr(M)p(|tr(M)|) Schritte einer Turingmaschine.

Es war lange unklar, ob dies im λ-Kalkül erreicht werden kann. Die Hauptprobleme sind die folgenden.

  • Es gibt Begriffe, die Normalformen (in einer Polynomzahl von Schritten) erzeugen, die exponentiell groß sind. Sogar das Aufschreiben der normalen Formen nimmt exponentielle Zeit in Anspruch.
  • Die gewählte Reduktionsstrategie spielt eine wichtige Rolle. Zum Beispiel gibt es eine Familie von Begriffen, die in einer Polynomzahl von parallelen β-Schritten (im Sinne einer optimalen λ-Reduktion ) abnimmt , deren Komplexität jedoch nicht elementar ist (dh schlechter als exponentiell).

Die Veröffentlichung " Beta Reduction is Invariant, Indeed " von B. Accattoli und U. Dal Lago klärt das Problem, indem sie eine "vernünftige" Codierung zeigt, die die Komplexitätsklasse P der polynomialen Zeitfunktionen beibehält , wobei von Kürzungen des äußersten linken Randes der Call-by-Name ausgegangen wird . Die wichtigste Erkenntnis ist, dass das exponentielle Aufblasen nur aus „uninteressanten“ Gründen erfolgen kann, die durch richtiges Teilen besiegt werden können. Mit anderen Worten, die Klasse P ist die gleiche, unabhängig davon, ob Sie sie mit Turing-Maschinenschritten oder mit (ganz links) -Reduktionen definieren.β

Ich bin mir nicht sicher, wie die Situation für andere Bewertungsstrategien ist. Mir ist nicht bekannt, dass ein ähnliches Programm für die Raumkomplexität durchgeführt wurde.

Martin Berger
quelle
23

Die Komplexität des Algorithmus ist so ausgelegt, dass sie von Details auf niedrigerer Ebene unabhängig ist.

Nein nicht wirklich. Wir zählen immer elementare Operationen in einigen Maschinenmodellen:

  • Schritte für Turingmaschinen.
  • Grundlegende Operationen auf RAMs.

Sie haben wahrscheinlich an das gesamte / / Geschäft gedacht. Während es stimmt, dass Sie mit Landau Asymptotics einige Implementierungsdetails abstrahieren können, werden Sie die Auswirkungen des Maschinenmodells nicht los. Algorithmen haben sehr unterschiedliche Laufzeiten, sagen wir TMs und RAMs - auch wenn Sie nur Klassen berücksichtigen!ΩΘOΘ

Daher hat Ihre Frage eine einfache Antwort: Fixieren Sie ein Maschinenmodell und welche "Operationen" zu zählen sind. Dies gibt Ihnen ein Maß. Wenn Sie möchten, dass die Ergebnisse mit nicht funktionalen Algorithmen vergleichbar sind, sollten Sie Ihre Programme am besten in RAM (für die Algorithmusanalyse) oder TM (für die Komplexitätstheorie) kompilieren und das Ergebnis analysieren. Möglicherweise existieren Übertragungssätze, um diesen Prozess zu vereinfachen.

Raphael
quelle
Einverstanden. Randnotiz: Menschen machen häufig eine Menge Fehler, was Operationen "konstant" sind. Angenommen, a + b ist, O(1)wenn es wirklich istO(log ab)
Paul Draper
3
@PaulDraper Das ist eine andere Annahme, nicht unbedingt ein Fehler. Wir können modellieren, was wir wollen - die Frage ist, ob es interessante Fragen beantwortet. Siehe auch hier .
Raphael
das klingt sehr viel wie "loswerden des maschinenmodells"
Paul Draper
@PaulDraper Hängt davon ab, welche Gefühle Sie dem Wort "Maschine" hinzufügen. Siehe auch diese Diskussion . FWIW, das Stückkosten-RAM-Modell - wohl das Standardmodell in der Algorithmenanalyse! - ist nützlich, sonst wäre es seit Jahrzehnten nicht mehr verwendet worden. Alle bekannten Grenzen für das Sortieren, Suchen usw. basieren auf diesem Modell. Es ist sinnvoll, weil es echte Computer gut modelliert, solange die Zahlen in Register passen.
Raphael
1

Anstatt Ihr Komplexitätsmaß in Bezug auf eine zugrunde liegende abstrakte Maschine zu formulieren, können Sie die Kosten in die Sprachdefinitionen selbst einbeziehen - dies wird als Kostendynamik bezeichnet . Man fügt jeder Bewertungsregel in der Sprache auf kompositorische Weise Kosten hinzu - das heißt, die Kosten einer Operation sind eine Funktion der Kosten ihrer Unterausdrücke. Dieser Ansatz ist für funktionale Sprachen am natürlichsten, kann jedoch für jede genau definierte Programmiersprache verwendet werden (natürlich sind die meisten Programmiersprachen leider nicht genau definiert).

Gartenkopf
quelle
<Diskussion darüber, was ein Maschinenmodell gelöscht hat.> Lassen Sie uns diese Diskussion im Chat fortsetzen .
Raphael