在範圍字典中查找值 - python

Question

我將2個文件與初始標識符列，起始值和結束值進行比較。第二個文件包含相應的標識符和另一個值列。

Ex。

文件1：

A  200  900 
A  1000 1200 
B  100  700 
B  900  1000 

文件2：

A  103 
A  200 
A  250 
B  50 
B  100 
B  150 

我想找到包含在第一個文件中找到的範圍內的第二個文件中的所有值，使我的輸出看起來像：

A  200 
A  250 
B  100 
B  150 

現在我已經創建了第一個文件的字典範圍列表： Ex。

if Identifier in Dictionary: 
    Dictionary[Identifier].extend(range(Start, (End+1))) 
else: 
    Dictionary[Identifier] = range(Start, (End+1)) 

然後我經過第二個文件和搜索範圍的字典中的值： 例。

if Identifier in Dictionary: 
    if Value in Dictionary[Identifier]: 
    OutFile.write(Line + "\n") 

雖然不是最佳的這個工程的相對較小的文件，但是我有幾個大的文件，並將該軟件被證明是非常低效的。我需要優化我的程序，以便運行速度更快。

Answer 1

from collections import defaultdict 
ident_ranges = defaultdict(list) 
with open('file1.txt', 'r') as f1 
    for row in f1: 
     ident, start, end = row.split() 
     start, end = int(start), int(end) 
     ident_ranges[ident].append((start, end)) 
with open('file2.txt', 'r') as f2, open('out.txt', 'w') as output: 
    for line in f2: 
     ident, value = line.split() 
     value = int(value) 
     if any(start <= value <= end for start, end in ident_ranges[ident]): 
      output.write(line) 

注意：使用defaultdict讓您範圍添加到您的字典中沒有一個鍵的存在首先檢查。使用any允許短路範圍檢查。使用鏈式比較是一個很好的Python語法快捷方式（start <= value <= end）。

Answer 2

由於你有很大的範圍，你的問題本質上只是一堆比較，所以存儲起始/結束元組的速度幾乎肯定比整個範圍快（特別是因爲你現在擁有的將會大部分重複如果兩個碰巧重疊，則範圍中的數字）。

# Building the dict 
if not ident in d: 
    d[ident] = (lo, hi) 
else: 
    old_lo, old_hi = d[ident] 
    d[ident] = (min(lo, old_lo), max(hi, old_hi)) 

那麼你比較只是看起來像：

# comparing... 
if ident in d: 
    if d[ident][0] <= val <= d[ident][1]: 
     outfile.write(line+'\n') 

，如果你不爲if ident in d製作單獨檢查的這兩個部分會走得更快。 Python字典非常好，而且速度很快，所以只需先打電話給它。你有能力爲字典提供默認值，所以使用它。我沒有這個基準或任何看到的加速是什麼，但你肯定會得到一些，它肯定工作：

# These both make use of the following somewhat silly hack: 
# In Python, None is treated as less than everything (even -float('inf)) 
# and empty containers (e.g.(), [], {}) are treated as greater than everything. 
# So we use the tuple ((), None) as if it was (float('inf'), float('-inf)) 

for line in file1: 
    ident, lo, hi = line.split() 
    lo = int(lo) 
    hi = int(hi) 
    old_lo, old_hi = d.get(ident, ((), None)) 
    d[ident] = (min(lo, old_lo), max(hi, old_hi)) 

# comparing: 
for line in file2: 
    ident, val = line.split() 
    val = int(val) 
    lo, hi = d.get(ident, ((), None)) 
    if lo <= val <= hi: 
     outfile.write(line) # unless you stripped it off, this still has a \n 

上面的代碼是我用的是要考什麼;它在幾秒鐘內運行在一百萬行的file2上。

Answer 3

你需要構造range(START, END)？這似乎是很浪費的，當你可以這樣做：

if START <= x <= END: 
    # process 

檢查，如果該值的範圍是緩慢的，因爲一）你已經構建列表和b）執行在列表中的線性搜索找到它。

Answer 4

你可以嘗試這樣的事情：

In [27]: ranges=defaultdict(list) 

In [28]: with open("file1") as f: 
    for line in f: 
     name,st,end=line.split() 
     st,end=int(st),int(end) 
     ranges[name].append([st,end]) 
    ....:   

In [30]: ranges 
Out[30]: defaultdict(<type 'list'>, {'A': [[200, 900], [1000, 1200]], 'B': [[100, 700], [900, 1000]]}) 

In [29]: with open("file2") as f: 
    for line in f: 
     name,val=line.split() 
     val=int(val) 
     if any(y[0]<=val<=y[1] for y in ranges[name]): 
      print name,val 
    ....:    
A 200 
A 250 
B 100 
B 150 

Answer 5

絕招：Python的讓你做in比較與xrange對象，這比用range做in快得多，並且更高效的內存。

所以，你可以做

from collections import defaultdict 

rangedict = defaultdict(list) 
... 
rangedict[ident].append(xrange(start, end+1)) 
... 

for i in rangedict: 
    for r in rangedict[i]: 
     if v in r: 
      print >>outfile, line