0

これが私のコードで、いくつかのメモがあります：

import re
import itertools

nouns = ['bacon', 'cheese', 'eggs', 'milk', 'houses', 'dog']
CC = ['and', 'or']

def search_and_replace(text):
    noun_patt = r'\b(' + '|'.join(nouns) + r')\b'
    CC_patt = r'\b(' + '|'.join(CC) + r')\b'
    patt = r'({0},? )+{1} {0}'.format(noun_patt, CC_patt)

    searched = re.search(patt, text) 
    phrase = searched.group()
    print "Check re.search match object exists:", phrase # "bacon, eggs, and milk" prints

    perm_phrase = itertools.permutations(phrase)
    print "Check permutated list exists:", perm_phrase # permutation object position in memory prints

    perm_phrase_list = list(perm_phrase)
    print "Permutated object as list:", perm_phrase_list # THIS IS WHERE MEMORY MAXES AND COMPUTER FREEZES!!!
    # So print does not happen.

    return perm_phrase_list

def main():
    text = "I like bacon, eggs, and milk"
    print search_and_replace(text)


if __name__ == '__main__':
    main()

コード内のメモからわかるように、コード行はperm_phrase_list = list(perm_phrase)大量の物理メモリを占有するため、コンピューターがフリーズします。(コードの各行の後に印刷して、問題がどこから始まるかを把握しました。通常、関数内では印刷しません)。順列からこのリストを作成しようとした時点で、なぜこれが起こるのだろうか?

このコードで permutations メソッドを使用できれば非常に便利です! それ以外の場合は、リスト内の要素の並べ替えに相当するものを作成する必要があります。

私はPython 2.7を使用しています

4

3 に答える 3

3

に文字列をフィードしていますitertools.permutations()。これは、可能なすべての文字の組み合わせに対して順列を生成することを意味します。

>>> phrase = re.search(patt, text).group()
>>> phrase
'bacon, eggs, and milk'
>>> next(itertools.permutations(phrase))
('b', 'a', 'c', 'o', 'n', ',', ' ', 'e', 'g', 'g', 's', ',', ' ', 'a', 'n', 'd', ' ', 'm', 'i', 'l', 'k')

フレーズの長さは 21 文字なので、21 文字になります。(階乗) == 51090942171709440000 の異なる順列。それぞれ 21 文字のタプルです。

このようなタプルの 1 つは、私の 64 ビット Mac では、合計 21 * 38 + 224 バイト = 1022 バイトのメモリを必要とします。文字はインターンされているため、実際にはタプルごとにメモリが必要であり、文字の 768 バイトは無視できます。つまり、 51090942171709440000 * 224 バイトはほぼ10 ゼビバイトです。

それはたくさんの思い出です。

おそらく、フレーズの可能な 21 文字順列をすべて生成する必要はありませんでした。メソッドで何をしたいのかを再考し、生成する出力を減らし、生成された組み合わせを 1 つずつループするだけで、それらすべてをリスト オブジェクトに展開しようとしない必要があります。

一致した単語の順列を作成したかったのではないかと思いますが、正規表現では個々の一致した単語が得られません。グループのキャプチャを繰り返すことはできません。全体をキャプチャしてから分割する必要があります。

noun_patt = r'\b(?:' + '|'.join(nouns) + r')\b'
CC_patt = r'\b(' + '|'.join(CC) + r')\b'
patt = r'((?:{0},? )+){1} ({0})'.format(noun_patt, CC_patt)

結果が乱雑になるの(?:..)を避けるために、グループは非キャプチャ グループです。

これにより、2 つのキャプチャ グループが得られます。1 つはコンマ区切りの名詞で、もう 1 つは最後の名詞です。空白とコンマで最初を分割します。

searched = re.search(patt, text) 
nouns = filter(None, re.split(r',\s*', searched.group(1))) + [searched.group(3)]

そして今、これらの名詞を並べ替えることができます:

for comb in itertools.permutations(nouns):
    # do something with this specific permutation

サンプルの結果は名詞が 3 つしかないため、6 つの順列を安全にリストに変換できます。

>>> nouns
['bacon', 'eggs', 'milk']
>>> list(itertools.permutations(nouns))
[('bacon', 'eggs', 'milk'), ('bacon', 'milk', 'eggs'), ('eggs', 'bacon', 'milk'), ('eggs', 'milk', 'bacon'), ('milk', 'bacon', 'eggs'), ('milk', 'eggs', 'bacon')]

おそらく、これらを文に再結合できます。

>>> cc = searched.group(2)
>>> for comb in itertools.permutations(nouns):
...     print ', '.join(comb[:-1]), cc, comb[-1]
... 
bacon, eggs and milk
bacon, milk and eggs
eggs, bacon and milk
eggs, milk and bacon
milk, bacon and eggs
milk, eggs and bacon
于 2013-09-23T19:15:55.920 に答える
1

コード行はperm_phrase_list = list(perm_phrase)、リストを作成しようとします。サイズが非常に大きい場合、大量のメモリが必要になる可能性があるため、これを行うべきではありません。結果を「ダンプ」するには、ジェネレーターを反復処理する必要があります。

for item in perm_phrase: print item #doesn't build the list
于 2013-09-23T19:02:17.883 に答える
1

まず、すべての値をリストに格納する正当な理由はありません。リストと同じくらい簡単に反復子を反復処理できます。だから、ただ戻ってperm_phraseください。値を出力したいだけの場合は、次のように記述します。

def main():
    text = "I like bacon, eggs, and milk"
    for perm in search_and_replace(text):
        print perm

repr(perm)明らかに、括弧やコンマを追加したり、印刷してリストのように見せたりするなど、必要に応じてフォーマットを設定できます。

イテレータを反復処理することで、すべてを一度に生成するのではなく、一度に 1 つの値のみを生成するため、メモリ ストレージの問題は発生しません。(また、順列ごとにコードを「パイプライン化」すること、キャッシュ ヒットを改善することなどによって、速度が向上する場合もあります。)

しかし、その間、あなたの質問は、文字の (21! = 51090942171709440000) 順列ではなく、単語の (4! = 24) 順列が必要だと言っています。splitそのためには、ある時点で文字列を単語に変換する必要があります。例えば：

perm_phrase = itertools.permutations(phrase.split())

これで、これらすべてを一度に簡単にメモリに収めることができます。ただし、一度にすべてをメモリに格納する正当な理由がない限り、イテレータを使用する方がよいでしょう。

于 2013-09-23T19:21:29.043 に答える