Оптимальная 2D структура данных
Я дал это длительное размышление, но действительно не смог придумать что-то.
Предположим, что я хочу m X n наборов элементов, поддающихся сортировке каким-либо столбцом и какой-либо строкой в под 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
5 ответов
Я бы создал два указательных массива, один для столбцов, а другой для строк. Итак, для ваших данных
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).
Для вставки столбца вы также добавляете его как последний элемент и соответствующим образом обновляете столбцы. Вставка столбца имеет вид O(m), строка - O(n).
Удаление также O(n) или O(m), здесь вы просто заменяете столбец/строку, которую хотите удалить, на последнюю, а затем удаляете индекс из массива индексов.
Вы можете использовать хэш-таблицу и вставить (i,j) -> узел, где (i,j) - это 2-тройка, содержащая 2 целых числа. Вы можете написать свой собственный пользовательский класс, который определяет метод Equals и метод GetHash() для этого ... или Python предоставляет его вам бесплатно.
Теперь ... что именно вы имеете в виду - сортировка по строке или столбцу? Приведите пример со значениями, пожалуйста!
Возможно, создав для него небольшую базу данных?
Алгоритмы сортировки баз данных, вероятно, лучше, чем изобретать колесо заново. Сделал бы MySql. Для повышения производительности таблицу можно создавать в памяти. Затем можно индексировать по столбцам, как обычную таблицу, и пусть движок базы данных делает грязную работу (упорядочивание и тому подобное). И тогда вы просто получите результат.
Просто чтобы добавить к ответам Мартинуса и Майка: то, что вам нужно, это, по сути, поворот, который они предлагают, и очень известная техника, используемая практически в любом численном алгоритме, включающем матрицы. Например, вы можете запустить быстрый поиск "LU декомпозиция с частичным поворотом" и "LU декомпозиция с полным поворотом". Дополнительные векторы, хранящие перестановки, называются "поворотами".
Если бы я передал эту проблему, я бы создал ряд и столбец, перенапряжение векторов. НАПРИМЕР. Чтобы сортировать строки, я бы определил порядок строки как обычно, но вместо копирования строк, я бы просто изменил вектор перезарядки ряда.
Это будет выглядеть что-то подобное:
// 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 = Rowmapping [ROW] [Colmapping [COL]]; ; ; , однако, вам придется пересчитать указатели каждый раз, что размеры данных изменяется, который может быть подвержен ошибкам.