Start a dictionary for loop at a specific key value

Question

Here is the code:

EDIT**** Please no more "it's not possible with unordered dictionary replies". I pretty much already know that. I made this post on the off-chance that it MIGHT be possible or someone has a workable idea.

#position equals some set of two dimensional coords
for name in self.regions["regions"]:  # I want to start the iteration with 'last_region'
    # I don't want to run these next two lines over every dictionary key each time since the likelihood is that the new
    # position is still within the last region that was matched.
    rect = (self.regions["regions"][name]["pos1"], self.regions["regions"][name]["pos2"])
    if all(self.point_inside(rect, position)):
        # record the name of this region in variable- 'last_region' so I can start with it on the next search...
        # other code I want to run when I get a match
        return
return # if code gets here, the points were not inside any of the named regions

Hopefully the comments in the code explain my situation well enough. Lets say I was last inside region "delta" (i.e., the key name is delta, the value will be sets of coordinates defining it's boundaries) and I have 500 more regions. The first time I find myself in region delta, the code may not have discovered this until, let's say (hypothetically), the 389th iteration... so it made 388 all(self.point_inside(rect, position)) calculations before it found that out. Since I will probably still be in delta the next time it runs (but I must verify that each time the code runs), it would be helpful if the key "delta" was the first one that got checked by the for loop.

This particular code can be running many times a second for many different users.. so speed is critical. The design is such that very often, the user will not be in a region and all 500 records may need to be cycled through and will exit the loop with no matches, but I would like to speed the overall program up by speeding it up for those that are presently in one of the regions.

I don't want an additional overhead of sorting the dictionary in any particular order, etc.. I just want it to start looking with the last one that it successfully matched all(self.point_inside(rect, position))

Maybe this will help a bit more.. The following is the dictionary I am using (only the first record shown) so you can see the structure I coded to above... and yes, despite the name "rect" in the code, it actually checks for the point in a cubical region.

{"regions": {"shop": {"flgs": {"breakprot": true, "placeprot": true}, "dim": 0, "placeplayers": {"4f953255-6775-4dc6-a612-fb4230588eff": "SurestTexas00"}, "breakplayers": {"4f953255-6775-4dc6-a612-fb4230588eff": "SurestTexas00"}, "protected": true, "banplayers": {}, "pos1": [5120025, 60, 5120208], "pos2": [5120062, 73, 5120257], "ownerUuid": "4f953255-6775-4dc6-a612-fb4230588eff", "accessplayers": {"4f953255-6775-4dc6-a612-fb4230588eff": "SurestTexas00"}}, more, more, more...}

Answer 1

You may try to implement some caching mechanism within a custom subclass of dict.

You could set a self._cache = None in __init__, add a method like set_cache(self, key) to set the cache and finally overriding __iter__ to yield self._cache before calling the default __iter__.

However, that can be kinda cumbersome, if you consider this stackoverflow answer and also this one.

For what it's written in your question, I would try, instead, to implement this caching logic in your code.

def _match_region(self, name, position):
    rect = (self.regions["regions"][name]["pos1"], self.regions["regions"][name]["pos2"])
    return all(self.point_inside(rect, position))


if self.last_region and self._match_region(self.last_region, position):
    self.code_to_run_when_match(position)
    return

for name in self.regions["regions"]:
    if self._match_region(name, position):
        self.last_region = name
        self.code_to_run_when_match(position)
        return
return # if code gets here, the points were not inside any of the named regions

Answer 2

That is right, dictionary is an unordered type. Therefore OrderedDict won't help you much for what you want to do.

You could store the last region into your class. Then, on the next call, check if last region is still good before check the entire dictionary ?

Answer 3

Instead of a for-loop, you could use iterators directly. Here's an example function that does something similar to what you want, using iterators:

def iterate(what, iterator):
    iterator = iterator or what.iteritems()
    try:
        while True:
            k,v = iterator.next()
            print "Trying k = ", k
            if v > 100:
                return iterator
    except StopIteration:
        return None

Instead of storing the name of the region in last_region, you would store the result of this function, which is like a "pointer" to where you left off. Then, you can use the function like this (shown as if run in the Python interactive interpreter, including the output):

>>> x = {'a':12, 'b': 42, 'c':182, 'd': 9, 'e':12}
>>> last_region = None
>>> last_region = iterate(x, last_region)
Trying k = a
Trying k = c
>>> last_region = iterate(x, last_region)
Trying k = b
Trying k = e
Trying k = d

Thus, you can easily resume from where you left off, but there's one additional caveat to be aware of:

>>> last_region = iterate(x, last_region)
Trying k =  a
Trying k =  c
>>> x['z'] = 45
>>> last_region = iterate(x, last_region)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 5, in iterate
RuntimeError: dictionary changed size during iteration

As you can see, it'll raise an error if you ever add a new key. So, if you use this method, you'll need to be sure to set last_region = None any time you add a new region to the dictionary.

Answer 4

TigerhawkT3 is right. Dicts are unordered in a sense that there is no guaranteed order or keys in the given dictionary. You can even have different order of keys if you iterate over same dictionary. If you want order you need to use either OrderedDict or just plain list. You can convert your dict to list and sort it the way it represents the order you need.

Answer 5

Without knowing what your objects are and whether self in the example is a user instance or an environment instance it is hard to come up with a solution. But if self in the example is the environment, its Class could have a class attribute that is a dictionary of all current users and their last known position, if the user instance is hashable.

Something like this

class Thing(object):
    __user_regions = {}
    def where_ami(self, user):
        try:
            region = self.__user_regions[user]
            print 'AHA!! I know where you are!!'
        except KeyError:
            # find region
            print 'Hmmmm. let me think about that'
            region = 'foo'
            self.__user_regions[user] = region

class User(object):
    def __init__(self, position):
        self.pos = position

thing = Thing()
thing2 = Thing()
u = User((1,2))
v = User((3,4))

Now you can try to retrieve the user's region from the class attribute. If there is more than one Thing they would share that class attribute.

>>> 
>>> thing._Thing__user_regions
{}
>>> thing2._Thing__user_regions
{}
>>> 
>>> thing.where_ami(u)
Hmmmm. let me think about that
>>> 
>>> thing._Thing__user_regions
{<__main__.User object at 0x0433E2B0>: 'foo'}
>>> thing2._Thing__user_regions
{<__main__.User object at 0x0433E2B0>: 'foo'}
>>> 
>>> thing2.where_ami(v)
Hmmmm. let me think about that
>>> 
>>> thing._Thing__user_regions
{<__main__.User object at 0x0433EA90>: 'foo', <__main__.User object at 0x0433E2B0>: 'foo'}
>>> thing2._Thing__user_regions
{<__main__.User object at 0x0433EA90>: 'foo', <__main__.User object at 0x0433E2B0>: 'foo'}
>>> 
>>> thing.where_ami(u)
AHA!! I know where you are!!
>>> 

Answer 6

You say that you "don't want an additional overhead of sorting the dictionary in any particular order". What overhead? Presumably OrderedDict uses some additional data structure internally to keep track of the order of keys. But unless you know that this is costing you too much memory, then OrderedDict is your solution. That means profiling your code and making sure that an OrderedDict is the source of your bottleneck.

If you want the cleanest code, just use an OrderedDict. It has a move_to_back method which takes a key and puts it either in the front of the dictionary, or at the end. For example:

from collections import OrderedDict

animals = OrderedDict([('cat', 1), ('dog', 2), ('turtle', 3), ('lizard', 4)])

def check_if_turtle(animals):
    for animal in animals:
        print('Checking %s...' % animal)
        if animal == 'turtle':
            animals.move_to_end('turtle', last=False)
            return True
    else:
        return False

Our check_if_turtle function looks through an OrderedDict for a turtle key. If it doesn't find it, it returns False. If it does find it, it returns True, but not after moving the turtle key to the beginning of the OrderedDict.

Let's try it. On the first run:

>>> check_if_turtle(animals)
Checking cat...
Checking dog...
Checking turtle...
True

we see that it checked all of the keys up to turtle. Now, if we run it again:

>>> check_if_turtle(animals)
Checking turtle...
True

we see that it checked the turtle key first.