Removing an item from a list in python

Question

Is there a way to remove an item from a list in python in O (1) complex.ie, delete (value): this search is performed linearly through the list and removes the rights.? So, is there a way to remove an element in O (1) complexity by specifying an index or value?

When an input list of 100,000 is assigned to the following code, it exceeds the 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

Answer 1

Not formally.

, ++ Python std::vector ( C ). O (1) , .

, , - , ( , memmov). , , , .

, Python, del L[index], O(N), .

list, , "" . O(1) ( ), del L[0] O(1) a deque.

, , , list , deque. C.

Answer 2

O (1) , ?

, ,

del L[index]

(, , O (1) - https://www.python.org/dev/peps/pep-3128/#motivation). , , . , O (N).

. , ( ), .

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

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

remove ( ) O (1)

Answer 3

python (, jupyer) :

>>>: %%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 can see, deleting an element by index from deque has O (1) complexity, while deleting from a list by index is a little more expansive, but still pretty constant compared to other O (n) operations, such as maximizing This is consistent with @ 6502's answer. In any case, if you need to use an initializer with a oriented list, the differences are very insignificant, because the time-building procedure prevails over time. Initialization by calling the actual constructor is preferred.