3

我有一个包含一列值的文件，我想用它来与包含两个共同构成一个范围的值的字典进行比较。

例如：文件 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 循环，程序将运行但速度非常慢。

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

4

1 回答 1

5

当您想通过完全匹配查找键时，字典非常有用。特别是，查找键的散列必须与存储键的散列相同。

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

在这种情况下，这里正确的数据结构可能是某种排序的集合。如果您只需要构建集合，然后多次使用它而无需修改它，那么只需sort生成一个列表并使用bisect模块即可为您完成。如果您需要在创建后修改集合，您将需要围绕某种二叉树或 B 树变体构建的东西，例如blistor bintrees。

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

当我们这样做时，将范围开始和停止值转换为整数一次会有所帮助，而不是每次都这样做。此外，如果您想使用 stdlib bisect，很遗憾您无法将 a 传递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。

在这一点上，我认为它变得足够复杂，以至于你想寻找一个库来为你做这件事。

但是，您可能需要考虑不同的解决方案。

如果您使用numpyor 数据库而不是纯 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
于 2013-05-13T20:10:23.237 回答