從字典中提取值。鍵上的範圍匹配

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]]