Самый быстрый способ перестановки подписок в python

Question

Какой самый быстрый способ переместить подсписщик из списка в Python?

Предположим, у нас есть список L = [a,b,c,d,e,f,g,h], теперь я хочу взять [c,d,e] и поместить его после g в список. Как я могу это сделать быстро?

Редактировать: Другими словами Я хотел бы написать функцию, которая:

1. извлекает подсписок L_sub длины п от L, в результате чего L_temp
2. вставить элементы L_sub при заданном позиция я в L_temp

основной вопрос, который я предполагаю, как вставить список в список как можно быстрее.

Answer 1

Я предполагаю, что ОП хочет сделать это InPlace.

Ключом к быстрому выполнению операции является минимизация создания списков и укорочение/удлинение списков. Это означает, что мы должны стремиться всегда выполнять присвоение индексов списка 1: 1, поэтому нет L[i:i] = L[a:b] и не L[a:b] = []. Использование циклов с insert и pop еще хуже, потому что тогда вы сокращаете и удлиняете список много раз. Конкатенационные списки также плохи, потому что вам сначала нужно создать один список для каждой части, а затем создать более крупные и крупные конкатенированные списки, по одному для каждого +. Поскольку вы хотите сделать это «inplace», вам придется назначить сгенерированный список 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 

Давайте сначала сделаем наблюдение. Если a = start, b = end = start + length и c - это позиция вставки, то операция, которую мы хотим сделать, - разрезать по маркам | и обмену span1 и span2.Но если b = start и c = end и a - позиция вставки, то мы также хотите обменять span1 и span2. Поэтому в нашей функции мы имеем дело с двумя последовательными сегментами, которые должны быть заменены.

Мы не можем полностью избежать создания новых списков, потому что нам нужно хранить перекрывающиеся значения при перемещении материала. Мы можем, однако сделаем список как можно короче, выбрав, какой из двух интервалов хранить во временном списке.

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 

Кос, кажется, сделал ошибку в своих таймингах, так что я переделал их свой код после коррекции аргументов (вычислений end от start и length), и этих результатов, от самого медленного до самого быстрого.

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 

Я не проверял, что любой из других подходов дает правильные результаты.

Answer 2

Я хотел бы сделать это с питоном подстроками

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 и end относятся к позиции подстроки вырезанных (конец неисключителен в обычном стиле питона. insert_at относится к позиции вставки вспомогательная строка снова зашла после

Я думаю, что это будет быстрее любого решения с итерацией в нем, если подстроки больше, чем символ или два в длину, так как хороший оптимизированный код C делая h подтяжка.

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

Давайте посмотрим, что мы получили до сих пор:

Код

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

Ориентиры:

> 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

Вот альтернативный 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)  

Выход:

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