Extract numbers within range python dictionary

I propose a simple answer that runs in 9seconds for two dictionaries that are 15MB each (31MB total), so it may be used as a baseline for comparison. Which is the desired speed?

I don't sum the results but find all eligible pairs, as I believe I don't quite understand how should they be summed. I believe already having the combinations it can be quite easy to apply your own rules.

Create two dictionaries

import sys
from numpy.random import default_rng

rng = rng = default_rng(12345)

MAX_KEY = 10000000
MAX_VALUE = 10000
M = 1000000

dictionaries = {'1': {}, '2':{}}

for i in range(M):
  for i in dictionaries:
    key = rng.integers(low=1, high=MAX_KEY)
    value = rng.integers(low=1, high=MAX_VALUE)
    dictionaries[i][key] = value
  
ch1 = dictionaries['1']
ch2 = dictionaries['2']

TOT_SIZE = 0
TOT_SIZE += sys.getsizeof(list(ch1))
TOT_SIZE += sys.getsizeof(list(ch2))
TOT_SIZE += sys.getsizeof([ch1[key] for key in ch1])
TOT_SIZE += sys.getsizeof([ch2[key] for key in ch2])

TOT_SIZE /= (1024**2)
print(f"TOT_SIZE = {TOT_SIZE} MB")

Function

def get_possiblePairs(TH = TH):
  
  possible_sums = {}
  list_keys = (list(ch1)+list(ch2))
  list_keys.sort()
  N = len(list_keys)

  possible_sums = {}
  coin_list = []
  for i in range(N):
    for j in range(i+1, N):
      key1 = list_keys[i]
      key2 = list_keys[j]
      if key2<key1+TH:
        if key1 in ch1 and key2 in ch2:
          coin = ch1[key1] + ch2[key2]
          possible_sums[(key1,key2)] = coin
      else:
        break
  for j in range(N):
    for i in range(i+1, N):
      key1 = list_keys[i]
      key2 = list_keys[j]
      if key1<key2+TH:
        if key1 in ch1 and key2 in ch2:
          coin = ch1[key1] + ch2[key2]
          possible_sums[(key1,key2)] = coin
          
      else:
        break

  return possible_sums

I like the solution posted by konrad-h, but I've decided to write mine which is somewhat simpler, and it appears to have less loops. However, it relies more on numpy functions, so I'm not sure which one is more efficient, and mine has a drawback - it won't work for the 3rd case.

I'll present the solution, and clarify why I think the 3rd case is difficult to solve regardless of the approach.

So, my approach is:

1.) Create numpy array of keys. I call these arrays c1_keys and c2_keys, for dictionaries ch1 and ch2 respectively.

2.) For every key1 in c1_keys, I find all keys keys in ch2_keys which are +-10 of key1.

3.) Create avg_ of all key2's found (their corresponding values from ch2).

4.) To list results append the sum of the avg and the value from ch1 provided by key1.

5.) Remove found key2's from numpy array ch2_keys.

def find_pairs(ch1, ch2):
    # dict keys to np array
    c1_keys = np.array(list(ch1.keys()))
    c2_keys = np.array(list(ch2.keys()))

    results = []
    # find pairs of keys
    for key1 in c1_keys:
        indices = np.logical_and(key1 - 10 <= c2_keys, c2_keys <= key1 + 10)
        sum_ = 0
        if np.any(indices):
            for index in c2_keys[indices]:
                sum_ += ch2[index]
            sum_ = sum_ / indices.sum()
            results.append(round(ch1[key1] + sum_))
            c2_keys = c2_keys[~indices]
    return results

Pro's:

-This solution will work faster and faster as the search progresses, because we're removing keys from the 2nd dictionary (that is, from the np.array)

-It will solve the most common and the rare case

Con's:

-Won't solve the 3rd case.

Explanation:

As @konrad-h has stated as well, he didn't know how to sum the eligible pairs, because it's somewhat confusing. This is why his solution has more loops. Suppose the dictionaries look like this:

ch1 = {
    1: 100,
    2: 200,
    3: 300,
    ...
}

ch2 = {
    1: 100,
    2: 200,
    3: 300,
    ...
}

How should we deal with this? For a +-10 tolerance, all keys 1-10 in ch1 will be compatible with all keys 1-10 from ch2. The only way that we can know that perfect pairs exist, is to do the complete search two times. First, we find all eligible pairs (which is what konrad-h) did. Second, we find the best pair combos (which also isn't simple).

This is why I highly suggest you reduce the accepted tolerance and sum the first eligible pairs you encounter. There is no way to know if two pairs in ch1 and ch2 exist, without passing through them twice. But you can easily do cases 1 and c2.