4 ms·

I don't know about dicts, but as far as I can tell, tuples give you all the generality, utility, and performance of lists.

swannodette 15y ago
Performance? Unless I'm mistaken you can't update tuples efficiently.
- nknight 15y ago
  How do you intend to "update" an immutable list? Isn't it... immutable?
  - snprbob86 15y ago
    As a pure function where the returned value utilizes structural sharing with the input values.
  - swannodette 15y ago
    http://en.wikipedia.org/wiki/Persistent_data_structure http://en.wikipedia.org/wiki/Persistent_data_structure
  - lihaoyi 15y ago
    Immutable lists can be preppended/popped in O(1)time, without affecting previous versions. Immutable dicts can have stuff added and removed in O(log n) time, without affecting previous versions. Scala's immutable vectors can have appending/prepending/concatenation/splitting/insertion/deletion in O(log n) time, without affecting previous versions. it's log base 32, so for any arrays using integer indexes, it'll never go above ~7, so it's basically constant. Basically, you get (almost) the performance of mutable data structures, except you don't mess up the old versions of the thing every time you change something. It's really pretty incredible, the performance characteristics people manage to get with structural sharing: http://www.scala-lang.org/docu/files/collections-api/collections_40.html http://www.scala-lang.org/docu/files/collections-api/collect...
    - soc88 15y ago
      The Scala stuff is impressive. Updated docs at the new site: http://docs.scala-lang.org/overviews/collections/performance-characteristics.html http://docs.scala-lang.org/overviews/collections/performance... The new ConcurrentTrie is also a great addition to 2.10.
    - sureshv 15y ago
      There's still a lookup hit of log-b32n versus contiguous memory immutable vector with O(1). Locality can also an issue with tree-like structures but muted with the large branch factor. Of course the flip side scala gives you the kitchen sink for persistance.
pjscott 15y ago
A tuple, behind the scenes, is just a type tag, a refcount, a length, and an array of PyObject pointers. A list, instead of having a fixed array of PyObject pointers, has a pointer to a dynamically resizable array of them. Tuples and lists are both iterable, they both have O(1) indexing and fairly efficient internal representations, but the key difference is mutability. A tuple is supposed to be a composite data type; a list is a dynamic array that you store things in. Aside from mutability, though, tuples can do pretty much anything lists can, and usually a bit more efficiently.

swannodette 15y ago

Performance? Unless I'm mistaken you can't update tuples efficiently.

nknight 15y ago
How do you intend to "update" an immutable list? Isn't it... immutable?
- snprbob86 15y ago
  As a pure function where the returned value utilizes structural sharing with the input values.
- swannodette 15y ago
  http://en.wikipedia.org/wiki/Persistent_data_structure http://en.wikipedia.org/wiki/Persistent_data_structure
- lihaoyi 15y ago
  Immutable lists can be preppended/popped in O(1)time, without affecting previous versions. Immutable dicts can have stuff added and removed in O(log n) time, without affecting previous versions. Scala's immutable vectors can have appending/prepending/concatenation/splitting/insertion/deletion in O(log n) time, without affecting previous versions. it's log base 32, so for any arrays using integer indexes, it'll never go above ~7, so it's basically constant. Basically, you get (almost) the performance of mutable data structures, except you don't mess up the old versions of the thing every time you change something. It's really pretty incredible, the performance characteristics people manage to get with structural sharing: http://www.scala-lang.org/docu/files/collections-api/collections_40.html http://www.scala-lang.org/docu/files/collections-api/collect...
  - soc88 15y ago
    The Scala stuff is impressive. Updated docs at the new site: http://docs.scala-lang.org/overviews/collections/performance-characteristics.html http://docs.scala-lang.org/overviews/collections/performance... The new ConcurrentTrie is also a great addition to 2.10.
  - sureshv 15y ago
    There's still a lookup hit of log-b32n versus contiguous memory immutable vector with O(1). Locality can also an issue with tree-like structures but muted with the large branch factor. Of course the flip side scala gives you the kitchen sink for persistance.

pjscott 15y ago

A tuple, behind the scenes, is just a type tag, a refcount, a length, and an array of PyObject pointers. A list, instead of having a fixed array of PyObject pointers, has a pointer to a dynamically resizable array of them. Tuples and lists are both iterable, they both have O(1) indexing and fairly efficient internal representations, but the key difference is mutability. A tuple is supposed to be a composite data type; a list is a dynamic array that you store things in. Aside from mutability, though, tuples can do pretty much anything lists can, and usually a bit more efficiently.