Рассчитать сумму каждого столбца разреженной матрицы с помощью C

Question

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

 Matrix =   [1 2 0 4 0 0 0 0;
             0 1 3 0 2 0 0 0;
             1 0 4 7 0 0 0 0;
             0 6 0 0 1 8 0 0;
             0 0 0 0 4 0 0 0;
             0 0 0 0 8 1 1 0;
             0 0 0 0 9 0 2 0;
             0 0 0 0 0 0 7 1]

Может, кто-нибудь посоветует, как решить эту проблему?Обратите внимание, что это образец матрицы, и на практике у меня огромные матрицы размеров (15 000 строк x 25 000 столбцов)

Answer 1

Может, кто-нибудь посоветует, как решить эту проблему?

1. Узнайте все необходимые и дополнительные операции над разреженными матрицами.

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

2. Выбратьправильный тип для описания значений в матрице.

   В частности, я рекомендую рассмотреть значения типа float, double, unsigned char, char со знаком, uint N _t и int N _t типов (для N = 8, 16, 32 или 64).

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

3. Выберите, какие структуры данных вы будете использовать для реализации разреженной матрицы.

   Статья Википедии о sparseМатрица описывает несколько типичных структур (DOK, LIL, COO, CSR, CSC, Yale).Если вы реализуете более одного, вам нужно будет написать не только все низкоуровневые операции для каждой, но и все комбинации для арифметических операций.(Например, если ваши разреженные матрицы используют форматы сжатой разреженной строки (CSR) или сжатого разреженного столбца (CSC), то вам потребуются четыре подпрограммы умножения матрицы на матрицу в зависимости от типов матриц с двумя аргументами (CSR × CSR,CSC × CSR, CSR × CSC, CSC × CSC), поскольку умножение матриц не является коммутативным.)

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

4. Напишите основные матричные процедуры ввода / вывода и модульные тесты для проверки правильности работы ваших структур данных.

   Как правило, вам нужно читать и писатьэти матрицы из / в файлы или потоки (например, стандартный ввод и вывод).Напишите те сначала.Затем напишите некоторые функции отладки, которые описывают, как хранятся данные матрицы.Как минимум, вы захотите написать тестовую программу, которая считывает матрицу (из стандартного ввода), печатает ее (в стандартный вывод) и формат хранения (в стандартную ошибку);Вы можете предоставить ему несколько входов тестового примера (по крайней мере, один со случайными данными), чтобы проверить, сохраняют ли данные туда и обратно правильные данные.Я часто использую awk как для генерации наборов тестовых данных, так и для сравнения числового результата с ожидаемым числовым выходом.
   

5. Напишите функцию, которая дает разреженную матрицу M , возвращает вектор строки v , где v _i = ∑ M _{j , i}

   Другими словами, элемент i в v является суммой всех элементов M встолбец i .
   

6. Напишите тестовую программу для своей функции и протестируйте ее.

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

Answer 2

Может, кто-нибудь посоветует, как решить эту проблему?

Вы составляете список, в котором хранятся ненулевые элементы матрицы.Для этого вам понадобится структура, которая определяет, как выглядит элемент такого списка:

struct sparseElement{
    int n;
    int m;
    int value;
}

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

sparseElement* sparse = malloc(n * sizeof(sparseElement))

Где n - количество ненулевых элементов.Затем вы можете заполнить список.

вычислить сумму ненулевых элементов для каждого столбца, используя язык C.

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

Конечно, это только возможная реализация.Большие, устоявшиеся библиотеки используют более сложные и эффективные структуры / алгоритмы.