从python中的列表中删除元素

Question

在O(1)复杂性中，从python中的列表中删除元素有任何方法吗?也就是说，删除(值)：这在列表中线性搜索，并删除正确的元素。？那么，是否可以通过指定索引或值来删除O(1)复杂性中的元素？

当向以下代码提供大小为100000的输入列表时，即使在使用"del“之后，它也超过了时间限制。

l=map(int,raw_input("").split(" "))
n=l[0]
k=l[1]
s=map(int,raw_input("").split(" "))
s=sorted(s)
count=0
tree=[]
while len(s)>0:
    poset=[]
    indices=[]
    i=0
    poset.append(s[i])
    indices.append(0)
    j=i+1
    while j<len(s):
       if s[j]==k*s[i]:
           poset.append(s[j])
           indices.append(j)
           i=j
        j+=1
    tmp=0
    for i in indices:
        del s[i-tmp]
        tmp+=1                  
    tree.append(poset)

for i in tree:
    if len(i)%2==0:
        count+=(len(i))/2
    else:
        count+=(len(i)+1)/2
print count

Answer 1

正式上没有。

如果您知道C++列表多少是作为指向对象的指针的std::vector实现的(用C语言来说，它们是指向连续指针数组的指针)。这使O(1)能够访问给定索引的元素，并允许调整大小，但是从列表中删除元素需要将所有后续元素向下移动一个元素以填补空白。

但是，请注意，所移动的只是指针，这并不需要修复引用计数器，所以非常快(基本上只是一个memmov调用)。移动所需的时间非常短，除非列表很大。

因此，从Python中删除元素，如果使用del L[index]知道索引，则形式上是O(N)，但具有一个很小的常数因子。

实现list对象是可能的，这样就可以通过向list对象添加一个“位相”值来从两端获得固定的时间删除。这将保持access O(1) (具有稍大一点的常数)，但也允许del L[0]成为O(1)，使其类似于deque。

但是，这是考虑到的，而不是实现的，因为它将使正常情况下的list访问更加复杂，并对具有特定结构deque的特殊情况进行优化。它还会破坏与任何C扩展模块访问列表的兼容性。

Answer 2

是否可以通过指定索引或值来删除O(1)复杂性中的元素？

如果你知道索引是什么，那么

del L[index]

工作速度非常快(但令人惊讶的是，O(1) - https://www.python.org/dev/peps/pep-3128/#motivation)不起作用。如果你只知道它的价值，那么它可能在任何地方，所以你必须搜索它。平均来说，它需要检查一半的元素，所以这是O(N)。

其他数据结构可能会有所帮助。如果您只想知道不同的元素是什么(而不关心顺序)，可以使用set。

s = set(['1','b', '1', 'a', 1])
s
s.remove(1)
s

产量输出

{1, '1', 'a', 'b'}
{'1', 'a', 'b'}

删除命令是(基本上) O(1)