Блог

У меня есть два набора данных, которые находятся в формате словаря:

 ch1 = {1000: 128, 
       2830: 1022, 
       3438: 198, 
       5908: 109} 

ch2 = {1295:  1203, 
       2836: 1238, 
       4901: 8367, 
       7608: 249} 
 

В настоящее время у меня есть код для поиска совпадений между ключами в одном словаре и ключами в другом:

 coin = [int(ch1[key]) int(ch2[key]) for key in ch1.keys() amp; ch2.keys()]
 

Я хочу изменить этот код, чтобы он находил ключи, которые находятся в заданном диапазоне друг от друга. Например, если в диапазоне 10, выходной список из примеров словарей будет [2260] равен сумме 1022 1238, путем сопоставления ключей 2830 из dic1 и 2836 из dic2.

Одним из ограничений является то, что файлы данных большие (~500 МБ), что ограничивает решения, о которых я думал, повторяя данные списка.

В том редком случае, когда в одном словаре есть два ключа, которые находятся в диапазоне ключа в другом словаре, это должно дать одно совпадение.

 ch1 = {1000: 128, 
       2830: 1022, 
       3438: 198, 
       5908: 109} 

ch2 = {1295:  1203, 
       2836: 1238, 
       2839: 8367, 
       7608: 249} 
 

Все равно должен уступить [5825] , раунд((1238 8367)/2 1022).

В еще более редком случае, когда есть две пары, не имеет значения, какая из них сопоставлена вместе. В этом случае должно быть только два выхода. Напр.:

 ch1 = {1000: 128, 
       2837: 1022, 
       2838: 198, 
       5908: 109} 

ch2 = {1295:  1203, 
       2836: 1238, 
       2839: 8367, 
       7608: 249} 
 

Результат = [2260, 8565] , который исходит из 1022 1238, 198 8367

Я предлагаю простой ответ, который выполняется за 9 секунд для двух словарей объемом 15 МБ каждый (всего 31 МБ), поэтому его можно использовать в качестве основы для сравнения. Какова желаемая скорость?

Я не суммирую результаты, а нахожу все подходящие пары, так как, по-моему, не совсем понимаю, как их следует суммировать. Я считаю, что, уже имея комбинации, может быть довольно легко применять свои собственные правила.

Создайте два словаря

 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")
 

Функция

 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
 

Мне нравится решение, опубликованное конрадом-h, но я решил написать свое, которое несколько проще, и, похоже, в нем меньше циклов. Однако он больше полагается на функции numpy, поэтому я не уверен, какая из них более эффективна, и у моей есть недостаток — она не будет работать в 3-м случае.

Я представлю решение и объясню, почему я считаю, что 3-й случай трудно решить, независимо от подхода.

Итак, мой подход таков:

1.) Создайте массив ключей numpy. Я называю эти массивы c1_keys и c2_keys , для словарей ch1 и ch2 соответственно.

2.) Для каждого key1 входа c1_keys я нахожу все ключи, ключи в ch2_keys которых есть -10 key1 .

3.) Создайте avg_ все key2 найденные (их соответствующие значения из ch2 ).

4.) К списку results добавьте сумму avg и значение из ch1 предоставленного key1 .

5.) Удалите найденные ключи 2 из массива numpy 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
 

Профи:

-Это решение будет работать все быстрее и быстрее по мере продвижения поиска, потому что мы удаляем ключи из 2-го словаря (то есть из np.массива)

-Это решит самый распространенный и редкий случай

Кон:

-Это не решит 3-е дело.

Объяснение:

Как также заявил @konrad-h, он не знал, как суммировать подходящие пары, потому что это несколько сбивает с толку. Вот почему в его решении больше петель. Предположим, что словари выглядят так:

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

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

Как нам с этим справиться? Для -10 допуска все клавиши 1-10 в ch1 будут совместимы со всеми клавишами 1-10 из ch2. Единственный способ, которым мы можем узнать, что существуют идеальные пары, — это выполнить полный поиск два раза. Во-первых, мы находим все подходящие пары (что и сделал Конрад-х.). Во-вторых, мы находим лучшие парные комбинации (что также непросто).

Вот почему я настоятельно рекомендую вам уменьшить допустимый допуск и суммировать первые подходящие пары, с которыми вы столкнетесь. Невозможно узнать, существуют ли две пары в ch1 и ch2 , не проходя через них дважды. Но вы можете легко выполнить случаи 1 и c2.