Python:找出整数列表是否一致 [英] Python: find out whether a list of integers is coherent

问题描述

我试图找出整数列表是连贯的还是一口气"的，这意味着两个相邻元素之间的差必须恰好是1，并且数字必须单调递增.我找到了一种巧妙的方法，我们可以按列表中的数字减去列表中元素的位置进行分组-当数字不一致时，这种差异会改变.显然，当序列中没有间隔或重复时，应该只有一组.

I am trying to find out whether a list of integers is coherent or 'at one stretch', meaning that the difference between two neighboring elements must be exactly one and that the numbers must be increasing monotonically. I found a neat approach where we can group by the number in the list minus the position of the element in the list -- this difference changes when the numbers are not coherent. Obviously, there should be exactly one group when the sequence does not contain gaps or repetitions.

测试:

>>> 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

它很好用，但是我个人发现，鉴于问题的简单性，该解决方案有点令人费解.您能否在不显着增加代码长度的情况下想出一种更清晰的方法来达到相同的目的?

It works well, but I personally find that this solution is a bit too convoluted in view of the simplicity of the problem. Can you come up with a clearer way to achieve the same without significantly increasing the code length?

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

From the answers given below, the solution

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

显然是赢家.对于小型列表(10 ^ 3个元素)，它的速度比groupby方法快10倍，而(在我的机器上)仍然比第二种最佳方法(使用izip_longest)快4倍.它的缩放行为最差，但是即使对于包含10 ^ 8个元素的大型列表，它仍然比次优方法(又是基于izip_longest的解决方案)快两倍.

clearly wins. For small lists (10^3 elements), it is on the order of 10 times faster than the groupby approach and (on my machine) still four times faster than the next best approach (using izip_longest). It has the worst scaling behavior, but even for a large list with 10^8 elements it is still two times faster than the next best approach, which again is the izip_longest-based solution.

通过timeit获得的相关计时信息:

Relevant timing information obtained with 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内存

推荐答案

表现如何

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

，或者如果它已经被排序，则只有它连贯

or if its only coherent if it is already sorted

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

如果您使用的是python 3，则需要list(range(...))

if you are using python 3 you will need list(range(...))

这篇关于Python:找出整数列表是否一致的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！