5

特定の文字列で重複するすべてのn長の部分文字列のリストを生成しようとしています。

たとえば、n6と文字列の場合"hereismystring"、リストを生成します["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にドロップダウンすることはまったく役に立ちますか？

参考までに、このテクニックは、私のマシン（新しいMacbook Pro）で500usの長さの文字列と30のnに対して約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（n）であるのに対し、dequeはO（1）だと思います

于 2013-01-28T06:13:47.390 に答える