У меня есть следующие настройки:
У меня большое количество uuids (в настоящее время около 10 тыс., Но ожидается неограниченный рост - это идентификаторы пользователей) и функция f: id -> разреженный вектор с 32-разрядными целочисленными значениями (не нужно беспокоиться о точности) , Функция достаточно дорогая (не так уж и возмутительно, но, вероятно, порядка 100 мс для данного идентификатора). Размерность разреженных векторов следует считать бесконечной, так как новые измерения могут появляться со временем, но на практике вряд ли когда-либо превысят около 20k (и отдельные результаты f вряд ли будут иметь более нескольких сотен ненулевых значений ).
Я хочу эффективно поддерживать следующие операции:
- добавить новый идентификатор в коллекцию
- сделать недействительным существующий идентификатор
- получить сумму f (id) в O (изменения с момента последнего поиска)
т.е. Я хочу кэшировать сумму векторов так, чтобы это было разумно делать постепенно.
Один из вариантов - поддержка операции удаления идентификатора и обработка недействительности как удаления с последующим добавлением. Проблема с этим заключается в том, что нам необходимо отслеживать все старые значения f, которые дороги в пространстве. Мне потенциально нужно использовать много экземпляров такого рода кэшированной структуры, поэтому я бы хотел этого избежать.
Вероятная схема использования заключается в том, что новые идентификаторы добавляются с довольно постоянной частотой и часто сначала становятся недействительными. Идентификаторы, которые были признаны недействительными в последнее время, с гораздо большей вероятностью будут снова признаны недействительными, чем идентификаторы, которые оставались действительными в течение длительного времени, но в принципе старый идентификатор все еще может быть признан недействительным.
В идеале я не хочу делать это в памяти (или, по крайней мере, мне нужен способ, позволяющий мне эффективно сохранять результат на диск), поэтому идея, которая позволяет мне воспользоваться существующей реализацией БД какого-либо рода, была бы особенно ценится.