On 25 October 2012 21:16, eryksun <eryk...@gmail.com> wrote: > On Thu, Oct 25, 2012 at 3:46 PM, Prasad, Ramit > <ramit.pra...@jpmorgan.com> wrote: >> >> Do you happen to know offhand if there is a difference between >> `in <list>` vs. `in <tuple>` vs. `in <set>`? > > The "in" comparison (__contains__ method) is equivalent for list and > tuple. It has to search through the sequence item by item, which makes > it an O(n) operation. On the other hand, a set/dict uses the hash() of > an object to map it to a known location in a table (performance > degrades if there are many collisions). On average, you can check if a > set/dict contains an item in constant time, i.e. O(1). The amortized > worst case is O(n).
Why do you say "*amortized* worst case"? Is there an occasional worse than O(n) operation that is insignificant when amortised? At first I assumed that was a slip of the tongue but you generally seem to know an incredible amount about the implementation of CPython, so now I'm curious. Oscar _______________________________________________ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: http://mail.python.org/mailman/listinfo/tutor
