python - 在python中重新定位子列表的最快方法

Question

从 Python 列表中重新定位子列表的最快方法是什么？

假设我们有一个列表L = [a,b,c,d,e,f,g,h]，现在我想把[c,d,e]它放在g列表后面。我怎样才能快速做到这一点？

编辑：换句话说，我想编写一个函数：

1. 从 L 中提取长度为n的子列表 L_sub ，留下 L_temp
2. 将给定位置i处的 L_sub 的项目插入 L_temp

我猜的主要问题是如何尽快将列表插入列表中。

Answer 1

我认为 OP 想要就地执行此操作。

使操作快速的关键是尽量减少列表的创建和列表的缩短/延长。这意味着我们必须努力始终对列表索引进行 1:1 分配，因此 noL[i:i] = L[a:b]和 no L[a:b] = []。将循环与insertand一起使用pop更糟糕，因为这样会多次缩短和延长列表。串联列表也很糟糕，因为您首先必须为每个部分创建一个列表，然后创建越来越大的串联列表，每个+. 由于您想“就地”执行此操作，因此您必须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 = startand是插入位置，那么我们c = end也想交换and 。所以在我们的函数中，我们只处理两个必须交换的连续段。aspan1span2

我们不能完全避免创建新列表，因为我们需要在移动内容时存储重叠的值。但是，我们可以通过选择将两个跨度中的哪一个存储到临时列表中来使列表尽可能短。

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 似乎在他的时间安排上犯了一个错误，所以我在更正参数（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

我会用 python 子字符串来做

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指要剪切的子字符串的位置（结束在通常的python样式中是非排他的。 指在剪切后insert_at重新插入子字符串的位置。

如果子字符串的长度超过一个或两个字符，我认为这将比任何包含迭代的解决方案更快，因为经过优化的 C 代码正在完成繁重的工作。

Answer 3

让我们检查一下到目前为止我们得到了什么：

代码

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 4

这是一个替代的就地解决方案：

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

Answer 5

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

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