logo标签列表

Python：查找整数列表是否连续

pythonsequencepython-itertools
7
我正在尝试确定整数列表是否连贯或“一次性”，这意味着相邻两个元素之间的差必须恰好为1，并且数字必须单调递增。我发现了一种巧妙的方法，可以根据列表中的数字减去元素在列表中的位置进行分组 - 当数字不连贯时，此差异会改变。显然，当序列不包含间隙或重复时应该有一个组。
>>> l1 = [1, 2, 3, 4, 5, 6]
>>> l2 = [1, 2, 3, 4, 5, 7]
>>> l3 = [1, 2, 3, 4, 5, 5]
>>> l4 = [1, 2, 3, 4, 5, 4]
>>> l5 = [6, 5, 4, 3, 2, 1]
>>> def is_coherent(seq):
...     return len(list(g for _, g in itertools.groupby(enumerate(seq), lambda (i,e): i-e))) == 1
... 
>>> is_coherent(l1)
True
>>> is_coherent(l2)
False
>>> is_coherent(l3)
False
>>> is_coherent(l4)
False
>>> is_coherent(l5)
False

这个解决方案运行良好，但我个人认为，在问题的简单性方面，这个解决方案有点过于复杂。你能想出一个更清晰的方法来实现相同的功能而不显著增加代码长度吗？

编辑：答案摘要

从下面给出的答案中，解决方案为

def is_coherent(seq):
    return seq == range(seq[0], seq[-1]+1)

明显胜出。对于小型列表（10^3个元素），它的速度约为groupby方法的10倍，且（在我的机器上）仍比下一个最好的方法（使用izip_longest）快四倍。它的缩放行为最差，但即使对于具有10^8个元素的大型列表，它仍然比下一个最好的方法快两倍，这也是基于izip_longest的解决方案。通过timeit获得相关的时间信息：
Testing is_coherent_groupby...
   small/large/larger/verylarge duration: 8.27 s, 20.23 s, 20.22 s, 20.76 s
   largest/smallest = 2.51
Testing is_coherent_npdiff...
   small/large/larger/verylarge duration: 7.05 s, 15.81 s, 16.16 s, 15.94 s
   largest/smallest = 2.26
Testing is_coherent_zip...
   small/large/larger/verylarge duration: 5.74 s, 20.54 s, 21.69 s, 24.62 s
   largest/smallest = 4.28
Testing is_coherent_izip_longest...
   small/large/larger/verylarge duration: 4.20 s, 10.81 s, 10.76 s, 10.81 s
   largest/smallest = 2.58
Testing is_coherent_all_xrange...
   small/large/larger/verylarge duration: 6.52 s, 17.06 s, 17.44 s, 17.30 s
   largest/smallest = 2.65
Testing is_coherent_range...
   small/large/larger/verylarge duration: 0.96 s, 4.14 s, 4.48 s, 4.48 s
   largest/smallest = 4.66

测试代码：

import itertools
import numpy as np
import timeit


setup = """
import numpy as np
def is_coherent_groupby(seq):
    return len(list(g for _, g in itertools.groupby(enumerate(seq), lambda (i,e): i-e))) == 1

def is_coherent_npdiff(x):
    return all(np.diff(x) == 1)

def is_coherent_zip(seq):
    return all(x==y+1 for x, y in zip(seq[1:], seq))

def is_coherent_izip_longest(l):
    return all(a==b for a, b in itertools.izip_longest(l, xrange(l[0], l[-1]+1)))

def is_coherent_all_xrange(l):
    return all(l[i] + 1 == l[i+1] for i in xrange(len(l)-1))

def is_coherent_range(seq):
    return seq == range(seq[0], seq[-1]+1)


small_list = range(10**3)
large_list = range(10**6)
larger_list = range(10**7)
very_large_list = range(10**8)
"""


fs = [
    'is_coherent_groupby',
    'is_coherent_npdiff',
    'is_coherent_zip',
    'is_coherent_izip_longest',
    'is_coherent_all_xrange',
    'is_coherent_range'
    ]


for n in fs:
    print "Testing %s..." % n
    t1 = timeit.timeit(
        '%s(small_list)' % n, 
        setup,
        number=40000
        )      
    t2 = timeit.timeit(
        '%s(large_list)' % n, 
        setup,
        number=100
        )     
    t3 = timeit.timeit(
        '%s(larger_list)' % n, 
        setup,
        number=10
        )
    t4 =  timeit.timeit(
        '%s(very_large_list)' % n, 
        setup,
        number=1
        )
    print "   small/large/larger/verylarge duration: %.2f s, %.2f s, %.2f s, %.2f s" % (t1, t2, t3, t4)
    print "   largest/smallest = %.2f" % (t4/t1)

测试机器：

  • Linux 3.2.0 (Ubuntu 12.04)
  • Python 2.7.3 (gcc 4.1.2)
  • 使用Intel编译器构建的numpy 1.6.2
  • CPU：E5-2650 @ 2.00GHz
  • 24 GB内存
6个回答
5
怎么样？
sorted_list = sorted(my_list)
return sorted_list == range(sorted_list[0],sorted_list[-1]+1)

如果只有排序后才能理解其连贯性

return my_list == range(my_list[0],my_list[-1]+1)

如果您正在使用Python 3，则需要使用list(range(...))

那你不就可以这样做吗：list == range(list[0], list[-1]+1)？ :) - Dr. Jan-Philip Gehrcke
是的，我不知道...这取决于你如何定义连贯性。啊，我看到你在编辑中添加了更多的例子 :) ... - Joran Beasley
1
你需要在Python 3中使用list()来包装range()；也许值得一提。 - Zero Piraeus
@JoranBeasley：我在问题中将其定义为“相邻两个元素之间的差必须恰好为1，并且数字必须单调递增”。 - Dr. Jan-Philip Gehrcke
您介意讨论一下这种方法的性能吗？它需要创建一个可能很大的列表，并比较两个可能很大的列表。此外，关于要求，您可以将 list == range(list[0], list[-1]+1) 安全地添加到您的答案中！（编辑：现在 Carl 已经做了...） - Dr. Jan-Philip Gehrcke
显示剩余3条评论
2
除非我在你的示例中忽略了什么，否则这个更简单的解决方案实际上更短。
>>> l1 = [1, 2, 3, 4, 5, 6]
>>> l2 = [1, 2, 3, 4, 5, 7]
>>> l3 = [1, 2, 3, 4, 5, 5]
>>> l4 = [1, 2, 3, 4, 5, 4]
>>> l5 = [6, 5, 4, 3, 2, 1]
>>> 
>>> def is_coherent(seq):
...     return seq == range(seq[0], seq[0]+len(seq), 1)
... 
>>> is_coherent(l1)
True
>>> is_coherent(l2)
False
>>> is_coherent(l3)
False
>>> is_coherent(l4)
False
>>> is_coherent(l5)
False
>>>

一些基本性能测试的结果似乎表明这种方法显著更快（我已将您的示例添加为 is_coherent2）：
Carl > python -m timeit -s 'from t import is_coherent, l1' 'is_coherent(l1)'
1000000 loops, best of 3: 0.782 usec per loop
Carl > python -m timeit -s 'from t import is_coherent, l3' 'is_coherent(l3)'
1000000 loops, best of 3: 0.796 usec per loop
Carl > python -m timeit -s 'from t import is_coherent2, l1' 'is_coherent2(l1)'
100000 loops, best of 3: 4.54 usec per loop
Carl > python -m timeit -s 'from t import is_coherent2, l3' 'is_coherent2(l3)'
100000 loops, best of 3: 4.93 usec per loop
基本上和 @JoranBeasley 建议的一样 -- 你认为这个方案相对于基于itertools的解决方案有什么表现上的差异呢？您想进行一些基准测试吗？ - Dr. Jan-Philip Gehrcke
更新了一些 timeit 的示例。 - Carl Groner
2
如果您正在寻找一个numpy解决方案：
import numpy as np

def is_coherent(x):
    return all(np.diff(x) == 1)

is_coherent(np.array([1,2,3,4,5]))
Out[39]: True

is_coherent(np.array([1,2,3,4,8]))
Out[40]: False
1
def is_coherent(seq):
    return all(x==y+1 for x, y in zip(seq[1:], seq))
2
去掉括号，你就可以将列表推导式转换成生成器推导式。 - Steven Rumbalski
1
这将短路并且不会创建额外的列表，因此非常适用于测试非常大的列表。
def is_coherent(l):
    return all(a==b for a, b in izip_longest(l, xrange(l[0], l[-1]+1)))

或者

def is_coherent(l):
    return all(l[i] + 1 == l[i+1] for i in xrange(len(l)-1))
这可能比我的解决方案更快，更节省内存。 - Joran Beasley
1
我收回之前的说法，这种方法比我的方法慢得多...但可能更好地利用了内存，因此仍然适用于非常大的列表（例如大于1000万）。 - Joran Beasley
@JoranBeasley：更节省内存？是的。但更快吗？可能不是，因为即使对于相对较大的列表，列表创建速度也非常快。 - Steven Rumbalski
@JoranBeasley：此外，在C语言中实现了将两个列表进行比较是否相等的功能。 - Steven Rumbalski
基于izip_longest的解决方案是最具扩展性的，非常有趣（请参见我的答案中的编辑）！ - Dr. Jan-Philip Gehrcke
0
我不会 Python，但我知道它的功能，这里有一个小循环函数，如果你更改语法以符合正确的 Python，它就能实现。
伪代码：
def is_coherent(seq):
     for x in xrange(1, len(seq)-1):
        if (seq[x+1]-seq[x] != 1)  return false;   
     return true
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接