On Mon, Jul 6, 2015 at 3:30 PM, Neil Girdhar firstname.lastname@example.org wrote: SortedDict (http://www.grantjenks.com/docs/sortedcontainers/sorteddict.html) manages to support indexing. Can OrderedDict do the same thing?
On Mon, Jul 6, 2015 at 5:59 PM, Eric Snow email@example.com wrote:
Don't forget that, as the docs describe, an "OrderedDict is a dict that remembers the order that keys were first inserted". While obviously there's an implicit sequence for that order, the focus is still on dict-ness with the sequence exposed through the normal mapping approach (iteration). If you want to get sequence semantics then first unpack the order into a sequence type like list or tuple. Or use some other type than OrderedDict.
On Mon, Jul 6, 2015 at 3:04 PM, Neil Girdhar firstname.lastname@example.org wrote: You can do indexing, insertion, and removal all in logarithmic time (which is basically constant) by using a B-tree as the underlying data structure. (See e.g. the blist package.)
If you want a
set that is indexable, it's quite
the sortedcontainers module. Just use the hash function as the key:
from sortedcontainers import SortedDict, SortedSet class DictWithIndex(SortedDict): def __init__(self, *args, **kwargs): super(DictWithIndex, self).__init__(hash, *args, **kwargs) class SetWithIndex(SortedSet): def __init__(self, *args, **kwargs): super(SetWithIndex, self).__init__(*args, key=hash, **kwargs)
The ordering can be quasi-random but the indexing can still be useful. Example usage:
In : d = DictWithIndex(enumerate('abcde')) In : d.iloc Out: 4 In : d.iloc[-2] Out: 3 In : s = SetWithIndex('abcde') In : s Out: 'e' In : s[-2] Out: 'd'
The likelihood that the hash collides is low and when it does so, the order will be based on insertion order.