[Python-ideas] Proposal for extending the collections module - bags / multisets, ordered sets / unique lists

[Michael Lenzen]

Sorry, the previous post was in the wrong thread.

Yes, checking for inclusion (elem in bag) and removing an elem would be 
O(1) time as opposed to O(n).  I think the former is the real case for 
bags over lists.  As for real world applications it makes a huge 
difference in a program I am running, I am repeatedly searching a 
collection of almost 1 million elements for an item and it takes a long 
time using a list.  A list just iterates through all of the elements 
until it finds what it's looking for whereas a bag just hashes the element.

-Michael Lenzen

On 07/17/2009 09:36 PM, Carl Johnson wrote:
> Excuse my ignorance, but it's been a while since I've taken an
> algorithms class: Would a bag have any Big-O performance advantage
> over just using a list but ignoring the fact that it's in an order?
> Non-big O but otherwise practical speed advantages?
>
> As for the ordered set, there I can see the uses much more clearly,
> and the proposal to included it has come up on this list before. At
> the same time though, I think some of those uses can also be realized
> using the new collections.Counter class. Then again, if there's
> interest, why not?
>
> -- Carl Johnson
> _______________________________________________
> Python-ideas mailing list
> Python-ideas at python.org
> http://mail.python.org/mailman/listinfo/python-ideas