用長字符串製作所有字符串片需要很長時間。它是至少 O（N^2）（因爲你創建了N個長度爲N的字符串，並且每一個都必須複製到內存中，從原始數據中獲取其源數據），這會破壞整體性能並使分類無關緊要。更不用說內存需求了！
，而不是實際切片串，在下以爲是爲了你用來創建循環串，在如何生成的字符串將比較順序i值 - 沒有實際創建它。事實證明這有點棘手。 （刪除/編輯這裏的一些東西，這是錯誤的。請參閱@TimPeters的回答）
我在這裏採取的方法是繞過標準庫 - 這使得很難（雖然不是不可能）比較這些字符串'按需' - 並做我自己的排序。這裏算法的自然選擇是基數排序，因爲我們無論如何都需要一次考慮一個字符串。
讓我們先設置。我正在編寫3.2版本的代碼，所以季節的味道。 （特別是在3.3以上，我們可以利用yield from。）我使用下面的進口：
from random import choice
from timeit import timeit
from functools import partial
我寫了一個通用的基數排序的功能是這樣的：
def radix_sort(values, key, step=0):
if len(values) < 2:
for value in values:
yield value
return
bins = {}
for value in values:
bins.setdefault(key(value, step), []).append(value)
for k in sorted(bins.keys()):
for r in radix_sort(bins[k], key, step + 1):
yield r
當然，我們並不需要是通用（我們的「 bin'只能用單個字符來標記，並且大概是確實是的意思是將該算法應用於字節的序列;）），但它並沒有傷害。也可能有可重用的東西，對吧？無論如何，這個想法很簡單：我們處理一個基本情況，然後根據關鍵函數的結果將每個元素放入一個「bin」中，然後我們按照已排序的bin順序從bin中取出值，遞歸排序每個元素bin的內容。
接口要求key(value, n)給我們nvalue的「基數」。所以對於簡單的情況，比如直接比較字符串，這可能很簡單，如lambda v, n: return v[n]。但是，這裏的想法是根據當前字符串中的數據（循環考慮）將索引與字符串進行比較。所以，讓我們定義一個關鍵：
def bw_key(text, value, step):
return text[(value + step) % len(text)]
現在招得到正確的結果是要記住，我們在概念上加入了我們並沒有實際創建的字符串的最後一個字符。如果我們考慮使用索引n製作的虛擬字符串，則由於我們如何迴轉 - 它的最後一個字符位於索引n - 1 - 並且一會兒的想法會向您證實這仍然適用於n == 0;）。 [但是，當我們向前捲動時，我們仍然需要保持字符串索引在界限內 - 因此是按鍵函數中的模運算。]
這是一個通用鍵函數，需要在text中傳遞給它它會在轉換value以供比較時參考。這就是functools.partial進來的地方 - 你也可以只用lambda，但這可以說是更乾淨，我發現它通常也更快。
不管怎麼說，現在我們可以很容易地編寫使用密鑰的實際變換：
def burroughs_wheeler_custom(text):
return ''.join(text[i - 1] for i in radix_sort(range(len(text)), partial(bw_key, text)))
# Notice I've dropped the square brackets; this means I'm passing a generator
# expression to `join` instead of a list comprehension. In general, this is
# a little slower, but uses less memory. And the underlying code uses lazy
# evaluation heavily, so :)
尼斯和漂亮。讓我們看看它是如何做的，我們會嗎？我們需要一個標準來比較它反對：
def burroughs_wheeler_standard(text):
return ''.join([i[-1] for i in sorted([text[i:] + text[:i] for i in range(len(text))])])
和定時程序：
def test(n):
data = ''.join(choice('abcdefghijklmnopqrstuvwxyz') for i in range(n)) + '$'
custom = partial(burroughs_wheeler_custom, data)
standard = partial(burroughs_wheeler_standard, data)
assert custom() == standard()
trials = 1000000 // n
custom_time = timeit(custom, number=trials)
standard_time = timeit(standard, number=trials)
print("custom: {} standard: {}".format(custom_time, standard_time))
通知我已經做了數學，決定對一些trials，負相關的長度test字符串。這應該將測試所用的總時間保持在相當窄的範圍內 - 對嗎？ ;）（錯了，當然，因爲我們建立的standard算法至少是O（N^2））
讓我們來看看它是如何做（*擊鼓聲*）：
>>> imp.reload(burroughs_wheeler)
<module 'burroughs_wheeler' from 'burroughs_wheeler.py'>
>>> burroughs_wheeler.test(100)
custom: 4.7095093091438684 standard: 0.9819262643716229
>>> burroughs_wheeler.test(1000)
custom: 5.532266880287807 standard: 2.1733253807396977
>>> burroughs_wheeler.test(10000)
custom: 5.954826800612864 standard: 42.50686064849015
哇。這有點可怕的跳躍。無論如何，正如你所看到的，新方法在短字符串上增加了大量的開銷，但是使實際的排序成爲瓶頸而不是字符串切分。:)
一個簡單的方法是寫一個代理類，需要一個字符串和偏移並實現比較，好像它是一個旋轉字符串。不過，你會爲小字符串引入大量的解釋器開銷。 – user2357112
如果您真的關注性能，請使用將源代碼編譯爲本機機器碼的語言。 – xis
@小哥蘇這裏的問題不在於語言，它是在解決問題的方法。 –