45

リスト内の None 以外のすべての項目が単一の連続したスライスに含まれているかどうかを簡単に判断する方法を探しています。 None 以外の項目の例として整数を使用します。

たとえば、リスト[None, None, 1, 2, 3, None, None]は連続する整数エントリの要件を満たしています。対照的に、整数の間に None エントリがあるため、連続で [1, 2, None, None, 3, None]はありません。

これを可能な限り明確にするために、さらにいくつかの例を示します。

連続:
[1, 2, 3, None, None]
[None, None, 1, 2, 3]
[None, 1, 2, 3, None]

非連続:
[None, 1, None, 2, None, 3]
[None, None, 1, None, 2, 3]
[1, 2, None, 3, None, None]

私の最初のアプローチは、変数を使用して、まだ遭遇したNoneかどうか、およびまだ遭遇したかどうかintを追跡することでした。 for ループに埋め込まれたステートメント。（醜さに加えて、すべての場合に機能するようになったわけではないことを告白します）。

リスト内の None 以外の項目が単一の連続したスライスで発生するかどうかを把握する簡単な方法を知っている人はいますか?

4

11 に答える 11

44 
def contiguous(seq):
    seq = iter(seq)
    all(x is None for x in seq)        # Burn through any Nones at the beginning
    any(x is None for x in seq)        # and the first group
    return all(x is None for x in seq) # everthing else (if any) should be None.

いくつかの例を次に示します。next(seq)イテレータから次のアイテムを取得するために使用できます。それぞれの後に次の項目を指すマークを付けます

例1:

seq = iter([None, 1, 2, 3, None])        #  [None, 1, 2, 3, None]
                                         # next^
all(x is None for x in seq)            
                                         #        next^
any(x is None for x in seq)            
                                         #                    next^ (off the end)
return all(x is None for x in seq)       # all returns True for the empty sequence

例 2:

seq = iter([1, 2, None, 3, None, None])  #    [1, 2, None, 3, None, None]
                                         # next^
all(x is None for x in seq)            
                                         #    next^
any(x is None for x in seq)            
                                         #             next^  
return all(x is None for x in seq)       # all returns False when 3 is encountered
于 2013-02-06T04:41:02.770 に答える
25

itertools.groupby救助に良い'ol ：

from itertools import groupby

def contiguous(seq):
    return sum(1 for k,g in groupby(seq, lambda x: x is not None) if k) == 1

与える

>>> contiguous([1,2,3,None,None])
True
>>> contiguous([None, 1,2,3,None])
True
>>> contiguous([None, None, 1,2,3])
True
>>> contiguous([None, 1, None, 2,3])
False
>>> contiguous([None, None, 1, None, 2,3])
False
>>> contiguous([None, 1, None, 2, None, 3])
False
>>> contiguous([1, 2, None, 3, None, None])
False

[編集]

コメントには議論があるようですので、なぜこのアプローチが他のアプローチよりも好きなのかを説明します。

非Noneオブジェクトの連続したグループが1つあるかどうかを調べようとしていますが、

sum(1 for k,g in groupby(seq, lambda x: x is not None) if k)

連続するグループの収集を行うように設計されたstdlibの関数を使用して、連続する非Noneオブジェクトの数をカウントします。私たちが見るとすぐにgroupby、私たちは「隣接するグループ」と思います。逆もまた同様です。その意味で、それは自己文書化です。これが基本的に私の目標の定義です。

IMHOの唯一の弱点は、短絡しないことです。これは修正できますが、考えてみると、好きなプリミティブを使用しているので、これを好む人もいます。「連続する非Noneグループの数を数える」 -これは、単に「できるだけ早く、隣接する非Noneグループが複数あるかどうかを教えてください」ということを好みます。

最後のアプローチを実装するためのアプローチの多くは、問題に関する巧妙な観察に依存しています。たとえば、「非なしオブジェクトの連続したグループが1つしかない場合、最初の非なしオブジェクトが見つかるまでスキャンしてから、オブジェクトをスキャンする場合」などです。最初の非Noneグループが存在する場合はそれが見つかるまで、残っているものがNoneであるかどうかが答えになります。」（または、私の問題の一部であるそのようなもの：私はそれについて考えなければなりません。）それを解決するために問題についての「実装の詳細」を使用するように感じ、解決するために使用できる問題のプロパティに焦点を当てます単に問題をPythonに指定して、Pythonに作業を任せるのではなく、

ことわざにあるように、私は頭脳が非常に少ないクマです。私の経験では、FAILが散らばっているルートなので、賢くする必要はありません。

いつものように、もちろん、そしておそらく彼らの賢さに比例して、すべての人のマイレージは変わるかもしれません。

于 2013-02-06T04:20:52.280 に答える
12

あなたは次のようなものを使うことができますitertools.groupby：

from itertools import groupby

def are_continuous(items):
    saw_group = False

    for group, values in groupby(items, lambda i: i is not None):
        if group:
            if saw_group:
                return False
            else:
                saw_group = True

    return True

これは、グループが2回表示されるまで繰り返されます。検討するかどうかはわかりません[None, None]ので、ニーズに合わせて調整してください。

于 2013-02-06T04:21:17.717 に答える
7

これは最善の方法ではないかもしれませんが、最初の非Noneエントリと最後のnon-Noneエントリを探してから、スライスのを確認することができますNone。例えば：

def is_continuous(seq):
    try:
        first_none_pos = next(i for i,x in enumerate(seq) if x is not None)
        #need the or None on the next line to handle the case where the last index is `None`.
        last_none_pos = -next(i for i,x in enumerate(reversed(seq)) if x is not None) or None
    except StopIteration: #list entirely of `Nones`
        return False
    return None not in seq[first_none_pos:last_none_pos]

assert is_continuous([1,2,3,None,None]) == True
assert is_continuous([None, 1,2,3,None]) == True
assert is_continuous([None, None, 1,2,3]) == True
assert is_continuous([None, 1, None, 2,3]) == False
assert is_continuous([None, None, 1, None, 2,3]) == False
assert is_continuous([None, 1, None, 2, None, 3]) == False
assert is_continuous([1, 2, None, 3, None, None]) == False

これは、どのシーケンスタイプでも機能します。

于 2013-02-06T04:21:27.897 に答える
7

シーケンス要素を消費する自然な方法は、次を使用することdropwhileです。

from itertools import dropwhile
def continuous(seq):
    return all(x is None for x in dropwhile(lambda x: x is not None,
                                            dropwhile(lambda x: x is None, seq)))

これは、ネストされた関数呼び出しなしで表現できます。

from itertools import dropwhile
def continuous(seq):
    core = dropwhile(lambda x: x is None, seq)
    remainder = dropwhile(lambda x: x is not None, core)
    return all(x is None for x in remainder)
于 2013-02-06T10:44:18.633 に答える
5

一発ギャグ：

contiguous = lambda l: ' ' not in ''.join('x '[x is None] for x in l).strip()

実際の作業はstrip関数によって行われます。削除された文字列にスペースがある場合、それらは先頭/末尾ではありません。関数の残りの部分は、リストを文字列に変換します。文字列には、それぞれにスペースがありますNone。

于 2013-02-06T12:11:53.290 に答える
3

@gnibbler のアプローチと groupby のアプローチを比較するために、いくつかのプロファイリングを行いました。@gnibber のアプローチは一貫して高速です。より長いリストの場合。たとえば、長さが 3 ～ 100 のランダムな入力のパフォーマンスが約 50% 向上し、50% の確率で単一の int シーケンス (ランダムに選択された) が含まれ、それ以外の場合はランダムな値が含まれます。以下のテストコード。2 つの方法を散在させて (どちらが最初に実行されるかをランダムに選択)、キャッシュ効果が確実にキャンセルされるようにしました。これに基づいて、groupbyアプローチはより直感的ですが、プロファイリングがこれが最適化するコード全体の重要な部分であることを示す場合、@ gnibberのアプローチが適切である可能性があります-その場合、適切なコメントを使用してall/any to consumer イテレーター値を使用して何が起こっているかを示します。

from itertools import groupby
import random, time

def contiguous1(seq):
    # gnibber's approach
    seq = iter(seq)
    all(x is None for x in seq)        # Burn through any Nones at the beginning
    any(x is None for x in seq)        # and the first group
    return all(x is None for x in seq) # everthing else (if any) should be None.

def contiguous2(seq):
    return sum(1 for k,g in groupby(seq, lambda x: x is not None) if k) == 1

times = {'contiguous1':0,'contiguous2':0}

for i in range(400000):
    n = random.randint(3,100)
    items = [None] * n
    if random.randint(0,1):
        s = random.randint(0,n-1)
        e = random.randint(0,n-s)
        for i in range(s,e):
            items[i] = 3
    else:
        for i in range(n):
            if not random.randint(0,2):
                items[i] = 3
    if random.randint(0,1):
        funcs = [contiguous1, contiguous2]
    else:
        funcs = [contiguous2, contiguous1]
    for func in funcs:
        t0 = time.time()
        func(items)
        times[func.__name__] += (time.time()-t0)

print
for f,t in times.items():
    print '%10.7f %s' % (t, f)
于 2013-02-06T18:10:20.083 に答える
2

numpy に触発されたソリューションを次に示します。すべての非 null 要素の配列インデックスを取得します。次に、各インデックスをそれに続くものと比較します。差が 1 より大きい場合、非 null の間に null があります。次のインデックスが 1 より大きいインデックスがない場合、ギャップはありません。

def is_continuous(seq):
    non_null_indices = [i for i, obj in enumerate(seq) if obj is not None]
    for i, index in enumerate(non_null_indices[:-1]):
        if non_null_indices[i+1] - index > 1:
            return False
    return True
于 2013-02-06T17:57:12.833 に答える
1

このアルゴリズムには、いくつかの欠点があります (リストから項目が削除されます)。しかし、それは解決策です。

None基本的に、最初と最後からすべての連続を削除すると。リストにいくつか見つかった場合None、整数は連続した形式ではありません。

def is_continuous(seq):
    while seq and seq[0] is None: del seq[0]
    while seq and seq[-1] is None: del seq[-1]

    return None not in seq

assert is_continuous([1,2,3,None,None]) == True
assert is_continuous([None, 1,2,3,None]) == True
assert is_continuous([None, None, 1,2,3]) == True
assert is_continuous([None, 1, None, 2,3]) == False
assert is_continuous([None, None, 1, None, 2,3]) == False
assert is_continuous([None, 1, None, 2, None, 3]) == False
assert is_continuous([1, 2, None, 3, None, None]) == False

しかし、小さなコードが悪になり得る別の例です。

strip()のメソッドが利用できることを望みますlist。

于 2013-02-06T05:50:19.583 に答える
1

私の最初のアプローチは、変数を使用して追跡することでした...

...これは、forループに埋め込まれた一連のif/elseステートメントに従うのが非常に難しく、非常にネストされたものになります...

いいえ！実際には、必要な変数は 1 つだけです。この問題を有限状態マシン (FSM) の観点から考えると、非常に優れた解決策が得られます。

状態を と呼びますp。最初pは 0 です。次に、状態の間を歩き始めます。

FSM

リスト内のすべての要素を調べても失敗しない場合、答えはTrueです。

dict で変換テーブルをエンコードする 1 つのバージョン

def contiguous(s, _D={(0,0):0, (0,1):1, (1,0):2, (1,1):1, (2,0):2, (2,1):3}):
    p = 0
    for x in s:
        p = _D[p, int(x is not None)]
        if p >= 3: return False
    return True

if ステートメントを使用する別のバージョン:

def contiguous(s):
    p = 0
    for x in s:
        if x is None and p == 1 or x is not None and (p == 0 or p == 2):
            p += 1
        if p >= 3: return False
    return True

つまり、私のポイントは、 usingifとforまだ Pythonic であるということです。

アップデート

FSM をエンコードする別の方法を見つけました。変換テーブルを 12 ビット整数にパックできます。

def contiguous(s):
    p = 0
    for x in s:
        p = (3684 >> (4*p + 2*(x!=None))) & 3
        if p >= 3: return False
    return True

ここで、マジック ナンバーである 3684 は、次の方法で取得できます。

    _D[p,a]     3  2  1  2  1  0
         p      2  2  1  1  0  0
         a      1  0  1  0  1  0
bin(3684) = 0b 11 10 01 10 01 00

可読性は他のバージョンほど良くありませんが、辞書検索を回避するため高速です。2 番目のバージョンはこれと同じくらい高速ですが、このエンコーディングの考え方を一般化して、より多くの問題を解決できます。

于 2013-02-16T16:06:15.283 に答える