La forma más rápida de reposicionar la sublista en python

Question

¿Cuál es la forma más rápida de reubicar una sublista de una lista en Python?

Digamos que tenemos una lista L = [a,b,c,d,e,f,g,h], ahora quiero tomar [c,d,e] y ponerlo después de g en la lista. ¿Cómo puedo hacer esto rápido?

Editar: En otras palabras, me gustaría escribir una función que:

1. extrae una lista secundaria L_sub de longitud n a partir de L, dejando L_temp
2. insertar los elementos de L_sub a una determinada posición i en L_temp

La cuestión principal que supongo que es la forma de insertar una lista en la lista lo más rápido posible.

Answer 1

Asumo PO quiere hacer esto in-situ.

La clave para realizar una operación rápida es minimizar la creación de listas y el acortamiento/alargamiento de listas. Esto significa que debemos esforzarnos por realizar siempre una asignación 1: 1 de índices de listas, de modo que no L[i:i] = L[a:b] y no L[a:b] = []. El uso de bucles con insert y pop es aún peor, porque acorta y alarga la lista muchas veces. Las listas de concatenación también son malas porque primero tiene que crear una lista para cada parte y luego crear listas concatenadas cada vez más grandes, una para cada +. Como quiera hacer esto "in situ", deberá asignar la lista generada al final al L[:].

# items: 0 | 1 2 3 | 4 5 6 7 | 8 9 
    #   a span1 b  span2  c 
    # pos:  1   4    8 

    # Result: 
    #   0 | 4 5 6 7 | 1 2 3 | 8 9 
    #   a  span2   span2 c 

Permite hacer una primera observación. Si a = start, b = end = start + length y c es la posición de inserción, entonces la operación que queremos hacer es cortar en los marcadores | y cambiar span1 y span2.Pero si b = start y c = end y a es la posición de inserción, entonces nosotros también queremos cambiar span1 y span2. Entonces, en nuestra función, solo tratamos con dos segmentos consecutivos que deben intercambiarse.

No podemos evitar totalmente hacer nuevas listas, porque necesitamos almacenar valores superpuestos mientras movemos cosas. Nos puede sin embargo, hacer la lista lo más breve posible, eligiendo cuál de los dos tramos para almacenar en una lista temporal.

def inplace_shift(L, start, length, pos): 
    if pos > start + length: 
     (a, b, c) = (start, start + length, pos) 
    elif pos < start: 
     (a, b, c) = (pos, start, start + length) 
    else: 
     raise ValueError("Cannot shift a subsequence to inside itself") 
    if not (0 <= a < b < c <= len(L)): 
     msg = "Index check 0 <= {0} < {1} < {2} <= {3} failed." 
     raise ValueError(msg.format(a, b, c, len(L))) 

    span1, span2 = (b - a, c - b) 
    if span1 < span2: 
     tmp = L[a:b] 
     L[a:a + span2] = L[b:c] 
     L[c - span1:c] = tmp 
    else: 
     tmp = L[b:c] 
     L[a + span2:c] = L[a:b] 
     L[a:a + span2] = tmp 

Kos parece haber cometido un error en sus tiempos, por lo que les hizo de nuevo con su código después de corregir los argumentos (el cálculo de endstart y length), y estos son los resultados, desde la más lenta a la más rápida.

Nick Craig-Wood: 100 loops, best of 3: 8.58 msec per loop 
vivek: 100 loops, best of 3: 4.36 msec per loop 
PaulP.R.O. (deleted?): 1000 loops, best of 3: 838 usec per loop 
unbeli: 1000 loops, best of 3: 264 usec per loop 
lazyr: 10000 loops, best of 3: 44.6 usec per loop 

No he probado que ninguno de los otros enfoques arroje resultados correctos.

Answer 2

lo haría con subcadenas pitón

def subshift(L, start, end, insert_at): 
    temp = L[start:end] 
    L = L[:start] + L[end:] 
    return L[:insert_at] + temp + L[insert_at:] 

print subshift(['a','b','c','d','e','f','g','h'], 2, 5, 4) 

start y end refieren a la posición de la subcadena de cortar (final es no exclusiva en el estilo pitón usual. insert_at se refiere a la posición para insertar la cadena sub volver de nuevo después se ha cortado.

creo que esto será más rápido que cualquier solución con iteración en ella, si las subseries son más que un personaje o dos en longitud como buen código C optimizado es haciendo la h eavy levantamiento.

Answer 3

>>> L = ['a','b','c','d','e','f','g','h'] 
>>> L[7:7] = L[2:5] 
>>> L[2:5] = [] 
>>> L 
['a', 'b', 'f', 'g', 'c', 'd', 'e', 'h'] 

Answer 4

def shift(L,start,n,i): 
    return L[:start]+L[start+n:i]+L[start:start+n]+L[i:] 

Answer 5

Vamos a ver lo que tenemos hasta ahora:

Código

def subshift(L, start, end, insert_at): 
    'Nick Craig-Wood' 
    temp = L[start:end] 
    L = L[:start] + L[end:] 
    return L[:insert_at] + temp + L[insert_at:] 

# (promising but buggy, needs correction; 
# see comments at unbeli's answer) 
def unbeli(x, start, end, at): 
    'unbeli' 
    x[at:at] = x[start:end] 
    x[start:end] = [] 

def subshift2(L, start, length, pos): 
    'PaulP.R.O.' 
    temp = pos - length 
    S = L[start:length+start] 
    for i in range(start, temp): 
     L[i] = L[i + length] 
    for i in range(0,length): 
     L[i + temp] = S[i] 
    return L 

def shift(L,start,n,i): 
    'vivek' 
    return L[:start]+L[start+n:i]+L[start:start+n]+L[i:] 

Puntos de Referencia:

> args = range(100000), 3000, 2000, 60000 

> timeit subshift(*args) 
100 loops, best of 3: 6.43 ms per loop 

    > timeit unbeli(*args) 
1000000 loops, best of 3: 631 ns per loop 

> timeit subshift2(*args) 
100 loops, best of 3: 11 ms per loop 

> timeit shift(*args) 
100 loops, best of 3: 4.28 ms per loop 

Answer 6

Aquí es una solución alternativa inplace:

def movesec(l,srcIndex,n,dstIndex): 
    if srcIndex+n>dstIndex: raise ValueError("overlapping indexes") 
    for i in range(n): 
     l.insert(dstIndex+1,l.pop(srcIndex)) 

    return l 


print range(10) 
print movesec(range(10),3,2,6)  

Salida:

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9] # orginal 
[0, 1, 2, 5, 6, 7, 3, 4, 8, 9] # modified