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. 将L_sub中给定位置i的项插入到L_temp中

我想主要的问题是如何尽可能快地将一个列表插入到列表中。

Answer 1

我假设 OP 想就地执行此操作。

使操作快速的关键是尽量减少列表的创建和列表的缩短/加长。这意味着我们必须努力始终对列表索引进行 1:1 分配，所以没有 L[i:i] = L[a:b]没有 L[a:b] = [] .使用 insert 的循环和 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 = 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

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

我没有测试任何其他方法是否产生正确的结果。