python - 在 python 中为 insert() 编写更快的实现

Question

本质上，我需要编写一个更快的实现来替代 insert() 以将元素插入列表中的特定位置。输入在列表中作为 [(index, value), (index, value), (index, value)]

例如:在 1,000,000 个元素的列表中插入 10,000 个元素大约需要 2.7 秒

def do_insertions_simple(l, insertions):
    """Performs the insertions specified into l.
    @param l: list in which to do the insertions.  Is is not modified.
    @param insertions: list of pairs (i, x), indicating that x should
        be inserted at position i.
    """
    r = list(l)
    for i, x in insertions:
        r.insert(i, x)
    return r

我的作业要求我将完成插入所需的时间加快 8 倍或更多

我当前的实现:

def do_insertions_fast(l, insertions):
    """Implement here a faster version of do_insertions_simple """
    #insert insertions[x][i] at l[i]
    result=list(l)
    for x,y in insertions:
      result = result[:x]+list(y)+result[x:]
    return result

示例输入:

import string
l = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
insertions = [(0, 'a'), (2, 'b'), (2, 'b'), (7, 'c')]
r1 = do_insertions_simple(l, insertions)
r2 = do_insertions_fast(l, insertions)
print("r1:", r1)
print("r2:", r2)
assert_equal(r1, r2)

is_correct = False
for _ in range(20):
    l, insertions = generate_testing_case(list_len=100, num_insertions=20)
    r1 = do_insertions_simple(l, insertions)
    r2 = do_insertions_fast(l, insertions)
    assert_equal(r1, r2)
    is_correct = True

运行上述代码时出现的错误:

r1: ['a', 0, 'b', 'b', 1, 2, 3, 'c', 4, 5, 6, 7, 8, 9]
r2: ['a', 0, 'b', 'b', 1, 2, 3, 'c', 4, 5, 6, 7, 8, 9]
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-8-54e0c44a8801> in <module>()
     12     l, insertions = generate_testing_case(list_len=100, num_insertions=20)
     13     r1 = do_insertions_simple(l, insertions)
---> 14     r2 = do_insertions_fast(l, insertions)
     15     assert_equal(r1, r2)
     16     is_correct = True

<ipython-input-7-b421ee7cc58f> in do_insertions_fast(l, insertions)
      4     result=list(l)
      5     for x,y in insertions:
----> 6       result = result[:x]+list(y)+result[x:]
      7     return result
      8     #raise NotImplementedError()

TypeError: 'float' object is not iterable

该文件正在使用 nose 框架来检查我的答案等，因此如果有任何您不认识的功能，它可能来自该框架。

我知道它正在正确插入列表，但是它不断引发错误“float object is not iterable”

我也尝试了一种不同的方法，它确实有效(切片列表，添加元素，添加列表的其余部分，然后更新列表)但是比 insert() 慢 10 倍

我不确定如何继续

编辑:我一直在错误地看待整个问题，现在我会尝试自己做，但如果我再次遇到困难，我会问一个不同的问题并在此处链接

Answer 1

从你的问题，强调我的:

I need to write a faster implementation as a replacement for insert() to insert an element in a particular position in a list

你做不到。如果有更快的方法，那么现有的 insert() 函数就会使用它。你做任何事情都不会接近速度。

您可以做的是编写一种更快的方法来进行多次插入。

让我们看一个有两个插入的例子:

>>> a = list(range(15))
>>> a.insert(5, 'X')
>>> a.insert(10, 'Y')
>>> a
[0, 1, 2, 3, 4, 'X', 5, 6, 7, 8, 'Y', 9, 10, 11, 12, 13, 14]

由于每次插入都会将所有值移到它的右边，这通常是一个 O(m*(n+m)) 时间算法，其中 n 是列表的原始大小，m 是插入的次数。

另一种方法是逐段构建结果，同时考虑插入点:

>>> a = list(range(15))
>>> b = []
>>> b.extend(a[:5])
>>> b.append('X')
>>> b.extend(a[5:9])
>>> b.append('Y')
>>> b.extend(a[9:])
>>> b
[0, 1, 2, 3, 4, 'X', 5, 6, 7, 8, 'Y', 9, 10, 11, 12, 13, 14]

这是 O(n+m) 时间，因为所有值只复制一次，没有移位。确定正确的片段长度有点棘手，因为较早的插入会影响较晚的插入。特别是如果插入索引未排序(在这种情况下，还需要 O(m log m) 额外的时间来对它们进行排序)。这就是为什么我必须使用 [5:9] 和 a[9:] 而不是 [5:10] 和 a [10:]

(是的，我知道，如果容量用尽，extend/append 会在内部复制更多内容，但如果您对事情的理解足以指出这一点，那么您也明白没关系:-)