Get the subdictionary based on range

Question

I have a dictionary which has coordinate pairs as a keys: i.e.:

d = {(15,21): "value1", (7,45): "value2", (500,321): "value3",...}

Now I need to return a sub dictionary of the elements where the keys are within a certain range: for example: the range of (6:16, 20:46) should return the following dictionary: d = {(15,21): "Value1", (7,45): value2} if there was no other element in that range. Is there any predefined dictionary function to do that? ..or do you have any other suggestions?

Thx

Answer 1

@Matej - If you are looking for nearest neighbor searching for large datasets, why don't you have a look at scipy.spatial.KDTree. Very quick kNN searching capabilities. You can easily turn an array into a KD-Tree and query it using the KDTree.query() or KDTree.query_ball_point() syntax.

Answer 2

it looks like you want range queries. for large and complex dicts, this might not be efficient.

you might want to have a look at this, you might have to modify some of your data though

http://packages.python.org/lupyne/examples.html

Answer 3

Here is one way to do it

d = {(15,21): "value1", (7,45): "value2", (500,321): "value3"}
x1, x2, y1, y2 = 6, 16, 20, 46 
dict((k,v) for k, v in d.iteritems() if x1<k[0]<x2 and y1<k[1]<y2)

Python 2.7 has added dictionary comprehensions. The last line becomes more readable:

{k: v for k, v in d.iteritems() if x1<k[0]<x2 and y1<k[1]<y2}

Answer 4

No, there is no predefined function to do that. You could probably use a list comprehension.

items = [ value for key, value in d.items() if key[0] in range(6,16) and key[1] in range(20, 46) ]

Answer 5

Python dictionaries are hash tables, which are not suitable for efficient range queries on large data sets. For efficient range queries, you need to store the data in some structure that keeps the keys sorted. If your data set is static (or at least changes infrequently), then a sorted list with binary search would work. Otherwise, you should really use a B-Tree or similar structure.

Answer 6

In Python 2.7 we have dictionary comprehensions which make this sort of thing easy to do and easy to read:

d = {(15,21): "value1", (7,45): "value2", (500,321): "value3",...}
d_in_range = {k: v for k, v in d if 6 < k[0] < 20 and 16 < k[1] < 46} # dictionary comprehension.