Эффективная (временная и пространственная сложность) структура данных для плотной и разреженной матрицы

Мне нужно прочитать файл, в котором хранится матрица с автомобилями (1 = BlueCar, 2 = RedCar, 0 = Empty).

Мне нужно написать алгоритм для перемещения машин матрицы таким образом:

  • синие движутся вниз;
  • красные двигаются вправо;
  • есть поворот, в котором движутся все синие, и поворот для перемещения всех красных.

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

Мне нужно достичь наилучшего возможного времени и пространства.

Из-за неизвестного размера матрицы, я думаю, хранить данные в куче.

Если матрица плотная, я думаю использовать что-то вроде:

short int** M = new short int*[m];
short int*  M_data = new short int[m*n];

for(int i=0; i< m; ++i) 
{
    M[i] = M_data + i * n;
}

С помощью этой структуры я могу выделить непрерывное пространство памяти, а также получить доступ к M[i][j].

Теперь проблема заключается в структуре выбора для случая разреженного, и я должен также рассмотреть, как я могу перемещать автомобили по алгоритму самым простым способом: например, когда я оцениваю автомобиль, Мне нужно легко найти, если в следующей позиции (вниз или вправо) есть другой автомобиль или если он пуст.

Сначала я решил определить объекты BlueCar и RedCar, которые наследуются от общего объекта Car. В этих объектах я могу сохранить координаты матрицы, а затем поместить их в:

std::vector<BluCar> sparseBlu;
std::vector<RedCar> sparseRed;

В противном случае я могу сделать что-то вроде:

vector< tuple< row, column, value >> sparseMatrix

Но проблема поиска того, что в следующей позиции все еще остается.

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

Ответы

Ответ 1

Почему бы просто не создать отображение памяти непосредственно над файлом? (если ваши данные 0,1,2 хранятся в смежных байтах (или битах) в файле, а положение этих байтов также представляет координаты автомобилей)

Таким образом вам не нужно выделять дополнительную память и читать во всех данных, а данные можно легко и эффективно получить с помощью M[i][j].

Переход по строкам будет дружественным к L1.

В случае очень редких данных вы можете просканировать данные один раз и сохранить список пустых областей/блоков в памяти (нужно хранить только начальные значения и размер), которые вы могли бы пропустить (и настроить там, где это необходимо) в дальнейших прогонах.

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

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

Чтобы дополнительно оптимизировать использование пространства и памяти, автомобили могут быть сохранены в 2 битах в файле.

Обновление

Мне нужно будет перемещать автомобили с openMP и MPI... Будет ли отображение памяти работать также с параллельными потоками?

Конечно, вы можете использовать многопоточность, но не уверены, что лучшим решением будет openMP, потому что, если вы работаете одновременно с разными частями данных, вам может потребоваться проверить некоторые перекрывающиеся области (например, автомобиль может двигаться от одного блока к другому).

Или вы можете позволить потокам работать в срединных частях блоков, а затем запускать другие потоки для выполнения границ (с красными автомобилями, которые были бы одним байтом, а синие автомобили - полной строкой).

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

Ответ 2

В несколько схожей задаче я просто использовал сжатое хранилище строк.

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

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

Там уже существует существующая реализация С++.