Title: How efficient is Python's 'in' or 'not in' operators, for large lists?
Tags: python;iteration;complexity-theory
Question: I have a list of over 100000 values and I am iterating over these values and checking if each one is contained in another list of random values (of the same size).
I am doing this by using if item[x] in randomList.
How efficient is this? Does python do some sort of hashing for each container or is it internally doing a straight up search of the other container to find the element I am looking for?
Also, if it does this search linearly, then does it create a dictionary of the randomList and do the lookup with that?
Comment: I've always wanted to write `is in`. :/

Comment: There isn't an `is in` - I presume you mean `in` ?

Comment: @SylvainLeroux where is it implied they are methods?

Comment: I assume you mean `if item[x] in randomlist`, not `...in randomlist[x]`

Comment: those are _[operators](http://docs.python.org/2/library/operator.html#operator.contains)_, not _methods_

Here is the accepted answer: in is implemented by the __contains__ magic method of the object it applies to, so the efficiency is dependent upon that. For instance, set, dict and frozenset will be hash based lookups, while list will require a linear search. However, xrange (or range in Python 3.x) has a __contains__ method that doesn't require a linear search, but instead can use the start/stop/step information to determine a truthy value. (eg: 7 in xrange(4, 1000000) isn't done linearly).
Custom classes are free to implement __contains__ however they see fit but ideally should provide some information about how it does so in documentation if "not obvious".
Comment for this answer: @Smac89: range under Python 2 creates a list.
Comment for this answer: Aha good point, I was wondering about xrange also. So is that the same for range??
Comment for this answer: @Smac89 no - `range` actually generates a list in Python 2 - so it'd have to do a linear search. But in Python 3, then `range` is the same as `xrange` in Python 2.

Here is another answer: You can do this without using a set if the two lists are sorted, as follows:
def gen(P1, P2):
i, j = 0, 0
I, J = len(P1), len(P2)
while i != I and j != J:
if P1[i] == P2[j]:
yield P1[i]
i, j = i + 1, j + 1
else:
if P1[i] < P2[j]:
i += 1
else:
j += 1
This returns the intersection of P1 and P2:
&gt;&gt;&gt; P1 = [1, 2, 3, 5, 90]
&gt;&gt;&gt; P2 = [2, 3, 5, 30, 48]
&gt;&gt;&gt; list(gen(P1, P2))
[2, 3, 5]
The algorithm is described here.

Here is another answer: You will want to pre-convert your list to a set, where hashing can be used for O(1) lookup.
See http://wiki.python.org/moin/TimeComplexity
(Normally, you have to search every element in a 'classical' list to tell if something is in it (unless your data structure also keeps a set of all elements, but that would add a huge amount of time and space complexity, and the programmer can implement it themselves).)
Comment for this answer: If you want to change it to a set or not depends entirely on how large the list is and how many times you are going to do lookups. So there is no "you will want to". Except "if it's slow you'll want to do performance testing".
Comment for this answer: "multiple times" is not enough. Making a set() also takes time.
Comment for this answer: So does that mean it actually does the search linearly?
Comment for this answer: Ok this makes sense. I usually used 'in' and 'not in' with both lists and dicts/sets thinking they are the same time complexity, but now I know
Comment for this answer: @LennartRegebro: actually he will want to, since he mentioned he is performing this operation multiple times.
Comment for this answer: Yes, `list`s are searched linearly. That's why you want to change it to a `set`.

Here is another answer: ninjagecko already answered the specific case of lists (and tuples FWIW), the general answer is : "it depends on the 'container' implementation" (I quote 'container' cause it can as well be a generator). For builtin types, you want sets or dicts for a fast lookup. Else you'd better check the doc or implementation for your container.

{'source': 'StackExchangeDataset', 'subset': 'stackoverflow.com', 'metadata': {'AnswerCount': 4, 'CommentCount': 5, 'ContentLicense': 'CC BY-SA 4.0', 'CreationDate': '2013:00:06/20/13', 'FavoriteCount': None, 'PostTypeId': 1, 'Tags': '<python><iteration><complexity-theory>', 'Title': "How efficient is Python's 'in' or 'not in' operators, for large lists?", 'ViewCount': 3004, 'id': 17220296, 'user_AboutMe': '<h2>General Tips:</h2>\n<p>The act of asking a question when you are stuck has two advantages:</p>\n<ul>\n<li>The process of forming the question has a high chance of leading you to the answer, so you may end up never having to ask your question</li>\n<li>By converting a problem into a question, you no longer have a problem, instead you now have a question, and someone is bound to have an answer!</li>\n</ul>\n<h2>Software eng tip(s):</h2>\n<ul>\n<li>Time estimates are hard. A good rule of thumb is to add one more of the largest unit of your time estimate.\n<ul>\n<li>For example, if you estimate that a task will take 1.5 hours, add another hour. If you estimate 1 day, add another day, if you estimate, 2 weeks, add another week, etc, etc.</li>\n</ul>\n</li>\n<li>When assigned the task of implementing a new feature or improving an existing one, consult your nearest domain expert before consulting Google. A domain expert could be a co-worker with experience in that area, or whoever had worked on the feature you are trying to improve.\n<ul>\n<li>When a domain expert does not exist, then you and your team are in no position to undertake such a task. Forget Google at this point, you all need to have a serious meeting to determine a new solution for the task at hand.</li>\n</ul>\n</li>\n<li>As a new developer, practice the art of asking questions. If you go three days working on a ticket and never ask a question, you are in danger of making a costly mistake.</li>\n</ul>\n<h2>Random</h2>\n<ul>\n<li>Every local variable is a global variable with limited scope.</li>\n</ul>\n', 'user_AccountId': 2389551.0, 'user_DisplayName': 'smac89', 'user_Reputation': 35032.0, 'user_Views': 3024.0, 'user_id': 2089675.0}}