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

Question

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

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

• если 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, но несколько списков. Это означает редактирование среза разреженной матрицы.

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

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

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

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

• Нетрудно найти алгоритм для эффективного выполнения ТОЛЬКО чистых вставок или сетевых удалений.

• Это труднее, когда любой из двух может произойти.

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

1. Erase/заменить
2. Вставка/замена

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

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

Answer 1

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

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

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

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

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

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

Answer 2

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

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

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

• read находится над ячейкой, которую необходимо удалить. В этом случае просто переместите read вперед без, добавляя что-нибудь в очередь.

• read переходит из одной ячейки в другую, чтобы между ними происходило вложение. В этом случае добавьте вставку в конец очереди, а затем перейдите к следующему соответствующему случаю.

• read находится в ячейке, которая нуждается в модификации. В этом случае вставьте измененную ячейку в конец очереди, напишите все, что находится впереди очереди, до write и поместите их вперед.

• read пришел на неиспользованную емкость вектора. В этом случае только write все, что осталось в очереди.

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

Answer 3

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

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

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

Answer 4

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

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 на «map». Если матрица очень разрежена, сложность O (nlog (n)) будет похожа на hash_map. BTW Я использовал указатель на col_type на кошельке, внешний хэш-карта растет намного (намного!) Быстрее таким образом.