用Python求连续范围的和

Question

我有一个叫做sumranges()的函数，它的作用是计算一个包含多个元组的元组中连续数字的范围总数。举个例子：

def sumranges(nums):
    return sum([sum([1 for j in range(len(nums[i])) if
                     nums[i][j] == 0 or
                     nums[i][j - 1] + 1 != nums[i][j]]) for
                i in range(len(nums))])

>>> nums = ((1, 2, 3, 4), (1, 5, 6), (19, 20, 24, 29, 400))
>>> print sumranges(nums)
7

从上面可以看到，它返回的是元组中连续数字的范围数量，也就是说：len((1, 2, 3, 4), (1), (5, 6), (19, 20), (24), (29), (400)) = 7。这里的元组总是按顺序排列的。

我现在的问题是，我的sumranges()函数写得很糟糕。我看着它就觉得不舒服。我现在的做法是遍历这个元组和每个子元组，如果当前数字不是（前一个数字 + 1），就给它赋值1，然后把这些值加起来。我觉得应该有更简单的方法来实现我的目标。有没有人知道更符合Python风格的方法呢？

补充：我已经对目前所有的答案进行了性能测试。感谢大家的回答。

性能测试的代码如下，使用的样本大小是10万：

from time import time
from random import randrange
nums = [sorted(list(set(randrange(1, 10) for i in range(10)))) for
        j in range(100000)]

for func in sumranges, alex, matt, redglyph, ephemient, ferdinand:
    start = time()
    result = func(nums)
    end = time()
    print ', '.join([func.__name__, str(result), str(end - start) + ' s'])

结果如下。实际答案显示用来验证所有函数返回的结果是否正确：

sumranges, 250281, 0.54171204567 s
alex, 250281, 0.531121015549 s
matt, 250281, 0.843333005905 s
redglyph, 250281, 0.366822004318 s
ephemient, 250281, 0.805964946747 s
ferdinand, 250281, 0.405596971512 s

RedGlyph在速度上稍微领先，但最简单的答案可能是Ferdinand的，可能在Python风格上也更胜一筹。

Answer 1

这里给你展示一个更接近你原始代码的例子：

def sumranges(nums):
    return sum( (1 for i in nums
                   for j, v in enumerate(i)
                   if j == 0 or v != i[j-1] + 1) )

这个例子的主要想法是：

• 避免创建中间的列表，而是使用生成器，这样可以节省一些资源。
• 当你已经选择了一个子元素时，避免使用索引（上面的 i 和 v）。

不过，在我的例子中，剩下的 sum() 还是必须要用的。

Answer 2

考虑一下：

>>> nums = ((1, 2, 3, 4), (1, 5, 6), (19, 20, 24, 29, 400))
>>> flat = [[(x - i) for i, x in enumerate(tu)] for tu in nums]
>>> print flat
[[1, 1, 1, 1], [1, 4, 4], [19, 19, 22, 26, 396]]
>>> import itertools
>>> print sum(1 for tu in flat for _ in itertools.groupby(tu))
7
>>> 

我们通过从每个值中减去它的索引，来“拉平”我们感兴趣的“递增坡道”，这样就把它们变成了一系列相同值的连续“段”；然后我们可以用之前提到的 itertools.groupby 来识别和计算这些“段”。这看起来是一个相当优雅（而且快速）的解决方案。

Answer 3

我来分享一下我的看法：

>>> sum(len(set(x - i for i, x in enumerate(t))) for t in nums)
7

这个想法基本上和Alex的帖子里描述的一样，不过这里用的是set，而不是itertools.groupby，所以表达式更简洁。因为set是用C语言实现的，而且计算一个集合的长度len()是非常快的，所以这个方法也应该运行得很快。