pyplot - title plt python

Manera eficiente de cambiar una lista en python

Question

¿Cuál es la forma más eficiente de cambiar una lista en python? En este momento tengo algo como esto:

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

¿Hay alguna manera mejor?

Answer 1

¿Cuál es el caso de uso? A menudo, en realidad no necesitamos una matriz completamente modificada, solo necesitamos acceder a un puñado de elementos en la matriz modificada.

La obtención de segmentos de Python es el tiempo de ejecución O (k), donde k es el sector, por lo que una rotación de sectores es el tiempo de ejecución N. El comando de rotación deque también es O (k). ¿Podemos hacerlo mejor?

Considere una matriz que es extremadamente grande (digamos, tan grande que sería computacionalmente lento cortarla). Una solución alternativa sería dejar la matriz original sola y simplemente calcular el índice del elemento que habría existido en nuestro índice deseado después de un cambio de algún tipo.

Acceder a un elemento desplazado se convierte en 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

Answer 2

¿Qué hay de usar pop(0) ?

list.pop([i])

Elimine el elemento en la posición dada en la lista y devuélvalo. Si no se especifica ningún índice, a.pop() elimina y devuelve el último elemento de la lista. (Los corchetes alrededor de la i en la firma del método indican que el parámetro es opcional, no que se deben escribir corchetes en esa posición. Verá esta notación con frecuencia en la Referencia de la biblioteca de Python).

Answer 3

Creo que estas buscando esto:

a.insert(0, x)

Answer 4

Creo que tienes la forma más eficiente.

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

Answer 5

Depende de lo que quieras que suceda cuando hagas esto:

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

Es posible que desee cambiar su:

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

a:

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

Answer 6

El siguiente método es O (n) en su lugar con memoria auxiliar constante:

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

Tenga en cuenta que en Python, este enfoque es terriblemente ineficiente en comparación con otros, ya que no puede aprovechar las implementaciones nativas de ninguna de las piezas.

Answer 7

Esto también depende de si desea cambiar la lista en su lugar (mutarla) o si desea que la función devuelva una nueva lista. Porque, según mis pruebas, algo como esto es al menos veinte veces más rápido que su implementación que agrega dos listas:

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

De hecho, incluso agregar un l = l[:] en la parte superior de eso para operar en una copia de la lista pasada es aún el doble de rápido.

Varias implementaciones con cierto tiempo en http://gist.github.com/288272

Answer 8

Jon Bentley en Programming Pearls (Columna 2) describe un algoritmo elegante y eficiente para rotar un vector n elemento x dejado por i posiciones:

Veamos el problema como transformar la matriz ab en la matriz ba , pero también supongamos que tenemos una función que invierte los elementos en una parte específica de la matriz. Comenzando con ab , revertimos a para obtener a r b , revertimos b para obtener a r b r , y luego revertimos todo para obtener (a r b r ) r , que es exactamente ba . Esto da como resultado el siguiente código para la rotación:

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

Esto se puede traducir a Python de la siguiente manera:

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

Manifestación:

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

Answer 9

La forma más sencilla en que puedo pensar:

a.append(a.pop(0))

Answer 10

La siguiente función copia la lista enviada a un templista, de modo que la función pop no afecta a la lista original:

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

Pruebas:

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)

Salida:

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]

Answer 11

No sé si esto es ''eficiente'', pero también funciona:

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

EDIT: ¡Hola de nuevo, acabo de encontrar un gran problema con esta solución! Considere el siguiente código:

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

El método shift_classlist () ejecuta el mismo código que mi x.insert (0, x.pop ()) - solution, otherlist es una lista independiente de la clase. Después de pasar el contenido de otherlist a la lista MyClass.classlist, al llamar a shift_classlist () también cambia la lista de otras listas:

SALIDA DE LA CONSOLA:

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!

Yo uso Python 2.7. No sé si eso es un error, pero creo que es más probable que no haya entendido algo aquí.

¿Alguien de ustedes sabe por qué sucede esto?

Answer 12

Numpy puede hacer esto usando el comando roll :

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

Answer 13

Otra alternativa:

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

Answer 14

Para funcionalidades similares como shift en otros lenguajes:

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

Answer 15

Para una implementación inmutable, podrías usar algo como esto:

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)

Answer 16

Para una lista X = [''a'', ''b'', ''c'', ''d'', ''e'', ''f''] y un valor de shift deseado de shift menor que la longitud de la lista , podemos definir la función list_shift() como a continuación

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

Ejemplos

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

Answer 17

Posiblemente un anillador sea más adecuado. No es una lista, aunque es probable que se comporte como una lista para sus propósitos.

El problema es que la eficiencia de un cambio en una lista es O (n), que se vuelve importante para listas lo suficientemente grandes.

Cambiar en un anillador es simplemente actualizar la ubicación del cabezal que es O (1)

Answer 18

Sólo algunas notas sobre el tiempo:

Si está comenzando con una lista, l.append(l.pop(0)) es el método más rápido que puede usar. Esto se puede mostrar solo con la complejidad del tiempo:

• deque.rotate es O (k) (k = número de elementos)
• lista de conversión deque es O (n)
• list.append y list.pop son ambos O (1)

Por lo tanto, si está comenzando con objetos deque , puede deque.rotate() al costo de O (k). Pero, si el punto de partida es una lista, la complejidad del tiempo de usar deque.rotate() es O (n). l.append(l.pop(0) es más rápido en O (1).

A modo de ejemplo, aquí hay algunos ejemplos de tiempos en iteraciones de 1M:

Métodos que requieren conversión de tipo:

• deque.rotate con objeto deque: 0.12380790710449219 segundos (el más rápido)
• deque.rotate con conversión de tipo: 6.853878974914551 segundos
• np.roll con nparray: 6.0491721630096436 segundos
• np.roll con conversión de tipo: 27.558452129364014 segundos

Lista de métodos mencionados aquí:

• l.append(l.pop(0)) : 0.32483696937561035 segundos (el más rápido)
• " shiftInPlace ": 4.819645881652832 segundos
• ...

El código de tiempo usado está abajo.

colecciones.deque

Demostrar que crear deques a partir de listas es 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

Si necesitas crear objetos deque:

1M iteraciones @ 6.853878974914551 segundos

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)

Si ya tienes objetos deque:

1M iteraciones @ 0.12380790710449219 segundos

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

Si necesitas crear nparrays

1M iteraciones @ 27.558452129364014 segundos

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

Si ya tienes nparrays:

1M iteraciones @ 6.0491721630096436 segundos

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)

"Desplazar en su lugar"

No requiere conversión de tipo

1M iteraciones @ 4.819645881652832 segundos

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

No requiere conversión de tipo

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

Answer 19

Si solo desea iterar sobre estos conjuntos de elementos en lugar de construir una estructura de datos separada, considere usar iteradores para construir una expresión generadora:

def shift(l,n):
return itertools.islice(itertools.cycle(l),n,n+len(l))
>>> list(shift([1,2,3],1))
[2, 3, 1]

Answer 20

Si su meta es la eficiencia, (¿ciclos? ¿Memoria?) Es mejor que mire el módulo de matriz: http://docs.python.org/library/array.html

Las matrices no tienen la sobrecarga de las listas.

Sin embargo, en lo que respecta a las listas puras, lo que tienes es tan bueno como puedes esperar hacer.

Answer 21

También me interesé en esto y perfplot algunas de las soluciones sugeridas con perfplot (un pequeño proyecto mío).

Resulta que

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

es, con mucho, el método más rápido para pequeños turnos n .

Para mayor n ,

data[n:] + data[:n]

no es malo

Esencialmente, perfplot realiza el cambio para aumentar las matrices grandes y mide el tiempo. Aquí están los resultados:

shift = 1 :

shift = 100 :

Código para reproducir la trama:

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

Answer 22

Tengo algo similar. Por ejemplo, para desplazarse por dos ...

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

Answer 23

Tomo este modelo de costos como referencia:

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

Su método para dividir la lista y concatenar dos sub-listas son operaciones de tiempo lineal. Sugeriría usar pop, que es una operación de tiempo constante, por ejemplo:

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

Answer 24

Un collections.deque está optimizado para tirar y empujar en ambos extremos. Incluso tienen un método dedicado de rotate() .

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]