![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
Rust hard task sqrt(n)
Nov. 3rd, 2022 08:14 pmМоя hard task свелась к проблеме поиска структуры, которая есть в стандартной библиотеке, и которая даёт мне возможность вставлять, удалять и находить максимум быстрее, чем o(n). Кроме того, структура должна поддерживать дубликаты. Rust пока не даёт 'first/last' для BTree, так что приходится думать самому.
Правильный ответ - binary search tree, но у меня не хватает сейчас мозгов его хорошо написать, и я не хочу туда коммититься.
Вот что я придумал "их того что было и палок".
объём данных: n
k = sqrt(n) (квадратный корень из n)
Создадим Vec (массив) и VecDeque (double ended queue) - такие есть в в стандартной библиотеке. Всего будет k (напоминаю, sqrt(n)) Vec'ов при ожидаемом размере каждого элемента - k. Получается sqrt(n) * sqrt(n) = n.
Все элементы хранятся упорядоченно. Каждый VecDeque упорядочен от младшего к старшему, каждый элемент Vec содержит в себе VecDeque, которые так же полностью упорядочены.
Вставка:
Найти двоичным поиском в Vec нужный элемент (VecDeque). o(log(k))
Найти двоичным поиском в VecDeque нужную позицию, либо дописать слева/справа. o(log(k))
Вставить элемент в указанный индекс. Сложность o(k/2), с поправкой на облечение "вставки в начало" (т.к. VecDeque).
После этого произойдёт переполнение VecDeque (размер станет больше k), и надо будет перекинуть элемент вверх или вниз. Возможно, в худшем случае вставка потребует перекидывать элементы между каждой "строкой" (VecDeque), так что худший случай - o(k) pop_back, o(k) push_front. в среднем o(k) операций.
Сложность: log(k) + log(k) + o(k/2) + o(k/2) + k + k =~= k
Удаление:
Найти двоичным поиском в Vec нужный элемент (VecDeque). o(log(k))
Найти двоичным поиском в VecDeque нужную позицию o(log(k))
Перенормировать длины: 2*o(k)
Сложность: o(k)
Поиск максимума o(1) - последний элемент последней строки.
Теперь, вспомним, что k - это sqrt(n), и получаем, что сложность вставки/удаления - sqrt(n), что лучше, чем n.
При использовании внутри алгоритма со сложностью n*log(n), получаем n*log(n)*sqrt(n), ~n1.5, что лучше, чем o(n).
Не фонтан, но...
Вопрос: не могу ли я расширить этот подход на более чем одно измерение? Теоретически, в пределе должно получиться как раз log(n).
Фактически, я хочу сделать дерево, в котором у меня в векторе хранятся вектора, внутри которых хранятся вектора... и так пока я не дойду до самого дна, то есть до leaf'а. Одним из интересных улучшений в рамках задачи является то, что я знаю максимальный размер (n) заранее и могу посчитать оптимальную глубину в момент создания, то есть мне не нужно пересчитывать глубины.
"дерево на векторах" мне кажется куда интереснее, чем обычный struct с left/right (как обычно дерево описывается).
Я сейчас попробую изобрести такое дерево, если не получится, попробую штурмовать задачу с n^(1.5) сложностью решения. Цена вопроса - для 10000 элементов квадратичное решение - это 100 миллионов операций, а 1.5 - это миллион. 100-кратное ускорение. Для 100k элементов - 100 миллиардов против 31 миллиона, 300-кратное ускорение.
Итак, как будет устроено DQTree? По аналогии с btree, я хочу ограничить глубину сканирования эффективным коэфицентом. Допустим, я выбираю коэфицент B (16).
У меня N элементов, и мне нужно посчитать, сколько слоёв нужно в дереве. log16N, округлённый вверх. Допустим, у меня 333333 элементов. Это 5 слоёв (из значения логарифма 4.58..)
В первом слое у меня B элементов (Vec), во втором слое у меня B элементов (тоже Vec), в третьем слое у меня B элементов, в четвёртом у меня B элементов, в пятом у меня Deque... А нужно ли оно тут? Если у меня там up to 16 элементов, то любой insert в него будет константным. Так что просто Vec. Все слои, кроме нижнего, содержат в себе только Vec следующего уровня. Нижний Vec содержит в себе числа.
Переименовываем стуктуру в VecTree.
Создание: Аллоцирвать все Vec'и. WUT? Это же o(n) операций. Нет.
Вместо Vec у нас появляется Option... При создании VecTree мы ничего не аллоцируем.
Вставка:
Дойти до нижнего элемента за o(log n), вставиться в него за o(B) времени (то есть за o(1)).
Каким образом я знаю, в какой элемент вставляться? Если это первый элемент, то понятно, самая левая ветка.
А если, допустим, у нас целиком уровень забит Vec'ами? Как нам понять, в какой Vec ходить?
Допустим, мы будем хранить min/max для обслуживаемого диапазона.
Итак, пройтись по элементам, выбрать подходящий диапазон. Если слишком маленький - расширить диапазон левого значения, если слишком большой - правого.
Спуститься на уровень ниже. Повторить.
Пока не прийдём к нижнему слою.
Двоичным поиском найти нужное место, вставиться.
После вставки мы проверяем размер Vec'а и думаем, что с этим делать. Если размер меньше B, то "и пофигу".
Если размер больше B, то надо вынуть элемент в ставить "куда" следует:
Если у нас нет соседа слева, то надо убирать правый элемент.
Если у нас нет соседа справа, то надо убирать левый элемент.
А если есть оба соседа? Как понять в какую сторону значение надо двигать? По-идее надо двигать в ту сторону, в которой меньше всего элементов.
Для этого мы записываем число элементов для каджого Vec'а. (не число элементов в Vec, а число элементов в Vec в Vec в Vec ... до самого дна).
То есть обычная (не leaf) нода выглядит так:
min
max
count
При спуске на слой ниже мы смотрим на предпочтения по перекидыванию значений. Для этого мы считаем число элементов в остальных элементах слоя (кроме того, в который мы погружаемся) и вычисляем left_count и right_count, который и известен следующему слою.
Когда слой решает, какой элемент удалять при переполнении, он смотрит какой меньше и с той стороны удаляет элемент. (Будет обидно, если удаляют элемент, который только что был вставлен... не создаст ли это бесконечный цикл? Удалённый элемент при ребалансировке надо вставлять... Это особый случай и нам надо проверять, к какому потомку мы посылаем элемент, если элемент на границе диапазона - к тому, у которого это будет "левое" значение или правое). Мы на эти вопросы всё равно смотрим, потому что двигаем min/max у элемента. У кого count меньше, того и элемент.
(возвращаемся к ребалансировке "лишнего" значения с нижнего слоя 'leaf'ов').
Итак, мы знаем с какой стороны удаляем лишнее значение. Мы его удаляем (размер становится B), после чего мы возвращаемся на уровень выше и вставляем значение в элемент с соотв стороны.
Это может вызвать ребалансировку в следующий элемент. Можно представить себе крайне неприятную ситуацию, при которой мы проходим все N/B-1 элементы, то есть получаем ребалансировку за o(n). Плохо-плохо.
А как мы к такой беде пришли? Потому что в старом коде с k=sqrt(n) нужно было не более чем 2*k операций на Dequeue, чтобы ребалансировать всё. Почему так? Потому что при ребалансировке у меня 2 операции на "псевдолиф" (pop_front/push_back).
А в VTree у меня мало того, что на каждый leaf B операций на вставку, то ещё и надо потенциально пройтись по всем значенниям. И переходов o(n). А было o(sqrt(n)), потому что я променял sqrt n на B, когда делал размер leaf'а снизу. Почему я это сделал? Чтобы сделать вставку дешевле. у старого кода вставка была дорогой o(k), и ребалансировка тоже дорогой. o(k). Получалось, что две условно дорогие операции дешевле, чем, казалось бы, быстрая вставка за o(log(n)), но очень дорогая ребалансировка за n.
Мы так не договаривались.
Окей, шаг назад. У нас есть sqrt(n). Там есть Vec>. Если мы сделаем Vec
Правильный ответ - binary search tree, но у меня не хватает сейчас мозгов его хорошо написать, и я не хочу туда коммититься.
Вот что я придумал "их того что было и палок".
объём данных: n
k = sqrt(n) (квадратный корень из n)
Создадим Vec (массив) и VecDeque (double ended queue) - такие есть в в стандартной библиотеке. Всего будет k (напоминаю, sqrt(n)) Vec'ов при ожидаемом размере каждого элемента - k. Получается sqrt(n) * sqrt(n) = n.
Все элементы хранятся упорядоченно. Каждый VecDeque упорядочен от младшего к старшему, каждый элемент Vec содержит в себе VecDeque, которые так же полностью упорядочены.
Вставка:
Найти двоичным поиском в Vec нужный элемент (VecDeque). o(log(k))
Найти двоичным поиском в VecDeque нужную позицию, либо дописать слева/справа. o(log(k))
Вставить элемент в указанный индекс. Сложность o(k/2), с поправкой на облечение "вставки в начало" (т.к. VecDeque).
После этого произойдёт переполнение VecDeque (размер станет больше k), и надо будет перекинуть элемент вверх или вниз. Возможно, в худшем случае вставка потребует перекидывать элементы между каждой "строкой" (VecDeque), так что худший случай - o(k) pop_back, o(k) push_front. в среднем o(k) операций.
Сложность: log(k) + log(k) + o(k/2) + o(k/2) + k + k =~= k
Удаление:
Найти двоичным поиском в Vec нужный элемент (VecDeque). o(log(k))
Найти двоичным поиском в VecDeque нужную позицию o(log(k))
Перенормировать длины: 2*o(k)
Сложность: o(k)
Поиск максимума o(1) - последний элемент последней строки.
Теперь, вспомним, что k - это sqrt(n), и получаем, что сложность вставки/удаления - sqrt(n), что лучше, чем n.
При использовании внутри алгоритма со сложностью n*log(n), получаем n*log(n)*sqrt(n), ~n1.5, что лучше, чем o(n).
Не фонтан, но...
Вопрос: не могу ли я расширить этот подход на более чем одно измерение? Теоретически, в пределе должно получиться как раз log(n).
Фактически, я хочу сделать дерево, в котором у меня в векторе хранятся вектора, внутри которых хранятся вектора... и так пока я не дойду до самого дна, то есть до leaf'а. Одним из интересных улучшений в рамках задачи является то, что я знаю максимальный размер (n) заранее и могу посчитать оптимальную глубину в момент создания, то есть мне не нужно пересчитывать глубины.
"дерево на векторах" мне кажется куда интереснее, чем обычный struct с left/right (как обычно дерево описывается).
Я сейчас попробую изобрести такое дерево, если не получится, попробую штурмовать задачу с n^(1.5) сложностью решения. Цена вопроса - для 10000 элементов квадратичное решение - это 100 миллионов операций, а 1.5 - это миллион. 100-кратное ускорение. Для 100k элементов - 100 миллиардов против 31 миллиона, 300-кратное ускорение.
Итак, как будет устроено DQTree? По аналогии с btree, я хочу ограничить глубину сканирования эффективным коэфицентом. Допустим, я выбираю коэфицент B (16).
У меня N элементов, и мне нужно посчитать, сколько слоёв нужно в дереве. log16N, округлённый вверх. Допустим, у меня 333333 элементов. Это 5 слоёв (из значения логарифма 4.58..)
В первом слое у меня B элементов (Vec), во втором слое у меня B элементов (тоже Vec), в третьем слое у меня B элементов, в четвёртом у меня B элементов, в пятом у меня Deque... А нужно ли оно тут? Если у меня там up to 16 элементов, то любой insert в него будет константным. Так что просто Vec. Все слои, кроме нижнего, содержат в себе только Vec следующего уровня. Нижний Vec содержит в себе числа.
Переименовываем стуктуру в VecTree.
Создание: Аллоцирвать все Vec'и. WUT? Это же o(n) операций. Нет.
Вместо Vec у нас появляется Option
Вставка:
Дойти до нижнего элемента за o(log n), вставиться в него за o(B) времени (то есть за o(1)).
Каким образом я знаю, в какой элемент вставляться? Если это первый элемент, то понятно, самая левая ветка.
А если, допустим, у нас целиком уровень забит Vec'ами? Как нам понять, в какой Vec ходить?
Допустим, мы будем хранить min/max для обслуживаемого диапазона.
Итак, пройтись по элементам, выбрать подходящий диапазон. Если слишком маленький - расширить диапазон левого значения, если слишком большой - правого.
Спуститься на уровень ниже. Повторить.
Пока не прийдём к нижнему слою.
Двоичным поиском найти нужное место, вставиться.
После вставки мы проверяем размер Vec'а и думаем, что с этим делать. Если размер меньше B, то "и пофигу".
Если размер больше B, то надо вынуть элемент в ставить "куда" следует:
Если у нас нет соседа слева, то надо убирать правый элемент.
Если у нас нет соседа справа, то надо убирать левый элемент.
А если есть оба соседа? Как понять в какую сторону значение надо двигать? По-идее надо двигать в ту сторону, в которой меньше всего элементов.
Для этого мы записываем число элементов для каджого Vec'а. (не число элементов в Vec, а число элементов в Vec в Vec в Vec ... до самого дна).
То есть обычная (не leaf) нода выглядит так:
min
max
count
При спуске на слой ниже мы смотрим на предпочтения по перекидыванию значений. Для этого мы считаем число элементов в остальных элементах слоя (кроме того, в который мы погружаемся) и вычисляем left_count и right_count, который и известен следующему слою.
Когда слой решает, какой элемент удалять при переполнении, он смотрит какой меньше и с той стороны удаляет элемент. (Будет обидно, если удаляют элемент, который только что был вставлен... не создаст ли это бесконечный цикл? Удалённый элемент при ребалансировке надо вставлять... Это особый случай и нам надо проверять, к какому потомку мы посылаем элемент, если элемент на границе диапазона - к тому, у которого это будет "левое" значение или правое). Мы на эти вопросы всё равно смотрим, потому что двигаем min/max у элемента. У кого count меньше, того и элемент.
(возвращаемся к ребалансировке "лишнего" значения с нижнего слоя 'leaf'ов').
Итак, мы знаем с какой стороны удаляем лишнее значение. Мы его удаляем (размер становится B), после чего мы возвращаемся на уровень выше и вставляем значение в элемент с соотв стороны.
Это может вызвать ребалансировку в следующий элемент. Можно представить себе крайне неприятную ситуацию, при которой мы проходим все N/B-1 элементы, то есть получаем ребалансировку за o(n). Плохо-плохо.
А как мы к такой беде пришли? Потому что в старом коде с k=sqrt(n) нужно было не более чем 2*k операций на Dequeue, чтобы ребалансировать всё. Почему так? Потому что при ребалансировке у меня 2 операции на "псевдолиф" (pop_front/push_back).
А в VTree у меня мало того, что на каждый leaf B операций на вставку, то ещё и надо потенциально пройтись по всем значенниям. И переходов o(n). А было o(sqrt(n)), потому что я променял sqrt n на B, когда делал размер leaf'а снизу. Почему я это сделал? Чтобы сделать вставку дешевле. у старого кода вставка была дорогой o(k), и ребалансировка тоже дорогой. o(k). Получалось, что две условно дорогие операции дешевле, чем, казалось бы, быстрая вставка за o(log(n)), но очень дорогая ребалансировка за n.
Мы так не договаривались.
Окей, шаг назад. У нас есть sqrt(n). Там есть Vec