Effiziente Möglichkeit, eine Liste in Python zu drehen

263

Was ist der effizienteste Weg, um eine Liste in Python zu drehen? Im Moment habe ich so etwas:

>>> def rotate(l, n):
...     return l[n:] + l[:n]
... 
>>> l = [1,2,3,4]
>>> rotate(l,1)
[2, 3, 4, 1]
>>> rotate(l,2)
[3, 4, 1, 2]
>>> rotate(l,0)
[1, 2, 3, 4]
>>> rotate(l,-1)
[4, 1, 2, 3]

Gibt es einen besseren Weg?

dzhelil
quelle
12
Dies ist keine wirkliche Verschiebung, da die anderen Sprachen (Perl, Ruby) den Begriff verwenden. Dies ist drehen. Vielleicht sollte die Frage entsprechend aktualisiert werden?
Vincent Fourmond
@dzhelil Ich mag Ihre ursprüngliche Lösung wirklich, weil sie keine Mutationen einführt
juanchito
2
numpy.roll
BoltzmannBrain
2
Ich denke rotateist das richtige Wort, nicht shift.
Codeforester
2
Die wirklich richtige Antwort ist, dass Sie die Liste niemals in erster Linie drehen sollten. Erstellen Sie eine "Zeiger" -Variable an der logischen Stelle in Ihrer Liste, an der sich der "Kopf" oder "Schwanz" befinden soll, und ändern Sie diese Variable, anstatt eines der Elemente in der Liste zu verschieben. Suchen Sie im Operator "modulo"% nach der effizienten Möglichkeit, Ihren Zeiger um den Anfang und das Ende der Liste zu "wickeln".
CND

Antworten:

280

A collections.dequeist für das Ziehen und Drücken an beiden Enden optimiert. Sie haben sogar eine spezielle rotate()Methode.

from collections import deque
items = deque([1, 2])
items.append(3)        # deque == [1, 2, 3]
items.rotate(1)        # The deque is now: [3, 1, 2]
items.rotate(-1)       # Returns deque to original state: [1, 2, 3]
item = items.popleft() # deque == [2, 3]
Ignacio Vazquez-Abrams
quelle
8
Für zukünftige Leser: collections.deque rotate()ist schneller als das Schneiden gemäß wiki.python.org/moin/TimeComplexity
Geoff
2
Beachten Sie jedoch, dass für die Verwendung zuerst deque.rotateeine Typkonvertierung in ein dequeObjekt erforderlich ist , die langsamer ist als l.append(l.pop(0)). Wenn Sie also zunächst ein Deque-Objekt haben, stellen Sie sicher, dass es am schnellsten ist. Andernfalls verwenden Sie l.append(l.pop(0)).
Purrell
8
Zur Ausarbeitung deque.rotateist O (k), aber die Typkonvertierung von Liste zu Deque ist O (n) . Wenn Sie also mit einer Liste beginnen, ist die Verwendung von deque.rotate O (n) + O (k) = O (n). l.append(l.pop(0))auf der anderen Seite ist O (1).
Purrell
3
@Purrell, das Öffnen des vorderen Elements ist O (n). In wiki.python.org/moin/TimeComplexity wird es als O (k) aufgeführt, und k ist die Anzahl der Elemente in der Liste nach dem angezeigten Element, da die Datenstruktur alle folgenden Elemente nach vorne in die Liste verschiebt. Aus diesem Grund kann nur das letzte Element in O (1) -Zeit eingefügt werden.
Kirk Boyer
88

Was ist mit nur zu verwenden pop(0)?

list.pop([i])

Entfernen Sie das Element an der angegebenen Position in der Liste und geben Sie es zurück. Wenn kein Index angegeben ist, a.pop()wird das letzte Element in der Liste entfernt und zurückgegeben. (Die eckigen Klammern iin der Methodensignatur bedeuten, dass der Parameter optional ist und Sie keine eckigen Klammern an dieser Position eingeben sollten. Diese Notation wird häufig in der Python-Bibliotheksreferenz angezeigt.)

Jamgold
quelle
16
Aber würde es nicht O (k) kosten, jedes Element in der Liste zu entfernen, wobei k die Anzahl der verbleibenden Elemente ist? Die Gesamtzeit beträgt
Pramod
5
Dies beantwortet die Frage nicht wirklich. Bei der Frage geht es nicht darum, Artikel in der richtigen Reihenfolge zurückzugeben, sondern darum, eine neue Liste in einer anderen Reihenfolge zu erstellen.
user650261
5
Nein, die Antwort auf die Frage mit Pop wäre l.append(l.pop(0). Was, wenn ich mich nicht irre, O (1) ist.
Purrell
4
list.pop ruft intern list_ass_slice auf, das memmove verwendet, um alle Elemente sehr schnell zu verschieben, aber es ist immer noch O (n). Siehe github.com/python/cpython/blob/master/Objects/listobject.c und wiki.python.org/moin/TimeComplexity . Das einzige Element, das in konstanter Zeit aus einer Python-Liste entfernt werden kann, ist das letzte.
DRayX
2
Abgestimmt. Von docs.python.org/3/tutorial/… Es ist auch möglich, eine Liste als Warteschlange zu verwenden, wobei das erste hinzugefügte Element das erste abgerufene Element ist ("first-in, first-out"). Listen sind für diesen Zweck jedoch nicht effizient. Während Anhänge und Pops am Ende der Liste schnell sind, ist das Einfügen oder Pops am Anfang einer Liste langsam (da alle anderen Elemente um eins verschoben werden müssen).
SantaXL
59

Numpy kann dies mit dem folgenden rollBefehl tun :

>>> import numpy
>>> a=numpy.arange(1,10) #Generate some data
>>> numpy.roll(a,1)
array([9, 1, 2, 3, 4, 5, 6, 7, 8])
>>> numpy.roll(a,-1)
array([2, 3, 4, 5, 6, 7, 8, 9, 1])
>>> numpy.roll(a,5)
array([5, 6, 7, 8, 9, 1, 2, 3, 4])
>>> numpy.roll(a,9)
array([1, 2, 3, 4, 5, 6, 7, 8, 9])
Richard
quelle
1
Was ich an SO liebe, ist, dass man manchmal im Antwort-Feed einige großartige neue Schätze wie diesen findet :)
noamgot
Dies ist, als ich es getestet habe, sehr, sehr langsam
Peter Harrison
@PeterHarrison: Da Sie keine Testdetails angeben, ist es schwer zu wissen, was Sie überhaupt meinen. Diese Antwort enthält vollständige Testdetails und einen Zeitvergleich.
Richard
33

Es hängt davon ab, was passieren soll, wenn Sie dies tun:

>>> shift([1,2,3], 14)

Vielleicht möchten Sie Folgendes ändern:

def shift(seq, n):
    return seq[n:]+seq[:n]

zu:

def shift(seq, n):
    n = n % len(seq)
    return seq[n:] + seq[:n]
jcdyer
quelle
5
NB: Dies stürzt bei leeren Listen ab.
Meawoppl
n = n% len (seq) return = seq [-n:] + seq [: - n]
user3303020
Können Sie erklären, warum n = n% len (seq)?
AerysS
16

Der einfachste Weg, den ich mir vorstellen kann:

a.append(a.pop(0))
Thijs
quelle
3
Dies ist der schnellste Weg für Listen. collections.dequeist schneller, aber für die meisten Fälle von a.append(a.pop(0))
Listenlänge
@runDOSrun die perfekte Antwort auf diese Frage, die leider als Duplikat geschlossen ist. Vielleicht stimmen Sie für die Wiedereröffnung?
Wolf
15

Wenn Sie nur über diese Elementmengen iterieren möchten, anstatt eine separate Datenstruktur zu erstellen, sollten Sie Iteratoren verwenden, um einen Generatorausdruck zu erstellen:

def shift(l,n):
    return itertools.islice(itertools.cycle(l),n,n+len(l))

>>> list(shift([1,2,3],1))
[2, 3, 1]
Phil H.
quelle
11

Dies hängt auch davon ab, ob Sie die Liste verschieben (mutieren) möchten oder ob die Funktion eine neue Liste zurückgeben soll. Denn nach meinen Tests ist so etwas mindestens zwanzigmal schneller als Ihre Implementierung, die zwei Listen hinzufügt:

def shiftInPlace(l, n):
    n = n % len(l)
    head = l[:n]
    l[:n] = []
    l.extend(head)
    return l

Tatsächlich ist das Hinzufügen eines l = l[:]oben, um eine Kopie der übergebenen Liste zu bearbeiten, immer noch doppelt so schnell.

Verschiedene Implementierungen mit etwas Timing unter http://gist.github.com/288272

keturn
quelle
3
Stattdessen l[:n] = []würde ich gehen del l[:n]. Nur eine Alternative.
Zot
1
Oh ja, guter alter Del. Ich vergesse oft del; Die Listenoperation ist eine Anweisung, keine Methode. Hat py3k diese Eigenart geändert oder haben wir sie noch?
Keturn
2
@keturn: delist immer noch eine Aussage in Py3. Allerdings x.__delitem__(y) <==> del x[y], wenn Sie also mit Methoden bevorzugen, l.__delitem__(slice(n))ist auch gleichwertig und arbeitet sowohl in der 2 & 3
martineau
9

Nur ein paar Hinweise zum Timing:

Wenn Sie mit einer Liste beginnen, l.append(l.pop(0))ist dies die schnellste Methode, die Sie verwenden können. Dies kann allein mit zeitlicher Komplexität gezeigt werden:

  • deque.rotate ist O (k) (k = Anzahl der Elemente)
  • Die Konvertierung von Liste zu Deque ist O (n).
  • list.append und list.pop sind beide O (1)

Wenn Sie also mit dequeObjekten beginnen, können Sie dies deque.rotate()auf Kosten von O (k) tun. Wenn der Ausgangspunkt jedoch eine Liste ist, beträgt die zeitliche Komplexität der Verwendung deque.rotate()O (n). l.append(l.pop(0)ist bei O (1) schneller.

Zur Veranschaulichung sind hier einige Beispiel-Timings für 1M-Iterationen aufgeführt:

Methoden, die eine Typkonvertierung erfordern:

  • deque.rotatemit Deque-Objekt: 0,12380790710449219 Sekunden (am schnellsten)
  • deque.rotatemit Typkonvertierung: 6.853878974914551 Sekunden
  • np.rollmit nparray: 6.0491721630096436 Sekunden
  • np.rollmit Typkonvertierung: 27.558452129364014 Sekunden

Hier erwähnte Methoden auflisten:

  • l.append(l.pop(0)): 0,32483696937561035 Sekunden (am schnellsten)
  • " shiftInPlace": 4.819645881652832 Sekunden
  • ...

Der verwendete Timing-Code ist unten.


collection.deque

Zeigen, dass das Erstellen von Deques aus Listen O (n) ist:

from collections import deque
import big_o

def create_deque_from_list(l):
     return deque(l)

best, others = big_o.big_o(create_deque_from_list, lambda n: big_o.datagen.integers(n, -100, 100))
print best

# --> Linear: time = -2.6E-05 + 1.8E-08*n

Wenn Sie Deque-Objekte erstellen müssen:

1M Iterationen @ 6.853878974914551 Sekunden

setup_deque_rotate_with_create_deque = """
from collections import deque
import random
l = [random.random() for i in range(1000)]
"""

test_deque_rotate_with_create_deque = """
dl = deque(l)
dl.rotate(-1)
"""
timeit.timeit(test_deque_rotate_with_create_deque, setup_deque_rotate_with_create_deque)

Wenn Sie bereits Deque-Objekte haben:

1 Million Iterationen bei 0,12380790710449219 Sekunden

setup_deque_rotate_alone = """
from collections import deque
import random
l = [random.random() for i in range(1000)]
dl = deque(l)
"""

test_deque_rotate_alone= """
dl.rotate(-1)
"""
timeit.timeit(test_deque_rotate_alone, setup_deque_rotate_alone)

np.roll

Wenn Sie nparrays erstellen müssen

1M Iterationen @ 27.558452129364014 Sekunden

setup_np_roll_with_create_npa = """
import numpy as np
import random
l = [random.random() for i in range(1000)]
"""

test_np_roll_with_create_npa = """
np.roll(l,-1) # implicit conversion of l to np.nparray
"""

Wenn Sie bereits nparrays haben:

1M Iterationen @ 6.0491721630096436 Sekunden

setup_np_roll_alone = """
import numpy as np
import random
l = [random.random() for i in range(1000)]
npa = np.array(l)
"""

test_roll_alone = """
np.roll(npa,-1)
"""
timeit.timeit(test_roll_alone, setup_np_roll_alone)

"Verschieben an Ort und Stelle"

Erfordert keine Typkonvertierung

1M Iterationen @ 4.819645881652832 Sekunden

setup_shift_in_place="""
import random
l = [random.random() for i in range(1000)]
def shiftInPlace(l, n):
    n = n % len(l)
    head = l[:n]
    l[:n] = []
    l.extend(head)
    return l
"""

test_shift_in_place="""
shiftInPlace(l,-1)
"""

timeit.timeit(test_shift_in_place, setup_shift_in_place)

l.append (l.pop (0))

Erfordert keine Typkonvertierung

1M Iterationen @ 0.32483696937561035

setup_append_pop="""
import random
l = [random.random() for i in range(1000)]
"""

test_append_pop="""
l.append(l.pop(0))
"""
timeit.timeit(test_append_pop, setup_append_pop)
Purrell
quelle
2
Während list.pop () eine Operation mit konstanter Zeit ist, ist list.pop (0) dies nicht . Es läuft in linearer Zeit in Bezug auf die Listenlänge. Sie können dies testen, indem Sie Ihr Timeit-Setup ändern:l = [random.random() for i in range(100000)]
Emu
1
list.pop ist keine konstante Zeitoperation. list.pop wird in O (k) -Zeit ausgeführt, wobei k die Anzahl der Elemente nach dem entfernten Element ist, sodass list.pop (0) O (n) ist. Intern verwendet list.pop list_ass_slice, das memmove verwendet, um Elemente viel schneller als jemals zuvor mit Python zu verschieben. Bei langen Listen ist dies jedoch immer noch sehr zeitaufwändig. Siehe github.com/python/cpython/blob/master/Objects/listobject.c und wiki.python.org/moin/TimeComplexity
DRayX
Danke für das Timing (und Kommentare @emu). Können wir also sagen, dass dies l.append(l.pop(0))die beste Leistung ist, um kurze Listen (ca. 7 Elemente) um eins zu verschieben?
Wolf
Nochmals l.append(l.pop(0))als Antwort: Diese Frage wird als Duplikat geschlossen. Vielleicht stimmen Sie für die Wiedereröffnung?
Wolf
8

Ich habe mich auch dafür interessiert und einige der vorgeschlagenen Lösungen mit perfplot (einem kleinen Projekt von mir) verglichen .

Es stellt sich heraus, dass

for _ in range(n):
    data.append(data.pop(0))

ist bei weitem die schnellste Methode für kleine Schichten n.

Für größere n,

data[n:] + data[:n]

ist nicht schlecht

Im Wesentlichen führt Perfplot die Verschiebung zum Erhöhen großer Arrays durch und misst die Zeit. Hier sind die Ergebnisse:

shift = 1::

Geben Sie hier die Bildbeschreibung ein

shift = 100::

Geben Sie hier die Bildbeschreibung ein


Code zur Reproduktion der Handlung:

import numpy
import perfplot
import collections


shift = 100


def list_append(data):
    return data[shift:] + data[:shift]


def shift_concatenate(data):
    return numpy.concatenate([data[shift:], data[:shift]])


def roll(data):
    return numpy.roll(data, -shift)


def collections_deque(data):
    items = collections.deque(data)
    items.rotate(-shift)
    return items


def pop_append(data):
    for _ in range(shift):
        data.append(data.pop(0))
    return data


perfplot.save(
    "shift100.png",
    setup=lambda n: numpy.random.rand(n).tolist(),
    kernels=[list_append, roll, shift_concatenate, collections_deque, pop_append],
    n_range=[2 ** k for k in range(7, 20)],
    logx=True,
    logy=True,
    xlabel="len(data)",
)
Nico Schlömer
quelle
Schönes Werkzeug, das du gebaut hast. Bezüglich der l.append(l.pop(0))als Antwort: Diese Frage wird als Duplikat geschlossen. Vielleicht stimmen Sie für die Wiedereröffnung?
Wolf
4

Möglicherweise ist ein Ringpuffer besser geeignet. Es ist keine Liste, obwohl es wahrscheinlich ist, dass sie sich für Ihre Zwecke wie eine Liste verhält.

Das Problem ist, dass die Effizienz einer Verschiebung in einer Liste O (n) ist, was für ausreichend große Listen signifikant wird.

Das Verschieben in einen Ringpuffer aktualisiert einfach die Kopfposition, die O (1) ist.

John La Rooy
quelle
4

Für eine unveränderliche Implementierung können Sie Folgendes verwenden:

def shift(seq, n):
    shifted_seq = []
    for i in range(len(seq)):
        shifted_seq.append(seq[(i-n) % len(seq)])
    return shifted_seq

print shift([1, 2, 3, 4], 1)
Bittercoder
quelle
3

Wenn Effizienz Ihr Ziel ist (Zyklen? Speicher?), Ist es möglicherweise besser, sich das Array-Modul anzusehen: anzusehen http://docs.python.org/library/array.html

Arrays haben nicht den Overhead von Listen.

Was reine Listen angeht, ist das, was Sie haben, so gut, wie Sie es sich erhoffen können.

rekursiv
quelle
3

Ich denke du suchst das:

a.insert(0, x)
Redreamalität
quelle
Ich sehe keinen Zusammenhang zwischen der Frage und Ihrer Antwort. Kannst du es bitte erklären?
Wolf
2

Eine andere Alternative:

def move(arr, n):
    return [arr[(idx-n) % len(arr)] for idx,_ in enumerate(arr)]
damio
quelle
1

Ich nehme dieses Kostenmodell als Referenz:

http://scripts.mit.edu/~6.006/fall07/wiki/index.php?title=Python_Cost_Model

Ihre Methode zum Aufteilen der Liste und zum Verketten von zwei Unterlisten sind Operationen mit linearer Zeit. Ich würde vorschlagen, Pop zu verwenden, was eine Operation mit konstanter Zeit ist, z.

def shift(list, n):
    for i in range(n)
        temp = list.pop()
        list.insert(0, temp)
herrfz
quelle
2
Update: Nehmen Sie dies als bessere Referenz: wiki.python.org/moin/TimeComplexity , verwenden Sie collections.dequeuepop und appendleft, die beide O (1) ops sind. In meiner ersten Antwort oben ist Einfügen O (n).
Herrfz
1
sollte seincollections.deque
herrfz
1

Ich weiß nicht, ob dies "effizient" ist, aber es funktioniert auch:

x = [1,2,3,4]
x.insert(0,x.pop())

EDIT: Hallo nochmal, ich habe gerade ein großes Problem mit dieser Lösung gefunden! Betrachten Sie den folgenden Code:

class MyClass():
    def __init__(self):
        self.classlist = []

    def shift_classlist(self): # right-shift-operation
        self.classlist.insert(0, self.classlist.pop())

if __name__ == '__main__':
    otherlist = [1,2,3]
    x = MyClass()

    # this is where kind of a magic link is created...
    x.classlist = otherlist

    for ii in xrange(2): # just to do it 2 times
        print '\n\n\nbefore shift:'
        print '     x.classlist =', x.classlist
        print '     otherlist =', otherlist
        x.shift_classlist() 
        print 'after shift:'
        print '     x.classlist =', x.classlist
        print '     otherlist =', otherlist, '<-- SHOULD NOT HAVE BIN CHANGED!'

Die Methode shift_classlist () führt denselben Code aus wie meine x.insert (0, x.pop ()) - Lösung. Otherlist ist eine von der Klasse unabhängige Liste. Nachdem Sie den Inhalt der anderen Liste an die Liste MyClass.classlist übergeben haben, ändert das Aufrufen von shift_classlist () auch die Liste der anderen Listen:

KONSOLE AUSGABE:

before shift:
     x.classlist = [1, 2, 3]
     otherlist = [1, 2, 3]
after shift:
     x.classlist = [3, 1, 2]
     otherlist = [3, 1, 2] <-- SHOULD NOT HAVE BIN CHANGED!



before shift:
     x.classlist = [3, 1, 2]
     otherlist = [3, 1, 2]
after shift:
     x.classlist = [2, 3, 1]
     otherlist = [2, 3, 1] <-- SHOULD NOT HAVE BIN CHANGED!

Ich benutze Python 2.7. Ich weiß nicht, ob das ein Fehler ist, aber ich denke, es ist wahrscheinlicher, dass ich hier etwas falsch verstanden habe.

Weiß jemand von euch, warum das passiert?

wese3112
quelle
2
Dies liegt daran, x.classlist = otherlistdass x.classlistsich Marken auf dieselbe Liste beziehen otherlistund beim Aufrufen x.shift_classlist()die Liste mutiert und beide Namen auf dasselbe Listenobjekt verweisen. Beide Namen scheinen sich zu ändern, da sie nur Aliase für dasselbe Objekt sind. Verwenden Sie x.classlist = otherlist[:]stattdessen, um eine Kopie der Liste zuzuweisen.
Dan D.
Hey wow! Vielen Dank! Ich wusste das wirklich nicht und es ist wirklich gut zu wissen! :)
wese3112
1

Die folgende Methode ist O (n) mit konstantem Hilfsspeicher:

def rotate(arr, shift):
  pivot = shift % len(arr)
  dst = 0
  src = pivot
  while (dst != src):
    arr[dst], arr[src] = arr[src], arr[dst]
    dst += 1
    src += 1
    if src == len(arr):
      src = pivot
    elif dst == pivot:
      pivot = src

Beachten Sie, dass dieser Ansatz in Python im Vergleich zu anderen schrecklich ineffizient ist, da er die nativen Implementierungen der einzelnen Teile nicht nutzen kann.

DRayX
quelle
Nun, eigentlich könnten Sie list.pop und list.append verwenden. Es ist nicht die Schuld der Sprache, dass Sie eine 12-Zeilen-Funktion geschrieben haben, die O (n) ist, wenn Sie gerade "l.append (l.pop (0))" hätten schreiben können, was eine konstante Zeit ist.
Purrell
l.append (l.pop (0)) ist O (n) (l.pop (0) muss jedes Element verschieben). Wenn Sie also m Werte verschieben möchten, ist die Komplexität tatsächlich O (n * m). Die Komplexität des von mir bereitgestellten Algorithmus beträgt O (n), unabhängig von der Anzahl der Verschiebungen. In der Praxis ist dies langsam, da in Python-Operationen anstelle von C so viel Logik ausgeführt wird (list.pop ist in c implementiert, siehe github.com/python/cpython/blob/master/Objects/listobject.c ).
DRayX
1

Ich habe ähnliche Sache. Zum Beispiel um zwei zu verschieben ...

def Shift(*args):
    return args[len(args)-2:]+args[:len(args)-2]
EyoelD
quelle
1

Ich denke, Sie haben den effizientesten Weg

def shift(l,n):
    n = n % len(l)  
    return l[-U:] + l[:-U]
John Ktejik
quelle
0

Was ist der Anwendungsfall? Oft brauchen wir kein vollständig verschobenes Array - wir müssen nur auf eine Handvoll Elemente im verschobenen Array zugreifen.

Das Abrufen von Python-Slices ist die Laufzeit O (k), wobei k das Slice ist. Eine geschnittene Rotation ist also die Laufzeit N. Der Deque-Rotationsbefehl lautet ebenfalls O (k). Können wir es besser machen?

Stellen Sie sich ein Array vor, das extrem groß ist (sagen wir, es ist so groß, dass es rechnerisch langsam wäre, es in Scheiben zu schneiden). Eine alternative Lösung wäre, das ursprüngliche Array in Ruhe zu lassen und einfach den Index des Elements zu berechnen, das nach einer Verschiebung in unserem gewünschten Index vorhanden gewesen wäre.

Der Zugriff auf ein verschobenes Element wird somit zu O (1).

def get_shifted_element(original_list, shift_to_left, index_in_shifted):
    # back calculate the original index by reversing the left shift
    idx_original = (index_in_shifted + shift_to_left) % len(original_list)
    return original_list[idx_original]

my_list = [1, 2, 3, 4, 5]

print get_shifted_element(my_list, 1, 2) ----> outputs 4

print get_shifted_element(my_list, -2, 3) -----> outputs 2 
Nick Lee
quelle
0

Die folgende Funktion kopiert die gesendete Liste in eine Vorlagenliste, sodass die Popup-Funktion die ursprüngliche Liste nicht beeinflusst:

def shift(lst, n, toreverse=False):
    templist = []
    for i in lst: templist.append(i)
    if toreverse:
        for i in range(n):  templist = [templist.pop()]+templist
    else:
        for i in range(n):  templist = templist+[templist.pop(0)]
    return templist

Testen:

lst = [1,2,3,4,5]
print("lst=", lst)
print("shift by 1:", shift(lst,1))
print("lst=", lst)
print("shift by 7:", shift(lst,7))
print("lst=", lst)
print("shift by 1 reverse:", shift(lst,1, True))
print("lst=", lst)
print("shift by 7 reverse:", shift(lst,7, True))
print("lst=", lst)

Ausgabe:

lst= [1, 2, 3, 4, 5]
shift by 1: [2, 3, 4, 5, 1]
lst= [1, 2, 3, 4, 5]
shift by 7: [3, 4, 5, 1, 2]
lst= [1, 2, 3, 4, 5]
shift by 1 reverse: [5, 1, 2, 3, 4]
lst= [1, 2, 3, 4, 5]
shift by 7 reverse: [4, 5, 1, 2, 3]
lst= [1, 2, 3, 4, 5]
rnso
quelle
0

Jon Bentley beschreibt in Programming Pearls (Spalte 2) einen eleganten und effizienten Algorithmus zum Drehen eines von Positionen hinterlassenen nElementvektors :xi

Betrachten wir das Problem als Umwandlung des Arrays abin das Array ba, nehmen wir aber auch an, dass wir eine Funktion haben, die die Elemente in einem bestimmten Teil des Arrays umkehrt. Beginnend mit abkehren wir aum , um zu bekommen , kehren um , um zu bekommen , und kehren dann das Ganze um , um zu bekommen , was genau ist . Dies führt zu folgendem Code für die Rotation:arbbarbr(arbr)rba

reverse(0, i-1)
reverse(i, n-1)
reverse(0, n-1)

Dies kann wie folgt in Python übersetzt werden:

def rotate(x, i):
    i %= len(x)
    x[:i] = reversed(x[:i])
    x[i:] = reversed(x[i:])
    x[:] = reversed(x)
    return x

Demo:

>>> def rotate(x, i):
...     i %= len(x)
...     x[:i] = reversed(x[:i])
...     x[i:] = reversed(x[i:])
...     x[:] = reversed(x)
...     return x
... 
>>> rotate(list('abcdefgh'), 1)
['b', 'c', 'd', 'e', 'f', 'g', 'h', 'a']
>>> rotate(list('abcdefgh'), 3)
['d', 'e', 'f', 'g', 'h', 'a', 'b', 'c']
>>> rotate(list('abcdefgh'), 8)
['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h']
>>> rotate(list('abcdefgh'), 9)
['b', 'c', 'd', 'e', 'f', 'g', 'h', 'a']
Eugene Yarmash
quelle
0

Für eine Liste X = ['a', 'b', 'c', 'd', 'e', 'f']und einen gewünschten Verschiebungswert von shift weniger als der Listenlänge können wir die Funktion list_shift()wie folgt definieren

def list_shift(my_list, shift):
    assert shift < len(my_list)
    return my_list[shift:] + my_list[:shift]

Beispiele,

list_shift(X,1)gibt ['b', 'c', 'd', 'e', 'f', 'a'] list_shift(X,3)zurück gibt zurück['d', 'e', 'f', 'a', 'b', 'c']

Helcode
quelle
1
Genau das hat das OP. Sie haben gerade die Namen geändert und eine Zusicherung hinzugefügt.
RufusVS
Die Funktion list_shiftin Ihrer Antwort ist identisch mit der Funktion shiftin der ursprünglichen Frage, daher ist dies keine Antwort auf die eigentliche Frage: "Gibt es einen besseren Weg?"
RufusVS
0
def solution(A, K):
    if len(A) == 0:
        return A

    K = K % len(A)

    return A[-K:] + A[:-K]

# use case
A = [1, 2, 3, 4, 5, 6]
K = 3
print(solution(A, K))

Zum Beispiel gegeben

A = [3, 8, 9, 7, 6]
K = 3

Die Funktion sollte zurückkehren [9, 7, 6, 3, 8]. Es wurden drei Umdrehungen gemacht:

[3, 8, 9, 7, 6] -> [6, 3, 8, 9, 7]
[6, 3, 8, 9, 7] -> [7, 6, 3, 8, 9]
[7, 6, 3, 8, 9] -> [9, 7, 6, 3, 8]

Für ein anderes Beispiel gegeben

A = [0, 0, 0]
K = 1

Die Funktion sollte zurückkehren [0, 0, 0]

Gegeben

A = [1, 2, 3, 4]
K = 4

Die Funktion sollte zurückkehren [1, 2, 3, 4]

Rakesh Kumar
quelle
0

Ich suchte nach einer Lösung für dieses Problem. Dies löst den Zweck in O (k).

def solution(self, list, k):
    r=len(list)-1
    i = 0
    while i<k:
        temp = list[0]
        list[0:r] = list[1:r+1]
        list[r] = temp
        i+=1
    return list
Ankit
quelle
-3

für ähnliche Funktionen wie die Verschiebung in anderen Sprachen:

def shift(l):
    x = l[0]
    del(l[0])
    return x
David
quelle
1
-1: Dies macht etwas anderes als das, was gefragt wird, und BTW ist auch gleichbedeutend mitL.pop(0)
6502