1

このスクリプトは、Pythonで文字列の類似性を計算するために作成しました。それをもっと速く実行させる方法はありますか？

tries = input()
while tries > 0:
    mainstr = raw_input()
    tot = 0
    ml = len(mainstr)
    for i in xrange(ml):
        j = 0
        substr = mainstr[i:]
        ll = len(substr)
        for j in xrange(ll):
            if substr[j] != mainstr[j]:
                break
            j = j + 1
        tot = tot + j
    print tot
    tries = tries - 1

編集：いくつかの最適化を適用した後、これはコードですが、それだけでは十分ではありません！

tries = int(raw_input())
while tries > 0:
    mainstr = raw_input()
    tot = 0
    ml = len(mainstr)
    for i in xrange(ml):
        for j in xrange(ml-i):
            if mainstr[i+j] != mainstr[j]:
                break
            j += 1
        tot += j
    print tot
    tries = tries - 1

編集2：コードの3番目のバージョン。それはまだ行きません！

def mf():
    tries = int(raw_input())
    for _ in xrange(tries):
        mainstr = raw_input()
        tot = 0
        ml = len(mainstr)
        for i in xrange(ml):
            for j in xrange(ml-i):
                if mainstr[i+j] != mainstr[j]:
                    break
                j += 1
            tot += j
        print tot
mf()
4

4 に答える 4

2

ループ内のメモリ割り当てをスキップできます。substr = mainstr[i:]不必要に新しい文字列を割り当てます。でのみ使用しますsubstr[j] != mainstr[j]。これは、と同等であるmainstr[i + j] != mainstr[j]ため、を作成する必要はありませんsubstr。

メモリの割り当てはコストがかかるため、タイトなループでは避けたほうがよいでしょう。

于 2012-07-20T10:43:04.187 に答える
2

i = mainstr.find(mainstr[0], i+1)すべてをチェックする代わりにを使用すると、一定の係数で改善できますi。i==0の特殊なケースも役立つ可能性があります。

コードを関数内に配置します。また、一定の要因で物事をスピードアップする可能性があります。

各ステップでのfor ... else: j += 1増分を回避するために使用します。j

文字列のすべてのサフィックスを比較するという事実を利用する、O（n ** 2）アルゴリズムよりも優れたものを見つけてください。

最も単純なC実装は、CPythonよりも100倍高速であり（Pypyは10〜30倍高速です）、次の課題に合格します。

import os

def string_similarity(string, _cp=os.path.commonprefix):
    return sum(len(_cp([string, string[i:]])) for i in xrange(len(string)))

for _ in xrange(int(raw_input())):
    print string_similarity(raw_input())

上記の最適化では数パーセントの改善しか得られず、CPythonでの課題に合格するには不十分です（Pythonの制限時間はわずか8倍です）。

（CPythonでは）次の間にほとんど違いはありません。

def string_similarity(string):
    len_string = len(string)
    total = len_string # similarity with itself
    for i in xrange(1, len_string):
        for n, c in enumerate(string[i:]):
            if c != string[n]:
                break
        else:
            n += 1

        total += n
    return total

と：

def string_similarity(string):
    len_string = len(string)
    total = len_string # similarity with itself
    i = 0
    while True:
        i = string.find(string[0], i+1)
        if i == -1:
            break
        n = 0
        for n in xrange(1, len_string-i):
            if string[i+n] != string[n]:
                break
        else:
            n += 1

        total += n
    return total
于 2012-07-20T11:16:32.080 に答える
1

このような単純な数値スクリプトの場合、実行する必要があるのは2つだけです。

  • PyPyを使用します（複雑な依存関係はなく、非常に高速になります）

  • ほとんどのコードを関数に入れます。これにより、CPythonとPyPyの両方の処理が大幅に高速化されます。それ以外の：

    some_code

行う：

def main():
    some_code

if __name__ == '__main__':
    main()

それはほとんどそれです。

乾杯、フィジャル

于 2012-07-21T16:48:15.670 に答える
0

これが私のものです。テストケースに合格しますが、絶対的に最速ではない場合があります。

import sys

def simstring(string, other):
    val = 0
    for l, r in zip(string, other):
        if l != r:
            return val
        val += 1
    return val


dsize = sys.stdin.readline()

for i in range(int(dsize)):
    ss = 0
    string = sys.stdin.readline().strip()
    suffix = string
    while suffix:
        ss += simstring(string, suffix)
        suffix = suffix[1:]
    sys.stdout.write(str(ss)+"\n")
于 2012-07-20T14:14:25.457 に答える