On Wed, Jul 12, 2017 at 7:52 PM, Paul Rubin <no.email@nospam.invalid> wrote: > Not so easily in Python since the built-in list and dict types are > designed for mutation update. In Haskell, the list type is a linked > list and the dictionary type is a balanced tree. So, you can make a new > list consisting of a new item consed to the front of the old list, and > you can make a new ("updated") dictionary by building O(log n) new > nodes.
Is that actual O(log n), or amortized? If you build a tree by forever inserting larger values (which can happen easily - imagine using a dict to record hourly statistics, using time.time()//3600 as the key), at some point it'll need to be rebalanced, which could at worst case be O(n). But I could believe that it's amortized logarithmic, although I can't myself prove that it is. ChrisA -- https://mail.python.org/mailman/listinfo/python-list