Алгоритм объединения коротких списков в длинный вектор

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

Скажем, что у меня есть операция, insert_erase_replace или ier для краткости. ier может делать следующее, учитывая позицию p, индекс столбца j и значение v:

if v==0, ier удаляет запись в p и сдвигает все последующие записи влево.
Если v!=0 и j уже присутствует в p, ier заменяет содержимое ячейки на p на v.
если v!=0 и j нет в p, ier вставляет запись v и индекс столбца j в p после правого смещения всех последующих записей.

Итак, все это тривиально.

Теперь скажем, что у меня есть ier2, что делает то же самое, за исключением того, что он принимает список, содержащий несколько индексов столбца j и соответствующие значения v. Он также имеет размер n, который указывает, сколько пар index/value присутствует в списке. Но поскольку вектор сохраняет только нули, иногда фактический размер вставки меньше n.

Еще тривиально.

Но теперь скажем, что у меня есть ier3, который берет не только один список, например ier2, но и несколько списков. Это означает редактирование среза разреженной матрицы.

В какой-то момент становится более эффективным выполнять итерацию через векторы, копируя их по частям и вставляя/заменяя/стираем индексы/значения list ier2 -style, когда мы приходим к каждой точке вставки. И если общий размер вставки приведет к тому, что мой вектор будет нуждаться в изменении размера, тогда мы это сделаем.

Учитывая, что мой вектор намного, намного больше, чем общая длина списков, есть алгоритм для эффективного объединения списков в вектор?

До сих пор вот что у меня:

Каждый список, переданный в ier3, представляет собой чистое удаление записей (сдвиг влево), замену сети (без движения, следовательно, дешевую) или чистую вставку записей (правая смена). Там также может быть некоторое перераспределение элементов, но дорогими частями являются чистые удаления и сетевые вставки.
Не сложно найти алгоритм для эффективного выполнения ТОЛЬКО чистых вставок или сетевых удалений.
Это сложнее, если любой из двух может произойти.

Единственное, что я могу сделать, это обработать его двумя проходами:

Erase/заменить
Вставить/заменить

Мы сначала стираем, потому что это делает более вероятным, что для любых вставок потребуется меньше копий.

Это правильный подход? Кто-нибудь знает о лучшем?

Ответ 1

Хорошо, поэтому я предполагаю, что интервалы, охватываемые в каждом списке в ier3, не пересекаются и даны вам по порядку. Если это предназначено для редактирования срезов матрицы, это кажется разумным. Я также предполагаю, что вам не нужно изменять размер вектора, потому что этот случай легко обнаруживается и разрешима.

Инициализируйте указатель read и указатель write к началу редактируемого вами вектора. Там будет instruction указатель на ie3 тоже, но я проигнорирую это здесь для ясности. Вам также понадобится очередь. На каждом шаге может произойти одна из нескольких вещей:

По умолчанию: ни read, ни write находятся в позиции, деталированной ier3. В этом случае добавьте элемент под read в обратную сторону очереди и напишите элемент в начале очереди в ячейку под write. Переместите оба указателя вперед.
read находится над ячейкой, которую необходимо удалить. В этом случае просто переместите read вперед один без, добавляя что-нибудь в очередь.
read переходит от одной ячейки к следующей, так что между ними должна произойти вставка. В этом случае добавьте вставку в конец очереди, а затем перейдите к следующему соответствующему случаю.
read находится в ячейке, которую необходимо изменить. В этом случае вставьте измененную ячейку в обратную сторону очереди, напишите все, что находится в начале очереди, на write и поместите их вперед.
read пришел к неиспользуемой емкости вектора. В этом случае просто write все, что осталось в очереди.

Чтобы создать базовый контур, но можно сделать пару оптимизаций: во-первых, если очередь пуста, переместите оба указателя вперед в следующую позицию, указанную ie3, ничего не делая. Во-вторых, свести к минимуму буфер, выполняя дополнительные шаги записи, когда read опережает write, а очередь не пуста.

Ответ 2

Я бы пошел с вашим планом, выделив несколько важных моментов.

Шаг стирания/замены должен начинаться слева и только перемещать точки в пределах диапазона - он может оставить "пробел". Он должен определять размер конечного вектора. В конце этого шага используйте определенный размер, чтобы переместить "хвост" вектора по мере необходимости, оставив точный объем пространства, необходимого для вставки бесплатно.

Вставки должны начинаться справа и заполнять промежуток, который мы оставили на шаге 1, копируя каждую точку в конечную позицию.

Это никогда не будет сдвигать основной вектор один раз и никогда не копировать какую-либо точку (из существующего среза или набора вставки) более чем в два раза, чтобы она была по существу линейной.

Другие структуры данных также могут оказаться полезными - резервирование пространства как спереди, так и конца или создание его из нескольких разделов, поэтому изменение размера не приведет к полной копии.

Еще одна оптимизация будет заключаться в том, чтобы разрешить некоторые вставки во время шага 1. Если вы удалили некоторые из них, завершите любую вставку, которую вы сразу встретите, пока она не сравняется, чтобы вам не пришлось перемещать какие-либо точки, пока вы не достигнете другого удаления.

Ответ 3

Пусть n - размер списка, а m - размер вектора. Похоже, что ier выполняет бинарный поиск j каждый раз, поэтому поисковая часть O(n*log(m)).

Предполагая, что элементы в списке отсортированы, как только вы найдете первый элемент, быстрее перейти к вектору, чтобы найти следующий. Таким образом, поиск становится O(log(m) + n) = O(n).

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

Ответ 4

Я могу предложить другой дизайн для разреженной матрицы, которая должна помочь вам добиться производительности и низкого объема памяти для больших разреженных матриц. Вместо вектора, почему бы не использовать 2D хеш-таблицу. что-то вроде (no std:: для меньшего кода):

typedef unordered_map< unsigned /* index */, int /* value */ > col_type;
unordered_map< unsigned /* index */, col_type*>; // may need to define hash function for col_type

внешний класс (sparse_matrix) выполняет поиск в O (1) для столбца. Если не найден, он выделяет новый столбец. Затем тип столбца ищет индекс столбца в O (1) и либо удаляет/заменяет, либо вставляет на основе исходной логики. Он может видеть, пустой ли столб и удалить его из хэш-карты "строка".

все основные операции add/delete/replace - O (1). Если вам нужна быстрая упорядоченная итерация матрицы, вы можете заменить unordered_map на "карту". Если матрица очень разрежена, сложность O (nlog (n)) будет похожа на hash_map. BTW Я использовал указатель на col_type на кошельке, внешний хэш-карта растет намного (намного!) Быстрее таким образом.