Структура данных для строковых индексов?

Question

Я ищу структуру данных для строковых индексов (UTF-8), которая была бы оптимизирована для запросов диапазона и использования пространства. Спасибо!

Разработка: У меня есть список строк произвольной длины utf-8, которые мне нужно индексировать. Я буду использовать только диапазон запросов.

Пример: У меня есть строки - яблоко, обезьяна, черный, круто, темно.

Запрос будет выглядеть примерно так: «получить от 2 до 3 элементов в порядке убывания» или «получить строки, начинающиеся с« ap »

Answer 1

Так как вы упомянули «относительно статический», простой отсортированный массив будет делать все, что вы хотите, и он сильно оптимизирован как с точки зрения пространства, так и времени.

«получить от 2 до 3 элементов в порядке убывания»просто поиск соответствующих индексов массива.

"получить строки, начинающиеся с 'ap'", можно сделать с помощью двоичного поиска.Поиск останавливается на или непосредственно перед первой строкой, начинающейся с 'ap', и с этого момента вы просто просматриваете, пока не найдете все такие строки.

Answer 2

Вы проверяли Пытается ?

Структура должна соответствовать тому, что вам нужно - и диапазон, и «начало с» должны быть простыми, плюс потребление памяти также хорошо.

Answer 3

Мне нравится ответ Касабланки: поскольку ваши данные относительно статичны, отсортированный список должен быть в порядке.

Если вам нужно что-то более легко обновляемое, вы можете работать с blist.sortedlist .

Вы могли бы даже работать с BTrees ZODB, которые уже включают в себя большую часть необходимой вам функциональности (то есть поиск по диапазону).