Эффективная структура данных для моей конкретной проблемы

Question

У меня есть очередь с приоритетами, которая содержит отсортированную матрицу A вместе с ее расположением (row, col) в матрице. Итак, у меня есть структура данных «queue_element», которая имеет три поля: queue_element.value, queue_element.row и queue_element.col

Мне нужно обработать очередь с приоритетами, и для каждого всплывающего элемента мне нужно вернуться в местоположение A (row, col) и удалить все элементы, лежащие в одной строке # и col #.

Так, например, если в верхней части очереди приоритетов есть element.value = 0,99, element.row = 4 и element.col = 20, то мне нужно обнулить A (4, :) и A (:, 20), где нотация «:» обозначает «все» или весь диапазон от 0 до конца. Это нотация MATLAB / Python, но для этого я использую C ++.

В настоящее время я использую отдельную булеву матрицу P (x, y) для исключения. Для каждого (x, y) местоположения, которое извлекается из очереди приоритетов, я просто зацикливаюсь на всей строке / столбце и устанавливаю ложное значение для всего, что находится в той же строке / столбце. Затем, когда я извлекаю элемент из очереди, я просто проверяю, установлено ли для него значение false в P (x, y).

Однако это довольно неэффективно. Базовый случай моего алгоритма требует только удаления всей строки / столбца.

РЕДАКТИРОВАТЬ: Извините, что пропустил последнюю часть моего вопроса ...

Более продвинутая версия этого алгоритма требует устранения всего в той же строке / столбце, но за исключением ближайших 4 соседей. Другая версия требует устранения всего, что находится в верхнем правом и нижнем левом квадранте матрицы, когда сетка X-Y размещена в позиции (строка, столбец).

Мой вопрос в основном заключается в том, существует ли очевидная структура данных, которую я мог бы использовать. Это должно было бы: а) позволить мне эффективно "исключить" или обнулить элементы, которые мне нужны, и б) дать мне возможность очень быстро проверить членство в наборе.

Есть идеи, как мне поступить?

Answer 1

То, что устранение двух квадрантов дает мне представление. Вы слышали о quadtree ?

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

Я не уверен, в каком порядке расположены ваши элементы, но если вы можете найти способ установить, возможно, диапазон приоритетов для каждого квадранта (например, нижний правый квадрант имеет приоритет от 1 до N, нижний левый - N От +1 до M и т. Д.), И напишите метод перебалансировки дерева, который выкладывает все в такую ​​структуру данных в зависимости от приоритета. Тогда проверка на членство в наборе будет действительно быстрой (вы исключаете 3/4 пространства поиска для каждого поиска итерации), и вы сможете урезать квадранты из дерева очень хорошо. Одна строка или столбец будут чертовски обрезать в квадродереве, при этом элементы пересекают два основных квадранта и множество второстепенных.

Что вы могли бы сделать, это построить временное квадродерево с использованием метода перебалансировки дерева, о котором я говорил, а затем обрезать два квадранта и вставить оставшиеся элементы в новую матрицу. А затем просто используйте матричную структуру для обнуления элементов, когда дело доходит до исключения строки / столбца. В обоих случаях само обрезание становится тривиальным, но построение квадродерева может быть настолько трудоемким, что это неэффективно.

Другим способом устранения квадранта матрицы является просто наличие вложенных циклов, идущих от [row, col] до [row, 0], затем [row-1, col] до [row-1,0] и обнулить каждый элемент таким образом?

РЕДАКТИРОВАТЬ: Итак, чтобы построить квадродерево, вам нужно будет поместить в него каждый элемент, так что вам нужно будет вызвать (рекурсивную) функцию для подключения куча указателей между различными элементами. Чтобы обнулить значение здесь, у нас есть указатель NULL, и, следовательно, нет дочернего элемента. Я лично не работал с quadtree, поэтому все, что я должен предложить, это ссылки на другие реализации .

У меня есть свои идеи для его реализации, но они наполовину сформированы, и из-за вашей потребности в масштабируемости я не буду пытаться спроектировать оптимальное для пространства квадродерево в этом посте.

Answer 2

Для вашей "другой версии" я бы взял другую тактику.Поскольку в каждой строке может быть не более одного элемента, найдите «лучший» элемент в каждой строке - элементы, которые не будут удалены, являются их подмножеством.Теперь просто изучите все пары и выясните, какие из них выжили.Если вы используете столбцы вместо строк, когда количество строк превышает количество столбцов, то это асимптотически так же быстро, как и создание матрицы.

РЕДАКТИРОВАТЬ: я не чувствую, как будто я получаю всю историю, потому чтотекущий алгоритм для других случаев работает так же быстро, как и создание матрицы.Есть инкрементные обновления или что-то?