Как эффективно найти непрерывный диапазон используемых / свободных слотов из дерева Фенвика
Предположим, что я отслеживаю использование слотов в дереве Фенвика. В качестве примера, давайте рассмотрим отслеживание 32 слотов, что приведет к макету дерева Фенвика, как показано на рисунке ниже, где числа в сетке указывают индекс в базовом массиве со счетчиками, которыми манипулирует дерево Фенвика, где значение в каждой ячейке равно сумма "используемых" элементов в этом сегменте (то есть ячейка 23 массива хранит количество используемых слотов в диапазоне [16-23]). Элементы на самом низком уровне (т. Е. Ячейки 0, 2, 4, ...) могут иметь значение только "1" (используемый слот) или "0" (свободный слот).
То, что я ищу, - это эффективный алгоритм для нахождения первого диапазона заданного числа смежных свободных слотов.
Для иллюстрации предположим, что у меня есть дерево Фенвика, показанное на рисунке ниже, в котором используется всего 9 слотов (обратите внимание, что светло-серые числа просто добавлены для ясности, а не хранятся в ячейках массива дерева).
Теперь я хотел бы найти, например, первый непрерывный диапазон из 10 свободных слотов, который должен найти этот диапазон:
Я не могу найти эффективный способ сделать это, и это вызывает у меня головную боль. Обратите внимание, что, поскольку необходимый объем дискового пространства имеет решающее значение для моих целей, я не хочу расширять дизайн до дерева сегментов.
Любые мысли и предложения о типе решения O(log N) будут приветствоваться.
РЕДАКТИРОВАТЬ
Время обновления после истечения периода вознаграждения. Спасибо за все комментарии, вопросы, предложения и ответы. Они заставили меня снова обдумать ситуацию, многому научили и указали мне (еще раз; однажды я могу выучить этот урок), что я должен больше концентрироваться на проблеме, которую хочу решить, задавая вопросы.
Поскольку Erik P. был единственным, кто дал разумный ответ на вопрос, который включал запрошенный код / псевдокод, он получит вознаграждение.
Он также правильно указал, что поиск O(log N) с использованием этой структуры невозможен. Престижность Dan Bjorge за предоставление доказательства, которое заставило меня задуматься о худшем случае.
Комментарий и ответ Evgeny Kluev заставили меня понять, что я должен был сформулировать свой вопрос по-другому. Фактически я уже делал в значительной степени то, что он предложил (см. https://gist.github.com/anonymous/7594508 - где показано, где я застрял до публикации этого вопроса), и задал этот вопрос, надеясь, что это будет эффективным способ поиска смежных диапазонов, тем самым предотвращая изменение этого дизайна на дерево сегментов (что потребовало бы дополнительных 1024 байтов). Однако представляется, что такое изменение может быть разумным.
Для всех, кто интересуется, дерево Фенвика с двоичным кодом, соответствующее примеру, используемому в этом вопросе (дерево Фенвика с 32 слотами, закодированное в 64 битах), можно найти здесь: https://gist.github.com/anonymous/7594245.
4 ответа
Я думаю, что самый простой способ реализовать все требуемые функции с O(log N) сложностью по времени и в то же время минимизировать требования к памяти - использовать битовый вектор для хранения всех значений 0/1 (свободные / использованные). Битовый вектор может заменить 6 низших уровней как дерева Фенвика, так и дерева сегментов (если реализовано как 64-битные целые числа). Таким образом, высота этих деревьев может быть уменьшена на 6, и требования к пространству для каждого из этих деревьев будут в 64 (или 32) раза меньше, чем обычно.
Сегментное дерево может быть реализовано как неявное двоичное дерево, расположенное в массиве (точно так же, как хорошо известная реализация max-heap). Корневой узел с индексом 1, каждый левый потомок узла с индексом i находится в 2*iкаждый правый потомок - у 2*i+1, Это означает, что требуется вдвое больше места по сравнению с деревом Фенвика, но, поскольку высота дерева уменьшается на 6 уровней, это не большая проблема.
Каждый узел дерева сегментов должен хранить одно значение - длину самой длинной непрерывной последовательности "свободных" слотов, начиная с точки, охватываемой этим узлом (или ноль, если такой начальной точки нет). Это делает поиск первого диапазона заданного числа смежных нулей очень простым: начните с корня, затем выберите левого потомка, если он содержит значение, большее или равное требуемому, в противном случае выберите правого потомка. Придя к некоторому листовому узлу, проверьте соответствующее слово битового вектора (на наличие нулей в середине слова).
Операции обновления более сложны. При изменении значения на "используется", проверьте соответствующее слово битового вектора, если оно пустое, поднимитесь по дереву сегмента, чтобы найти ненулевое значение для некоторого левого потомка, затем спуститесь по дереву, чтобы добраться до самого правого листа с этим значением, а затем определите, как заново добавленный слот разбивает "свободный" интервал на две половины, затем обновляет все родительские узлы как для добавленного слота, так и для начального узла разделяемого интервала, а также устанавливает бит в битовом векторе. Изменение значения на "свободное" может быть реализовано аналогично.
Если также необходимо получить число ненулевых элементов в некотором диапазоне, реализуйте дерево Фенвика для того же битового вектора (но отдельно от дерева сегментов). В реализации дерева Фенвика нет ничего особенного, за исключением того, что сложение вместе 6 нижних узлов заменяется операцией "подсчет населения" для некоторого слова битового вектора. Для примера использования дерева Фенвика вместе с битовым вектором смотрите первое решение для Magic Board на CodeChef.
Все необходимые операции для битового вектора могут быть реализованы довольно эффективно, используя различные побитовые приемы. Для некоторых из них (начальное / конечное число нулей и количество населения) вы можете использовать встроенные функции компилятора или инструкции ассемблера (в зависимости от целевой архитектуры).
Если битовый вектор реализован с 64-битными словами и узлами дерева - с 32-битными словами, оба дерева занимают 150% пространства в дополнение к битовому вектору. Это может быть значительно уменьшено, если каждому листовому узлу соответствует не одно битовое векторное слово, а небольшой диапазон (4 или 8 слов). Для 8 слов дополнительное пространство, необходимое для деревьев, составило бы только 20% размера битового вектора. Это делает реализацию немного более сложной. При правильной оптимизации производительность должна быть примерно такой же, как в варианте для одного слова на листовой узел. При очень большом наборе данных производительность, вероятно, будет лучше (поскольку вычисления в битовых векторах более удобны для кэша, чем при обходе деревьев).
Как Макдовелла предлагает в своем ответе, пусть K2 = K/2, округляя вверх, и пусть M будет наименьшей степенью 2, то есть>= K2. Многообещающим подходом будет поиск смежных блоков нулей K2, полностью содержащихся в одном блоке размера M, и как только мы их найдем, проверьте соседние блоки размера M, чтобы увидеть, содержат ли они достаточное количество смежных нулей. Для начального сканирования, если число 0 в блоке
Это предполагает следующий код. Ниже A[0 .. N-1] - массив деревьев Фенвика; Предполагается, что N является степенью 2. Я предполагаю, что вы считаете пустые слоты, а не непустые; если вы предпочитаете считать пустые слоты, достаточно легко перейти от одного к другому.
initialize q as a stack data structure of triples of integers
push (N-1, N, A[n-1]) onto q
# An entry (i, j, z) represents the block [i-j+1 .. i] of length j, which
# contains z zeroes; we start with one block representing the whole array.
# We maintain the invariant that i always has at least as many trailing ones
# in its binary representation as j has trailing zeroes. (**)
initialize r as an empty list of pairs of integers
while q is not empty:
pop an entry (i,j,z) off q
if z < K2:
next
if FW(i) >= K:
first_half := i - j/2
# change this if you want to count nonempty slots:
first_half_zeroes := A[first_half]
# Because of invariant (**) above, first_half always has exactly
# the right number of trailing 1 bits in its binary representation
# that A[first_half] counts elements of the interval
# [i-j+1 .. first_half].
push (i, j/2, z - first_half_zeroes) onto q
push (first_half, j/2, first_half_zeroes) onto q
else:
process_block(i, j, z)
Это позволяет нам обрабатывать все блоки размера M с по крайней мере K / 2 нулями по порядку. Вы можете даже рандомизировать порядок, в котором вы помещаете первую и вторую половину на q, чтобы получить блоки в случайном порядке, что может быть неплохо для борьбы с ситуацией, когда первая половина вашего массива заполняется гораздо быстрее, чем вторая половина
Теперь нам нужно обсудить, как обрабатывать отдельный блок. Если z = j, то блок полностью заполнен нулями, и мы можем смотреть как влево, так и вправо, чтобы добавить нули. В противном случае нам нужно выяснить, начинается ли оно с>= K/2 смежных нулей, и если да, то сколько именно, а затем проверить, заканчивается ли предыдущий блок подходящим числом нулей. Точно так же мы проверяем, заканчивается ли блок>= K/2 смежными нулями, и если да, то сколько именно, и затем проверяем, начинается ли следующий блок с подходящим числом нулей. Поэтому нам понадобится процедура для определения количества нулей, с которых начинается или заканчивается блок, возможно, с помощью ярлыка, если он по крайней мере a или самое большее b. Чтобы быть точным: позвольте end_with_zeroes(i, j, min, max) быть процедурой, которая возвращает количество нулей, которым заканчивается блок из [i-j+1 .. j], с ярлыком для возврата max, если результат будет больше, чем max и min, если результат будет меньше, чем min. Аналогично для start_with_zeroes(i, j, min, max).
def process_block(i, j, z):
if j == z:
if i > j:
a := ends_with_zeroes(i-j, j, 0, K-z)
else:
a := 0
if i < N-1:
b := starts_with_zeroes(i+j, j, K-z-a-1, K-z-a)
else:
b := 0
if b >= K-z-a:
print "Found: starting at ", i - j - a + 1
return
# If the block doesn't start or end with K2 zeroes but overlaps with a
# correct solution anyway, we don't need to find it here -- we'll find it
# starting from the adjacent block.
a := starts_with_zeroes(i, j, K2-1, j)
if i > j and a >= K2:
b := ends_with_zeroes(i-j, j, K-a-1, K-a)
if b >= K-a:
print "Found: starting at ", i - j - a + 1
# Since z < 2*K2, and j != z, we know this block doesn't end with K2
# zeroes, so we can safely return.
return
a := ends_with_zeroes(i, j, K2-1, j)
if i < N-1 and a >= K2:
b := starts_with_zeroes(i+j, K-a-1, K-a)
if b >= K-a:
print "Found: starting at ", i - a + 1
Обратите внимание, что во втором случае, когда мы находим решение, может оказаться возможным сместить начальную точку влево немного дальше. Вы можете проверить это отдельно, если вам нужна самая первая позиция, с которой она может начать.
Теперь все, что осталось, - это реализовать start_with_zeroes и конец_with_zeroes. Чтобы проверить, что блок начинается с минимум мин нулями, мы можем проверить, что он начинается с 2^h нулей (где 2^h <= min), проверив соответствующую запись Fenwick; затем аналогичным образом проверьте, начинается ли оно с 2^H нулей, где 2^H >= max, чтобы сократить путь в другую сторону (кроме случаев, когда max = j, более сложно найти правильный счет из дерева Фенвика); затем найдите точное число.
def starts_with_zeroes(i, j, min, max):
start := i-j
h2 := 1
while h2 * 2 <= min:
h2 := h2 * 2
if A[start + h2] < h2:
return min
# Now h2 = 2^h in the text.
# If you insist, you can do the above operation faster with bit twiddling
# to get the 2log of min (in which case, for more info google it).
while h2 < max and A[start + 2*h2] == 2*h2:
h2 := 2*h2
if h2 == j:
# Walk up the Fenwick tree to determine the exact number of zeroes
# in interval [start+1 .. i]. (Not implemented, but easy.) Let this
# number be z.
if z < j:
h2 := h2 / 2
if h2 >= max:
return max
# Now we know that [start+1 .. start+h2] is all zeroes, but somewhere in
# [start+h2+1 .. start+2*h2] there is a one.
# Maintain invariant: the interval [start+1 .. start+h2] is all zeroes,
# and there is a one in [start+h2+1 .. start+h2+step].
step := h2;
while step > 1:
step := step / 2
if A[start + h2 + step] == step:
h2 := h2 + step
return h2
Как видите, start_with_zeroes довольно снизу вверх. Я думаю, что вам необходимо использовать более подход "сверху вниз", так как проверка второй половины чего-либо в дереве Фенвика немного сложнее. Вы должны быть в состоянии сделать подобный тип итерации бинарного стиля поиска.
Этот алгоритм определенно не O(log(N)), и я догадываюсь, что это неизбежно. Дерево Фенвика просто не дает информации, которая так хороша для вашего вопроса. Тем не менее, я думаю, что этот алгоритм будет довольно хорошо работать на практике, если подходящие интервалы довольно распространены.
@ Эрик раскрыл разумный алгоритм звучания. Однако отметим, что в худшем случае эта задача имеет нижнюю границу сложности Ω(N/K).
Доказательство:
Рассмотрим сокращенную версию проблемы, где:
- N и K являются степенями 2
- N> 2K> = 4
Предположим, что ваш входной массив состоит из (N/2K) блоков размером 2K. Один фрагмент имеет форму K 0, за которой следует K 1, каждый второй фрагмент - это строка "10", повторенная K раз. Существует (N/2K) таких массивов, каждый из которых имеет ровно одно решение проблемы (начало одного "специального" блока).
Пусть n = log2(N), k = log2(K). Давайте также определим корневой узел дерева как находящийся на уровне 0 и листовые узлы как находящиеся на уровне n дерева.
Обратите внимание, что из-за того, что наш массив состоит из выровненных фрагментов размером 2K, уровень nk дерева будет просто состоять из числа единиц в каждом фрагменте. Тем не менее, каждый из наших кусков имеет одинаковое количество единиц. Это означает, что каждый узел на уровне nk будет идентичен, что, в свою очередь, означает, что каждый узел на уровне <= nk также будет идентичен.
Это означает, что дерево не содержит информации, которая может устранить неоднозначность "специального" чанка, пока вы не начнете анализировать уровень n-k+1 и ниже. Но поскольку все узлы (N / K) на этом уровне, кроме 2, идентичны, это означает, что в худшем случае вам придется исследовать O(N/K) узлов, чтобы устранить неоднозначность решения с остальными узлы.
Одна быстрая проверка при поиске диапазона из K смежных слотов состоит в том, чтобы найти наибольшую мощность двух, меньшую или равную K/2. Любые K непрерывных нулевых слотов должны содержать хотя бы один выровненный по Фенвику диапазон слотов размером <= K/2, который полностью заполнен нулями. Вы можете найти в дереве Фенвика сверху такие куски выровненных нулей, а затем найти первый, который можно расширить, чтобы получить диапазон из K смежных нулей.
В вашем примере самый низкий уровень содержит 0 или 1, а верхний уровень содержит суммы потомков. Нахождение отрезков 0 будет проще, если на самом низком уровне будут 0, где вы в данный момент пишете 1, и счетчик числа смежных нулей слева, где вы в данный момент пишете нули, а верхние уровни содержат максимальное значение любого потомка. Обновление будет означать больше работы, особенно если у вас были созданы и уничтожены длинные строки нулей, но вы могли бы найти крайнюю левую строку нулей длиной по крайней мере K с одним поиском в левой ветви, где максимальное значение было по крайней мере K На самом деле здесь проделана большая работа по обновлению, создавая и уничтожая прогоны 1,2,3,4... на самом низком уровне. Возможно, если вы оставили самый низкий уровень, как это было первоначально определено, и провели индивидуальный анализ последствий изменений, вы могли бы иметь верхние уровни, показывающие самый длинный отрезок нулей, начиная с любого потомка данного узла - для быстрого поиска - и получить разумный Стоимость обновления.