バイナリ2D配列のユニークな行を見つける

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

：ここ

は簡単なバージョンです必要なことなくループ内で実行できます。 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;  
} 

ここでは最適化を行います。バイナリマトリックスで作業している場合、なぜ整数を使用していますか？それはRAMの4倍以上かかるので、bool array[rows][cols]を使用してください。行数と列数は定数なので、関数に渡す必要はありません。グローバルconst int rows = 7, cols = 5を宣言することができます。もう一つ重要な要素です。大きな行列で一意のバイナリ行を検索する場合は、見つかったものを数える価値があります。既に2^colを見つけた場合は、そのままループを抜けてください。

検索方法が複雑です。あなたの問題を解決する2つの簡単な方法を示してみましょう。

もっとコンパクトな方法：

// 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 
    } 
} 

そして、最も簡単なの1：

// 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は、これらの値（0または1）厳密にバイナリであると仮定0と31間の値に5 intの部分配列を変換します。機能removeDuplicatesで

• 、あなたは、式のシフトカウンタとしてこれらの値を使用：mask値1とintある(mask << (value-1))。今まで見た行を追跡するのは巧妙な方法ですが、式はvalue == 0の未定義の動作を呼び出します。

あなたはtrackerためunsigned longタイプを使用してこの問題を修正する必要があり、少なくとも32ビットを持つことが保証され、(1UL << value)は定義された値31から0ごとに異なります。

複雑さは、実際にO（行* colsの）ですが、このアルゴリズムは、本質的にcols <= 5に限定されているので、colsが任意に成長できない複雑さについて話をすることは困難です。

さらに、pow(2, i)を使用すると、バイナリ値を計算するのに非常に効率的ではありません。あなたのコード内の最も遅い部分は200000行と配列のために、それはかなりの時間を要し100万回と呼ばれることがありますので、それを使用していない、std::pow()ある

#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; 
}