6

次のような多くの文字列を含む巨大なリストがあります。

['xxxx','xx','xy','yy','x',......]

現在、別の文字列内に存在するすべての文字列を削除する効率的な方法を探しています。たとえば、'xx' 'x' は 'xxxx' に収まります。

データセットが膨大なので、他に効率的な方法はないかと考えていました

if a in b:

完全なコード: おそらくいくつかの最適化部分を含む:

for x in range(len(taxlistcomplete)):
if delete == True:
    x = x - 1
    delete = False
for y in range(len(taxlistcomplete)):
    if taxlistcomplete[x] in taxlistcomplete[y]:
        if x != y:
            print x,y
            print taxlistcomplete[x]
            del taxlistcomplete[x]
            delete = True
            break
    print x, len(taxlistcomplete)

コードの更新版:

for x in enumerate(taxlistcomplete):
if delete == True:
    #If element is removed, I need to step 1 back and continue looping.....
    delete = False
for y in enumerate(taxlistcomplete):
    if x[1] in y[1]:
        if x[1] != y[1]:
            print x[1],y[1]
            print taxlistcomplete[x]

            del taxlistcomplete[x[0]]
            delete = True
            break
print x, len(taxlistcomplete)

列挙型で実装されましたが、これがより効率的であり、削除ステップを実装する方法があるかどうか疑問に思っているので、検索することも少なくなります。

ほんの短い考え...

基本的に私が見たいのは...

要素がリスト内の他の要素と一致しない場合、これをファイルに書き込みます。したがって、「xxxxx」が「xx」、「xy」、「wfirfj」などにない場合... 印刷/保存

とにかくこれ以上最適化できるとは思わないので、新しいシンプルなバージョン...

print 'comparison'

file = open('output.txt','a')

for x in enumerate(taxlistcomplete):
    delete = False
    for y in enumerate(taxlistcomplete):
        if x[1] in y[1]:
            if x[1] != y[1]:
                taxlistcomplete[x[0]] = ''
                delete = True
                break
    if delete == False:
        file.write(str(x))
4

4 に答える 4

9

x in <string>高速ですが、リスト内の他のすべての文字列に対して各文字列をチェックするには O(n^2) 時間がかかります。比較を最適化して数サイクルを削減する代わりに、別のデータ構造を使用して、各文字列を 1 回のルックアップでチェックできるようにすることで、大幅な節約を実現できます。

「プレフィックス ツリー」(またはトライ) と呼ばれるデータ構造があり、文字列が以前に見た文字列のプレフィックスであるかどうかを非常に迅速に確認できます。ググってください。別の stringの途中で発生する文字列にも関心があるためx、形式などのすべての部分文字列にインデックスを付けますx, x[1:], x[2:], x[3:],(したがってn、長さの文字列の部分文字列のみn)。つまり、位置 0、1、2 などで開始し、文字列の末尾まで続く部分文字列にインデックスを付けます。そうすれば、新しい文字列がインデックス内の何かの最初の部分であるかどうかを確認できます。

次に、次のように O(n) 時間で問題を解決できます。

  1. 弦の長さが短い順に並べます。これにより、文字列がまだ見たことのないものの部分文字列になる可能性がなくなります。長さだけを気にするので、バケット ソートは O(n) 時間で実行できます。

  2. 空のプレフィックス ツリーから始めて、順序付けられた文字列のリストをループします。各 string についてx、プレフィックス ツリーを使用して、それが以前に見た文字列の部分文字列であるかどうかを確認します。x, x[1:], x[2:]そうでない場合は、その部分文字列などをプレフィックス ツリーに追加します。

長いリストの途中での削除は非常にコストがかかるため、保持したい文字列を新しいリストに集めると、さらに高速化されます (実際の文字列はコピーされず、参照のみがコピーされます)。完了したら、元のリストとプレフィックス ツリーを削除します。

それが複雑すぎる場合は、少なくともすべてをすべてと比較しないでください。文字列をサイズ順に (降順で) 並べ替え、各文字列をその前の文字列とのみ照合します。これにより、わずかな労力で 50% のスピードアップが得られます。また、その場で削除するのではなく、新しいリストを作成 (またはすぐにファイルに書き込む) してください。

于 2012-05-01T15:23:11.357 に答える
2

'$'元の文字列のいずれにも含まれていないことが保証されている文字 (私の例で使用します) を識別できると仮定した場合の簡単な方法を次に示します。

result = ''
for substring in taxlistcomplete:
    if substring not in result: result += '$' + substring
taxlistcomplete = result.split('$')

これは、部分文字列検索に 1 つの大きな文字列を作成するだけで、部分文字列検索に対する Python の内部最適化を活用します:)

于 2012-05-01T16:22:37.977 に答える
0

リスト内包表記（注）を使用するinことは、問題を解決するための最も速く、よりPythonicな方法です。

[element for element in arr if 'xx' in element]
于 2012-05-01T15:09:34.913 に答える
0

これが私の提案です。まず、要素を長さで並べ替えます。明らかに文字列が短いほど、別の文字列の部分文字列である可能性が高くなります。次に、2 つの for ループがあり、リストを実行して、el が部分文字列であるリストからすべての要素を削除します。最初の for ループは、各要素を 1 回だけ渡すことに注意してください。

最初にリストをソートすることにより、リスト内の要素の順序を破棄します。したがって、順序が重要な場合、このソリューションは使用できません。

編集。リストに同一の要素はないと思います。el == el2 の場合は、同じ要素だからです。

a = ["xyy", "xx", "zy", "yy", "x"]
a.sort(key=len)

for el in a:
    for el2 in a:
        if el in el2 and el != el2:
            a.remove(el2)
于 2012-05-01T15:58:22.873 に答える