Функция проверки равенства

Question

Ниже приведена функция, которая предназначена для проверки равенства между соседними числами в одномерном векторе.

Этот 1D вектор будет иметь значения, которые будут представлять сетку nxn. [v это вектор]

Когда они равны, возвращается false.

Например, рассмотрим эту сетку 3x3:

i\j| 0 | 1 | 2
0  | 1 | 2 | 3
1  | 4 | 5 | 6
2  | 7 | 8 | 9

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

В дополнение к тому, что я написал, похоже, не самый эффективный способ сделать это. Конечно, может быть более простой способ сделать это, чем перечислять 5 новых переменных?

for( int i= 0; i < n ; i++ ){
    for( int j = 0; j < n; j++){
        int x = v[convert(i, j, n)];
        int c = v[convert(i-1, j, n)];
        int s = v[convert(i+1, j, n)];
        int b = v[convert(i, j+1, n)];
        int n = v[convert(i, j-1, n)];

        if (x == c || x == s || x == b || x == n ) {
            return false;
        }
    }
}

//another function used to convert 2d into 1D index
 int convert(int row, int col, int rowlen){
    return row*rowlen+col;
}

Буду признателен за любую помощь.

Answer 1

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

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

Первой оптимизацией было бы разделение операции на тесты строк и столбцов:

// Test adjacency in rows
for (const int *rowptr = v, *end = v + n * n;
     rowptr != end;
     rowptr += n)
{
    for (int col = 1; col < n; col++) {
        if (rowptr[col-1] == rowptr[col]) return false;
    }
}

// Test adjacency in columns
for (const int *row0ptr = v, *row1ptr = v + n, *end = v + n * n;
     row1ptr != end;
     row0ptr = row1ptr, row1ptr += n)
{
    for (int col = 0; col < n; col++) {
        if (row0ptr[col] == row1ptr[col]) return false;
    }
}

Чтобы не делать два прохода по всему массиву, вам нужно их объединить, но он начинает становиться немного запутанным. Обратите внимание, что два отдельных прохода в настоящее время имеют разные границы (цикл проверки строк от столбца 1 до n, тогда как цикл проверки столбцов от строки 0 до n-1).

Объединение циклов имеет смысл только в том случае, если n достаточно велико и если абсолютно критично, что этот фрагмент кода быстр. Идея состоит в том, чтобы выполнить один проход через весь массив, избегая проблем с такими вещами, как пропадание кэша L1 во втором проходе.

Это будет выглядеть примерно так:

const int *row0ptr = v, *row1ptr = v + n, *end = v + n * n
for ( ; row1ptr != end; row0ptr = row1ptr, row1ptr += n)
{
    // Test first column
    if (row0ptr[0] == row1ptr[0]) return false;

    // Test row0 and remaining columns
    for (int col = 1; col < n; col++) {
        if (row0ptr[col-1] == row0ptr[col]) return false;
        if (row0ptr[col] == row1ptr[col]) return false;
    }
}

// Test last row
for (int col = 1; col < n; col++) {
    if (row0ptr[col-1] == row0ptr[col]) return false;
}

Answer 2

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

     int x = v[convert(i, j, n)];
     if (i > 0 && x == v[convert(i-1, j, n)])
         return false;
     if (i < n - 1 && x == v[convert(i+1, j, n)])
         return false;
     if (j > 0 && x == v[convert(i, j-1, n)])
         return false;
     if (j < n - 1 && x == v[convert(i, j+1, n)])
         return false;