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 循环，程序似乎不会运行(或者可能运行得太慢而无法获得结果)，因为我在每个字典中有超过 7,000 个值。如果我将 while 循环更改为 if 循环，程序会运行但速度非常慢。

我正在寻找一种让这个程序更快更高效的方法

Answer 1

当您想通过精确匹配查找键时，字典非常有用。特别是，查找键的哈希值必须与存储键的哈希值相同。

如果您的范围是一致的，您可以通过编写一个散列函数来伪造这一点，该散列函数为一个范围以及该范围内的每个值返回相同的值。但如果不是，则此哈希函数将必须跟踪所有已知范围，这会将您带回到您开始时遇到的相同问题。

在那种情况下，这里正确的数据结构可能是某种排序集合。如果您只需要建立集合，然后多次使用它而不修改它，只需对列表进行排序并使用 bisect模块会为你做。如果您需要在创建后修改集合，您将需要围绕二叉树或某种 B 树变体构建的东西，例如 blist或 bintrees .

这将减少查找范围从 N/2 到 log2(N) 的时间。因此，如果您有 10000 个范围，而不是 5000 次比较，您将进行 14 次。

当我们这样做时，将范围开始值和结束值转换为整数一次而不是每次都这样做会有所帮助。此外，如果您想使用标准库 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 不会切断它。

如果您期望每次平均查找超过 log N 个匹配项，您可以使用两个排序列表和 bisect 来实现。

但除此之外，您需要更复杂的数据结构和更复杂的代码。例如，如果您可以节省 N^2 空间，则可以通过为第一个列表中的每个范围创建一个第二个列表(按末尾排序)并将所有具有匹配开头的值的值保持在 log 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]):
    # ...

做:

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