在Python中展平范围对（heapy/bisect？）

Question

在生物信息学中，我们进行了大量的以下转换：

>>> data = {
    (90,100):1,
    (91,101):1,
    (92,102):2,
    (93,103):1,
    (94,104):1
}

>>> someFuction(data)

{
     90:1,
     91:2,
     92:4,
     93:5,
     94:6,
     95:6,
     96:6,
     97:6,
     98:6,
     99:6,
    100:6,
    101:5,
    102:4,
    103:2,
    104:1
}

其中数据中的元组总是唯一的一对。 但是有很多方法可以实现这种转变——有些方法明显优于其他方法。我试过的一个方法是：

newData = {}
for pos, values in data.iteritems():
    A,B = pos
    for i in xrange(A,B+1):
        try: newData[i] += values
        except KeyError: newData[i] = values

这样做的好处是它又短又甜，但我不确定它是否有效率。。。。 我有一种感觉，不知何故把dict变成一个列表，然后再做xrange，会节省很多时间。我们说的是每个实验数周的计算工作。像这样：

>>> someFuction(data)
[ 
    [90,90,1], 
    [91,91,2], 
    [92,92,4], 
    [93,93,5], 
    [94,100,6], 
    [101,101,5], 
    [102,102,4], 
    [103,103,2], 
    [104,104,1] 
]

然后执行for/xrange循环。 Python上的人已经推荐了二分法和heapy，但是在与二分法做了一整天的斗争之后，我不能想出一个好的算法，我可以100%地一直工作。如果这里有人能帮我，甚至给我指出正确的方向，我将万分感激：）

Answer 1

不知道为什么只有20个观点和反对票。也许是因为它太过领域化了？你知道吗

不管怎样，我昨晚制定了一个解决方案，将一个文件的总运行时间从大约400分钟缩短到251分钟。我会张贴代码，但它相当长，并可能有缺陷的边缘案件。出于这个原因，我会说“工作”代码可以在程序“rawSeQL”中找到，但最有帮助的算法改进是：

• 在重叠的数组上循环并用一个乘数值将它们展平为非重叠数组产生了巨大的差异，因为xrange（）现在不需要重复自身。

• 使用集合.defaultdict（int）与上面的try/except循环有很大区别。收款台（）和orderedict比try/except慢得多。

• 我使用了bisect_left（）来查找插入下一个非重叠片段的位置，结果是这样，但是添加bisect的'low'参数来限制它需要检查的列表的范围，从而大大减少了计算时间。如果对输入列表进行排序，则low的值始终是对分的最后一个返回值，这使得此过程变得简单：）

heapy有可能提供更多的好处，但是现在上面提到的主要算法改进可能会超过任何编译时技巧。我现在有75个文件要处理，这意味着只要这三件事就可以节省大约12500天的计算时间：）