search

caesar0301 / treelib

An efficient implementation of tree data structure in python 2/3.
http://treelib.readthedocs.io/en/latest/
Other
801 stars 185 forks source link

Can it use SortedDict from the SortedCollection for children's order? #72

Open evandrocoan opened 7 years ago

evandrocoan commented 7 years ago

Can it use SortedDict from the SortedCollection for children's order?

Use SortedDict from the SortedCollection.

A SortedDict provides the same methods as a dict. Additionally, a SortedDict efficiently maintains its keys in sorted order. Consequently, the keys method will return the keys in sorted order, the popitem method will remove the item with the highest key, etc.

Related to:

  1. https://github.com/caesar0301/treelib/issues/65 - How to order by data?
caesar0301 commented 7 years ago

Issue #65 addressed a more general ordering of nodes by ANY attribute. SortedDict may replace the inner node dict, but it may introduce more performance concerns (see SO http://stackoverflow.com/questions/8176513/ordereddict-performance-compared-to-deque).

evandrocoan commented 7 years ago

I see that Ordered dict is implemented in Python (slower), while the current structure is written right on C (faster). So could we create a new type of node called OrderedNode, based on OrderedDict, and use these nodes instead of the current nodes, if it is wanted ordered nodes. If somehow the performance for this new Node type would be bad, an alternative could be looked into, improving the new node type OrderedNode.

ghost commented 6 years ago

Note that regular python dictionaries started preserving insertion order as an implementation detail in cpython 3.6, and from 3.7 it's now guaranteed by Guido's decree: 'Make it so. "Dict keeps insertion order" is the ruling.' https://mail.python.org/pipermail/python-dev/2017-December/151283.html