removing element from a list in python

Question

Is there any way of removing an element from a list in python in O(1) complexity.i.e., remove(value): this searches linearly through the list and removes right.? So, is there any way to delete an element in O(1) complexity by specifying index or value?

When input list of size 100000 is given to the following code,it is exceeding time limit..,even after using "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

Assuming you using CPython? If so, no, there is no such way for lists. Check TimeComplexity. — Marcin
– Marcin, Commented Jan 5, 2015 at 7:08
The formatting of your code has some problems. Please check it again. Make sure that if you copy and paste it does what you expect. — Joel
– Joel, Commented Jan 5, 2015 at 8:34
An issue to speed up. Everytime len(s) is calculated, it's an O(N) calculation. So each time it starts one of your while loops it recalculates len(s). You can replace while len(s)>0: with while s: The j<len(s) can be sped up by setting s_length = len(s) and then do while j<s_length. If we know the goal of your code and the indenting is clean, I think we'll be able to give more suggestions. — Joel
– Joel, Commented Jan 5, 2015 at 8:40
And your final for loop: for i in tree: i_length = len(i) and then replace all the len(i) with i_length. So I think the most obvious problem with your code is that you repeatedly calculate len(list) for some list. That's very slow. — Joel
– Joel, Commented Jan 5, 2015 at 8:42

6502 · Accepted Answer · 2015-01-05 07:22:23Z

Formally not.

If you know C++ Python lists are implemented more or less as std::vectors of of pointers to objects (in C parlance they are pointers to a contiguous array of pointers). This gives O(1) access to element given the index and allows resizing, however deleting an element from the list requires shifting all subsequent elements down by one element to fill the gap.

Note however that what are moved are just pointers and this is done without needing to fix reference counters and so it's extremely fast (basically just a single memmov call). The time required for the shifting is extremely small unless the list is huge.

So deleting an element from a list in Python if the index is known using del L[index] is formally O(N) but with a tiny constant factor.

It would be possible to implement list objects so that you can get constant time removal from either end by adding a "phase" value to the list object. This would keep access O(1) (with a slightly larger constant) but also allowing del L[0] to be O(1) making it similar to a deque.

This however was considered and not implemented because it would make list access more complex for a normal case and optimize for a special case for which you have a specific structure deque. It would also break compatibility with any C extension module accessing lists.

Joel · Accepted Answer · 2015-01-05 07:15:19Z

2

Is there any way to delete an element in O(1) complexity by specifying index or value?

If you know what the index is, then

del L[index]

works very quickly (but, surprisingly not O(1) -- https://www.python.org/dev/peps/pep-3128/#motivation). If you just know the value, well it could be anywhere, so you'll have to search for it. On average it'll have to check half the elements, so this is O(N).

Other data structures can help. If you only want to know what the distinct elements are (and don't care about the order), you can use a set.

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

yields output

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

and the remove command is (basically) O(1)

answered Jan 5, 2015 at 7:15

Joel

24k9 gold badges79 silver badges104 bronze badges

Comments

fortea · Accepted Answer · 2018-02-09 09:29:25Z

Open a python terminal (e.g. jupyer) and try this:

>>>: %%timeit
...: l = [i for i in range(10000000)]
...: del l[0] # O(?)
322 ms ± 1.68 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

>>>: %%timeit
...: l = list(range(10000000))
...: del l[0] # O(?)
195 ms ± 1.42 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

>>>: %%timeit
...: l = [i for i in range(10000000)]
...: del l[-1] # O(?)
306 ms ± 2.64 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

>>>>: %%timeit
...: l = list(range(10000000))
...: del l[-1] # O(?)
267 ms ± 2.68 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

>>>: %%timeit
...: l = [i for i in range(10000000)]
...: l.append(500) # O(1)
299 ms ± 3.28 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

%%timeit
...: l = list(range(10000000))
...: l.append(500) # O(1)
265 ms ± 1.87 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

>>>: %%timeit
...: l = [i for i in range(10000000)]
...: max(l) # O(n)
463 ms ± 15.5 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

>>>: %%timeit
...: l = list(range(10000000))
...: max(l) # O(n)
335 ms ± 10.7 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

>>>: from collections import deque # lets compare with deque

>>>: %%timeit
...: l = deque(range(10000000))
...: max(l) # O(n)
365 ms ± 1.83 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

>>>: %%timeit
...: l = deque(range(10000000))
...: l.append(500) #O(1)
283 ms ± 5.19 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

>>>: %%timeit
...: l = deque(range(10000000))
...: del l[0]
279 ms ± 2.78 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

>>>: %%timeit
...: l = deque(range(10000000))
...: del l[9999999]
286 ms ± 3.87 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

As you see, removing an item by index from a deque has a complexity of O(1), while removing from a list by index is sligthly more expansive but still quite constant compared to other O(n) operations like maximum computation. This is coherent with @6502 answer. Anyway, if you need to use the directed list initializer, differences are very very little because the time is dominated by the costruction procedure. The directed initialization through the call to the actual constructor is preferable.

Collectives™ on Stack Overflow

removing element from a list in python

3 Answers 3

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related