5

我正在尝试生成给定字符串中所有重叠的 n 长度子字符串的列表。

例如，对于 n of6和字符串，"hereismystring"我将生成 list ["hereis", "ereism", "reismy", ..., "string"]。我现在使用的简单代码如下所示：

n = 6
l = len(string)
substrings = [string[i:(i + n)] for i in xrange(l - n + 1)]

很容易。问题是，我想加快速度（我有很多很长的字符串）。Python中有更快的技术吗？考虑到 Python 的字符串例程无论如何都在 C 语言中，是否会下降到 Cython 的帮助？

作为参考，对于 500 长度的字符串和 30 的 n，此技术在我的机器（新的 Macbook Pro）上大约需要 100us。

我在这里先向您的帮助表示感谢！

4

2 回答 2

2

从哪种 Python 编码技术最快的问题上退后一步，我会以不同的方式处理这个问题。由于所有字符串的长度相同，并且都来自单个源字符串，为什么不直接使用字符范围，而不是将它们转换为正确的字符串呢？您将避免大量分配和复制，但您必须调整代码以知道每个“字符串”的长度为 n 个字符。

换句话说，当您想使用子字符串时，只需直接从源字符串中读取范围。您将尽可能快地从缓存中提取所需的字符。您可以将“子字符串”仅表示为源字符串的偏移量。

有时，如果您想要超快的性能，您必须放弃熟悉的数据结构。只是一个想法。

于 2013-01-28T05:54:36.683 回答
1

怎么样：

>>> d = deque("hereismystring")
>>> s = ''.join(d)[:6]
>>> while not len(s) % 6:
...    print s
...    _ = d.popleft()
...    s = ''.join(d)[:6]
... 
hereis
ereism
reismy
eismys
ismyst
smystr
mystri
ystrin
string
>>>

我相信双端队列是 O(1) 而列表是 O(n)

于 2013-01-28T06:13:47.390 回答