Реализация алгоритма в C# представляется катастрофической

Question

Я пытался реализовать алгоритм, указанный в этой статье: [здесь - пожалуйста, игнорируйте математику, поскольку она не имеет отношения к вопросу] [2]. Этот алгоритм очень прост в формальном концептуальном анализе. Вход представляет собой матрицу NXM, хранящуюся как X и . в TXT-файле. В соответствии с введенным в документе псевдокодом вход должен быть представлен как матрица

Answer 1

Не имея возможности увидеть источник реализации C++, с которым вы сравниваете, невозможно точно сказать, почему это намного быстрее, чем ваш код на C#, но поскольку каждое из ваших значений равно 0 или 1, то одна оптимизация, которую вы можете сделать (за счет повышения вашего кода), заключается в том, чтобы хранить значения в какой-либо структуре данных битмаски или точно так же, как упакованные значения битов в массивах int и использовать операции манипуляции бит, чтобы манипулировать ими. Возможно, реализация C++ делает это, но это не показано в опубликованном псевдокоде для удобства объяснения.

Например, поскольку CT_WIDTH равно 126, вы можете сохранить одну строку в 4 х 32-разрядных целых числах (128 бит) вместо 126 целых чисел.

Тогда такие операции, как это:

match = true; 
for (int j = 0; j < CT_WIDTH; j++) 
{ 
    if (B[j] == 1 && FCAContext[rows[y][i] * CT_WIDTH + j] == 0) 
    { 
     match = false; 
     break; 
    } 
} 

Может быть переписано, как это, эффективно обрабатывать 32 значений одновременно:

// CT_WIDTH_SHIFTED = (CT_WIDTH + 31)/32 
match = true; 
int index = rows[y][i] * CT_WIDTH_SHIFTED; 
for (int j = 0; j < CT_WIDTH_SHIFTED; j++) 
{ 
    if (B[j] & FCAContext[index + j] != B[j]) 
    { 
     match = false; 
     break; 
    } 
} 

Аналогично, это:

for (int j = 0; j < CT_WIDTH; j++) 
    if (FCAContext[rows[y][i] * CT_WIDTH + j] == 0) 
     D[j] = 0; 

Может быть переписана как

for (int j = 0; j < CT_WIDTH_SHIFTED; j++) 
    D[j] &= FCAContext[index + j]; 

Значения в FCAContext, D и B должны храниться как упакованные биты.

Например, чтобы установить бит в массиве, вместо того, чтобы использовать такой код, чтобы установить ий элемент в целочисленном массиве:

B[j] = 1; 

вы бы прежде всего вычислить индекс путем деления J на 32, сдвинув влево на 5 (j >> 5) и вычислив бит внутри элемента следующим образом: < < (j & 31), который сдвинут справа на оставшуюся часть j, деленную на 32, затем установите его побитно ИЛИ:

B[j >> 5] |= 1 << (j & 31) 

Here's онлайн-учебник о маскировании бит. Дополнительные сведения см. В разделе «Бит-манипуляция», «бит-сдвиг», «бит-маскировка», «бит-хакинг» и «бит-операции»/«побитовые операции». Бит-манипуляция может быть довольно затруднительной и делает ваш код трудным для чтения.

Также рассмотрите возможность использования класса .NET BitArray.