Структура данных для эффективного доступа к случайным фрагментам данных из вызова API

Question

Мы пишем библиотеку для API, которая использует упорядоченный поток данных.Через этот Api вы можете делать вызовы данных по частям.Например, если я хочу элементы 15-25, я могу сделать вызов API для этого.

Библиотека, которую мы пишем, позволит клиенту также вызывать любой фрагмент данных, но мы хотим, чтобы библиотека быламаксимально эффективно с этими вызовами API, насколько это возможно.Поэтому, если я уже запросил пункты 21-30, я больше не хочу запрашивать эти отдельные элементы данных.Если кто-то спрашивает у библиотеки 15-25, мы хотим вызвать API для 15-20.Нам нужно будет найти, какие данные у нас уже есть, и избежать повторного запроса этих данных.

Какая структура данных наиболее эффективна для хранения результатов этих вызовов API?Наборы данных не будут большими, поэтому время поиска в локальной памяти не так уж и много.Мы ищем простоту и чистоту кода.Есть несколько очевидных ответов на эту проблему, но мне любопытно, есть ли у кого-нибудь из ботаников структуры данных элегантное решение, которое не приходит в голову.

Для справки мы пишем код на Python, но на самом деле просто ищемдля структуры данных, которая решает эту проблему элегантно.

Answer 1

Каноническая структура данных, часто используемая для решения этой проблемы, представляет собой интервальное дерево.(См. эту статью в Википедии .) Ваша проблема может заключаться в том, что вам необходимо знать, какие отправленные вами сообщения (какие интервалы) пересекаются с тем, что вы пытаетесь отправить, - затем вырежьте интервалы,пересекаются с тем, что вы пытаетесь отправить (что является линейным временем по отношению к количеству интервалов, которые вы обнаружите, перекрываются), и вы там.Тем не менее, «дополненное» дерево на полпути вниз по статье в Википедии выглядит проще в реализации, поэтому я буду придерживаться этого.Должна быть "log N" временная сложность, амортизация или нет.

Answer 2

Я бы использовал сбалансированное двоичное дерево (например, http://pypi.python.org/pypi/bintrees/0.4.0) для отображения начала -> (конец, данные). Когда поступает новый запрос для диапазона [b, e), выполните поиск для b ( затем следует перейти к предыдущей записи, если b! = key), выполнить другой поиск e (также шаг назад), отсканировать все записи между результирующими ключами, опустить недостающие диапазоны и объединить все интервалы из кэша и новые данные в один интервал. , За N интервалов в кэше вы получите амортизированную стоимость O (log-N) за каждое обновление кэша.

Вы также можете просто сохранить список (начало, конец, данные) кортежей, упорядоченный по началу, и использовать bisect_right для поиска. Стоимость: O (N = количество кэшированных интервалов) для каждого обновления в худшем случае, но если клиенты стремятся запрашивать данные в возрастающем порядке, обновление кэша будет O (1).

Поиск в кэше в любом случае - O (log-N).