[EMAIL PROTECTED] (Alex Martelli) writes: > > turn indicates that both implementations actually work about same and > > your "O(n squared)" argument is irrelevant. > > It's indeed irrelevant when the behavior _isn't_ quadratic (as in the > case of intersections) -- but unfortunately it _is_ needlessly quadratic > in most interesting cases involving containers (catenation of sequences, > union of sets, merging of dictionaries, merging of priority-queues, > ...), because in those cases the intermediate temporary values tend to > grow, as I tried to explain in more detail above.
Mostly directed to samwyse: Alex is correct here and I'd add that Python and its libraries are written for an imperative, mutating approach though there are some situations in which you can write in functional style without a big efficiency hit. In particular, the quadratic behavior Alex points out is because of Python's hash-based implementation of sets, so you can't make a new set that adds or removes one element from the old set, without copying all the elements around. A more purist functional approach would probably implement sets with some other data structure such as AVL trees, so you can make a new one that adds or deletes some node in O(log n) time (it would share almost all of its structure with the old one). So instead of O(n) for the hash-based mutating implementation or O(n**2) for the hash/copying based functional implementation, you get O(n log n) for the functional tree implementation. Haskell's Data.Map module does something like this. There's a book "Purely Functional Data Structures" by Chris Okasaki that shows how to implement dicts, priority queues, and fancier objects in functional style based on similar principles. If you want to try out functional programming in a lightweight language (much easier to grok than Haskell) you might look at Hedgehog Lisp: http://hedgehog.oliotalo.fi/ It includes a functional dictionary implementation based on AVL trees but with a Python dictionary-like API. -- http://mail.python.org/mailman/listinfo/python-list
