从python中的列表中删除元素

Question

是否有任何方法可以在O(1)complexity.ie中删除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++ Python列表或多或少被实现std::vector为指向对象的指针(在C语言中它们是指向连续指针数组的指针).这给了O(1)访问给定索引的元素并允许调整大小,但是从列表中删除元素需要将所有后续元素向下移动一个元素以填补间隙.

但请注意,移动的只是指针而且无需修复引用计数器就可以完成,因此它非常快(基本上只需一次memmov调用).除非清单很大,否则换班所需的时间非常短.

因此,如果已知使用索引,则从Python中的列表中删除元素del L[index]是正式O(N)但具有微小的常数因子.

可以实现list对象,以便通过向列表对象添加"阶段"值,从任一端获取恒定时间.这将继续访问O(1)(有稍大常数),而且还允许del L[0]将O(1)使其成为类似deque.

然而,这被考虑并未实现,因为它会使list正常情况下的访问变得更复杂,并针对您具有特定结构的特殊情况进行优化deque.它还会破坏与任何C扩展模块访问列表的兼容性.