行列内の重複する行をチェックする効率的なアルゴリズム

Question

整数の行列Mが与えられます。 2つの行が同じであるかどうかを確認してください。最適なアプローチを与える。

Example: 
[{1, 2, 3}, 
{3, 4, 5}, 
{1, 2, 3}] 

上記の行列では、行1と行3は同じです。

考えられる解決策：

Given a matrix, we can convert each row in a string (example using to_string() 
method of C++ and concatenating each element in a row to a string). We do this 
for every row of the matrix, and insert it in a table that is something like 
(map<string, int> in C++). And hence, duplicate row can be checked in O(mn) time 
for an mxn matrix. 

が、私はこれよりも良い行うことができますか？または、上記の方法に欠陥がありますか？

Answer 1

あなたの方法は機能しますが、その複雑さは間違っています。

まず、試験要素はstd::mapにある場合はnはマップ内の要素の数であり、fは/挿入任意の二つの要素がマップで検索比較するのに要する時間の上限である複雑O(log(n) * f)を有しています。

あなたの場合、すべての文字列の長さはmです。したがって、マップ内の2つの要素を比較するにはO(m)が必要です。

だからあなたの方法の総複雑さは、次のとおりです。マップにn文字列を挿入するための

O(n * log(n) * m)。

ただし、地図ではなくハッシュテーブルを使用して、漸近的に最適である（すべてのデータを読み込む必要があるため）期待通りに最大速度をO(n * m)にすることができます。これは、ハッシュテーブルが挿入操作の平均複雑度がO(1)であり、すべての入力文字列のハッシュ関数が1回だけ計算されるためです。

C++にはunordered_setを使用できます。

Answer 2

行列のサイズによっては、すべてを文字列に変換するのは時間と空間をかなり浪費しているようです。

各行に固有の可能性のあるハッシュを計算しないのはなぜでしょうか。たとえば、すべてのエントリのビットごとの論理和を計算し、そのハッシュを行のインデックスと共にマルチマップに保存することができます。各行を調べるときに、そのハッシュを計算し、そのハッシュがすでに存在するかどうかを確認します。そうであれば、同じ行を他の行と同じハッシュで比較し、等しいかどうかを確認します。

これは、より良いBig-Oの複雑さはありませんが、ほぼ確実に小さな定数と少ないスペースを使用します。