Можно ли сортировать в 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 ():

 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?

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:]) 

работает почти так же быстро, но имеет проблемы с памятью, о которых вы упоминаете.

  • Доступ к переменным функции caller в Python
  • time.sleep () Эквивалент на Tkinter
  • Использование класса в качестве типа подсказки для аргументов в его методах
  • SyntaxError: неожиданный EOF при разборе
  • Как я могу написать asyncio сопрограммы, которые, возможно, действуют как обычные функции?
  • Распечатайте целое число или float с n десятичными знаками
  • данные сокетов процесса, которые заканчиваются разрывом строки
  • команда для обратной функции ERF в python
  • Отправить изображение через сокет в виде двоичных данных
  • Unorderable Types: int () <str ()
  • UnicodeEncodeError при использовании функции компиляции
  • Python - лучший язык программирования в мире.