提取范围 python 字典中的数字

Question

我有两个字典格式的数据集：

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() & ch2.keys()]

我想更改此代码，以便它可以找到彼此之间给定范围内的键。例如，如果在 10 的范围内，示例字典的输出列表将是 [2260] 作为 1022+1238 的总和，通过匹配来自 dic1 的键 2830 和来自 dic2 的键 2836。

一个限制是数据文件很大 (~500Mb)，这限制了我认为遍历列表数据的解决方案。

在极少数情况下，一个字典中有两个键在另一个字典中的键的范围内，这应该给出一个匹配项。

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

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

应该仍然产生 [5825], round((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

Answer 1

我提出了一个简单的答案，它可以在 9 秒内运行两个字典，每个字典 15MB（总共 31MB），所以它可以用作比较的基线。期望的速度是多少？

我不对结果求和，而是找到所有符合条件的对，因为我相信我不太明白应该如何对它们求和。我相信已经有了组合，可以很容易地应用您自己的规则。

创建两个词典

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

Answer 2

我喜欢 konrad-h 发布的解决方案，但我决定编写我的解决方案，它稍微简单一些，而且循环似乎更少。但是，它更多地依赖于 numpy 函数，所以我不确定哪个更有效，而且我的有一个缺点 - 它不适用于第三种情况。

我将介绍解决方案，并阐明为什么我认为第 3 种情况无论采用何种方法都难以解决。

所以，我的做法是：

1.) 创建 numpy 键数组。我将这些数组分别称为 c1_keys 和 c2_keys，用于字典 ch1 和 ch2。

2.) 对于 c1_keys 中的每个 key1，我发现 ch2_keys 中的 all keys keys 是 +-10共 key1.

3.) 创建所有找到的 key2 的 avg_（它们对应的值来自 ch2）。

4.) 要列出 results，请附加 avg 的总和以及 key1 提供的 ch1 中的值。

5.) 从 numpy 数组 ch2_keys.

中删除找到的 key2

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

专业版：

-随着搜索的进行，此解决方案的工作速度会越来越快，因为我们正在从第二个字典（即 np.array）中删除键

-它将解决最常见和最罕见的情况

缺点：

-不会解决第 3 种情况。

解释：

正如@konrad-h 所说，他不知道如何对符合条件的对求和，因为这有点令人困惑。这就是为什么他的解决方案有更多的循环。假设字典看起来像这样：

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

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

我们该如何处理？对于 +-10 容差，ch1 中的所有键 1-10 将与 ch2 中的所有键 1-10 兼容。我们知道完美对存在的唯一方法是进行两次完整搜索。首先，我们找到所有符合条件的对（这是 konrad-h 所做的）。其次，我们找到最好的配对组合（这也不简单）。

这就是为什么我强烈建议您降低可接受的公差并对您遇到的第一个符合条件的对求和。不通过两次就无法知道 ch1 和 ch2 中的两对是否存在。但是您可以轻松地完成案例 1 和案例 c2。

提取范围 python 字典中的数字

Extract numbers within range python dictionary

python

dictionary

matching

bigdata