Skuteczny sposób na obracanie listy w pythonie

Jaki jest najskuteczniejszy sposób obracania listy w pythonie? Teraz mam coś takiego:

>>> 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]

Czy jest lepszy sposób?

A collections.dequejest zoptymalizowany do ciągnięcia i pchania na obu końcach. Mają nawet dedykowaną rotate()metodę.

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]

A co z samym używaniem pop(0)?

list.pop([i])

Usuń element z podanej pozycji na liście i zwróć go. Jeśli nie określono indeksu, a.pop()usuwa i zwraca ostatni element na liście. (Nawiasy kwadratowe wokół ipodpisu metody oznaczają, że parametr jest opcjonalny, a nie, że należy wpisać nawiasy kwadratowe w tej pozycji. Notację tę często zobaczysz w Skorowidzu biblioteki Python.)

Numpy może to zrobić za pomocą rollpolecenia:

>>> 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])

Zależy to od tego, co chcesz, aby to się stało:

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

Możesz zmienić swoje:

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

do:

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

Najprostszy sposób, w jaki mogę wymyślić:

a.append(a.pop(0))

Jeśli chcesz po prostu iterować te zestawy elementów zamiast tworzyć osobną strukturę danych, rozważ użycie iteratorów do skonstruowania wyrażenia generatora:

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

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

Zależy to również od tego, czy chcesz przesunąć listę na miejscu (mutując ją), czy też chcesz, aby funkcja zwróciła nową listę. Ponieważ według moich testów coś takiego jest co najmniej dwadzieścia razy szybsze niż implementacja, która dodaje dwie listy:

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

W rzeczywistości nawet dodanie l = l[:] do góry tego, aby działało na kopii przekazanej listy, jest jeszcze dwa razy szybsze.

Różne implementacje z pewnym czasem na http://gist.github.com/288272

Kilka uwag na temat czasu:

Jeśli zaczynasz od listy, l.append(l.pop(0))jest to najszybsza metoda, jakiej możesz użyć. Można to pokazać przy samej złożoności czasowej:

• deque.rotate to O (k) (k = liczba elementów)
• konwersja listy do deque to O (n)
• zarówno list.append, jak i list.pop są O (1)

Jeśli więc zaczynasz od dequeobiektów, możesz to zrobić deque.rotate()kosztem O (k). Ale jeśli punktem początkowym jest lista, złożoność czasowa użycia deque.rotate()wynosi O (n). l.append(l.pop(0)jest szybszy przy O (1).

Dla ilustracji, oto kilka przykładowych czasów dla iteracji 1M:

Metody wymagające konwersji typu:

• deque.rotatez obiektem deque : 0,12380790710449219 sekund (najszybszy)
• deque.rotatez konwersją typu: 6,853878974914551 sekund
• np.rollz nparray: 6.0491721630096436 sekund
• np.rollz konwersją typu: 27.558452129364014 sekund

Wymień metody wymienione tutaj:

• l.append(l.pop(0)): 0,32483696937561035 sekund (najszybszy)
• „ shiftInPlace”: 4,819645881652832 sekund
• ...

Zastosowany kod czasowy znajduje się poniżej.

collections.deque

Pokazuje, że tworzenie deques z list to O (n):

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

Jeśli chcesz utworzyć obiekty deque:

Iteracje 1M @ 6.853878974914551 sekund

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)

Jeśli masz już obiekty deque:

1M iteracje @ 0,12380790710449219 sekund

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

Jeśli potrzebujesz stworzyć nparrays

1M iteracje @ 27.558452129364014 sekund

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
"""

Jeśli masz już nparrays:

1M iteracji @ 6.0491721630096436 sekund

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)

„Przesunięcie w miejscu”

Nie wymaga konwersji typu

1M iteracje @ 4,819645881652832 sekundy

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))

Nie wymaga konwersji typu

1M iteracje @ 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)

Zainteresowałem się tym i porównałem niektóre z sugerowanych rozwiązań z perfplot ( mój mały projekt).

Okazało się, że

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

jest zdecydowanie najszybszą metodą na małe zmiany n.

Dla większych n,

data[n:] + data[:n]

nie jest źle.

Zasadniczo perfplot wykonuje zmianę w celu zwiększenia dużych tablic i mierzy czas. Oto wyniki:

shift = 1:

shift = 100:

Kod do odtworzenia fabuły:

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)",
)

Być może bardziej odpowiedni jest bufet pierścieniowy. To nie jest lista, chociaż jest prawdopodobne, że może zachowywać się wystarczająco jak lista do twoich celów.

Problem polega na tym, że wydajność przesunięcia na liście wynosi O (n), co staje się znaczące dla wystarczająco dużych list.

Przesunięcie bufora pierścieniowego oznacza po prostu aktualizację położenia głowy, którym jest O (1)

Dla niezmiennej implementacji możesz użyć czegoś takiego:

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)

Jeśli twoim celem jest wydajność (cykli? Pamięci?), Możesz lepiej spojrzeć na moduł macierzy: http://docs.python.org/library/array.html

Tablice nie mają narzutu list.

Jeśli chodzi o czyste listy, to, co masz, jest tak dobre, jak możesz mieć nadzieję.

Myślę, że tego szukasz:

a.insert(0, x)

Inna alternatywa:

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

Przyjmuję ten model kosztów jako odniesienie:

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

Metodą dzielenia listy i łączenia dwóch podlist są operacje liniowe. Sugerowałbym użycie popu, który jest operacją o stałym czasie, np .:

def shift(list, n):
    for i in range(n)
        temp = list.pop()
        list.insert(0, temp)

Nie wiem, czy to jest „wydajne”, ale działa również:

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

EDYCJA: Witam ponownie, właśnie znalazłem duży problem z tym rozwiązaniem! Rozważ następujący kod:

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!'

Metoda shift_classlist () wykonuje ten sam kod, co mój x.insert (0, x.pop ()) - rozwiązanie, otherlist jest listą niezależną od klasy. Po przekazaniu zawartości otherlist do listy MyClass.classlist wywołanie shift_classlist () zmienia również listę otherlist:

WYJŚCIE KONSOLI:

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!

Używam Python 2.7. Nie wiem, czy to błąd, ale myślę, że bardziej prawdopodobne jest, że coś tutaj nie zrozumiałem.

Czy ktoś z was wie, dlaczego tak się dzieje?

Następująca metoda to O (n) w miejscu ze stałą pamięcią pomocniczą:

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

Zauważ, że w Pythonie takie podejście jest okropnie nieefektywne w porównaniu do innych, ponieważ nie może korzystać z natywnych implementacji żadnego z elementów.

Mam podobne rzeczy. Na przykład, aby przesunąć o dwa ...

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

Myślę, że masz najbardziej efektywny sposób

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

Jaki jest przypadek użycia? Często nie potrzebujemy w pełni przesuniętej tablicy - wystarczy uzyskać dostęp do kilku elementów w przesuniętej tablicy.

Pobieranie wycinków w Pythonie to środowisko wykonawcze O (k), gdzie k jest wycinkiem, więc obrót w plasterkach to środowisko wykonawcze N. Polecenie odwrotnego obrotu to także O (k). Czy możemy zrobić lepiej?

Rozważmy tablicę, która jest bardzo duża (powiedzmy, że tak duża, że ​​jej wycięcie byłoby wolniejsze obliczeniowo). Alternatywnym rozwiązaniem byłoby pozostawienie oryginalnej tablicy w spokoju i po prostu obliczenie indeksu elementu, który istniałby w naszym pożądanym indeksie po pewnym przesunięciu.

Dostęp do przesuniętego elementu staje się w ten sposób 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 

Poniższa funkcja kopiuje listę wysłaną do szablonu, dzięki czemu funkcja pop nie wpływa na oryginalną listę:

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

Testowanie:

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)

Wynik:

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]

Jon Bentley w Programming Pearls (kolumna 2) opisuje elegancki i skuteczny algorytm obracania nwektora elementu-elementu xpozostawionego o ipozycje:

Spójrzmy na problem jako przekształcenie tablicy abw tablicę ba, ale załóżmy, że mamy funkcję, która odwraca elementy w określonej części tablicy. Zaczynając od ab, odwracamy, aaby uzyskać , odwracamy, aby uzyskać , a następnie odwracamy wszystko, aby uzyskać , co jest dokładnie . Powoduje to następujący kod do obrotu:arbbarbr(arbr)rba

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

Można to przetłumaczyć na Python w następujący sposób:

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

Próbny:

>>> 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']

Dla listy X = ['a', 'b', 'c', 'd', 'e', 'f']i pożądanej wartości przesunięcia shift mniejszej niż długość listy możemy zdefiniować funkcję list_shift()jak poniżej

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

Przykłady

list_shift(X,1)zwraca ['b', 'c', 'd', 'e', 'f', 'a'] list_shift(X,3)zwraca['d', 'e', 'f', 'a', 'b', 'c']

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))

Na przykład dane

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

funkcja powinna wrócić [9, 7, 6, 3, 8]. Wykonano trzy obroty:

[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]

Podany inny przykład

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

funkcja powinna wrócić [0, 0, 0]

Dany

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

funkcja powinna wrócić [1, 2, 3, 4]

Szukałem na miejscu rozwiązania tego problemu. To rozwiązuje cel w 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

dla podobnej funkcjonalności jak zmiana w innych językach:

def shift(l):
    x = l[0]
    del(l[0])
    return x