Можно ли сортировать в python 3 с использованием сопоставлений строк в буфере (на основе указателей)?
Рассмотрим проблему сортировки всех суффиксов строки, где суффикс является подстрокой от некоторого индекса i до конца строки. Вместо создания списка отсортированных суффиксов мы можем создать список индексов, соответствующих начальным точкам отсортированных суффиксов. Тогда мы можем сделать что-то вроде этого:
text = ... some text string ... sortedIndices = sorted([i for i in range(len(text))], key = lambda i: text[i:]) Это работает для коротких строк, но если строка достаточно длинная, у нас закончится память, потому что ключевая функция приводит к копированию суффикса, и все ключи сгенерированы с самого начала. В python 2.7 есть пятно вокруг этого, а именно, функция buffer ():
- В чем разница между __iter__ и __getitem__?
- Является ли generator.next () видимым в python 3.0?
- Добавление динамических методов тестирования с помощью декоратора
- PyCrypto - Как работает вектор инициализации?
- Python 3.2 пропускает строку в csv.DictReader
sortedIndices = sorted([i for i in range(len(text))], key = lambda i: buffer(text, i))
В этом случае ключ – это просто указатель на текстовую строку, поэтому требуемая общая память намного меньше (O (n) vs O (n * n)). Следовательно, он будет работать с гораздо более длинными строками. Это прекрасно работает в версии 2.7, но в 3.x функция buffer () удалена в пользу памяти, которая в отличие от буфера не работает – AFAIK – поддерживает сопоставление строк на основе указателей (т. Е. Без использования метода tobytes, который создает копию строки). Мой вопрос: есть ли способ сделать что-то подобное в python 3.x?
- Подсчет числа дней недели между двумя датами
- Найти max (и min) на интервале перемещения с помощью python
- Поддержка нескольких версий для доктрин Python
- Подождите, пока stdout на Popen
- pprint сортирует dicts, но не устанавливает?
- Как удалить индекс из созданного Dataframe в Python?
- Возможно ли установить приоритет блокировки?
- Ленько транспонировать список в Python
2 Solutions collect form web for “Можно ли сортировать в python 3 с использованием сопоставлений строк в буфере (на основе указателей)?”
Мне кажется, что память не делает этого. На самом деле это может быть хорошо.
Вы все равно можете сделать это с помощью класса, который в любом случае более объектно ориентирован:
#!/usr/local/cpython-3.3/bin/python import sys import functools @functools.total_ordering class Suffix_comparison: def __init__(self, string, starting_position): self.string = string self.starting_position = starting_position def __lt__(self, other): if self.string[self.starting_position:] < other.string[other.starting_position]: return True else: return False def __eq__(self, other): if self.string[self.starting_position:] == other.string[other.starting_position]: return True else: return False def __str__(self): return self.string __repr__ = __str__ def main(): list_ = [] for line in sys.stdin: stripped_line = line.rstrip('\n') list_.append(Suffix_comparison(stripped_line, 5)) list_.sort() for line in list_: print(line) main()
Ну, я тоже работаю над этой проблемой.
И я только что перешел с Python 2.7 на 3. WinPython, у которого есть очень классный редактор под названием Spyder.
Насколько я могу судить, объекты памяти совершенно бесполезны.
Я также попробовал функцию itertools.islice, но не мог понять, как это сделать.
Поэтому я решил написать собственную небольшую функцию сравнения:
def suffixArrayCompare (x, y): глобальный globalText
i = 0 end = len(globalText) - max(x, y) while i < end: if globalText[x+i] < globalText[y+i]: return -1 elif globalText[x+i] > globalText[y+i]: return 1 i += 1 return 0
И это называется так:
indexes = sorted(indexes, key = functools.cmp_to_key(lambda x,y:suffixArrayCompare(x, y)))
Это так же быстро, как я могу сделать это. Это все еще не так быстро, как буферный путь в 2.7, но не слишком далеко. И он ничего не копирует.
Эта
#indexes = sorted(indexes, key = lambda x: globalText[x:])
работает почти так же быстро, но имеет проблемы с памятью, о которых вы упоминаете.