Можно ли сортировать в 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 ():
- Поставщик данных Python unittest
- input () vs sys.stdin.read ()
- Недействительный токен SyntaxError
- <__ main__. объект в 0x02C08790> PYTHON
- Python PIL: найдите размер изображения, не записывая его в виде файла
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?
- Разница между pip3 и python3 -m pip
- Python 3.4 многопроцессорная очередь быстрее, чем Pipe, неожиданно
- Несколько потоков с Autobahn, ApplicationRunner и ApplicationSession
- вернуть значение из одного скрипта 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:])
работает почти так же быстро, но имеет проблемы с памятью, о которых вы упоминаете.