例を使用して、2次元配列での反復、または計算の複雑さを検索します。

良い一日、親愛なるhabrasociety。



私が2年目または3年目に研究所で学んだとき（つまり、一般的にはそれほど前ではありませんでした）、とりわけ「アルゴリズムとデータ構造」と呼ばれる科目がありました。 しかし、彼らはそこでアルゴリズムと構造自体だけでなく、「計算の複雑さ」などの概念についても語った。 認めますが、それはあまり興味がありませんでした。



「確かに空間的および時間的複雑さのアルゴリズムの研究に煩わされるのは、非常に高性能/高負荷のシステムを開発するとき、または非常に大量のデータを扱うときだけです」



しかし、最近、一見単純なタスクのために、心を大きく変える必要がありました。



タスクは次のとおりです。いくつかの（ほとんどが数値の）データを持つExcelテーブルがありました。 これらのデータは、詳細に入ることなく、サブシステムで使用される識別子でした。 テーブルで繰り返し値を見つけて、さまざまな要因に応じて、それらの処理方法を決定する必要がありました。 この時点で、「自動的に実行しないのはなぜですか」という質問がすでにあるかもしれません。 実際、自動化システムで対処できず、人間の介入が必要なデータセットは、テーブルに分類されました。

当然、大量のデータ（平均でドキュメントあたり約5〜10列、1000行）を手動で並べ替えることは恩恵のない作業なので、少なくとも繰り返しを見つけるという点では、プロセスを少し簡略化することにしました。

厳密な組織規則のためにCで別のユーティリティを書くことは不可能だったので、VBAについて少し読んで（まったく知りませんでした）、VBAマクロの形式で解決策を考え出す必要がありました。



そのため、アルゴリズムに直接渡します。

実際、Excelシートで繰り返しを見つけるタスクは、2次元配列で繰り返しを見つけるタスクです。 しかし、それを行う方法は？ 奇妙なことに、Googleはこのような一見些細な作業を解決するのを完全に手伝うことができず、頭の中で少し考えなければなりませんでした。

シンプルなソリューション

頭に浮かぶ最も単純で、最も直接的で基本的な解決策は、ポイントごとの比較です。 VBAでは、次のようになります。

Sub FindMatches() Dim sCol, sRow, cCol, cRow As Integer For sCol = 1 To 10 For sRow = 1 To 10 For cCol = sCol + 1 To 10 For cRow = 1 To 10 If Cells(sRow, sCol) = Cells(cRow, cCol) Then If Cells(sRow, sCol).Font.Color = RGB(0, 0, 0) Then Cells(sRow, sCol).Font.Color = RGB(0, 150, 0) End If Cells(cRow, cCol).Font.Color = RGB(150, 0, 0) End If Next cRow Next cCol Next sRow Next sCol End Sub
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

したがって、テーブルの各セルを取得し、それ以降のすべてのセルと比較します（要素のエントリが最初に発生する列では繰り返しができないため、次の列から比較を開始することに注意してください）、偶然の一致が見つかった場合は、それらを赤で塗りつぶします。 便利ですか？ かなり。 ただし、ここで計算の複雑さが明らかになります。 これは、一見あまり良くないマシンで処理するのにかかる時間です。

• 100セル（10x10）-70ミリ秒
• 200セル（10x20）-240ミリ秒
• 400セル（10x40）-920ミリ秒
• 2000セル（20x100）-23535ミリ秒

一般に、入力での要素数がn倍になると、操作時間はn ²倍になります。 もちろん、そのような決定は私には受け入れられませんでした。

少しシンプルなソリューション

それでは、アルゴリズムを少し高速化してみましょう。 私が最初に気づいたのは、シートのセルに直接アクセスする操作には膨大な時間がかかることであり、これらの操作の数を最小限に抑えるようにしてください。 この問題の解決策として、セルからメモリへのデータの初期記録を選択し、このメモリをすでに使用しています。 このためには、2次元配列が理想的です。



一般に操作の数を減らすために、各一意の値を個別の配列に書き込み、この一意の要素の配列とのみ比較することにしました。 次のようになります。

 Sub FindMatches() Dim row As Integer //  Dim col As Integer //  Dim Values(5000, 5) As Integer //   Dim DistinctValues() As Integer //  Dim DistinctCount As Integer //   Dim i As Integer // Dim IsUnique As Boolean //  //        ReDim DistinctValues(0 To 0) DistinctCount = 0 //   Values   . For col = 1 To 5 For row = 1 To 5000 Values(row, col) = Cells(row, col) Next row Next col // . For col = 1 To 5 For row = 1 To 5000 //    Values  .            DistinktValues. IsUnique = True For i = 0 To DistinctCount - 1 If DistinctValues(i) = Values(row, col) Then //  ,       . IsUnique = False Cells(row, col).Font.Color = RGB(255, 75, 75) Exit For End If Next i //  ,      ,       DistinctValues,      If IsUnique = True Then DistinctCount = DistinctCount + 1 ReDim Preserve DistinctValues(0 To DistinctCount) DistinctValues(DistinctCount - 1) = Values(row, col) Cells(row, col).Font.Color = RGB(75, 175, 75) End If Next row Next col End Sub
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

そのため、既に検出された一意の要素とのみ比較することで、要素比較操作の数を大幅に削減しました。 また、シート内のセルに対する操作の数を2つに減らしました（1つ目はセルの値を配列に保存すること、2つ目はセルをペイントすることです）。 作業時間はどれほど短縮されますか？



残念ながら、このアルゴリズムの速度は入力データのエントロピーに大きく依存しています。 一意の要素の配列と比較しているため、この配列が大きいほど、時間がかかります。 言い換えると、入力に一意の要素が多いほど、アルゴリズムの動作が遅くなります。 25,000個のセル（5列と5,000行）に対して2つのテストを実施しました。 最初のテストでは、すべてのセルに同じ値（1）が入力され、2番目のテストでは、反対に、繰り返しなしで異なる値が入力されました。

最初の場合、アルゴリズムは816ミリ秒かかり、2番目の場合、ほぼ19秒かかりました 。 しかも、これは、息をのむような58 分間で25,000個の細胞を消化できる最初の完全な検索よりも大幅に高速です。



しかし、最高のものを追求することには限界がありません。 少し考えてから、車輪を再発明するのではなく、実績のあるアルゴリズムを使用することにしました。 私が選んだのは、ご存じのとおり、複雑度O（n log n）のクイックソートアルゴリズムです。

クイックフィックス

では、クイックソートを使用して問題を解決するにはどうすればよいですか？

 // ,  . Type MyCell row As Long col As Long Value As Long End Type //  ,            . Sub QSort(sortArray() As MyCell, ByVal leftIndex As Long, _ ByVal rightIndex As Long) Dim compValue As MyCell Dim i As Long Dim J As Long Dim tempNum As MyCell i = leftIndex J = rightIndex compValue = sortArray(CLng((i + J) / 2)) //  . Do Do While (sortArray(i).Value < compValue.Value And i < rightIndex Or _ (sortArray(i).Value = compValue.Value And sortArray(i).col < compValue.col) Or _ (sortArray(i).Value = compValue.Value And sortArray(i).col = compValue.col And sortArray(i).row < compValue.row)) i = i + 1 Loop Do While (compValue.Value < sortArray(J).Value And J > leftIndex Or _ (sortArray(J).Value = compValue.Value And sortArray(J).col > compValue.col) Or _ (sortArray(J).Value = compValue.Value And sortArray(J).col = compValue.col And sortArray(J).row > compValue.row)) J = J - 1 Loop If i <= J Then tempNum = sortArray(i) sortArray(i) = sortArray(J) sortArray(J) = tempNum i = i + 1 J = J - 1 End If Loop While i <= J If leftIndex < J Then QSort sortArray(), leftIndex, J If i < rightIndex Then QSort sortArray(), i, rightIndex End Sub Sub FindMatches() //   Dim myRange As Range Set myRange = Selection //      Dim ColCount, RowCount As Integer ColCount = myRange.Columns.Count RowCount = myRange.rows.Count Dim FirstCol, FirstRow As Integer FirstCol = myRange.Column FirstRow = myRange.row //   ,       . Dim MyCells() As MyCell ReDim MyCells(ColCount * RowCount) Dim col, row As Integer Dim i As Long For col = FirstCol To FirstCol + ColCount - 1 For row = FirstRow To FirstRow + RowCount - 1 MyCells(CLng((col - FirstCol) * RowCount + row - FirstRow)).row = row MyCells(CLng((col - FirstCol) * RowCount + row - FirstRow)).col = col MyCells(CLng((col - FirstCol) * RowCount + row - FirstRow)).Value = CLng(Val(Cells(row, col))) Next row Next col //      Call QSort(MyCells, 0, ColCount * RowCount - 1) // . Cells(1, 1).Font.Color = RGB(0, 255, 0) For i = 1 To ColCount * RowCount - 1 If MyCells(i).Value <> MyCells(i - 1).Value Then Cells(MyCells(i).row, MyCells(i).col).Font.Color = RGB(0, 255, 0) Else Cells(MyCells(i).row, MyCells(i).col).Font.Color = RGB(255, 0, 0) End If Next i Cells(MyCells(firstOccurance).row, MyCells(firstOccurance).col).Font.Color = RGB(0, 255, 0) End Sub
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

並べ替えに加えて、シート上の選択した領域の処理も追加しました。これはより便利だからです。



このアルゴリズムの動作原理は非常に簡単です。 セルのアドレス（行と列の番号）とその値を格納するデータ構造を作成します。 次に、これらの構造から配列が作成され、そこにシートのすべてのデータが入力されます。 配列はクイックソートでソートされます。

その後、ソートされた配列を一度通過して要素に色を付けるだけで十分です。同じ値を持つグループの最初の要素は緑で、残りはすべて赤です。



クイックソートアルゴリズム自体は不安定である、つまり、同じキーを持つ要素の順序が保持されないことに注意してください。 この場合、キーはセルの値であったため、従来のバージョンでは、同じ値を持つ要素の各グループで、要素はランダムな順序で配置されていました。 明らかに、これは私には向いていません。なぜなら、テーブルの最初のエントリを検索するには、各グループをセル番号で再度ソートする必要があるからです。 これを避けるために、復venの要素を再配置するための2つの条件を追加して、クイックソートキーを拡張しました。値が一致した場合、要素はシートに表示される順序で整列します。



生産性の向上はどのくらいでしたか？ このアルゴリズムは、4.2秒でランダムな値を持つ100,000個のセルを持つシートを処理します。これは、私の意見では、かなり受け入れられる結果です。



それでは、これらすべてからどのような結論を引き出すことができますか？

1. 第一に、アルゴリズムの計算の複雑さの問題は、一見単純なタスクにも関連しており、それに遭遇するために、まったく信じられないほどの量のデータを扱う必要はありません。
2. 第二に、車輪を再発明しようとしないでください。 多くの場合、最良の選択肢は、実績のある古典的なアルゴリズムを特定のタスクに適応させることです。

  PS <source>タグはVBAの強調表示をサポートしていないため、少なくともコメントを強調表示するために、Cの強調表示とCスタイルのコメントを使用する必要がありました。