Структура данных / Алгоритм управления неперекрывающимися диапазонами значений?
Я работаю над системой, которая имеет 10 тысяч флагов для пользователя. Все флаги являются последовательными по номерам, от 0 до X, независимо от того, что X заканчивается. Ожидается, что Х будет расти со временем. И мы ожидаем, что будет много-много пользователей.
Наши основные проблемы:
- Возможность быстро проверить, установил ли пользователь какой-либо данный флаг.
- Возможность быстро установить флаг.
- Возможность оптимизировать хранилище данных до минимально возможного размера.
С флагами 10 КБ мы смотрим около 1 КБ данных на пользователя в памяти, если мы используем битовый вектор. Что может быть слишком много. И что еще хуже, это в Javascript, хранящемся в базе данных документов, сериализованной в JSON, что означает, что у нас есть несколько вариантов хранения, ни один из которых мне особенно не нравится.
- Сохраняйте флаги как вывод JSON объекта Uint32Array. Похоже:
"{"0":10,"1":4294967295}", К сожалению, в среднем требуется 17 байт на 4 байта, которые хранятся, когда флаги приближаются к заполненному состоянию, что в 4 раза больше памяти и приводит к 5 Кб памяти при сериализации. Это не идеально. - Выполните нашу собственную сериализацию JSON, используя base64, чтобы избежать раздутых размеров подхода числа-как-строки. К сожалению, это добавляет дополнительный этап обработки к фазам ввода / вывода JSON, что усложняет ситуацию, потому что теперь мы должны изменить наши данные во время процесса и замедлить все.
Итак... ненадолго отложим идею битвектора. Мне было интересно, если есть, возможно, лучший подход. Я подумал об использовании "массива диапазонов", что-то вроде:
[{"m":0,"x":100},{"m":102},{"m":108,"x":204}]
Мы можем сделать несколько предположений относительно данных в этой системе, что и привело меня к такому подходу:
- Флаги никогда не устанавливаются. Как только это установлено, это останется установленным.
- Флаги, как правило, сгруппированы. Если установлен флаг X, существует большая вероятность того, что X-1 и X+1 также будут установлены.
- Флаги обычно устанавливаются при увеличении значений индекса. Если установлен флаг X, то X-1 с большей вероятностью будет установлен, чем X+1, а X+1, вероятно, будет установлен довольно скоро после этого.
Поэтому из-за этих условий я думаю, что хранение массива объектов диапазона может быть оптимальным решением. Таким образом, со временем флаги пользователя в конечном итоге сливаются в одну запись с большим диапазоном. Оптимальный случай конечно:
[{"m":0,"x":10000}]
Конечно, наихудший сценарий - если им каким-то образом удается оказаться в состоянии, в котором они устанавливают все остальные флаги.
[{"m":0},{"m":2},{"m":4},{"m":6},{"m":8},{"m":10}...{"m":10000}]
Это было бы плохо. Я думаю, что это намного хуже, чем решение bitvector. Но мы уверены, что этого не произойдет.
Итак, что касается возможности быстро решить, установлен ли флаг; это просто O(logn) бинарный поиск (так как массив будет отсортирован); просто найдите объект диапазона, ближайший к вашему номеру, проверьте, находится ли ваш номер в этом диапазоне, и вернитесь.
Вставки более хитры. Это все еще будет бинарный поиск, но теперь мы модифицируем массив.
- одна соседняя вставка родного брата: оптимальный сценарий. Мы находим диапазон, где минимальное или максимальное значение равно единице от числа, которое мы вставляем, и просто уменьшаем или увеличиваем значение текущего диапазона. O(1)
- Не вставлять соседних братьев и сестер: просто вставьте новый узел с установленным значением min. O(n), потому что мы будем перемещать все после него в массиве вниз.
- Вставьте двух соседних братьев и сестер: измените значение max на максимальное значение правого диапазона братьев и сестер, удалите диапазон правых братьев и сестер из массива и сдвиньте все после него влево. На).
Поэтому случаи 2+3 заставляют меня задуматься, не стоит ли мне пытаться использовать какое-то сбалансированное двоичное дерево поиска для этого. Красно-черное дерево, например.
Это стоит беспокоиться? Я обдумываю это?