Найти уникальные строки в двоичном двумерном массиве

Question

Распечатайте номера строк, которые являются уникальными.

Следующая моя реализация:

#include <iostream> 
#include <cmath> 

int rowsToInt(int m[][5], int row, int cloumLen) { 
    int sum = 0; 
    // m[row][column] 
    for (int i = 0; i < cloumLen; i++) { 
     sum += m[row][i]*(std::pow(2,i)); 
    } 
    return sum; 
} 

void removeDuplicate(int m[][5], int row, int column) { 
    if (!m) { 
     return; 
    } 

    int tracker = 0; 
    int mask = 1; 
    int value; 

    for (int i = 0; i < row; i++) { 
     value = rowsToInt(m, i, column); // 3 
     if (((mask << (value - 1)) & tracker) == 0) { 
      // print unique row 
      std::cout << "row: " << i << " is unique" << std::endl; 

      // set that bit to 1 
      tracker = tracker^(mask << (value - 1)); 
     } 
    } 
} 

int main() { 
    int array[5][5] = { 
     {0,1,0,0,1}, 
     {1,0,1,1,0}, 
     {0,1,0,0,1}, 
     {1,1,1,0,0}, 
     {1,1,0,1,1} 
    }; 
    removeDuplicate(array, 5, 5); 
    return 0; 
} 

выход:

row: 0 is unique 
row: 1 is unique 
row: 3 is unique 
row: 4 is unique 

что время работы? Я думаю, что его O (строка строки *); потому что каждую строку посещают каждый элемент столбца.

Это оптимальное время работы?

Answer 1

Самая медленная часть в вашем коде std::pow(), для массива с 200000 строк он будет назвать один миллион раз, что занимает значительное время, так что не использовать его в петлях без необходимости. Если вам нужны полномочия 2, самым быстрым способом является использование побитового вращения, как и @chqrlie. В общем, если вам нужны мощности на N, вы можете получить их следующим образом:

int rowsToInt (bool m[][5], int row, int cloumLen) { 
    int sum = 0; 
    for (int i = 0, p = 1; i < cloumLen; i++) { 
     sum += m[row][i]*p; 
     p *= N; 
    } 
    return sum;  
} 

Теперь для оптимизации. Если вы работаете с бинарной матрицей, почему вы используете целочисленную? Он занимает в 4 раза больше оперативной памяти, поэтому используйте bool array[rows][cols]. Количество строк и столбцов - это константы, поэтому нет необходимости передавать их в функции. Вы можете просто объявить глобальным const int rows = 7, cols = 5. И еще один важный фактор. Если вы ищете уникальные двоичные строки в большой матрице, стоит подсчитать найденные. Если вы уже нашли 2^cols из них, просто оставьте цикл.

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

Более компактный способ:

// the code inside removeDuplicate function 
unsigned long tracker = 0; // now it looks like 32 zeros 
for (int i = 0; i < row; ++i) { 
    int value = rowsToInt (m, i, column); // getting dec value 

    if (((tracker >> value) & 1) == 0) { // if the valueth bit is equal to zero 
     tracker |= (1UL << value); // set it equal to one 
     std::cout << "row: " << i << " is unique" << std::endl; 
     if (tracker = 0xffffffff) return; // if all bits are equal to 1, we've found all the unique rows 
    } 
} 

И один из самых простых:

// the code inside removeDuplicate function 
bool found[32] = {false}; // using array instead of UL 
int counter = 0; // and simple counter of unique rows 

for (int i = 0; i < row; i++) { 
    int value = rowsToInt (m, i, column); // getting dec value 

    if (!found[value]) { // if the valueth element is equal to zero 
     found[value] = true; // set it equal to one 
     ++counter; // and increase the counter 
     std::cout << "row: " << i << " is unique" << std::endl; 
     if (counter == 32) return; 
    } 
} 

Answer 2

Ваш метод, кажется, есть проблема:

• функцию rowsToInt преобразует подмассив 5 int до значения между 0 и 31 условии, что эти значения являются двоичным (0 или 1).

• в функции removeDuplicates, можно использовать эти значения в качестве счетчиков сдвига в выражении: (mask << (value-1)) где mask является int со значением 1. Это проницательный способ отслеживать просматриваемые строки, но выражение вызывает неопределенное поведение для value == 0.

Вы должны решить эту проблему, используя unsigned long типа для tracker, гарантированно иметь по крайней мере 32 бита, и (1UL << value) определены и различны для значений 0 к 31.

Сложность действительно O (строки * перевалы), но алгоритм по своей сути ограничивается cols <= 5, поэтому трудно говорить о сложности, когда cols не может расти сколь угодно.

Кроме того, использование pow(2, i) очень неэффективно для вычисления двоичных значений.

Вот упрощенная версия:

#include <iostream> 
#include <cmath> 

int rowsToInt(int m[][5], int row, int cloumLen) { 
    int sum = 0; 
    // m[row][column] 
    for (int i = 0; i < cloumLen; i++) { 
     sum += m[row][i] << i; 
    } 
    return sum; 
} 

void removeDuplicate(int m[][5], int row, int column) { 
    if (!m) { 
     return; 
    } 

    unsigned long tracker = 0; 

    for (int i = 0; i < row; i++) { 
     int value = rowsToInt(m, i, column); // 3 
     if (((1UL << value) & tracker) == 0) { 
      // print unique row 
      std::cout << "row: " << i << " is unique" << std::endl; 
      // set that bit to 1 
      tracker |= 1UL << value;   
     } 
    } 
} 

int main() { 
    int array[7][5] = { 
     {0,1,0,0,1}, 
     {1,0,1,1,0}, 
     {0,1,0,0,1}, 
     {1,1,1,0,0}, 
     {1,1,0,1,1}, 
     {0,0,0,0,0}, 
     {0,0,0,0,0}, 
    }; 
    removeDuplicate(array, 7, 5); 
    return 0; 
}