1

I have a little Problem in Python. I got a 2 dimensional dictionary. Lets call it dict[x,y] now. x and y are integers. I try to only select the key-pair-values, which match between 4 points. Function should look like this:

def search(topleft_x, topleft_y, bottomright_x, bottomright_y):    

For example: search(20, 40, 200000000, 300000000)  

Now are Dictionary-items should be returned that match to: 
                      20 < x < 20000000000
               AND    40 < y < 30000000000

Most of the key-pair-values in this huge matrix are not set (see picture - this is why i cant just iterate).

This function should return a shorted dictionary. In the example shown in the picture, it would be a new dictionary with the 3 green circled values. Is there any simple solution to realize this? I recently used 2-for-loops. In this example they would look like this:

def search():
    for x in range(20, 2000000000):
        for y in range(40, 3000000000):
            try:
                #Do something
            except:
                #Well item just doesnt exist

Of course this is highly inefficient. So my question is: How to Boost up this simple thing in Python? In C# i used Linq for stuff like this... What to use in python?

Thanks for help!

Example Picture

m4rcde
  • 95
  • 1
  • 6
  • Please can you give an example of the dict? I don't understand why you need to try every value with `for x in range(20, 2000000000):` – roganjosh Feb 22 '18 at 21:18
  • @roganjosh thanks for your answer. Because if i do so many loops, the program is much too slow! in a 2 dimensional dictionary, this would be like 6e+19 loops ^^ – m4rcde Feb 22 '18 at 21:30
  • I've just seen your complete response. It has nothing at all to do with what I asked. I'm well-aware of the issue, I asked you to provide an example input. See how to create a [Minimal, Complete and Verifiable example](https://stackoverflow.com/help/mcve) – roganjosh Feb 22 '18 at 21:46

1 Answers1

1

You dont go over random number ranges and ask 4million times for forgiveness - you use 2 number range to specify your "filters" and go only over existing keys in the dictionary that fall into those ranges:

# get fancy on filtering if you like, I used explicit conditions and continues for clearity
def search(d:dict,r1:range, r2:range)->dict:
    d2 = {}
    for x in d:              # only use existing keys in d - not 20k that might be in
        if x not in r1:                        # skip it - not in range r1
            continue
        d2[x] = {}
        for y in d[x]:       # only use existing keys in d[x] - not 20k that might be in
            if y not in r2:                    # skip it - not in range r2
                continue 
            d2[x][y] = "found: " + d[x][y][:]  # take it, its in both ranges
    return d2    


d = {}
d[20] = {99:  "20",999:  "200",9999:  "2000",99999:  "20000",}
d[9999] = { 70:"70",700:"700",7000:"7000",70000:"70000"}

print(search(d,range(10,30), range(40,9000)))

Output:

{20: {99: 'found: 20', 999: 'found: 200'}}

It might be useful to take a look at modules providing sparse matrices.

Patrick Artner
  • 50,409
  • 9
  • 43
  • 69