Оптимальная структура 2D-данных

Question

Я много думал об этом, но на самом деле не смог что-то придумать.

Предположим, что я хочу, чтобы X X собирал элементы, сортируемые по любому столбцу и любой строке под O (m * n), а также возможность вставлять или удалять строку в O (m + n) или меньше .. . Является ли это возможным?

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

Пример sortability:

1 100 25 34 
2 20 15 16 
3 165 1 27 

Сортировка по 3-й ряд:

25 1 34 100 
15 2 16 20 
1 3 27 165 

Сортировка, что к 1-й столбец:

1 3 27 165 
15 2 16 20 
25 1 34 100 

Answer 1

Я бы создал два массива индексов, один для столбцов и один для строк. Таким образом, для данных

1 100 25 34 
2 20 15 16 
3 165 1 27 

создаются два массива:

• cols = [0, 1, 2, 3]
• rows = [0, 1, 2]

Затем, когда вы хотите, чтобы отсортировать матрицу по 3-ю строку, вы сохранить оригинал матрица нетронутой, но просто измените матрицу индексов соответственно:

• cols = [2, 0, 3, 1]
• rows = [0, 1, 2]

Хитрость теперь получить доступ к вашей матрице с одним косвенностью. Поэтому вместо доступа к нему с m[x][y] вы получаете к нему доступ m[cols[x]][rows[y]]. Вы также должны использовать m [cols [x]] [rows [y]] при выполнении переупорядочения массива rows/cols.

Этот способ сортировки O(n*log(n)), и доступ O(1).

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

+-+ 
|0| -> [0 1 2 3 4] 
|1| -> [0 1 2 3 4] 
|2| -> [0 1 2 3 4] 
+-+ 

Чтобы вставить строку, просто вставьте его в последней позиции и обновить массив индекса rows соответственно, с правильное положение. Например. когда rows был [0, 1, 2], и вы хотите вставить его спереди, ряды станут [3, 0, 1, 2]. Таким образом, вставка строки равна O(n).

Чтобы вставить столбец, вы также добавите его в качестве последнего элемента и соответствующим образом обновите cols. Вставка столбца: O(m), строка O(n).

Удаление также O(n) или O(m), здесь вы просто заменяете столбец/строку, которую хотите удалить, с последним, а затем удаляете индекс из массива индексов.

Answer 2

Вы можете использовать хэш-таблицу и вставить (я , j) ->, где (i, j) является 2-кортежем, содержащим 2 целых числа. Вы можете написать собственный собственный класс, который определяет метод Equals и метод GetHash() для этого ... или Python предоставляет его вам бесплатно.

Теперь ... что именно вы имеете в виду - сортируется по строке или столбцу? Приведите пример со значениями!

Answer 3

Возможно, создав для этого небольшую базу данных?

Алгоритмы сортировки баз данных, вероятно, лучше, чем изобретать колесо. MySql будет делать. Чтобы получить производительность, таблица может быть создана в памяти. Затем вы можете индексировать столбцы как обычную таблицу и позволить движку базы данных выполнять грязную работу (заказ и т. Д.). И тогда вы просто собираете результаты.

Answer 4

Если мне была предоставлена ​​эта проблема, я бы создал перенос строк и столбцов. НАПРИМЕР. для сортировки строк я бы определил порядок строк как обычно, но вместо копирования строк я бы просто изменил вектор переопределения строк.

Это будет выглядеть примерно так:

// These need to be set up elsewhere. 
size_t nRows, nCols; 
std::vector<T> data; 

// Remapping vectors. Initially a straight-through mapping. 
std::vector<size_t> rowMapping(nRows), colMapping(nCols); 
for(size_t y = 0; y < nRows; ++y) 
    rowMapping[y] = y; 
for(size_t x = 0; x < nCols; ++x) 
    colMapping[x] = x; 

// Then you read data(row, col) with 
T value = data[rowMapping[row] * nCols + colMapping[col]]; 

P.S. небольшая оптимизация заключалась бы в том, чтобы хранить указатели в rowMapping вместо индексов. Это позволит вам сделать T value = rowMapping[row][colMapping[col]];, однако вам придется пересчитывать указатели каждый раз, когда изменяются размеры data, которые могут быть подвержены ошибкам.

Answer 5

Просто добавьте ответы Мартинуса и Майка: вам нужно, по сути, поворот, что они предлагают, и очень хорошо известную технику, используемую в почти любом числовом алгоритме с использованием матриц. Например, вы можете выполнить быстрый поиск «Разложение LU с частичным поворотным» и «Разложение LU с полным поворотом». Дополнительные векторы, которые хранят перестановки, называются «поворотными».