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：代码的第三个版本。还是不行！

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

如果你使用i = mainstr.find(mainstr[0], i+1)而不是检查 all ，你可以通过一个常数因子来改进它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 回答
2

您可以跳过循环内的内存分配。substr = mainstr[i:]不必要地分配一个新字符串。你只在 中使用它substr[j] != mainstr[j]，相当于mainstr[i + j] != mainstr[j]，所以你不需要构建substr.

内存分配很昂贵，因此您需要在紧密循环中避免它们。

于 2012-07-20T10:43:04.187 回答
1

对于这样简单的数字脚本，您只需要做两件事：

  • 使用 PyPy（它没有复杂的依赖关系，而且速度会大大提高）

  • 将大部分代码放在一个函数中。这极大地加快了 CPython 和 PyPy 的速度。代替：

    一些代码

做：

def main():
    some_code

if __name__ == '__main__':
    main()

差不多就是这样。

干杯，菲亚尔

于 2012-07-21T16:48:15.670 回答
0

Here's mine. It passes the test case, but may not be the absolute fastest. 

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 回答