如何有效地创建子字符串

Question

给定一个字符串，通常是一个句子，我想提取所有长度为 3, 4, 5, 6 的子字符串。如何仅使用 Python 的标准库有效地实现此目的？这是我的方法，我正在寻找一种更快的方法。在我看来，无论哪种方式，三个外部循环似乎都是不可避免的，但也许有一个 itertools 左右的低级优化解决方案。

import time def naive(test_sentence, start, end): grams = [] for word in test_sentence: for size in range(start, end): for i in range(len(word)): k = word[i:i+size] if len(k)==size: grams.append(k) return grams n = 10**6 start, end = 3, 7 test_sentence = "Hi this is a wonderful test sentence".split(" ") start_time = time.time() for _ in range(n): naive(test_sentence, start, end) end_time = time.time() print(f"{end-start} seconds for naive approach")

naive() 的输出：

['thi', 'his', 'this', 'won', 'ond', 'nde', 'der', 'erf', 'rfu', 'ful', 'wond', 'onde', 'nder', 'derf', 'erfu', 'rful', 'wonde', 'onder', 'nderf', 'derfu', 'erful', 'wonder', 'onderf', 'nderfu', 'derful', 'tes', 'est', 'test', 'sen', 'ent', 'nte', 'ten', 'enc', 'nce', 'sent', 'ente', 'nten', 'tenc', 'ence', 'sente', 'enten', 'ntenc', 'tence', 'senten', 'entenc', 'ntence']

第二个版本：

def naive2(test_sentence,start,end): grams = [] for word in test_sentence: if len(word) >= start: for size in range(start,end): for i in range(len(word)-size+1): grams.append(word[i:i+size]) return grams

Answer 1

我相信这会做到：

test_sentence = "Hi this is a wonderful test sentence".split()

lengths = [3, 4, 5, 6]

result = []
for t in test_sentence:
    for l in lengths:
        if len(t) >= l:
            start = 0
            while start + l <= len(t):
                result.append(t[start:start+l])
                start += 1

Answer 2

好吧，我认为这不可能改进算法，但你可以微优化函数：

def naive3(test_sentence,start,end):
    rng = range(start,end)
    return [word[i:i+size] for word in test_sentence
                           if len(word) >= start
                           for size in rng
                           for i in range(len(word)+1-size)]

Python 3.8 引入了对性能非常有用的 assignment Expressions。因此，如果你可以使用最新版本，那么你可以这样写：

def naive4(test_sentence,start,end):
    rng = range(start,end)
    return [word[i:i+size] for word in test_sentence 
                           if (lenWord := len(word)+1) > start
                           for size in rng
                           for i in range(lenWord-size)]

以下是性能结果：

naive2: 8.28 µs ±  55 ns per call
naive3: 7.28 µs ± 124 ns per call
naive4: 6.86 µs ±  48 ns per call    (20% faster than naive2)

请注意，naive4 的一半时间用于创建 word[i:i+size] 字符串对象，其余时间主要用于 CPython 解释器（主要是由于 creation/reference-counting/deletion 个可变大小的整数对象）。

如何有效地创建子字符串

How to create substrings efficiently

python

performance