Строка-майор против замешательства в столбце

Ответ 1

Посмотрим сначала на алгебру; алгебра даже не имеет понятия "макет памяти" и т.д.

Из алгебраического pov реальная матрица MxN может действовать на вектор | R ^ N с правой стороны и дает вектор | R ^ M.

Таким образом, если вы сидели на экзамене и получали MxN Matrix и вектор R ^ N, вы могли бы с тривиальными операциями размножать их и получать результат - будет ли этот результат правильным или неправильным, не будет зависеть от того, использует ли ваше программное обеспечение для проверки ваших результатов внутреннее использование столбца или макета главной строки; это будет зависеть только от того, правильно ли вы рассчитали сокращение каждой строки матрицы с (единственным) столбцом вектора.

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

Таким образом, разница между программным обеспечением, которое выравнивает значение столбца и программное обеспечение, использующее row-major-layout , не является тем, что вычисляет, а просто как.

Чтобы выразить это более подробно, разница между этими макетами в отношении сокращения однорядного числа строк с вектором столбца - это просто средство для определения

Where is the next element of the current row?

• Для строки-мажор-макета это элемент только в следующем ковше в памяти
• Для макета-макета столбца элемент в ковше M заканчивается.

И вот оно.

Чтобы показать вам, как набирается эта магия столбца/строки:

Вы не отметили свой вопрос "С++", но поскольку вы упомянули " glm, я предположим, что вы можете ладить с С++.

В стандартной библиотеке С++ есть печально известный зверь valarray, который, помимо других сложных функций, перегрузки operator [], один из них может принимать std::slice (что по сути является очень скучной вещью, состоящей всего из трех чисел целочисленного типа).

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

Ответ 2

Я думаю, что вы смешиваете детали реализации с использованием, если хотите.

Давайте начнем с двухмерного массива или матрицы:

    | 1  2  3 |
    | 4  5  6 |
    | 7  8  9 |

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

   -+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
    |       |       |       |       |       |       |       |       |  
   -+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
       \/                   \       /
      one byte               one integer

    low memory    ------>                          high memory

Другой способ представления

Итак, вопрос заключается в том, как сопоставить двумерную структуру (нашу матрицу) на эту одномерную структуру (т.е. память). Есть два способа сделать это.

• Строковый порядок: в этом порядке сначала помещаем первую строку в память, а затем вторую и так далее. Сделав это, мы получили бы в памяти следующее:

  -+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |   1   |   2   |   3   |   4   |   5   |   6   |   7   |   8   |   9   |
  -+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  

С помощью этого метода мы можем найти данный элемент нашего массива, выполнив следующую арифметику. Предположим, мы хотим получить доступ к элементу $M_ {ij} $массива. Если мы предположим, что у нас есть указатель на первый элемент массива, скажем ptr, и знаете количество столбцов, которые говорят nCol, мы можем найти любой элемент по:

     $M_{ij} = i*nCol + j$ 

Чтобы увидеть, как это работает, рассмотрим M_ {02} (т.е. первая строка, третий столбец - помните, что C основано на нуле.

      $M_{02} = 0*3 + 2 = 2

Итак, мы получаем доступ к третьему элементу массива.

2. Порядок сортировки по столбцу: в этом порядке сначала помещаем первый столбец в память, а затем второй, и так далее. Сделав это, мы получили бы в памяти следующее:

   -+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |   1   |   4   |   7   |   2   |   5   |   8   |   3   |   6   |   9   |
   -+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   

SO, формат short answer - row-major и column-major описывает, как два (или более высоких) размерных массива отображаются в одномерный массив памяти.

Надеюсь, это поможет. Т.

Ответ 3

Вы правы. неважно, хранит ли система данные в строковой структуре или столбце-майоре. Это как протокол. Компьютер: "Эй, человек. Я собираюсь хранить ваш массив таким образом. Нет проблем. Однако, когда дело доходит до производительности, это имеет значение. рассмотрим следующие три вещи.

1. большинство массивов доступны в строчном порядке.

2. Когда вы обращаетесь к памяти, она не считывается непосредственно из памяти. Сначала вы храните несколько блоков данных из памяти в кеш, затем читаете данные из кеша в ваш процессор.

3. Если требуемые данные отсутствуют в кеше, кеш должен повторно извлекать данные из памяти

Когда кеш извлекает данные из памяти, важна локальность. То есть, если вы редко храните данные в памяти, ваш кеш должен чаще извлекать данные из памяти. Это действие искажает производительность ваших программ, поскольку доступ к памяти намного медленнее (более 100 раз!), А затем доступ к кешу. Чем меньше вы получаете доступ к памяти, тем быстрее ваша программа. Таким образом, этот массив строк является более эффективным, поскольку доступ к его данным с большей вероятностью будет локальным.

Ответ 4

Неважно, что вы используете: просто будьте последовательны!

Строка майора или столбца - это просто соглашение. Не имеет значения. C использует строку major, Fortran использует столбец. Оба работают. Используйте какой стандарт в своем языке программирования/среде.

Несоответствие двух будет! @# $stuff up

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

Row major: A(i,j) element is at A[j + i * n_columns];  <---- mixing these up will
Col major: A(i,j) element is at A[i + j * n_rows];     <---- make your code fubar

Неверно сказать, что код для умножения матрицы одинаковый для основной строки и столбца

(Конечно, математика умножения матрицы одинакова). Представьте, что у вас в памяти два массива:

X = [x1, x2, x3, x4]    Y = [y1, y2, y3, y4]

Если матрицы хранятся в столбце майор, то X, Y и X * Y:

IF COL MAJOR: [x1, x3  *  [y1, y3    =   [x1y1+x3y2, x1y3+x3y4
               x2, x4]     y2, y4]        x2y1+x4y2, x2y3+x4y4]

Если матрицы хранятся в строке major, то X, Y и X * Y:

IF ROW MAJOR:  [x1, x2    [y1, y2     = [x1y1+x2y3, x1y2+x2y4;
                x3, x4]    y3, y4]       x3y1+x4y3, x3y2+x4y4];

X*Y in memory if COL major   [x1y1+x3y2, x2y1+x4y2, x1y3+x3y4, x2y3+x4y4]
              if ROW major   [x1y1+x2y3, x1y2+x2y4, x3y1+x4y3, x3y2+x4y4]

Здесь нет ничего глубокого. Это всего лишь два разных соглашения. Это как измерение в милях или километрах. Либо работает, вы просто не можете переворачивать назад и вперед между ними без преобразования!

Ответ 5

Хорошо, поэтому, учитывая, что слово "путаница" буквально в названии, я могу понять уровень... путаницы.

Во-первых, эта абсолютно является реальной проблемой

Никогда, НИКОГДА не поддавайтесь идее, что "он используется, но... ПК в настоящее время..."

Из основных проблем здесь: -Cache eviction strategy (LRU, FIFO, etc.) as @Y.C.Jung was beginning to touch on -Branch prediction -Pipelining (it depth, etc) -Actual physical memory layout -Size of memory -Architecture of machine, (ARM, MIPS, Intel, AMD, Motorola, etc.)

Этот ответ будет сосредоточен на архитектуре Гарварда, машине Фон Неймана, поскольку он наиболее применим к текущему компьютеру.

Иерархия памяти:

https://en.wikipedia.org/wiki/File:ComputerMemoryHierarchy.svgis

Является сопоставлением стоимости и .

Для сегодняшней стандартной системы ПК это будет примерно так: SIZE: 500GB HDD > 8GB RAM > L2 Cache > L1 Cache > Registers. SPEED: 500GB HDD < 8GB RAM < L2 Cache < L1 Cache < Registers.

Это приводит к идее временной и пространственной локальности. Один из них означает как ваши данные организованы (код, рабочий набор и т.д.), Другое означает физически , где ваши данные организованы в "память".

Учитывая, что "большинство" сегодняшних ПК - это машины малоподобные (Intel), в последнее время они закладывают данные в память в определенном порядке с маленьким порядком. Это принципиально отличается от "большой".

https://www.cs.umd.edu/class/sum2003/cmsc311/Notes/Data/endian.html (покрывает его скорее... swiftly;))

(Для простоты этого примера я собираюсь "сказать", что все происходит в отдельных записях, это неверно, к ним обычно обращаются целые блоки кэша и сильно меняют своего производителя, а тем более модель).

Итак, теперь, когда у нас есть наш путь, если гипотетически ваша программа потребовала 1GB of data from your 500GB HDD, загрузилась в ваш 8GB of RAM,, затем в иерархию cache, а затем в конечном итоге registers, где ваша программа пошла и прочитала первую запись из вашей самой свежей строки кэша только для того, чтобы иметь вторую (в ВАШЕМ коде) желаемую запись, которая сидит в next cache line, (т.е. следующая ROW вместо столбца у вас будет кеш MISS.

Предполагая, что кеш заполнен, поскольку он маленький, при промахе, согласно схеме выселения, будет выведена строка, чтобы освободить место для линии, которая "Имеет" следующие данные, которые вам нужны. Если этот шаблон повторяется, у вас будет MISS на КАЖДОМ попытке получения данных!

Хуже того, вы будете высекать строки, которые действительно имеют действительные данные, которые вам понадобятся, поэтому вам нужно будет найти их СНОВА и СНОВА.

Термин для этого называется: thrashing

https://en.wikipedia.org/wiki/Thrashing_(computer_science) и действительно может сбой плохо написанной/подверженной ошибкам системы. (Подумайте о Windows BSOD)....

С другой стороны, если вы правильно выложили данные (т.е. строчный ряд)... вы ДОЛЖНЫ все еще иметь промахи!

Но эти промахи будут только появляться в конце каждого поиска, а не на КАЖДОЙ попытке поиска.. Это приводит к порядку разницы в производительности системы и программы.

Очень простой фрагмент:

#include<stdio.h>

#define NUM_ROWS 1024
#define NUM_COLS 1024

int COL_MAJOR [NUM_ROWS][NUM_COLS];

int main (void){
        int i=0, j=0;
        for(i; i<NUM_ROWS; i++){
                for(j; j<NUM_COLS; j++){
                        COL_MAJOR[j][i]=(i+j);//NOTE i,j order here!
                }//end inner for
        }//end outer for
return 0;
}//end main

Теперь скомпилируйте с помощью gcc -g col_maj.c -o col.o

Теперь запустите с помощью time ./col.o real 0m0.009s user 0m0.003s sys 0m0.004s

Теперь повторите для майнера ROW:

#include<stdio.h>

#define NUM_ROWS 1024
#define NUM_COLS 1024

int ROW_MAJOR [NUM_ROWS][NUM_COLS];

int main (void){
        int i=0, j=0;
        for(i; i<NUM_ROWS; i++){
                for(j; j<NUM_COLS; j++){
                        ROW_MAJOR[i][j]=(i+j);//NOTE i,j order here!
                }//end inner for
        }//end outer for
return 0;
}//end main

Compile: terminal4$ gcc -g row_maj.c -o row.o Run: time ./row.o real 0m0.005s user 0m0.001s sys 0m0.003s

Теперь, как вы можете видеть, Строка была значительно быстрее.

Не уверены? Если вы хотите увидеть более резкий пример: Сделайте матрицу 1000000 x 1000000, инициализируйте ее, перенесите ее и распечатайте на стандартный вывод. `` `

(Обратите внимание, что в системе * NIX вам нужно установить ulimit unlimited)

ВОПРОСЫ с моим ответом: -Optimizing compilers, they change a LOT of things! -Type of system -Please point any others out -This system has an Intel i5 processor

Ответ 6

Сегодня нет оснований использовать другой порядок столбцов и столбцов, существует несколько библиотек, которые поддерживают его в c/С++ (eigen, armadillo,...). Кроме того, порядок столбцов более естественный, например. снимки с [x, y, z] хранятся в виде среза по фрагменту в файле, это порядок столбцов. Хотя в двух измерениях может возникнуть проблема выбора лучшего порядка, в более высоком измерении совершенно ясно, что порядок столбцов - это единственное решение во многих ситуациях.

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

Странно, что кто-то создает библиотеку с порядком строки. Это ненужная трата энергии и времени. Надеюсь, что в один прекрасный день все будет упорядочено по колонке, и все путаницы просто исчезнут.

Ответ 7

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

• подробно объясняется в предыдущих ответах, поэтому я добавлю к 2.

Ответ eulerworks указывает, что в его примере использование основной матрицы строк привело к значительному замедлению в расчете. Ну, он прав, но результат может быть в то же время отменен.

Порядок цикла был для (над строками) {для (над столбцами) {сделать что-то над матрицей}}. Это означает, что двойной цикл будет обращаться к элементам в строке, а затем перейти к следующей строке. Например, A (0,1) → A (0,2) → A (0,3) → ... → A (0, N_ROWS) → A (1,0) → ...

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

Теперь мы можем переключить цикл таким образом, чтобы он выполнял (над столбцами) {для (над строками) {что-то делать над матрицей}}. Для этого случая результат будет точно противоположным. Основной расчет столбца будет быстрее, поскольку цикл будет считывать элементы в столбцах линейным образом.

Следовательно, вы могли бы также помнить об этом: 1. Выбор формата хранения основных строк или столбцов зависит от вашего вкуса, хотя традиционное сообщество программирования C, похоже, предпочитает формат строки. 2. Хотя вы в значительной степени свободны в выборе того, что вам может понравиться, вы должны быть совместимы с понятием индексации. 3. Кроме того, это очень важно, имейте в виду, что при написании своих собственных алгоритмов попробуйте упорядочить циклы, чтобы он соблюдал формат хранения по вашему выбору. 4. Будьте последовательны.

Ответ 8

Учитывая приведенные выше объяснения, приведен фрагмент кода демонстрирующий концепцию.

//----------------------------------------------------------------------------------------
// A generalized example of row-major, index/coordinate conversion for
// one-/two-dimensional arrays.
// ex: data[i] <-> data[r][c]
//
// Sandboxed at: http://swift.sandbox.bluemix.net/#/repl/5a077c462e4189674bea0810
//
// -eholley
//----------------------------------------------------------------------------------------

// Algorithm

let numberOfRows    = 3
let numberOfColumns = 5
let numberOfIndexes = numberOfRows * numberOfColumns

func index(row: Int, column: Int) -> Int {
    return (row * numberOfColumns) + column
}

func rowColumn(index: Int) -> (row: Int, column: Int) {
    return (index / numberOfColumns, index % numberOfColumns)
}

//----------------------------------------------------------------------------------------

// Testing

let oneDim = [
       0,    1,    2,    3,    4,
       5,    6,    7,    8,    9,
      10,   11,   12,   13,   14,
]

let twoDim = [
    [  0,    1,    2,    3,    4 ],
    [  5,    6,    7,    8,    9 ],
    [ 10,   11,   12,   13,   14 ],
]

for i1 in 0..<numberOfIndexes {
    let v1 = oneDim[i1]
    let rc = rowColumn(index: i1)
    let i2 = index(row: rc.row, column: rc.column)
    let v2 = oneDim[i2]
    let v3 = twoDim[rc.row][rc.column]
    print(i1, v1, i2, v2, v3, rc)
    assert(i1 == i2)
    assert(v1 == v2)
    assert(v2 == v3)
}

/* Output:
0 0 0 0 0 (row: 0, column: 0)
1 1 1 1 1 (row: 0, column: 1)
2 2 2 2 2 (row: 0, column: 2)
3 3 3 3 3 (row: 0, column: 3)
4 4 4 4 4 (row: 0, column: 4)
5 5 5 5 5 (row: 1, column: 0)
6 6 6 6 6 (row: 1, column: 1)
7 7 7 7 7 (row: 1, column: 2)
8 8 8 8 8 (row: 1, column: 3)
9 9 9 9 9 (row: 1, column: 4)
10 10 10 10 10 (row: 2, column: 0)
11 11 11 11 11 (row: 2, column: 1)
12 12 12 12 12 (row: 2, column: 2)
13 13 13 13 13 (row: 2, column: 3)
14 14 14 14 14 (row: 2, column: 4)
*/