Поиск значения в словаре диапазонов - 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 

На данный момент я создал словарь из первого файла с список диапазонов: Пример.

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

я затем пройти через второй файл и поиск значения в словаре диапазонов: Ex.

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 

Проверяется значение находится в диапазоне медленно, потому что а) вы должны были построить список и б) выполнить линейный поиск по списку, чтобы найти его ,

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 объектами, что намного быстрее, чем делать in с range, и гораздо меньше памяти.

Таким образом, вы можете сделать

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