Frage Zusammengesetzte Begriffe und Listen in Prolog


Warum sind zusammengesetzte Begriffe in Bezug auf die Leistung den Listen vorzuziehen? Beispielsweise,

matrix(row(1,2,3),row(1,2,3),row(1,2,3))

ist vorzuziehen

[[1,2,3],[1,2,3],[1,2,3],[1,2,3]]

Vielen Dank!


5
2018-04-24 23:49


Ursprung


Antworten:


Etwas, das die andere (ausgezeichnete) Antwort nicht erwähnte:

Der Zugriff auf das Mitglied einer Liste anhand seiner Position bedeutet, dass Sie die Liste durchlaufen müssen. Der Zugriff auf das Argument eines Begriffs sollte in konstanter Zeit möglich sein. Für einen wahlfreien Zugriff sollte ein Begriff also effizienter sein.


Kurz zur Seite: Sie können versuchen, die Liste marginal schneller durchlaufen zu lassen. Aber die SWI-Prolog Implementierung von nth0_det/3 riecht fast verzweifelt;)


Das könnte Sie interessieren Dieser Thread, besonders diese Zusammenfassung das spricht unter anderem über Listen und Begriffe.

Ein paar Faustregeln folgen.

Anwendungsfall:

  • Wenn Sie im Voraus wissen, wie viele Dinge Sie haben, verwenden Sie einen Begriff.
  • Wenn Sie 0 oder mehr der gleichen Dinge haben können, verwenden Sie eine Liste.
  • Wenn Sie eine Nachschlagetabelle benötigen, ist keine optimal

Effizienz:

  • Wenn Sie einen wahlfreien Zugriff wünschen, verwenden Sie einen Begriff
  • Wenn Ihr Algorithmus auf einer einfach verknüpften Liste gut funktioniert, ist eine Prolog-Liste eine gute Wahl.

Aus dem letzten Punkt folgt: Versuchen Sie, Algorithmen zu finden, die verknüpfte Listen verwenden, nicht Random-Access-Arrays. Es ist nicht immer möglich, aber für viele Probleme haben Sie die Wahl. Das klassische Beispiel wäre eine schnelle Sortierung im Vergleich zu einer Mischsortierung: In Prolog ist eine Mischsortierung definitiv schneller.

So oder so, stellen Sie zuerst sicher, dass Sie es richtig machen, dann sorgen Sie sich um die Effizienz. Stellen Sie sicher, dass Sie die Leistungsengpässe messen, bevor Sie mit der Optimierung beginnen.

Die Wahl eines optimalen Algorithmus und einer optimalen Datenstruktur bedeutet natürlich, dass Sie sowohl Ihr Problem als auch die verfügbaren Werkzeuge kennen müssen. Nicht relevant für Ihr Problem, aber das Schöne an der "Standard Template Library" für C ++ ist, dass sowohl für Algorithmen als auch für Datenstrukturen die Zeitkomplexität ("große O-Notation") eine inhärente Eigenschaft und kein Implementierungsdetail ist.


6
2018-04-25 09:37



Zuerst nur um klar zu sein: Listen sind eine Art zusammengesetzter Begriff.

Um zu sehen, welche Listen sind, verwenden Sie write_canonical/1. Zum Beispiel mit GNU Prolog:

| ?- write_canonical([1,2,3]).  
'.'(1,'.'(2,'.'(3,[])))

Bezüglich der Repräsentation im Gedächtnis empfehle ich Richard O'Keefes Buch. Die Details unterscheiden sich zwischen den Systemen, aber Sie können ziemlich sicher sein, dass Sie den Begriff darstellen row(1,2,3) in Erinnerung brauchen Sie:

  • eine Speicherzelle für den Funktor
  • 3 Speicherzellen für die Argumente

Für den Ausdruck .(1, .(2, .(3, []) In einer einfachen Speicherdarstellung benötigen Sie:

  • 3 Speicherzellen für die drei '.'/2 Funktoren
  • 3 Speicherzellen für 1, 2, 3
  • wahrscheinlich einige mehr (wie für []).

Sie sehen bereits, dass die Verwendung von Listen mindestens grob ist zweimal so viel Speicher in dieser Darstellung.

Ein paar einfache Tests, die Sie selbst durchführen können, helfen Ihnen, den Unterschied im Speicherverbrauch dieser Darstellungen für Ihr System zu sehen.


6
2018-04-25 00:07



Ein weiterer Aspekt ist die zeitliche Leistung beim Zugriff auf ein bestimmtes Element. Mit einer Liste erhalten Sie einen linearen Zugriff auf ihre Elemente. Aber mit einem zusammengesetzten Ausdruck der Form functor(arg1, arg2, ..., argn, ...)Wir können den Standard verwenden arg/3 Eingebautes Prädikat für den konstanten Zugriff auf jedes Argument. I.e. O (N) gegen O (1) mit jeder sinnvollen Prolog-Implementierung.

Aber es gibt keine definitive Antwort auf Ihre formulierte Frage. Die beste Lösung hängt von dem speziellen Problem ab, das Sie lösen. Beispielsweise kann das Anwenden einer Operation auf alle Argumente mit einer Liste schneller sein (im Vergleich zur Verwendung einer Lösung auf Basis von arg/3). Es hängt aber auch vom verwendeten Prolog-System ab. Wenn Leistung ein Hauptanliegen ist, ist Benchmarking der Schlüssel. Vermeiden Sie es, dies auf einer Mikroebene zu tun und berücksichtigen Sie stattdessen, wie der Begriff in allen Teilen Ihrer Anwendung, die damit umgehen, erstellt und aufgerufen wird.


4
2018-04-25 09:43