Geek asks and answers

Use the iterator protocol to access a sorted dictionary

I have a dictionary of "vcomments" where the keys are integer integers. When navigating through the keys, I need to do this sorted or sorted in order. I am currently using

for key_pt in sorted(self.view.vcomments.iterkeys()):

but I also need to find these keys (or the following key) that are outside or up to a certain number:

    if direction == 'down':
        sorted_pts = (key_pt for key_pt in sorted(self.view.vcomments.iterkeys()) if key_pt > curr_pt)
    else:
        sorted_pts = (key_pt for key_pt in reversed(sorted(self.view.vcomments.iterkeys())) if key_pt < curr_pt)
    try:
        next_pt = sorted_pts.next()
    except StopIteration:

  • Is it possible to create an iterator class (using the iterator protocol) that will store the dictionary and let me scroll them forward or backward? I suppose / suggest that I may need to first assign an attribute value that will indicate if the next loop should be redirect / reverse.

  • Is it possible to include a generator function (nested) in my iterator class, which will allow me to get the next key; i.e. outside or in front of the provided integer?

  • Similarly, will I be able to send start and end points and retrieve all the keys that are between these values ​​(in sorted order)?

I apologize for asking three (albeit related) questions - the answer to the first would give me a start. And I'm not rude enough to expect a complete solution, just an indication of whether these are possible goals for me.

Added: and I still would need to get one single dictionary element by its key.

+3
source share
4 answers

, - . - - , , .

  • . O (n).

  • , , O (log n). , , , , , - OrderedDict, .

  • , wikipedia , O (log n).

Python - , , .

, , . , . , . , O (n) O (n log n), ...

>>> class SortIterDict(dict):
...     def __iter__(self):
...         return iter(sorted(super(SortIterDict, self).__iter__()))
...     def __reversed__(self):
...         return reversed(tuple(iter(self)))
...     def get_next(self, n):
...         return next((x for x in iter(self) if x > n), None)
...     def get_prev(self, n):
...         return next((x for x in reversed(self) if x < n), None)
... 
>>> d = SortIterDict({'d':6, 'a':5, 'c':2})
>>> list(d)
['a', 'c', 'd']
>>> list(reversed(d))
['d', 'c', 'a']
>>> d.get_next('b')
'c'
>>> d.get_prev('b')
'a'
+4

, , . Python dicts , OrderedDict ( ). , blist.sorteddict , blist.sortedlist, , .

, ( ), ? /, , , /.

. reversed:

for key in mydict:
  # do something

for key in reversed(mydict.keys()):
  # do something

- () , ; ?

, itertools , - :

from itertools import dropwhile, takewhile
# find next key beyond 4
next(dropwhile(lambda x: x <= 4, mydict))
# find last key before 20
next(dropwhile(lambda x: x >= 20, reversed(mydict.keys()))

:

def first_beyond(pivot, seq):
  next(dropwhile(lambda x: x <= pivot, seq))

first_beyond(4, mydict)
first_beyond(20, reversed(mydict.keys()))

, , ( )?

:

from itertools import dropwhile, takewhile
def between(begin, end, seq):
  return takewhile(lambda x: x <= end, 
                   dropwhile(lambda x: x < begin, seq))

:

>>> list(between(4, 30, [1,2,4,8,16,32]))
[4, 8, 16]

: , . , :

keys = sorted(mydict)

# forward and backward iteration
for k in keys:
  # ...
for k in reversed(keys):
  # ...

# function that returns a forward or backward iterator based on an argument
def forward_or_backward(seq, forward=True):
  for x in (iter if forward else reversed)(seq):
    yield x

# random access inside a loop
for i, key in enumerate(keys):
  # next element
  key[i+1]

# the between and first_beyond functions above also work for lists

. , , , , .

+2

, , .

, dict, , int, (r ?) dict? , , , ( , - ), , .

, , , .

It would probably be worthwhile to implement a treap or red-black tree implementation and change it so that you can specify a key and return a key-value pair on the next or previous key. If you often insert or delete values, one of them might be better.

+1
source

It seems that orderdict is likely to give you what you want. The documentation is here .

0
source

More articles:


All Articles