Ordering python sets

[Carl Banks]

On Oct 25, 4:58 am, Lie Ryan <lie.1... at gmail.com> wrote:
> On Wed, 22 Oct 2008 10:43:35 -0700, bearophileHUGS wrote:
> > Mr.SpOOn:
> >> Is there another convenient structure or shall I use lists and define
> >> the operations I need?
>
> > <musings>
> > As Python becomes accepted for more and more "serious" projects some
> > more data structures can eventually be added to the collections module:
> > - SortedSet, SortedDict: can be based on red-black trees. Require items
> > to be sortable (them being hashable isn't required, but it's probably
> > more safe that they are immutable). - Odict: a dict ordered according to
> > insertion order. - Bidict: a unordered dict that allows O(1) retrieval
> > on both keys and values (that are both unique).
> > - Graph: a directed unsorted data structure like mine may be acceptable
> > too.
> > - Bitset: dynamically re-sizable and efficient in space and time, easy
> > to implement in C.
> > - Chain: simulates a double linked list, but its implementation can be
> > similar to the current Deque but allowing not completely filled blocks
> > in the middle too. (I haven't named it just List because there's a name
> > clash with the list()).
> > - I use all those data structures in Python programs, plus some more,
> > like interval map, trie (and a dawg), persistent dict and persistent
> > list, kd-tree, BK-tree, Fibonacci Heap, a rank & select, a disjoint-
> > set, and maybe more. But those are uncommon enough to be left out of a
> > standard library.
> > - A problem with the Chain data structure is how to represent iterators
> > in Python. I think this is a big problem, that I don't know how to solve
> > yet. A possible solution is to make them owned by the Chain itself, but
> > this makes the code slow down linearly in accord to the number of the
> > iterators. If someone has a solution I'm all ears. </musings>
>
> > Bye,
> > bearophile
>
> <anotherrandommusing>
> Since python is dynamic language, I think it should be possible to do
> something like this:
>
> a = list([1, 2, 3, 4, 5], implementation = 'linkedlist')
> b = dict({'a': 'A'}, implementation = 'binarytree')
> c = dict({'a': 'A'}, implementation = 'binarytree')

-1

This doesn't buy you anything over simply implementing different types
altogether.

a = collections.linkedlist([1,2,3,4,5])
b = collections.btree({'a': 'A'})

In fact, it adds a whole lot of complexity to the built-in types.


Carl Banks