7

整数のリストが一貫しているか、「一気に」かを調べようとしています。つまり、隣接する 2 つの要素の差は正確に 1 であり、数値は単調に増加している必要があります。リスト内の番号からリスト内の要素の位置を引いたものでグループ化できる、きちんとしたアプローチを見つけました。この違いは、番号が一貫していない場合に変わります。明らかに、シーケンスにギャップや繰り返しが含まれていない場合、グループは 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 要素) の場合、アプローチよりも 10 倍高速でありgroupby、(私のマシンでは) 次善のアプローチ (を使用izip_longest) よりもさらに 4 倍高速です。これは最悪のスケーリング動作をしますが、10^8 の要素を持つ大きなリストの場合でも、次善のアプローチである にizip_longest基づいたソリューションよりも 2 倍高速です。

で取得した関連するタイミング情報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 のメモリ
4

6 に答える 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(...))

于 2013-08-08T17:01:45.793 に答える
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
于 2013-08-08T17:34:58.500 に答える
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
于 2013-08-08T17:12:03.757 に答える