8

所以我想知道如何使用 Python 2.7 最有效地获取用于表示如下索引的值列表：（但长度最多为 250,000+）

indices = [2, 4, 5]

并从一个更大的列表中删除该索引列表，如下所示：（3,000,000+ 个项目）

numbers = [2, 6, 12, 20, 24, 40, 42, 51]

得到这样的结果：

[2, 6, 20, 42, 51]

我正在寻找一种有效的解决方案。我知道有很多方法可以做到这一点，但这不是我的问题。效率是。此外，此操作必须执行多次，并且列表都将呈指数级变小。我没有一个方程来表示随着时间的推移它们会变小多少。

编辑：

数字必须始终在列表中保持排序，或者在删除索引后返回排序。称为索引的列表可以排序或不排序。它甚至不必在列表中。

4

6 回答 6

7

您可能需要考虑使用numpy库来提高效率（如果您正在处理整数列表，这可能不是一个坏主意）：

>>> import numpy as np
>>> a = np.array([2, 6, 12, 20, 24, 40, 42, 51])
>>> np.delete(a, [2,4,5])
array([ 2,  6, 20, 42, 51])

注释np.delete：http ://docs.scipy.org/doc/numpy/reference/generated/numpy.delete.html

保持主数组不变，但维护一个掩码数组可能也值得考虑（虽然也没有对此进行任何速度测试......）

于 2012-11-27T00:41:04.087 回答
6

我怀疑在索引之间获取整个切片可能比列表理解更快

def remove_indices(numbers, indices):
    result = []
    i=0
    for j in sorted(indices):
        result += numbers[i:j]
        i = j+1
    result += numbers[i:]
    return result
于 2012-11-27T01:41:32.160 回答
4

另外的选择：

>>> numbers = [2, 6, 12, 20, 24, 40, 42, 51]
>>> indicies = [2, 4, 5]
>>> offset = 0
>>> for i in indicies:
...     del numbers[i - offset]
...     offset += 1
...
>>> numbers
[2, 6, 20, 42, 51]

编辑：

因此，在这个答案完全错误之后，我对每种不同的方法进行了基准测试：

在此处输入图像描述

横轴是项目数，纵轴是以秒为单位的时间。

最快的选择是使用切片来构建一个新列表（来自@gnibbler）：

def using_slices(numbers, indices):
    result = []
    i = 0
    for j in indices:
        result += numbers[i:j]
        i = j + 1
    result += numbers[i:]

令人惊讶的是它和“设置”（@Eric）击败numpy.delete（@Jon Clements）

这是我使用的脚本，也许我错过了一些东西。

于 2012-11-27T00:36:35.130 回答
3

这是我的第一种方法。

def remove_indices(numbers, indices):
    indices = set(indices)
    return [x for i, x in enumerate(numbers) if i not in indices]

这是一个测试模块，用于在您指定的条件下对其进行测试。（300 万个元素，需要删除 25 万个元素）

import random

def create_test_set():
    numbers = range(3000000)
    indices = random.sample(range(3000000), 250000)
    return numbers, indices

def remove_indices(numbers, indices):
    indices = set(indices)
    return [x for i, x in enumerate(numbers) if i not in indices]

if __name__ == '__main__':
    import time
    numbers, indices = create_test_set()
    a = time.time()
    numbers = remove_indices(numbers, indices)
    b = time.time()
    print b - a, len(numbers)

在我的笔记本电脑上大约需要 0.6 秒。如果您要多次使用它，您可以考虑预先设置索引。

（FWIW bradley.ayers 解决方案花费的时间比我愿意等待的时间长。）

编辑：这稍微快一点：（0.55 秒）

def remove_indices(numbers, indices):
    return [numbers[i] for i in xrange(len(numbers)) if i not in indices]
于 2012-11-27T00:40:59.093 回答
2

效率不高，但方法不同

indices = set([2, 4, 5])

result = [x for i,x in enumerate(numbers) if i not in indices]
于 2012-11-27T00:41:51.933 回答
1

实现这一目标的另一种不同方法：

>>> numbers = [2, 6, 12, 20, 24, 40, 42, 51]
>>> indices = [2, 4, 5]
>>> [item for item in numbers if numbers.index(item) not in indices]
[2, 6, 20, 42, 51]
于 2016-11-21T14:21:08.970 回答