On Tue, Nov 18, 2008 at 3:46 PM, Luke Palmer <[EMAIL PROTECTED]> wrote: > On Tue, Nov 18, 2008 at 10:37 AM, David Menendez <[EMAIL PROTECTED]> wrote: >> This isn't really a fair comparison. Map, IntMap, and Trie are >> persistent data structures, and Python dictionaries are ephemeral. >> (That is, when you "add" a key to a Map, you actually create a new one >> that shares structure with the old one, and both can be used in >> subsequent code. In Python, you would have to copy the dictionary.) > > But when these persistent data structures are used in a > single-threaded way, why should we not hope for the performance to be > comparable? > > It may not be easy, but just saying "they are persistent" is not > really an excuse.
I guess that depends on what you mean by "comparable". Chris Okasaki demonstrated that, for some data structures, a persistent implementation could be made with the same asymptotic bounds as an ephemeral implementation, but I would still expect the persistent version to be worse by a constant factor when used ephemerally. Ephemeral data structures are naturally optimized for ephemeral use cases. (I would also expect the reverse to be true.) -- Dave Menendez <[EMAIL PROTECTED]> <http://www.eyrie.org/~zednenem/> _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe