удалить элементы: но какой контейнер выбрать

Question

Я храню ненулевые представления разреженной матрицы в некоторых триплетах, известных в числовом сообществе как хранилище сжатых разреженных строк, записи хранятся построчно, например, матрица 4x4 представляется как

r:0 0 1 1 2 2 3 3 3
c:0 3 2 3 2 3 1 2 3 
v:1 5 2 2 4 1 5 4 5

поэтому «r» - индексы строк, «c» - индексы столбцов, а «v» - значения, связанные с двумя индексами выше этого значения.

Я хотел бы удалить некоторые строки и столбцы из моего матричного представления, скажем, строки и столбцы: 1 и 3. Поэтому я должен удалить 1 и 3 из массивов 'r' и 'c'. Я также пытаюсь узнать больше о производительности контейнеров stl и прочитать немного больше. В качестве первой попытки создайте мультикарту и удалите элементы, зацикливая их с помощью метода find для мультикарты. Это удаляет найденные ключи, однако может оставить некоторые из искомых значений в массиве 'c', после чего я поменял местами пары ключей и значений и выполнил ту же операцию для второй карты, однако это не показалось мне очень хорошим решением. кажется, это довольно быстро (на проблему с 50000 записей), хотя. Таким образом, вопрос в том, что было бы наиболее эффективным способом сделать это со стандартными контейнерами?

Answer 1

Как вы получаете доступ к матрице?Вы просматриваете определенные строки / столбцы и делаете что-то с ними таким образом, или вы используете всю матрицу за раз для таких операций, как умножение матрицы на вектор или процедуры факторизации?Если вы обычно не индексируете по строке / столбцу, тогда может быть более эффективно хранить ваши данные в std::vector контейнерах.

В этом случае ваша операция удаления - это итерация по всему контейнеру, скольжение внизпоследующие элементы вместо записей, которые вы хотите удалить.Очевидно, что здесь есть компромиссы.Ваш подход карты / мультикарты займет около 1004 * времени для удаления k записей, но операции с целыми матрицами в этом представлении будут очень неэффективными (хотя, надеюсь, все же O(n), а не O(n log n)).

Используя представление массива, удаление одной строки или столбца может занять O(n) времени, но вы можете удалить произвольное количество строк или столбцов за один и тот же проход, сохранив их индексы в паре хеш-таблиц или деревьев отображения.и делает поиск для каждой записи.После сканирования удаления вы можете либо изменить размеры векторов до количества элементов, которые вы оставили, что экономит память, но может повлечь за собой копирование, либо просто сохранить явное количество действительных записей, торгуя мертвой памятью для экономии времени.

Answer 2

Вы можете использовать карту (между парой строк и столбцов) и значение, что-то вроде map<pair<int,int>, int>

Если затем вы хотите удалить строку, вы перебираете элементы и удаляете те, которые будут удалены. То же самое можно сделать для столбцов.