代码之家 › 专栏 › 技术社区 › alvas

在字典中查找给定整数的值,该整数可以在字典的元组键之间找到

key-value tuples data-structures dictionary python

alvas · 技术社区 · 5 年前

给定一个 x 元组键和字符串值字典:

x = {(0, 4): 'foo', (4,9): 'bar', (9,10): 'sheep'}

任务是编写函数,找到给定特定数字的值,例如,如果用户输入3,它应该返回 'foo' 我们可以假设密钥中没有重叠的数字。

另一个例子是,如果用户输入9,它应该返回 'bar' .

我试着转换 x dict到一个列表中,并按如下方式编写函数,但如果键中的值范围非常大,则函数不是最优的:

from itertools import chain

mappings = None * max(chain(*x))

for k in x:
    for i in range(k[0], k[1]):
        mappings[i] = x[k] 

def myfunc(num):
    return mapping[num]

否则怎么可能 myfunc 功能写?
是否有更好的数据结构来保持 mapping ?

1 回复 | 直到 5 年前

Amit Vikram Singh 5 年前

您可以将密钥转换为 numpy 数组和使用 numpy.searchsorted 搜索查询。因为钥匙是 left open 我已将密钥的打开值增加了 1 在阵列中。

每个查询都是有序的 O(log(n)) .

创建数组:

A = np.array([[k1+1, k2] for k1, k2 in x])
>>> A
array([[ 1,  4],
       [ 5,  9],
       [10, 10]])

搜索查询功能:

def myfunc(num):
    ind1 = np.searchsorted(A[:, 0], num, 'right')
    ind2 = np.searchsorted(A[:, 1], num, 'left')
    if ind1 == 0 or ind2 == A.shape[0] or ind1 <= ind2: return None
    return vals[ind2]

打印:

>>> myfunc(3)
'foo'

Timur Shtatland 5 年前

遍历字典并与键进行比较:

x = {(0, 4): 'foo', (4, 9): 'bar', (9, 10): 'sheep'}

def find_tuple(dct, num):
    for tup, val in dct.items():
        if tup[0] <= num < tup[1]:
            return val
    return None

print(find_tuple(x, 3))
# foo
print(find_tuple(x, 9))
# sheep
print(find_tuple(x, 11))
# None

一个更好的数据结构是一个只有区间左边界(作为键)和相应值的字典。然后你可以使用 bisect 正如其他答案所提到的那样。

import bisect
import math

x = {
    -math.inf: None,
    0: 'foo',
    4: 'bar',
    9: 'sheep',
    10: None,
}

def find_tuple(dct, num):
    idx = bisect.bisect_right(list(dct.keys()), num)
    return list(dct.values())[idx-1]

print(find_tuple(x, 3))
# foo
print(find_tuple(x, 9))
# sheep
print(find_tuple(x, 11))
# None

Aelarion 5 年前

您可以简单地迭代键并比较值(而不是创建映射)。这比先创建映射更有效,因为你可以有一个类似的键 (0, 100000) 这将产生不必要的开销。

根据OP的评论编辑答案

x = {(0, 4): 'foo', (4,9): 'bar', (9,10): 'sheep'}

def find_value(k):
    for t1, t2 in x:
        if k > t1 and k <= t2:   # edited based on comments
            return x[(t1, t2)]
    
    # if we end up here, we can't find a match
    # do whatever appropriate, e.g. return None or raise exception
    return None

注: 在元组键中不清楚它们是否是输入数字的包含范围。例如,如果用户输入 4 ,如果他们得到 'foo' 或 'bar' ? 这将影响您在上述代码片段中描述的函数中的比较。 (见上面的编辑,这应该符合您的要求)。

~~在上述示例中,输入 4. 会回来的 'foo' ,因为它将满足存在的条件 k >= 0 and k <= 4 ,因此在继续循环之前返回。~~

编辑:措辞和拼写错误修复

Andrej Kesely 5 年前

这里有一个解决方案,使用 pandas.IntervalIndex 和 pandas.cut 请注意,我将最后一个键“调整”为(10,11),因为我正在使用 closed="left" 在我的IntervalIndex中。如果您希望间隔在不同侧(或两侧)关闭,可以更改此设置:

import pandas as pd

x = {(0, 4): "foo", (4, 9): "bar", (10, 11): "sheep"}

bins = pd.IntervalIndex.from_tuples(x, closed="left")
result = pd.cut([3], bins)[0]

print(x[(result.left, result.right)])

打印:

foo

其他解决方案使用 bisect 模块(假设范围是连续的,因此没有“间隙”):

from bisect import bisect_left

x = {(0, 4): "foo", (4, 9): "bar", (10, 10): "sheep"}

bins, values = [], []
for k in sorted(x):
    bins.append(k[1])  # intervals are closed "right", eg. (0, 4]
    values.append(x[k])

idx = bisect_left(bins, 4)
print(values[idx])

打印:

foo