Существует ли эффективная структура данных для обмена строками и столбцами?

Question

У меня есть матрица чисел, и я хотел бы иметь возможность:

1. Поменять строки
2. Обмен столбцов

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

У меня есть отчетливое ощущение, что нет беспроигрышной структуры данных, которая дает O (1) для обеих операций, хотя я не уверен, как это доказать. Или я не прав?

Answer 1

Не подумав об этом полностью:

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

m = 
[0] -> 1 2 3
[1] -> 4 5 6
[2] -> 7 8 9 

c[] {0,1,2}

Теперь, чтобы обменять столбцы 1 и 2, вы просто измените c на {0,2,1}

Когда вы захотите прочитать строку 1, вы сделаете

for (i=0; i < colcount; i++) {
   print m[1][c[i]];
}

Answer 2

Просто случайность, хотя здесь (нет опыта, насколько хорошо это действительно работает, и без кофе поздно ночью):

Я думаю, что внутренняя часть матрицы должна быть хеш-таблицей, а не массивом.

Каждая ячейка в массиве имеет три элемента информации:

1. Строка, в которой находится ячейка
2. Столбец, в котором находится ячейка
3. Значение ячейки

На мой взгляд, это легко представить кортежем ((i, j), v), где (i, j) обозначает положение ячейки (i-я строка, j-й столбец), а v

Это было бы несколько нормальное представление матрицы. Но давайте отвлечемся от идей здесь. Вместо i, обозначающего строку как позицию (т. Е. От 0 до 1 до 2 до 3 и т. Д.), Давайте просто рассмотрим i как своего рода канонический идентификатор для соответствующей ей строки. Давайте сделаем то же самое для j. (Хотя в самом общем случае i и j могут быть неограниченными, давайте предположим простой случай, когда они останутся в пределах [0..M] и [0..N] для M x N матрицы, но не обозначают фактические координаты ячейки).

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

int RowMap[M];

Для m-й строки RowMap[m] дает идентификатор строки в текущей матрице.

Мы будем использовать то же самое для столбцов:

int ColumnMap[N];

где ColumnMap[n] - идентификатор n-го столбца.

Теперь вернемся к хеш-таблице, которую я упоминал в начале:

Поскольку у нас есть полная информация (размер матрицы), мы должны быть в состоянии генерировать идеальную функцию хеширования (без коллизий). Вот одна из возможностей (для массивов небольшого размера):

int Hash(int row, int column)
{
    return row * N + column;
}

Если это хеш-функция для хеш-таблицы, мы должны получить нулевые коллизии для большинства размеров массивов. Это позволяет нам читать / записывать данные из хеш-таблицы за O (1) раз.

Классная часть связывает индекс каждой строки / столбца с идентификаторами в хеш-таблице:

// row and column are given in the usual way, in the range [0..M] and [0..N]
// These parameters are really just used as handles to the internal row and
// column indices
int MatrixLookup(int row, int column)
{
    // Get the canonical identifiers of the row and column, and hash them.
    int canonicalRow = RowMap[row];
    int canonicalColumn = ColumnMap[column];
    int hashCode = Hash(canonicalRow, canonicalColumn);

    return HashTableLookup(hashCode);
}

Теперь, поскольку интерфейс к матрице использует только эти дескрипторы, а не внутренние идентификаторы, операция swap строк или столбцов соответствует простому изменению в массиве RowMap или ColumnMap:

// This function simply swaps the values at
// RowMap[row1] and RowMap[row2]
void MatrixSwapRow(int row1, int row2)
{
    int canonicalRow1 = RowMap[row1];
    int canonicalRow2 = RowMap[row2];

    RowMap[row1] = canonicalRow2
    RowMap[row2] = canonicalRow1;
}

// This function simply swaps the values at
// ColumnMap[row1] and ColumnMap[row2]
void MatrixSwapColumn(int column1, int column2)
{
    int canonicalColumn1 = ColumnMap[column1];
    int canonicalColumn2 = ColumnMap[column2];

    ColumnMap[row1] = canonicalColumn2
    ColumnMap[row2] = canonicalColumn1;
}

Так и должно быть - матрица с O (1) доступом и мутацией, а также O (1) перестановкой строк и O (1) перестановкой столбцов. Конечно, даже O (1) хеш-доступ будет медленнее, чем O (1) доступа на основе массива, и будет использоваться больше памяти, но по крайней мере существует равенство между строками / столбцами.

Я старался быть как можно более агностиком, когда дело доходит до того, как именно вы реализуете свою матрицу, поэтому я написал несколько C. Если вы предпочитаете другой язык, я могу изменить его (было бы лучше, если бы вы поняли), но я думаю, что это довольно информативно, хотя я не могу гарантировать, что это исправление в отношении C, так как я на самом деле парни из C ++, пытающиеся вести себя как парни из C прямо сейчас (и я упоминал, что у меня нет кофе ?). Лично, написание на полном ОО-языке сделало бы это более привлекательным, а также придало бы коду некоторую прелесть, но, как я уже сказал, это было быстрое внедрение.