strcmp для Python или как эффективно сортировать подстроки (без копирования) при построении массива суффиксов

Question

Вот очень простой способ построить массив суффиксов из строки в python:

def sort_offsets(a, b):
    return cmp(content[a:], content[b:])

content = "foobar baz foo"
suffix_array.sort(cmp=sort_offsets)
print suffix_array
[6, 10, 4, 8, 3, 7, 11, 0, 13, 2, 12, 1, 5, 9]

Однако «content [a:]» создает копию содержимого, котораястановится очень неэффективным, когда контент становится большим.Поэтому мне интересно, есть ли способ сравнить две подстроки без необходимости их копировать.Я пытался использовать встроенный буфер, но это не сработало.

Answer 1

Функция buffer не копирует всю строку, но создает объект, который ссылается только на исходную строку. Если воспользоваться предложением Interjay, это будет:

suffix_array.sort(key=lambda a: buffer(content, a))

Answer 2

Я не знаю, есть ли быстрый способ сравнения подстрок, но вы можете сделать свой код намного быстрее (и проще), используя key вместо cmp:

suffix_array.sort(key=lambda a: content[a:])

Это создаст подстроку только один раз для каждого значения.

Редактировать: Возможным недостатком является то, что для подстрок потребуется O (n ^ 2) памяти.

Answer 3

+ 1 за очень интересную задачу! Я не вижу никакого очевидного способа сделать это напрямую, но мне удалось добиться значительного ускорения (порядка 100 000 символьных строк) вместо использования следующей функции сравнения:

def compare_offsets2(a, b):
    return (cmp(content[a:a+10], content[b:b+10]) or
            cmp(content[a:], content[b:]))

Другими словами, начните со сравнения первых 10 символов каждого суффикса; только если результат этого сравнения равен 0, что свидетельствует о том, что у вас есть совпадение для первых 10 символов, вы продолжаете сравнивать все, что вам достаточно.

Очевидно, что 10 может быть чем угодно: экспериментируйте, чтобы найти лучшее значение.

Эта функция сравнения также является хорошим примером того, что нелегко заменить ключевой функцией.

Answer 4

Вы можете использовать тип расширения blist , который я написал. A blist работает как встроенный list, но (среди прочего) использует копирование при записи, так что для взятия фрагмента требуется O (log n) времени и памяти.

from blist import blist

content = "foobar baz foo"
content = blist(content)
suffix_array = range(len(content))
suffix_array.sort(key = lambda a: content[a:])
print suffix_array
[6, 10, 4, 8, 3, 7, 11, 0, 13, 2, 12, 1, 5, 9]

Мне удалось создать суффикс_арриса из случайно сгенерированной строки длиной 100 000 символов менее чем за 5 секунд, включая генерацию строки.