如何高效地创建子字符串

Question

如何高效地创建子字符串

5

给定一个字符串，通常是一个句子，我想提取长度为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

- Marcel Braasch

你的示例字符串的期望输出是什么？ - defladamouse

1

len(k)==size检查可以被消除 - 唯一可能失败的方式是如果您从句子末尾开始切片，但这可以通过减少for i循环的范围来更好地处理。此外，您真的需要所有子字符串同时存在于列表中吗？通过在生成器函数中逐个生成它们，内存使用量可以大大减少。 - jasonharper

内存对我来说不是问题，时间才是。嗯，好的，考虑一下边界…… - Marcel Braasch

哇，我删掉了长度检查并将其移动到单词级别，并寻找正确的边界。速度翻倍了。正在修改代码。 - Marcel Braasch

嗯，{end-start} 秒 不正确。你能修正一下并且展示一下两种解决方案的时间吗？ - Kelly Bundy

2个回答

0

我相信这样做就可以了：

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

- defladamouse

你能否证明这确实比OP的方法更快？它看起来很相似，具有相同的O(n^3)值。 - Matthew Barlowe

它的速度与我的第二种方法完全相同（尝试了10次运行，每次值略有不同）。 - Marcel Braasch

从理论角度来看，我不确定有太多需要优化的地方。这可能更多是一个库的问题。 - Marcel Braasch

如果你真的在寻求性能，最好还是用 C 编写代码，然后将其作为 Python 的包装器。 - defladamouse

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Jérôme Richard · Accepted Answer

我认为无法改进算法，但您可以微调该函数：

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 引入了赋值表达式，这对于性能来说非常有用。因此，如果您可以使用较新版本，则可以编写以下代码：

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 解释器上（主要是因为创建 / 引用计数 / 删除变量大小的整数对象）。