Schneiden einer Liste in Python, ohne eine Kopie zu generieren

74

Ich habe folgendes Problem.

Bei einer Liste von Ganzzahlen Lmuss ich alle Unterlisten generieren L[k:] for k in [0, len(L) - 1], ohne Kopien zu generieren .

Wie schaffe ich das in Python? Irgendwie mit einem Pufferobjekt?

python list slice Chris
quelle
Möchten Sie keine Kopien der Liste selbst erstellen oder möchten Sie keine Kopien der darin enthaltenen Objekte erstellen?
senderle
Ich möchte keine Kopien der darin enthaltenen Objekte erstellen, während ich die Slices generiere.
Chris
Python erstellt standardmäßig keine Kopien.
Amber
1
Woher wissen Sie, dass Kopien angefertigt werden? Haben Sie eine Zunahme der Ressourcen bemerkt?
mt3

Antworten:

114

Die kurze Antwort

Durch das Schneiden von Listen werden keine Kopien der Objekte in der Liste generiert. es kopiert nur die Verweise auf sie. Das ist die Antwort auf die gestellte Frage.

Die lange Antwort

Testen auf veränderliche und unveränderliche Werte

Lassen Sie uns zunächst den Grundanspruch testen. Wir können zeigen, dass selbst bei unveränderlichen Objekten wie ganzen Zahlen nur die Referenz kopiert wird. Hier sind drei verschiedene ganzzahlige Objekte mit jeweils demselben Wert:

>>> a = [1000 + 1, 1000 + 1, 1000 + 1]

Sie haben den gleichen Wert, aber Sie können sehen, dass es sich um drei verschiedene Objekte handelt, da sie unterschiedliche ids haben:

>>> map(id, a)
[140502922988976, 140502922988952, 140502922988928]

Wenn Sie sie in Scheiben schneiden, bleiben die Referenzen gleich. Es wurden keine neuen Objekte erstellt:

>>> b = a[1:3]
>>> map(id, b)
[140502922988952, 140502922988928]

Die Verwendung verschiedener Objekte mit demselben Wert zeigt, dass sich der Kopiervorgang nicht um das Internieren kümmert, sondern lediglich die Referenzen direkt kopiert.

Das Testen mit veränderlichen Werten ergibt das gleiche Ergebnis:

>>> a = [{0: 'zero', 1: 'one'}, ['foo', 'bar']]
>>> map(id, a)
[4380777000, 4380712040]
>>> map(id, a[1:]
... )
[4380712040]

Untersuchen des verbleibenden Speicheraufwands

Natürlich werden die Referenzen selbst kopiert. Jeder kostet 8 Bytes auf einem 64-Bit-Computer. Und jede Liste hat ihren eigenen Speicheraufwand von 72 Bytes:

>>> for i in range(len(a)):
...     x = a[:i]
...     print('len: {}'.format(len(x)))
...     print('size: {}'.format(sys.getsizeof(x)))
... 
len: 0
size: 72
len: 1
size: 80
len: 2
size: 88

Wie Joe Pinsonault uns erinnert , summiert sich dieser Overhead. Und ganzzahlige Objekte selbst sind nicht sehr groß - sie sind dreimal größer als Referenzen. Dies spart Ihnen im absoluten Sinne etwas Speicherplatz, aber asymptotisch kann es hilfreich sein, mehrere Listen, die "Ansichten" sind, in demselben Speicher zu haben.

Speichern von Speicher mithilfe von Ansichten

Leider bietet Python keine einfache Möglichkeit, Objekte, die "Ansichten" sind, in Listen zu erstellen. Oder vielleicht sollte ich "zum Glück" sagen! Sie müssen sich also keine Gedanken darüber machen, woher eine Scheibe kommt. Änderungen am Original wirken sich nicht auf das Slice aus. Insgesamt erleichtert dies das Nachdenken über das Verhalten eines Programms erheblich.

Wenn Sie wirklich Speicher sparen möchten, indem Sie mit Ansichten arbeiten, sollten Sie numpyArrays verwenden. Wenn Sie ein numpyArray in Scheiben schneiden , wird der Speicher zwischen dem Slice und dem Original geteilt:

>>> a = numpy.arange(3)
>>> a
array([0, 1, 2])
>>> b = a[1:3]
>>> b
array([1, 2])

Was passiert, wenn wir etwas ändern aund erneut betrachten b?

>>> a[2] = 1001
>>> b
array([   1, 1001])

Dies bedeutet jedoch, dass Sie sicherstellen müssen, dass Sie beim Ändern eines Objekts nicht versehentlich ein anderes Objekt ändern. Das ist der Kompromiss, wenn Sie verwenden numpy: weniger Arbeit für den Computer und mehr Arbeit für den Programmierer!

senderle
quelle
3
In einem unveränderlichen Objekt (z. B. einem Tupel) sind die Referenzen unveränderlich, aber die Elemente, auf die sie verweisen, können veränderbar sein. Ein Tupel mit 3 Listen kann also nicht geändert werden. Es bezieht sich immer auf dieselben 3 Listen, aber der Inhalt jeder Liste kann sich wie in jeder Liste ändern.
Trichoplax
6
Die Antwort ist zwar korrekt, das Beispiel zeigt sie jedoch nicht, da kleine Ganzzahlen interniert sind. versuche es id(2)oder sogar id(1+1). Ein besseres Beispiel wäre zu verwenden a = [[], [], []].
Exp HP
1
Oder bei weiterer Lektüre gibt die Frage tatsächlich an, dass die Liste aus ganzen Zahlen besteht, und ich finde es ziemlich merkwürdig, dass der Autor sich überhaupt Sorgen um Artikelkopien macht! (Ich würde eher denken, dass das OP Ihre Bitte um Klärung nicht vollständig verstanden hat und eigentlich "Ansichten" in die ursprüngliche Liste erhalten wollte)
Exp HP
1
Diese Antwort ist richtig, aber ich denke, es ist erwähnenswert, dass das Kopieren von Arrays von Zeigern immer noch teuer sein kann, wenn Sie sehr große Arrays haben
Joe Pinsonault
@ExpHP, das könnte wahr sein. Ich habe versucht, nicht langatmig zu sein, aber ich denke, das ist für eine Frage wie diese unmöglich! Bearbeitet.
senderle
25

Je nachdem, was Sie tun, können Sie möglicherweise verwenden islice.

Da es über Iteration arbeitet, werden keine neuen Listen erstellt, sondern es werden einfach Iteratoren erstellt, die yieldElemente aus der ursprünglichen Liste enthalten, wie für ihre Bereiche angefordert.

Bernstein
quelle
6
Das Schlimme dabei ist, dass eine Islice kein Objekt ausnutzt , das die getitem- Methode implementiert und alles als Iterator behandelt. Daher iteriert sie immer vom ersten Element der Liste bis zur ersten Position der Liste, um zu ergeben die Werte im Bereich.
jgomo3
3

Eine einfache Alternative dazu islicedurchläuft keine Listenelemente, die nicht benötigt werden:

def listslice(xs, *args):
    for i in range(len(xs))[slice(*args)]:
        yield xs[i]

Verwendung:

>>> xs = [0, 2, 4, 6, 8, 10]

>>> for x in listslice(xs, 2, 4):
...     print(x)
4
6
Mateen Ulhaq
quelle
1

Ich habe eine ListViewKlasse geschrieben, die es vermeidet, auch nur den Rücken der Liste zu kopieren:

https://gist.github.com/3noch/b5f3175cfe39aea71ca4d07469570047

Dies unterstützt verschachteltes Schneiden, sodass Sie weiter in die Ansicht schneiden können, um engere Ansichten zu erhalten. Zum Beispiel : ListView(list(range(10)))[4:][2:][1] == 7.

Beachten Sie, dass dies nicht vollständig gebacken ist und ein gutes Stück mehr Fehlerprüfung verdient, wenn die zugrunde liegende Liste zusammen mit einer Testsuite mutiert ist.

Elliot Cameron
quelle
0

Im Allgemeinen ist das Aufteilen von Listen die beste Option.

Hier ist ein schneller Leistungsvergleich:

from timeit import timeit
from itertools import islice

for size in (10**4, 10**5, 10**6):
    L = list(range(size))
    S = size // 2
    def sum_slice(): return sum(L[S:])
    def sum_islice(): return sum(islice(L, S, None))
    def sum_for(): return sum(L[i] for i in range(S, len(L)))

    assert sum_slice() == sum_islice()
    assert sum_slice() == sum_for()

    for method in (sum_slice, sum_islice, sum_for):
        print(f'Size={size}, method={method.__name__}, time={timeit(method, number=1000)} ms')

Ergebnisse:

Size=10000,   method=sum_slice,  time=0.0298 ms
Size=10000,   method=sum_islice, time=0.0449 ms
Size=10000,   method=sum_for,    time=0.2500 ms
Size=100000,  method=sum_slice,  time=0.3262 ms
Size=100000,  method=sum_islice, time=0.4492 ms
Size=100000,  method=sum_for,    time=2.4849 ms
Size=1000000, method=sum_slice,  time=5.4092 ms
Size=1000000, method=sum_islice, time=5.1139 ms
Size=1000000, method=sum_for,    time=26.198 ms
gatopeich
quelle