首页 > 求优化一个查找有序list的相同子串的算法

求优化一个查找有序list的相同子串的算法

输入:有序的list
要求:查找相同的子串,且相同子串必须是连续的,例如[1,2,1,2]就是1,2子串为相同的,但[1,2,3,1,2]就不是。
输出:[(字串,次数), ...]

现在的问题是这两重循环导致了算法为O(n^2),效率过于低下了,求优化~~~

from collections import defaultdict

def get_patterns(values):
    start = 0
    total_length = len(values)
    patterns = defaultdict(lambda : 1)
    while start < total_length:
        next_start = start + 2
        while next_start < total_length:
            ori_values = values[start:next_start]
            if ori_values == values[next_start:(next_start+len(ori_values))]:
                patterns[tuple(ori_values)] += 1
                next_start += len(ori_values)
            else:
                next_start += 1
        start += 1
    return list(patterns.iteritems())

if __name__ == '__main__':
    print get_patterns([1,2,3,5,1,2])
    print get_patterns([1,2,1,2,3,5])
    print get_patterns([1,2,1,2,1,3,5])

运行结果:

[]
[((1, 2), 2)]
[((1, 2), 2), ((2, 1), 2)]

已经搞定了,用numpy后性能嗖嗖嗖的,现在木有性能问题了……


如果你要输出具体所有的子串的话,效率很慢的。

【热门文章】
【热门文章】