Verwirrende [...] Liste in Python: Was ist das?

Question

Also schrieb ich einen einfachen binären Baum in Python und stieß auf [...]

Ich glaube nicht, dass dies mit dem Ellipsis-Objekt verwandt ist, mehr scheint es etwas mit einer Unendlichkeit zu tun haben Schleife (wegen der flachen Kopie von Python?). Die Quelle dieser unendlichen Schleife und warum es nicht erweitert erhalten, während erweitert, wenn etwas erreicht, das ich vollständig verloren bin, aber

>>> a 
[[[[[], [], 8, 3], [[], [], 3, 2], 6, 3], [], 1, 4], [[], [], -4, 2], 0, 0] 
>>> Keys(a)#With a+b 
[0, 1, 6, 8, 3, -4] 
>>> Keys(a)#With [a,b] 
[8, [...], [...], 3, [...], [...], 6, [...], [...], 1, [...], [...], -4, [...], [...], 0, [...], [...]] 
>>> Keys(a)[1]#?? 
[8, [...], [...], 3, [...], [...], 6, [...], [...], 1, [...], [...], -4, [...], [...], 0, [...], [...], 8, [...], [...], 3, [...], [...], 6, [...], [...], 1, [...], [...], -4, [...], [...], 0, [...], [...]] 

Version a + b

def Keys(x,y=[]): 
    if len(x):y+=[x[2]]+Keys(x[0],y)+Keys(x[1],y)#Though it seems I was using y=y[:]+, this actually outputs an ugly mess 
    return y 

Version mit mit [a , b]

def Keys(x,y=[]): 
    if len(x):y+=[x[2],Keys(x[0],y),Keys(x[1],y)] 
    return y 

Also was genau ist [...]?

Answer 1

BEARBEITEN: Wie oben erwähnt, ist dies nicht das Ellipsis-Objekt, sondern das Ergebnis einer geloopten Liste. Ich bin hier auf die Waffe gesprungen. Das Wissen über das Ellipsis-Objekt ist ein gutes Stück Wissen über das Zurückladen, wenn Sie in einem tatsächlichen Code eine Ellipse finden, und nicht die Ausgabe.

---

Das Ellipsis-Objekt in Python wird für die erweiterte Slice-Notation verwendet. Es wird nicht in aktuellen Python-Core-Bibliotheken verwendet, kann jedoch von Entwicklern in eigenen Bibliotheken definiert werden. Zum Beispiel verwenden NumPy (oder SciPy) dies als Teil ihres Array-Objekts. Sie müssen sich die Dokumentation von tree() ansehen, um genau zu wissen, wie sich Ellipsis in diesem Objekt verhält.

Von Python documentation:

3.11.8 Die Auslassungspunkte Objekt

Diese Aufgabe wird durch erweiterte Slice Notation (siehe Python Referenz Manual) verwendet wird. Es unterstützt keine speziellen Operationen. Es gibt genau ein Ellipsenobjekt mit dem Namen Ellipsis (ein vordefinierter Name).

Es wird als Ellipse geschrieben.

Answer 2

Es kann auch erscheinen, wenn Sie eine kreisförmige Struktur mit einer Liste haben, die auf sich selbst zeigt. Wie folgt aus:

>>> a = [1,2] 
>>> a.append(a) 
>>> a 
[1, 2, [...]] 
>>> 

Da Python nicht die Struktur ausdrucken kann (es wäre eine Endlosschleife sein) verwendet es die Auslassungszeichen zu zeigen, dass es Rekursion in der Struktur ist.

---

Ich bin mir nicht ganz sicher, ob die Frage war, was, was los ist und wie es zu beheben, aber ich werde versuchen, die Funktionen, die oben zu korrigieren.

In beiden machen Sie zuerst zwei rekursive Aufrufe, die Daten zur Liste y hinzufügen, und dann AGAIN die zurückgegebenen Daten an y anhängen. Dies bedeutet, dass dieselben Daten mehrmals im Ergebnis vorhanden sind.

Entweder sammeln einfach alle Daten, ohne irgendeiner y Zugabe mit so etwas wie

return [x[2]]+keys(x[0])+keys(x[1]) 

oder tun nur das Anfügen der Anrufe, mit so etwas wie

y += [x[2]] 
keys(x[0], y) #Add left children to y... 
keys(x[1], y) #Add right children to y... 
return y 

(natürlich beide Diese Snippets brauchen Handhabung für leere Listen usw.)

@Abgan auch darauf hingewiesen, dass Sie wirklich wollen y=[] in der Initialisierung .

Answer 3

Ich verstehe Ihren Code oben nicht, aber die [...] denke ich ist der Python-Interpreter überspringt unendliche Datenstrukturen. Zum Beispiel:

>>> a = [0, 1] 
>>> a[0] = a 
>>> a 
[[...], 1] 

Es sieht aus wie Ihre Baumstruktur wird Schleife.

Die Antworten zu Scheibenobjekten sind neben dem Punkt.

Answer 4

Ich glaube, dass dein 'Baum' sich selbst enthält, daher enthält es Zyklen.

Versuchen Sie diesen Code:

 
    a = [1,2,3,4] 
    print a 
    a.append(a) 
    print a 

Die ersten Druckausgaben:

 
    [1,2,3,4] 

während der zweite:

 
    [1,2,3,4, [...]] 

Der Grund

 
def Keys(x,y=[]): 

verwendet Das ist falsch und böse ist. List ist ein veränderbares Objekt, und wenn es als Standardparameter verwendet wird, wird es zwischen Funktionsaufrufen beibehalten. Also jede y + = „etwas“ Operation ergänzt die gleiche Liste (in allen Funktionsaufrufen, und da die Funktion rekursiv ...)

---

Siehe Effbot oder Devshed für weitere Details über veränderbare Objekte weitergegeben als Standardwerte für Funktionen.

Answer 5

Ich glaube nicht, dass dies mit dem Ellipsis-Objekt zusammenhängt, eher scheint es etwas mit einer Unendlichkeitsschleife zu tun zu haben (wegen Python's flacher Kopie?). Die Quelle dieser unendlichen Schleife und warum es nicht erweitert erhalten, während erweitert, wenn etwas erreicht, das ich vollständig verloren bin, aber

Blick auf den folgenden Code:

>>> a = [0] 
>>> a.append(a) 
>>> print a 
[0, [...]] 

Wie ist Python soll einen drucken? Es ist eine Liste, die eine Null und einen Verweis auf sich selbst enthält.Daher ist es eine Liste, die eine Null und einen Verweis auf eine Liste enthält

[0, [...]] 

die wiederum eine Null ist und einen Verweis auf eine Liste enthält

[0, [0, [...]]] 

die wiederum eine Null und eine Referenz enthält auf eine Liste, und so weiter, rekursiv:

[0, [0, [0, [...]]]] 
[0, [0, [0, [0, [...]]]]] 
[0, [0, [0, [0, [0, [...]]]]]] 
... 

Es ist nichts falsch mit der rekursiven Datenstruktur selbst. Das einzige Problem ist, dass es nicht angezeigt werden kann, denn dies würde eine unendliche Rekursion bedeuten. Daher stoppt Python bei dem ersten Rekursionsschritt und behandelt das Infinity-Problem, das nur die Ellipse druckt, wie in früheren Antworten darauf hingewiesen wurde.

Answer 6

Ok, also in den Punkten:

1. Du unendliche Daten Struktur zu schaffen:

   def Keys(x,y=[])

   die gleiche 'y' in jeder Anruf verwenden. Das ist einfach nicht korrekt.

2. Die print Aussage ist jedoch klug genug, nicht ein unendlichen Daten zu drucken, aber Selbstreferenz mit einem [...] (bekannt als Ellipsis)

3. Der Python Sie können markieren um solche Struktur richtig zu adressieren, so können Sie

   a.keys()[1][1][1]

   und so weiter schreiben. Warum solltest du nicht?
4. Die y = y[:] Anweisung kopiert einfach die Liste y. Kann fest mit y = list(y)

mehr getan werden Versuchen Sie, den folgenden Code:

 
def Keys(x,y=None): 
    if y is None: 
     y = [] 
    if len(x): 
     y += [x[2], Keys(x[0],y), Keys(x[1],y)] 
    return y 

Aber noch denke ich, dass es dich beißen kann. Sie verwenden immer noch die gleiche Variable y (ich meine das gleiche Objekt) an drei Stellen in einem Ausdruck:

 y += [x[2], Keys(x[0], y), Keys(x[1], y)]

Ist das, was Sie wirklich wollen, erreichen? Oder vielleicht sollten Sie versuchen:

 
def mKeys(x,y=None): 
    if y is None: 
     y = [] 
    if len(x): 
     z = [x[2], mKeys(x[0], y), mKeys(x[1],y)] 
     return z 
    return [] 

Answer 7

Für den Unterschied zwischen den beiden Versionen der Funktionstasten, beachten Sie folgenden Unterschied:

y+=[x[2]]+Keys(x[0],y)+Keys(x[1],y) 

Der rechte Seite Wert in dieser Aussage ist eine Liste, die enthält x [2], sowie die Elemente des Schlüssels (x [0], y) und die Elemente des Schlüssels (x [1], y)

y+=[x[2],Keys(x[0],y),Keys(x[1],y)] 

Der rechte Seite Wert in dieser Anweisung ist eine Liste, die enthält x [2], plus die LIST-Tasten (x [2], y) und die LIST-Tasten (x [1], y).

Also die Version mit [a, b] wird verursacht, dass y sich selbst als Elemente enthält.

Einige andere Hinweise:

1. Da in Python, wird der Standardwert Objekt einmal erstellt, wenn die Funktion definiert ist, wird die erste Version nicht funktionieren wie das Beispiel zeigt. Es enthält mehrere Kopien einiger Schlüssel. Es ist schwer zu erklären, kurz, aber Sie können eine Idee bekommen, indem Sie die Werte von x, y bei jedem Aufruf von Keys drucken.

   Dies wird bestätigt, indem Sie die Funktion auf meinem Computer mit Python 2.5.2 ausführen.

2. Auch weil der Standardwert nur einmal zur Funktionsdefinitionszeit definiert ist, funktioniert auch die Funktion zum ersten Mal korrekt, sie funktioniert nicht beim Aufruf mit einem anderen a, da die Schlüssel im ersten Binärbaum erhalten bleiben in y.

   Sie können dies sehen, indem Sie Keys (a) zweimal aufrufen oder in zwei verschiedenen Listen aufrufen.

3. Der zweite Parameter ist für dieses Problem nicht erforderlich. Die Funktion kann wie folgt sein:

   def Keys (a): wenn a = []: return [] sonst: return [a [2]] + Keys (a [0]) + Keys (a [1])

   Das Definieren einer rekursiven Funktion enthält grundsätzlich zwei Teile, löst Teilprobleme und kombiniert die Ergebnisse. In Ihrem Code wird der Kombinationsergebnis-Teil zweimal wiederholt: einer durch Akkumulieren in y, einer durch Hinzufügen der Liste zusammen.

Answer 8

Wenn Sie einen Pretty verwendet hätte, wäre, hätte der Ausgang selbst

>>> l = [1,2,3,4] 
>>> l[0]=l 
>>> l 
[[...], 2, 3, 4] 
>>> pp = pprint.PrettyPrinter(indent = 4) 
>>> pp.pprint(l) 
[<Recursion on list with id=70327632>, 2, 3, 4] 
>>> id(l) 
70327632 

Mit anderen Worten: es ist etwas wie

Answer 9

Die Frage ist erklärend, weil einer der Das Listenelement referenziert die Liste selbst. Wenn also versucht wird, alle Elemente zu drucken, würde es niemals enden.

Illustration:

x = range(3) 
x.append(x) 
x[3][3][3][3][3][0] = 5 
print x 

Ausgang:

[5, 1, 2, [...]] 

x[3] ist ein sich x bezieht. Gleiches gilt für x[3][3].

Dies kann besser [hier] sichtbar gemacht werden (http://pythontutor.com/visualize.html#code=x+%3D+range(3%29%0Ax.append(x%29%0Ax%5B3%5D%5B3%5D%5B3%5D%5B3%5D%5B3%5D%5B0%5D+%3D+5%0Aprint+x&mode=display&origin=opt-frontend.js&cumulative=false&heapPrimitives=false&textReferences=false&py=2&rawInputLstJSON=%5B%5D&curInstr=4)