Hat Python einen Listenkonstruktor?

7

Hat python einen Listenkonstruktor wie den cons in OCaml ( :: ) (oder lisp), der eine head element- und tail -Liste benötigt und eine neue Liste zurückgibt head::tail ?

Ich habe nach Python-Listenkonstruktoren gesucht und am Ende etwas anderes über __init__ gefunden. siehe z.B. Eine Liste in Python erstellen - etwas, was hinterhältig vor sich geht?

Um zu verdeutlichen, was ich suche ist die Umkehrung der folgenden Listenzerlegung in Python in dieser Frage gefunden :

%Vor%

Dies ergibt:

%Vor%

Ich suche nach einem Listenkonstruktor, z.B. cons oder :: so, dass

%Vor%     
tinlyx 10.02.2016, 04:01
quelle

4 Antworten

9

Um Ihre Frage zu beantworten, gibt es keine direkte Entsprechung zu den Widersprüchen, die Sie normalerweise in sogenannten "funktionalen" Sprachen finden würden (Lisp, OCaml, Haskell, etc.)

Das liegt daran, dass zwei konkurrierende Modelle Listen von Elementen in Programmiersprachen darstellen.

Verknüpfte Listen

Der, mit dem Sie vertraut zu sein scheinen, wird als verkettete Liste bezeichnet.

Eine verknüpfte Liste besteht aus Cons-Zellen, die jeweils zwei Referenzen enthalten:

  • der erste auf ein Element der Liste und heißt head
  • der andere zur nächsten Cons-Zelle in der Liste und ist tail

Da Listen selten unendlich sind, würde die letzte const-Zelle normalerweise auf einen speziellen Wert zeigen, die leere Liste, manchmal nil genannt.

Wenn Sie die Liste als zukünftige Referenz in einer Variablen speichern möchten, behalten Sie einen Verweis auf die erste Cons-Zelle.

Hier ist eine visuelle Darstellung von Wikipedia .

In diesem Modell wird jede Liste notwendigerweise durch Hinzufügen von Elementen zu der Front konstruiert, indem eine neue Cons-Zelle erzeugt wird, die auf das neue Element als Kopf und auf die zuvor konstruierte Unterliste als deren Schwanz zeigt. Aus diesem Grund wird der Cons-Operator manchmal auch als Listenkonstruktor bezeichnet.

Arrays

Dies ist das Modell, das normalerweise von imperativen Sprachen wie Python bevorzugt wird. In diesem Modell ist eine Liste nur ein Verweis auf einen Bereich im Speicher.

Nehmen wir an, Sie erstellen eine Liste genau so:

%Vor%

Immer wenn Sie eine Liste erstellen, wird Python ihr einen kleinen Speicherbereich zuweisen, in dem die Elemente gespeichert werden, mit etwas mehr Platz, nur für den Fall, dass Sie Elemente später hinzufügen möchten. Um es zu speichern, würden Sie einfach einen Verweis auf das erste Element und auf die Größe des Speicherbereichs speichern:

%Vor%

Wenn Sie ein Element am Ende der Liste hinzufügen möchten, können Sie append

verwenden %Vor%

Ergebnis in der folgenden Liste:

%Vor%

Nehmen wir an, Sie haben eine anfängliche 0 vergessen und möchten sie jetzt an der Vorderseite hinzufügen. Sie können wirklich die Einfügemethode (mit einer Einfügeposition von 0) verwenden:

%Vor%

Aber am Anfang der Liste ist kein Platz! Python hat keine andere Wahl, als jedes einzelne Element einzeln zu kopieren und an der Stelle auf der rechten Seite zu kopieren:

%Vor%

Es mag für ein so kleines Array nicht viel zu sein scheinen, aber stellen Sie sich vor, Ihr Array ist viel größer und Sie wiederholen diese Operation viele Male: Sie würden so viel Zeit damit verbringen, Ihre Liste aufzubauen!

Aus diesem Grund werden Sie keinen Listenkonstruktor in Sprachen finden, die Arrays für ihre Listen wie Python verwenden.

Weiter tauchen: Warum die zwei verschiedenen Modelle?

Sie wundern sich vielleicht, warum verschiedene Sprachen unterschiedliche Listenmodelle bevorzugen und eines der beiden Modelle überlegen ist.

Dies liegt daran, dass diese beiden Datenstrukturen in verschiedenen Kontexten unterschiedliche Leistungen aufweisen. Zwei Beispiele:

Zugriff auf ein Element in der Mitte

Nehmen wir an, Sie möchten das fünfte Element der Liste erhalten.

In der verknüpften Liste müssten Sie Folgendes erhalten:

  • die erste Cons-Zelle
  • dann der Schwanz dieser Zelle, um das zweite Element
  • zu bekommen
  • dann der Schwanz dieser Zelle, um das dritte Element
  • zu bekommen
  • dann der Schwanz dieser Zelle, um das vierte Element
  • zu bekommen
  • und schließlich der Schwanz dieser Zelle, um das fünfte Element
  • zu erhalten

Sie müssten also 5 Referenzen durchgehen!

Bei einem Array ist das viel einfacher: Sie kennen die Referenz des ersten Elements. Sie müssen nur auf die 4 Referenzpunkte auf der rechten Seite zugreifen, vorausgesetzt, die Elemente befinden sich alle in einem zusammenhängenden Speicherbereich!

Wenn Sie sehr oft auf zufällige Elemente einer sehr großen Liste zugreifen müssen, sind Arrays viel besser.

Einfügen eines Elements in der Mitte

Stellen Sie sich vor, Sie möchten jetzt ein Element in die Mitte einfügen.

Mit einer verknüpften Liste:

  • Sie finden die Cons-Zelle, die dem letzten Element vor dem Einfügepunkt entspricht.
  • Sie erstellen eine neue Cons-Zelle mit einem Kopf, der auf das Element zeigt, das Sie hinzufügen möchten, und dem gleichen Schwanz wie die Conts-Zelle, die Sie gerade gefunden haben.
  • Sie können jetzt den Schwanz dieser Zelle so ändern, dass er auf die neu erstellte Zelle zeigt.

Bei einem Array müssen Sie genauso wie beim Hinzufügen eines Elements in der Mitte jedes Element rechts vom Einfügepunkt um eine Stelle nach rechts kopieren!

In dieser Situation ist das die verkettete Liste, die eindeutig überlegen ist.

    
Arthur 10.02.2016, 17:46
quelle
6

Python-Listen sind veränderbar, gegenüber OCamls, die eine Semantik mit unveränderlichem Wert haben, aber wenn a ein Element und b eine Liste ist, können Sie das gewünschte Ergebnis mit [a] + b erhalten, das ein neues zurückgibt Liste, die a enthält, gefolgt von den Elementen in b , und weder a noch b . Ein üblicheres Muster für den Aufbau einer Liste wäre jedoch, dass append oder extend gleich vor Ort sind.

    
hobbs 10.02.2016 04:11
quelle
6

Einige schlagen vor, dass Sie tun:

%Vor%

Was funktioniert, wenn b vom Typ list ist. Sie werden jedoch oft mit einem Objekt arbeiten, das entweder eine Liste oder ein Tupel ist oder (fügen Sie hier Ihr liebstes iterierbares Objekt ein). In diesem Fall ist es vielleicht mehr wert zu tun:

%Vor%

Das macht die ganze Sache agnostisch für den Typ von b (das erlaubt, dass dein Code mehr "ducky" ist, was irgendwie nett sein kann). . .

Natürlich gibt es auch andere Möglichkeiten. . . Zum Beispiel könnten Sie wählen, dass Sie itertools erreichen möchten:

%Vor%

Wiederum haben wir den Vorteil, dass wir uns nicht darum kümmern, welche Art von iterierbarem b ist, und wir nehmen einen Nebenvorteil der Iteration träge - Wir werden keine neue Liste oder Tupel erstellen. Wir machen nur ein Objekt, das dasselbe ergibt, wenn Sie darüber iterieren. Dies kann Speicher sparen (und manchmal Zyklen für Ihre CPU), kann aber auch unbeabsichtigte Konsequenzen haben, wenn b auch eine Art generatorähnliches Objekt ist, das zur gleichen Zeit an anderer Stelle iteriert wird (was nicht passiert) zufällig sehr oft).

    
mgilson 10.02.2016 04:14
quelle
1

Sie können die Liste Verkettung verwenden

%Vor%     
ebracho 10.02.2016 04:12
quelle

Tags und Links