Menu
Is the in operator's speed in python proportional to the length of the iterable?
So,
len(x) #10
if(a in x): #lets say this takes time A
pass
len(y) #10000
if(a in y): #lets say this takes time B
pass
Is A > B?
767
Is the in operator's speed in Python proportional to the length of the iterable? Yes. The time for in to run on a list of length n is O(n) . It should be noted that it is O(1) for x in set and x in dict as they are hashed, and in is constant time.
set is as fast as it gets. However, if you rewrite your code to create the set once, and not change it, you can use the frozenset built-in type. It's exactly the same except immutable. If you're still having speed problems, you need to speed your program up in other ways, such as by using PyPy instead of cPython.
In Python, the in operator determines whether a given value is a constituent element of a sequence such as a string, array, list, or tuple. When used in a condition, the statement returns a Boolean result of True or False. The statement returns True if the specified value is found within the sequence.
In a survey of the energy efficiency of 27 programming languages, C tops the list, and Python was the second most inefficient.
There's no general answer to this: it depends on the types of a and especially of b. If, for example, b is a list, then yes, in takes worst-case time O(len(b)). But if, for example, b is a dict or a set, then in takes expected-case time O(1) (i.e., constant time).
About "Is A > B?", you didn't define A or B. As above, there's no general answer to which of your in statements will run faster.
104
A summary for in:
list - Average: O(n)
set/dict - Average: O(1), Worst: O(n)
See this for more details.
21
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
