[Tutor] For - if - else loop; print selective output

[Steven D'Aprano]

On 26/10/12 07:16, eryksun wrote:
> On Thu, Oct 25, 2012 at 3:46 PM, Prasad, Ramit
> <ramit.prasad at 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).

To be precise: dict lookup, deletion and insertion are amortized O(1)
(on average, constant time) assuming there are no hash collisions.

When there are collisions, they are O(k) where k is the number of
colliding items. So in the worst case where k=n (the number of items
in the dict), dicts perform a little worse than lists, but in the
typical case, they are usually much, much faster.

"Amortized" strictly only refers to deletion and insertion. Since
lookups don't modify the dict, a lookup always takes the same time.
But deletions and insertions will occasionally trigger a resize of
the dict, which obviously takes a lot longer than the non-resizing
cases. But if you spread the average cost of the resize over many
insertions or deletions, you get amortized O(1) time.



-- 
Steven