从字典中提取值。键上的范围匹配

Question

我创建了一本词典myDict，它拥有以下形式的1000万个条目。字典中的每个条目表示{(id, age): code}

>>> myDict = {('1039', '68.0864'): '42731,42781,V4501', 
       ('1039', '68.1704'): '4770,4778,V071', 
       ('0845', '60.4476'): '2724,27800,4019', 
       ('0983', '63.3936'): '41401,4168,4240,V1582,V7281' 
      } 

恒定ageOffset与值定义= 0.1

给定一个(id,age)元组，如何可以取的所有值从myDict具有键(id, X)其中：

age <= X <= age+ageOffset 

我需要执行这个获取操作200亿次。

Examples: 
1. 
myTup = ('1039', '68.0') 
the answer is: '42731,42781,V4501' 

2. 
myTup = ('0845', '60.0') 
Ans : No value returned 

编辑： 我可以创建一个子字典，部分匹配的关键的第一个元素的基础上。我的意思是，如果元组键的第一个元素匹配，则创建一个子字典。根据我的数据，这不会超过几百。然后执行线性范围搜索，比较元组键中的第二个元素并查找相应的值。

Answer 1

要做这个操作200亿（！）次，你将不得不预先处理你的数据。

首先，我会通过ID组：

def preprocess(data): 
    from collections import defaultdict # Python 2.5+ only 
    preprocessed = defaultdict(list) 
    # group by id 
    for (id, age), value in data.iteritems(): 
     preprocessed[id].append((float(age), value)) 
    # sort lists for binary search, see edit 
    for key, value in preprocessed.iteritems(): 
     value.sort() 
    return preprocessed 

结果应该是这样的：

>>> preprocess(myDict) 
defaultdict(<type 'list'>, { 
    '0845': [(60.4476, '2724,27800,4019')], 
    '0983': [(63.3936, '41401,4168,4240,V1582,V7281')], 
    '1039': [(68.0864, '42731,42781,V4501'), (68.1704, '4770,4778,V071')]} 

如果相对少的项目共享相同的ID，从而导致短名单，你可能会得到过滤列表。

def lookup(data, id, age, age_offset=0.1): 
    if id in data: 
     return [value for x, value in data[id] if age <= x <= age+age_offset] 
    else: 
     return None  

lookup(preprocessed, '1039', 68.0) # Note that I use floats for age 
['42731,42781,V4501'] 

但是，如果许多项目共享相同的ID，你将不得不穿越长的列表，使得查找相对缓慢。在这种情况下，您将不得不应用进一步的优化。

编辑：由@Andrey彼得罗夫的建议

from bisect import bisect_left 
from itertools import islice, takewhile 
def optimized_lookup(data, id, age, age_offset=0.1): 
    if id in data: 
     l = data[id] 
     idx = bisect_left(l, age) 
     return [a for a,v in takewhile(lambda (x, value): x <= age+age_offset, islice(l, idx, None))] 
    else: 
     return None 

Answer 2

def getr(t): 
    id = float(t[0]) 
    age = float(t[1]) 
    os = 0.1 
    rs = [] 
    correct_id=fixed[id] 
    for k in correct_id.keys(): 
     if (k > age and k <= age + os): 
      rs.append(correct_id.get(k)) 
    return rs 

ct = {('1039', '68.0864'): '42731,42781,V4501', 
     ('1039', '68.1704'): '4770,4778,V071', 
     ('0845', '60.4476'): '2724,27800,4019', 
     ('0983', '63.3936'): '41401,4168,4240,V1582,V7281' } 

fixed={} 

for k in ct: 
    if not(float(k[0]) in fixed): 
     fixed[float(k[0])]={} 
    fixed[float(k[0])][float(k[1])] = ct[k] 

print "1" 
myTup = ('1039', '68.0') 
assert(getr(myTup) == ['42731,42781,V4501']) 

#the answer is: '42731,42781,V4501' 

print "2" 
myTup = ('0845', '60.0') 
assert(getr(myTup) == []) 
#Ans : No value returned 

Answer 3

这里有一个办法做到这一点在numpy的，虽然我没有测试过，我非常有信心它会大大快于循环字典。我用一个Numpy记录数组替换了字典结构，并使用np.where来查找与您输入的参数相匹配的行。

import numpy as np 

myDict = {('1039', '68.0864'): '42731,42781,V4501', 
       ('1039', '68.1704'): '4770,4778,V071', 
       ('0845', '60.4476'): '2724,27800,4019', 
       ('0983', '63.3936'): '41401,4168,4240,V1582,V7281' 
      } 

records=[] 
for k,v in myDict.iteritems(): 
    records.append([k[0], float(k[1]), v]) 

myArr = np.rec.fromrecords(records, formats='S10, f4, S100', 
          names="ID, Age, Code") 

def findInMyArray(arr, requestedID, requestedAge, tolerance=0.1): 
    idx = np.where(((arr["Age"] - requestedAge) < tolerance) & (arr["ID"] == requestedID)) 
    return idx 

idx = findInMyArray(myArr, "1039", 68.0, tolerance=0.1) 
print "The index found is: ", idx 
print "The values are: ", myArr["Code"][idx[0]]