插入列表中间的最有效方法是什么？

Question

我正在读取一个文件并构建一个列表a2。 我想在a2列表的前两个项目后，从b列表中插入3行到a2列表中。

b = ["This is a line", "another line", "and another one"]
a2 = ['a1', 'a2', 'a3']

i = 0
for x, y in map(None, a2[0:2], a2):
    i = i + 1
    if x == y:
        continue
    else:
        for newLine in b:
            a2.insert(i-1, newLine)
            i = i+1
print a2

上述代码给出了我期望得到的结果，如['a1', 'a2', 'This is a line', 'another line', 'and another one', 'a3']。但由于我将从大型文本文件中构建列表并在其中插入几行，因此我认为必须使它更具性能直观性！

- Ciasto piekarz

---

你真的需要它作为列表吗？使用迭代器可能更有效率。 - jonrsharpe

这并没有回答我的问题。你能给一个更具体的例子，说明你真正尝试达成的目标吗？ - jonrsharpe

a2[0:2] 中的数字 2 是从哪里来的？问题在于，最简单的方法是 a2[:2] + b + a2[2:]，但这需要知道这些索引。另外，在这之后您想对 a2 做什么？如果您仅按序访问其元素（例如写回文件或某些算法），编写生成器函数将是更快的选择，因为它避免了预先构建整个列表的开销。 - Ulrich Eckhardt

顺便问一下，你用的是哪个Python版本？不是3.x（我建议你使用这个版本），而是2.x系列中的一个…… - Ulrich Eckhardt

@san 插入应该只发生在2个位置之后吗？你的列表a2最初大小是固定的还是可能会变化？ - gsb-eng

Answer 1

如何处理 -

a2[2:2] = b

演示 -

>>> b = ["This is a line", "another line", "and another one"]
>>> a2 = ['a1', 'a2', 'a3']
>>> a2[2:2] = b
>>> a2
['a1', 'a2', 'This is a line', 'another line', 'and another one', 'a3']

以下是我所了解的一些方法（包括OP发布的方法）的时间信息 -

def func1():
    b = ["This is a line", "another line", "and another one"]
    a2 = ['a1', 'a2', 'a3']
    i = 0
    for x, y in map(None, a2[0:2], a2):
        i = i + 1
        if x == y:
            continue
        else:
            for newLine in b:
                a2.insert(i-1, newLine)
                i = i+1
    return a2


def func2():
    b = ["This is a line", "another line", "and another one"]
    a2 = ['a1', 'a2', 'a3']
    a2 = a2[:2] + b + a2[2:]
    return a2

def func3():
    b = ["This is a line", "another line", "and another one"]
    a2 = ['a1', 'a2', 'a3']
    a2[2:2] = b
    return a2


import timeit

print timeit.timeit(func1,number=500000)
print timeit.timeit(func2,number=500000)
print timeit.timeit(func3,number=500000)

结果 -

1.81288409233
0.621006011963
0.341125011444

---

计时结果，其中a有100000个元素，b有1000个元素 -

def func1():
    global a2
    global b
    i = 0
    for x, y in map(None, a2[0:2], a2):
        i = i + 1
        if x == y:
            continue
        else:
            for newLine in b:
                a2.insert(i-1, newLine)
                i = i+1
            break
    return a2


def func2():
    global a2
    global b
    a2 = a2[:2] + b + a2[2:]
    return a2

def func3():
    global a2
    global b
    a2[2:2] = b
    return a2

def func4():
    global a2
    global b
    a2.reverse()
    b.reverse()
    for i in b:
        a2.insert(-2, i)
    return a2

import timeit

a2 = ['a1' for _ in range(100000)]
b = ['a2' for i in range(1000)]

print timeit.timeit(func1,number=10,setup = 'from __main__ import a2,b')
print timeit.timeit(func2,number=10,setup = 'from __main__ import a2,b')
print timeit.timeit(func3,number=10,setup = 'from __main__ import a2,b')
print timeit.timeit(func4,number=10,setup = 'from __main__ import a2,b')

结果 -

1.00535297394
0.0210499763489
0.001296043396
0.0044310092926

参考时序测试 - https://ideone.com/k4DANI

- Anand S Kumar

---

你的解决方案基本上与问题中的相同，只是以另一种方式编写。请注意，根据文档，s.insert(i, x)与s[i:i]=x相同。它几乎不会更有效率，因为它必须将列表中所有后续元素向后移动一步。 - skyking

你有没有检查上面发布的时间信息？ - Anand S Kumar

@AnandSKumar 是的，那又怎样？试着让a有3000000个元素而不是3个。请注意他谈论的是巨大的文件。 - skyking

@skyking，请检查最新更新，使用具有100000个元素的a2进行测试，不要在没有尝试过的情况下说无根据的话。 - Anand S Kumar

请注意，您必须减少要执行的运行次数。请注意，如果将a2增加十倍，则前三个解决方案的增加量大致相同 - 尽管您没有更改插入次数。最后一个解决方案取决于这样一个观察结果：插入是在列表开头完成的（我对这种假设是否正确持怀疑态度 - 请参见问题的评论）。 - skyking

Answer 2

我认为您的列表 a2 在开始时不是固定大小，并且您必须在索引1之后将list b的所有值插入到list a2中。

通常情况下，list.insert() 的工作方式如下：如果list l1的大小为n（假设n很大），并且如果您尝试从开头添加另一个巨大的list l2，例如从位置2开始l1.insert(2, val)，这应该会将list l1的其他元素从2到n-1移动到每次插入的下一个位置。

我们可以通过反转l1和l2来避免这种情况。

让我们考虑您的列表 l1、l2，我们需要将所有 l2 的值从 索引 2 插入到 l1 中。

>>> l1 = range(1, 10)
>>> l2 = range(10, 20)
>>> l1
[1, 2, 3, 4, 5, 6, 7, 8, 9]
>>> l2
[10, 11, 12, 13, 14, 15, 16, 17, 18, 19]

在以下方式将l2插入到l1之后......

>>> i = 2
>>> for j in l2:
...     l1.insert(i, j)
...     i += 1
>>> l1
[1, 2, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 3, 4, 5, 6, 7, 8, 9]

以上述方式插入时，每次将值3, 4, 5, 6, 7, 8, 9插入到l1中，在适当的list.resize后已经移到了下一个位置。假设你的'l1'大小是一千万，这些值的移动会成为一个负担。

为了避免在每次插入时在列表内部进行数据移动，在你的情况下，你可以从末尾插入值，需要反转列表l1和l2并执行l1.insert(-2, l2.val)。

>>> l1
[1, 2, 3, 4, 5, 6, 7, 8, 9]
>>> l2
[10, 11, 12, 13, 14, 15, 16, 17, 18, 19]
>>> l1.reverse()
>>> l2.reverse()
>>> l1
[9, 8, 7, 6, 5, 4, 3, 2, 1]
>>> l2
[19, 18, 17, 16, 15, 14, 13, 12, 11, 10]
>>> for i in l2:
...     l1.insert(-2, i)
... 

插入后，您将得到以下结果...

>>> l1
[9, 8, 7, 6, 5, 4, 3, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 2, 1]

如果您观察到在这种插入方式中发生的数据移动，只有值2, 1在插入l2的值时一直被移动。

您可以简单地反转l1以获得所需的值列表。

>>> l1.reverse()
>>> l1
[1, 2, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 3, 4, 5, 6, 7, 8, 9]

这样我们就可以避免在 list.insert() 中发生最常见的 数据移动。

时间统计：https://ideone.com/owzWza

注意：这个解决方案在你的情况下很好用，但是如果你在 list 的 中间 插入了一些值，你需要再考虑另一个最佳解决方案。

- gsb-eng

---

@AnandSKumar 在这个问题中，他给出了一个简单的列表，用于从特定位置插入一个到另一个，如果你只尝试那些值，几乎不会看到执行时间上的差异，但是当你在a2列表和b列表中使用数百万的值时，就会看到差异。 - gsb-eng

@AnandSKumar 我不确定你尝试了什么，但我已经将“列表长度”增加到“10k”，这是结果 https://ideone.com/owzWza - gsb-eng

@AnandSKumar 想象一下如果“列表长度”达到“数百万”，会有什么结果。 - gsb-eng

@AnandSKumar 是的，切片总是比其他方法更有优势，但在这里他谈论的是文件，如果文件大小是“巨大”的话，他不应该将所有内容都读入内存，此时他可以轻松地反转“文件”并以高效的方式“读取”文件，然后使用我的方法来完成此操作。 - gsb-eng

Answer 3

如果你真的想做你在问题中描述的事情，最快的解决方案（如果你要插入的数组变得很大）是使用自定义容器类。已经指出反转列表会更快，但每次插入元素时反转列表（并在之后再次反转）也是代价高昂的。可以尝试这样的代码：

class ReverseList:
    def __init__(self, *args, **kwds):
        self.revlist = list(*args, **kwds)
        self.revlist.reverse()

    def __getitem__(self, key):
        # if you need slicing you need to improve this:
        return self.revlist[-key] 

    def __setitem__(self, key, val):
        # if you need slicing you need to improve this:
        return self.revlist[-key] = val

    def insert(self, pos, val):
        self.revlist.insert(-pos, val)

    # etc

- skyking