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

当你想通过精确匹配查找密钥时,字典很棒.特别是,查找键的散列必须与存储键的散列相同.

如果您的范围是一致的,您可以通过编写一个哈希函数来伪造它,该函数返回一个范围的相同值,以及该范围内的每个值.但如果它们不是,那么这个哈希函数必须跟踪所有已知范围,这会将您带回到您开始时遇到的同样问题.

在这种情况下,这里的正确数据结构可能是某种排序集合.如果您只需要构建集合,然后多次使用它而无需修改它,只需sort一个列表并使用该bisect模块就可以为您完成.如果你需要在创建后修改集合,你需要一些围绕二叉树或某种B树变体构建的东西,比如blist或bintrees.

这将减少找到从N/2到log2(N)的范围的时间.所以,如果你有10000个范围,而不是5000个比较,你将会做到14个.

虽然我们正在使用它,但有助于将范围的开始和结束值转换为整数,而不是每次都将其转换为整数.另外,如果你想使用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不会削减它.

如果您希望每次平均查找超过log 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]):
    # ...

做:

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