1

多くのbool値を含むリストがあり、このパターンを取得したい: True, True, False, True, True. これを行うには、前の要素の処理中にループ内の次の要素を取得する必要があると思います。どうすればいいですか？

i += 1おまけの質問:リスト内の要素の位置をモノ以外でインクリメントする方法はありますか?

4

4 に答える 4

2

私は刺すでしょう：

subset = [True, True, False, True, True]
main = [False, True, False, True, True, True, False, True, True, False, True, False, True]

for i, j in  enumerate(xrange(len(subset), len(main) + 1)):
    if main[i:j] == subset:
        print subset, 'is at', i
        break
else:
    print 'not found'

注：これは少し強引ですが、1回限りの場合は問題ありません...それ以外の場合は、試行を見てください...

于 2012-11-01T23:12:36.133 に答える
1 
l = len(some_list) - 3
for i, thing in enumerate(some_list):
    if i == l: break
    if thing and some_list[i+1] and not some_list[i+2] and some_list[i+3]:
        bingo(i)

別の未テストの試み：

needle = [True, True, False, True, True]
needle_len = len(needle)
for i in range(len(stack)-needle_len+1):
    if needle == stack[i:i+needle_len]:
        bingo(i)
于 2012-11-01T22:50:49.317 に答える
1

質問を正しく理解していれば、あなたがやろうとしていることは とまったく同じですがstr.find、文字列内の部分文字列ではなく、リスト内の部分リストを探しています。

もしそうなら：

def findSubList(l, sub):
  return (''.join('T' if x else 'F' for x in l)
          .find(''.join('T' if x else 'F' for x in sub)))

これはハックに思えるかもしれませんが、理にかなっています: リスト内のサブリストを見つけたい場合、どちらも簡単に文字列に変換でき、文字列内のサブ文字列を見つけるための組み込み関数が既に存在するため、なぜ使わない？

遅すぎることが判明するかもしれませんが、実際には、これをコード化するのは非常に高速であるため、目的に対して遅すぎるかどうかをテストする価値があります。(そして、遅すぎるとしても、おそらく文字列への変換部分が遅いのでしょう。最初は bool のリストの代わりに文字列を使用するか、最初に 1 回変換してから 200 回の検索を行うのが妥当かもしれません。 、または何でも。)

これがやむを得ず遅すぎる場合、次に行うことは、の実装を調べて、str.findそれを一般的なシーケンス検索に変換することです。Python のソースがあるので、これはそれほど難しいことではありません。ただし、str.findC にある可能性があり、移植が困難になる可能性があります。その場合でも、純粋な Python をstr.findオンラインで検索したいかもしれませんが、見つからないと仮定しましょう。

次のステップは、PyPI にシーケンス検索モジュールがあるかどうかを確認することです。

そうでない場合でも、実装が簡単であるか、ActiveState やウィキペディアのような場所で無料で実装されている、よく知られたアルゴリズムがいくつかあります。リストといくつかの比較については、ウィキペディアの文字列検索アルゴリズムを参照してください。(パフォーマンス特性は、提供されていない要因 (実行する必要がある検索の数、メイン、サブセット、またはその両方が異なるなど) によって異なります。つまり、より多くの情報がなければ、どれが最適かを推測することはできません。)

標準の文字列検索アルゴリズムでさえ十分に高速ではない可能性があり、8 ビット文字ではなく 1 ビットを検索するという事実を利用することで、効率が大幅に向上します。(パターンが固定されている場合、検索を有限状態マシンとして記述し、それをハードコーディングされた、証明可能な最適な実装に変えることさえできるはずです…)

そのため、自分で何かを設計する必要があるかもしれません。しかし、あなたがそうする可能性は非常に低いですし、可能であればそうすることは避けたいと思います. 明らかに一般的な問題が発生した場合は、最初の原則から解決しようとするのではなく、解決済みの問題であると想定して解決策を探す価値があります。

于 2012-11-01T23:22:33.570 に答える
0

かなり効率的で、スライディング ウィンドウ アプローチを使用し、線形時間で実行する必要があります。 

def find_x_in_y(subset, main):
    """ Returns a list of the indexes of the first value of matches. """
    results = []
    for i in xrange(len(main)):
        if main[i:i+5] == subset:
              results.append(i)
    return results

# values borrowed from @JonClements
subset = [True, True, False, True, True]
main = [False, True, False, True, True, True, False, True, True, False, True, False, True]

>>> find_x_in_y(subset, main)
... [4]

@abarnertファイン、これは実際に非常に効率的なアプローチです。

非常に効率的で、bool リスト全体を bitarray に変換し、ネイティブ検索メソッドを実行します。 

from bitarray import bitarray

def find_x_in_y(subset, main):
    subarray = bitarray(subset)
    mainarray = bitarray(main)
    return [int(i) for i in mainarray.itersearch(subarray)]

timeit結果：

Length of main:                     10      100     1000    10000   100000   1000000

returning _all_ matches:
# number of matches                  1       10      100     1000    10000    100000
# sliding window approach     (0.00059, 0.00502, 0.04194, 0.26211, 2.55554, 26.21962)
# bitarray approach           (0.00028, 0.00072, 0.00484, 0.02926, 0.2822,   2.93676)

returning first match:
# sliding window approach     (0.00034, 0.00034, 0.00034, 0.00021, 0.00026,  0.00059)
# bitarray approach           (0.00017, 0.00017, 0.00016, 0.00011, 0.00014,  0.00049)
# joined string approach      (0.00134, 0.00721, 0.06244, 0.39224, 4.21628, 39.63207)
于 2012-11-01T23:23:57.943 に答える