Effiziente iteration über slice in Python

Wie effizient sind die Iterationen über slice-Operationen in Python? Und wenn eine Kopie ist unvermeidlich mit Scheiben, gibt es eine alternative?

Ich weiß, dass eine slice-operation über eine Liste ist O(k), wobei k die Größe der Scheibe.

x[5 : 5+k]  # O(k) copy operation

Jedoch bei der Iteration über einen Teil einer Liste ist, finde ich, dass die sauberste (und die meisten Pythonic?) Weg, dies zu tun (die zimmerreserviereung, ohne das resort zu den Indizes) ist zu tun:

for elem in x[5 : 5+k]:
  print elem

Aber meine intuition ist, dass diese Ergebnisse noch in eine teure Kopie der Teilliste, anstatt einfach nur die Iteration über die vorhandene Liste.

Wenn Sie besorgt sind, zum kopieren der Scheibe, ich denke, die alternative ist, Durchlaufen die Indizes mit range(5, 5 + k).
Gefahr! Sie habe schlechte Beratung früher; itertools.islice nicht so funktionieren, wie wir es uns gedacht haben. Wenn Sie eine islice ab 1000000, Python wird die Schleife durch die erste 1000000 Elemente Ihrer Liste, bevor Sie nachgeben nichts. Dies könnte wiederum eine linear-Zeit-Algorithmus quadratische oder schlechter.

InformationsquelleAutor WaelJ | 2013-08-04

Können Sie itertools.islice um eine geschnittene iterator aus der Liste:

Beispiel:

>>> from itertools import islice
>>> lis = range(20)
>>> for x in islice(lis, 10, None, 1):
...     print x
...     
10
11
12
13
14
15
16
17
18
19

Update:

Wie bereits von @user2357112 die Leistung islice hängt von dem start Punkt der Scheibe und der Größe der iterierbar normale Scheibe wird blitzschnell in fast allen Fällen und sollte bevorzugt werden. Hier sind einige weitere timing-Vergleiche:

Für Riesige Listen islice ist etwas schneller, oder gleich normale Scheibe, wenn die Scheibe ist Startpunkt ist weniger als die Hälfte der Größe der Liste, für die größeren Indizes normalen Scheibe ist der klare Sieger.

>>> def func(lis, n):
        it = iter(lis)
        for x in islice(it, n, None, 1):pass
...     
>>> def func1(lis, n):
        #it = iter(lis)
        for x in islice(lis, n, None, 1):pass
...     
>>> def func2(lis, n):
        for x in lis[n:]:pass
...     
>>> lis = range(10**6)

>>> n = 100
>>> %timeit func(lis, n)
10 loops, best of 3: 62.1 ms per loop
>>> %timeit func1(lis, n)
1 loops, best of 3: 60.8 ms per loop
>>> %timeit func2(lis, n)
1 loops, best of 3: 82.8 ms per loop

>>> n = 1000
>>> %timeit func(lis, n)
10 loops, best of 3: 64.4 ms per loop
>>> %timeit func1(lis, n)
1 loops, best of 3: 60.3 ms per loop
>>> %timeit func2(lis, n)
1 loops, best of 3: 85.8 ms per loop

>>> n = 10**4
>>> %timeit func(lis, n)
10 loops, best of 3: 61.4 ms per loop
>>> %timeit func1(lis, n)
10 loops, best of 3: 61 ms per loop
>>> %timeit func2(lis, n)
1 loops, best of 3: 80.8 ms per loop


>>> n = (10**6)/2
>>> %timeit func(lis, n)
10 loops, best of 3: 39.2 ms per loop
>>> %timeit func1(lis, n)
10 loops, best of 3: 39.6 ms per loop
>>> %timeit func2(lis, n)
10 loops, best of 3: 41.5 ms per loop

>>> n = (10**6)-1000
>>> %timeit func(lis, n)
100 loops, best of 3: 18.9 ms per loop
>>> %timeit func1(lis, n)
100 loops, best of 3: 18.8 ms per loop
>>> %timeit func2(lis, n)
10000 loops, best of 3: 50.9 us per loop    #clear winner for large index
>>> %timeit func1(lis, n)

Für Kleinen Listen normale Scheibe ist schneller als islice für fast alle Fälle.

>>> lis = range(1000)
>>> n = 100
>>> %timeit func(lis, n)
10000 loops, best of 3: 60.7 us per loop
>>> %timeit func1(lis, n)
10000 loops, best of 3: 59.6 us per loop
>>> %timeit func2(lis, n)
10000 loops, best of 3: 59.9 us per loop

>>> n = 500
>>> %timeit func(lis, n)
10000 loops, best of 3: 38.4 us per loop
>>> %timeit func1(lis, n)
10000 loops, best of 3: 33.9 us per loop
>>> %timeit func2(lis, n)
10000 loops, best of 3: 26.6 us per loop

>>> n = 900
>>> %timeit func(lis, n)
10000 loops, best of 3: 20.1 us per loop
>>> %timeit func1(lis, n)
10000 loops, best of 3: 17.2 us per loop
>>> %timeit func2(lis, n)
10000 loops, best of 3: 11.3 us per loop

Fazit:

Gehen für den normalen Scheiben.

itertools.islice funktioniert nicht auf diese Weise! Es ist gebaut für das schneiden von beliebigen iterables, und es wird nicht versuchen, Sie zu verwenden __getitem__. Wenn Sie versuchen, eine islice ab 1000000, islice wird eine Schleife durch die erste 1000000 Elemente Ihrer Liste, bevor die nachgeben, nichts, völlig zerstören Ihre Leistung.
Ich habe einige timing-Vergleiche, können Sie erklären, wie kann das sein, quadratisch oder schlechter? Timing die Ergebnisse sind für islice.
Quadratische Zeit wäre, wenn Sie versucht, Durchlaufen eine große Anzahl von kleinen Stückchen von einer Liste vom Anfang zum Ende; Ihre Laufzeit wäre quadratisch in der Anzahl der Scheiben statt linear in der Größe der Liste.
Was lis, und welche Python-version ist das? Mein timing die Ergebnisse sind das Gegenteil von Euch.
ist range(10**6). Dies ist IPython-shell, py2.7.4.
islice gewinnen können, wenn die Scheibe größer ist als der Teil, dass kommt vor, aber wenn start ist viel größer als stop - start -, Leistungs-tanks. Siehe timing-Daten in meine (korrigierte) Antwort.
Wieder schauen. Regelmäßige Scheibe ist die Einnahme von Mikrosekunden. islice ist die Einnahme von Millisekunden.
Duh! facepalm, ich glaube ich muss etwas Schlaf. BTW, Dank etwas neues gelernt heute.
Das ist ein sehr guter Punkt! Vielen Dank für die Mühe das überprüft 🙂

InformationsquelleAutor Ashwini Chaudhary

7

Verwenden:
```
for elem in x[5 : 5+k]:
```
Es ist Pythonic! Diese änderung nicht, bevor Sie haben profilierten Sie den code und bestimmt, dass dies ein Engpass -- obwohl ich bezweifle, dass Sie jemals finden, dass dies die wichtigste Quelle von einem Engpass.

In Bezug auf Geschwindigkeit, es wird wahrscheinlich Ihre beste Wahl sein:
```
In [30]: x = range(100)

In [31]: k = 90

In [32]: %timeit x[5:5+k]
1000000 loops, best of 3: 357 ns per loop

In [35]: %timeit list(IT.islice(x, 5, 5+k))
100000 loops, best of 3: 2.42 us per loop

In [36]: %timeit [x[i] for i in xrange(5, 5+k)]
100000 loops, best of 3: 5.71 us per loop
```
In Bezug auf Speicher, es ist nicht so schlimm, könnte man denken. x[5: 5+k] ist ein flachen Kopie von Teil x. Also, auch wenn die Objekte in x sind groß, x[5: 5+k] ist eine neue Liste zu erstellen mit k-Elemente verweisen auf die gleichen Objekte wie in der x. So brauchen Sie nur extra Speicher zum erstellen einer Liste mit k Verweise auf bereits bestehende Objekte. Das ist wahrscheinlich nicht gehen, um die Quelle der Probleme mit dem Speicher.

InformationsquelleAutor unutbu
4

Nur durchqueren die gewünschten Indizes, es gibt keine Notwendigkeit, erstellen Sie eine neue Scheibe für dieses:
```
for i in xrange(5, 5+k):
    print x[i]
```
Zugegeben: es sieht unpythonic, aber es ist effizienter als das erstellen eines neuen Segments in dem Sinne, dass kein zusätzlicher Speicher ist verschwendet. Eine alternative wäre die Verwendung eines iterator, wie gezeigt, in @AshwiniChaudhary Antwort.
- Ein weiteres Problem mit index-basierter Ansatz IndexError.
- Ich glaube, dass für so ein einfaches Szenario für den Einsatz, eine einfachere Antwort ist die beste. Nicht alles fancy und pythonic, mit Iteratoren und Scheiben und Verstehens etc. für diejenigen von uns, die kommen aus einer C-ähnlichen hintergrund, manchmal ein guter Alter index-basierte Traversierung wird gut funktionieren
- Dies ist eigentlich die langsamste Lösung. Sie können es ausprobieren mit timeit. Iteratoren und die Scheiben sind nicht besonderes, Sie sind basic, core Python-Funktionen.
- gut, das ist eye-opening!
InformationsquelleAutor Óscar López
2

Bist du schon dabei eine O(n) iteration über die Scheibe. In den meisten Fällen ist dies viel mehr ein Anliegen, als die eigentliche Gestaltung der Scheibe, was passiert, ganz in der optimierten C. Looping über eine Scheibe, sobald Sie gemacht haben, dauert es mehr als doppelt so lang wie die Scheibe, auch wenn man gar nichts mit:
```
>>> timeit.timeit('l[50:100]', 'import collections; l=range(150)')
0.46978958638010226
>>> timeit.timeit('for x in slice: pass',
                  'import collections; l=range(150); slice=l[50:100]')
1.2332711270150867
```
Könnten Sie versuchen, Durchlaufen die Indizes mit xrange, aber für die Buchhaltung benötigte Zeit zum abrufen der Liste element, es ist langsamer als schneiden. Auch wenn Sie überspringen Sie diesen Teil, es immer noch nicht, beat-slicing:
```
>>> timeit.timeit('for i in xrange(50, 100): x = l[i]', 'l = range(150)')
4.3081963062022055
>>> timeit.timeit('for i in xrange(50, 100): pass', 'l = range(150)')
1.675838213385532
```
Nicht verwenden itertools.islice dafür!!!! Es wird Schleife durch die Liste von Anfang an und nicht als den Sprung auf die Werte, die Sie möchten mit __getitem__. Hier einige timing-Daten, die zeigen, wie seine Leistung hängt davon ab, wo die Scheibe beginnt:
```
>>> timeit.timeit('next(itertools.islice(l, 9, None))', 'import itertools; l = r
ange(1000000)')
0.5628290558478852
>>> timeit.timeit('next(itertools.islice(l, 999, None))', 'import itertools; l =
 range(1000000)')
6.885294697594759
```
Hier islice verlieren regelmäßige schneiden:
```
>>> timeit.timeit('for i in itertools.islice(l, 900, None): pass', 'import itert
ools; l = range(1000)')
8.979957560911316
>>> timeit.timeit('for i in l[900:]: pass', 'import itertools; l = range(1000)')

3.0318417204211983
```
Dies ist auf Python 2.7.5, im Falle eines späteren Versionen hinzufügen Liste-spezifische Optimierungen.

InformationsquelleAutor user2357112
0

Ich denke, ein besserer Weg ist, mit einer c-ähnlichen iteration, wenn der 'k' ist so groß (wie ein großes " k " - wie 10000000000000 - selbst machen könnte, warten Sie etwa 10 Stunden, um die Antwort in einer pythonic for-Schleife)

hier ist, was ich versuche zu sagen Sie tun:
```
i = 5 ## which is the initial value
f = 5 + k ## which will be the final index

while i < f:
    print(x[i])
    i += 1
```
Ich nehme an, dies könnte man Sie nicht einfach in 5 Stunden (ab der pythonic äquivalente for-Schleife tun Sie es für etwa 10 Stunden), dass für große k, dass ich sagte, weil Sie brauchen, um zu gehen von 5 bis 10000000000005 nur einmal!
jede Verwendung von 'range()' von 'xrange()' oder auch das schneiden selbst (als yo oben erwähnt) machen das Programm nur tun 20000000000000 Iterationen, die dazu führen könnten, die eine längere Ausführungszeit, denke ich. (wie Lerne ich mit einem generator-Methode zur Rückgabe eines wiederholenden Objekt, müssen den generator laufen zuerst komplett gemacht werden, und es dauert doppelt Zeit zu tun, job; Eine für den generator selbst und die andere für die 'for' - Schleife)

Herausgegeben:

In python 3 die generator-Methode/Objekt nicht ausführen müssen, um den ersten zu machen, die iterierbar-Objekt für die for-Schleife
- Dies ist tatsächlich langsamer! Zeit und sehen.
InformationsquelleAutor ARF

Schreibe einen Kommentar

Du musst angemeldet sein, um einen Kommentar abzugeben.