Python ускоряет поиск значения в словаре диапазонов

Question

У меня есть файл со столбцом значений, который я хотел бы использовать для сравнения со словарем, который содержит два значения, которые вместе образуют диапазон.

, например: файла A:

Chr1 200 .... 
Chr3 300  

Файл B:

Chr1 200 300 ... 
Chr2 300 350 ... 

Сейчас я создал словарь значений для файла B:

for Line in FileB: 
     LineB = Line.strip('\n').split('\t') 
     Ranges[Chr].append(LineB) 

Для сравнения :

for Line in MethylationFile: 
     Line = Line.strip("\n") 
     Info = Line.split("\t") 
     Chr = Info[0] 
     Location = int(Info[1]) 
     Annotation = "" 
     for i, r in enumerate(Ranges[Chr]): 
      n = i + 1 
      while (n < len(Ranges[Chr])): 
        if (int(Ranges[Chr][i][1]) <= Location <= int(Ranges[Chr][i][2])): 
         Annotation = '\t'.join(Ranges[Chr][i][4:]) 
        n +=1 
      OutFile.write(Line + '\t' + Annotation + '\n') 

Если я выхожу из цикла while, программа, похоже, не запускается (или, вероятно, работает слишком медленно, чтобы получить результаты), так как у меня более 7000 значений в каждом словаре. Если я изменил цикл while на цикл if, программа будет работать, но с невероятно медленными темпами.

Я ищу способ сделать эту программу быстрее и эффективнее

Answer 1

Словари велики, когда вы хотите посмотреть ключ по точному соответствию. В частности, хэш ключа поиска должен быть таким же, как хэш сохраненного ключа.

Если ваши диапазоны согласованы, вы можете подделать это, написав хеш-функцию, которая возвращает то же значение для диапазона, и для каждого значения в этом диапазоне. Но если это не так, эта хеш-функция должна отслеживать все известные диапазоны, что возвращает вас к той же самой проблеме, с которой вы начинаете.

В этом случае правильная структура данных здесь, вероятно, представляет собой некоторую сортированную коллекцию. Если вам нужно только собрать коллекцию, а затем использовать ее много раз, не изменяя ее, просто введите список и используйте модуль bisect, сделав это для вас. Если вам нужно изменить коллекцию после создания, вам понадобится что-то построенное вокруг двоичного дерева или варианта B-дерева, например blist или bintrees.

Это сократит время поиска диапазона от N/2 до log2 (N). Итак, если у вас есть 10000 диапазонов, вместо 5000 сравнений, вы сделаете 14.

В то время как мы на нем, это поможет преобразовать значения начала и остановки диапазона в ints один раз, вместо того, чтобы делать это каждый раз. Кроме того, если вы хотите использовать stdlib bisect, вы, к сожалению, не можете передать key для большинства функций, поэтому давайте реорганизовать диапазоны в сопоставимый заказ. Итак:

for Line in FileB: 
    LineB = Line.strip('\n').split('\t') 
    Ranges[Chr].append(int(LineB[1]), int(LineB[2]), [LineB[0]) 

for r in Ranges: 
    r.sort() 

Теперь, вместо этого цикла:

for i, r in enumerate(Ranges[Chr]): 
    # ... 

ли это:

i = bisect.bisect(Ranges[Chr], (Location, Location, None)) 
if i: 
    r = Ranges[Chr][i-1] 
    if r[0] <= Location < r[1]: 
     # do whatever you wanted with r 
    else: 
     # there is no range that includes Location 
else: 
    # Location is before all ranges 

Вы должны быть осторожными, думая о bisect, и возможно, я получил это неправильно с первой попытки, поэтому ... прочитайте документы о том, что он делает, и поэкспериментируйте с вашими данными (распечатайте результаты функции bisect), прежде чем доверять этому.

---

Если диапазоны могут перекрываться, и вы хотите, чтобы быть в состоянии найти все диапазоны, которые содержат значения, а не только один, вам нужно немного больше, чем это, чтобы держать вещи эффективно. Невозможно полностью упорядочить перекрывающиеся диапазоны, поэтому bisect не отрежет.

Если вы ожидаете больше совпадений в логах N на средний поиск, вы можете сделать это с помощью двух отсортированных списков и bisect.

Но в остальном вам нужна более сложная структура данных и более сложный код. Например, если вы можете зарезервировать пространство N^2, вы можете сохранить время в журнале N, указав для каждого диапазона в первом списке второй список, отсортированный по концу, всех значений с соответствующим началом.

И в этот момент я думаю, что он становится достаточно сложным, и вы хотите найти библиотеку, чтобы сделать это за вас.

---

Однако, возможно, вы захотите рассмотреть другое решение.

Если вы используете numpy или базу данных вместо чистого Python, это не может сократить алгоритмическую сложность от N до log N ... но она может сократить постоянные накладные расходы в 10 раз или около того, что может быть достаточно хорошим , Фактически, если вы делаете тонны поисков в небольшом небольшом списке, это может быть даже лучше.

Плюс, это выглядит намного проще, и как только вы привыкнете к операциям массива или SQL, это может быть даже более читаемым. Итак:

RangeArrays = [np.array(a[:2] for a in value) for value in Ranges] 

... или, если Ranges отображение ДИКТ строки на значения, вместо списка:

RangeArrays = {key: np.array(a[:2] for a in value) for key, value in Ranges.items()} 

Затем, вместо этого:

for i, r in enumerate(Ranges[Chr]): 
    # ... 

Do:

comparisons = Location < RangeArrays[Chr] 
matches = comparisons[:,0] < comparisons[:,1] 
indices = matches.nonzero()[0] 
for index in indices: 
    r = Ranges[indices[0]] 
    # Do stuff with r 

(Вы может, конечно, сделать вещи более кратким, но это стоит делать это таким образом и распечатывать все промежуточные шаги, чтобы понять, почему это работает)

Или, используя базу данных:.

cur = db.execute('''SELECT Start, Stop, Chr FROM Ranges 
        WHERE Start <= ? AND Stop > ?''', (Location, Location)) 
for (Start, Stop, Chr) in cur: 
    # do stuff