2次元配列の削除ノードの最適化

Question

私は次元720x90の二次元配列を持っています。 RとCの行を列としましょう。 R1 = {C1、...、C90}

....

R720 = {C1、...、C90}今

、Iは、データのいずれかどうかを確認しますいずれかの行は他の行のどこにでも表示されます。たとえば、行470と列67のデータが行672と列34の複製であるとします。この場合、データセットから行470と行672の両方を削除してチェックを継続します。私はすべての行をチェックした後、残っている行のインデックスだけを出力したい。私はこれのbrute-forceメソッドを書いています。しかし、このコードを実行すると、決して返されず、私はなぜそれを診断することができません。また、これを行うより効率的な方法がありますか？

//check all the subsets of the interleaved data 
public static int checkSubsets(String[][] subsets){ 
    List subset = new ArrayList(); 
    for(int i = 0; i< 720; i++){ 
     for(int j = 0; j < 90; j++) 
      subset.add(subsets[i][j]); 
    } 
    Object duplicate; 
    Iterator itr = subset.iterator(); 
    while(itr.hasNext()){  
     duplicate = itr.next();  
     while(itr.hasNext()){  
      subset.remove(duplicate); 
      itr=subset.iterator(); //to avoid concurrent modification 
      itr.next();  
     } 
    } 
    return subset.size(); 
} 

説明：マトリックスの各値を調べながら繰り返しています。私はR1 C1（行1 - 列1）の最初の値を取る。私はこれらの値が12,346,123,356行のどこかにあることを知ります。それから私は行列からすべての行を削除します。だから行列は5行小さくなります。私は行1を今すぐ停止し、行2に移動します。行12,346,123、および356をスキップし続けます。したがって、一意の行（すべて90の値が一意です）の後です。

Answer 1

アルゴリズムはほぼありますが、有用なデータ構造はありません。

スパイスのビットを追加するには、Java 8を多少使用しました。

あなたが行ったように、重複をチェックするために値を収集することができます。 しかし、その値の最初の行を覚えておく必要があります。そこには、重複が存在するかどうかまだ分かりません。

public static int checkSubsets(String[][] subsets) { 

    // The results. 
    final Set<Integer> duplicateRows = new HashSet<>(); 

    // From the first occurrence of a duplicate value we do not know it yet, 
    // so need to remember. 
    final Map<String, Integer> firstRowOfValue = new HashMap<>(); 

    for (int i = 0; i < subsets.length; ++i) { 
     for (int j = 0; j < subsets[i].length; ++j) { 
      final String value = subsets[i][j]; 
      Integer oldRow = firstRowOfValue.putIfAbsent(value, i); 
      if (oldRow != null) { // Duplicates 
       duplicateRows.add(i); 
       duplicateRows.add(oldRow); 
       // oldRow might already be added if third duplicate or same row. 
      } 
     } 
    } 

    IntStream.rangeOf(0, subsets.length) 
     .filter(i -> !duplicateRows.contains(i)) 
     .forEach(System.out::println); 
    return subsets.length - duplicateRows.size(); 
} 

---

IntStream一部は、Java 7で次のようになります。

for (int i = 0; i < subsets.length; ++i) { 
    if (!duplicateRows.contains(i)) { 
     System.out.println(i); 
    } 
} 

のJava 7を使用すると、安全にputとここputIfAbsentを置き換えることができます。

Answer 2

あなたが書いたコードが要件と関係しているかどうかはわかりませんが、私はあなたに答えのアプローチを与えますが、まず自分で試してみる必要があります。

重複する可能性があるかどうかを確認するために各行を繰り返し実行する必要があることは明らかですが、これはパフォーマンスの低下を招きますが、HashMapを使用してこれを克服することができます。配列のノードの値であり、値はこのノードの座標でなければなりません。

各行の配列を反復処理するときは、行のすべてのノード間で共通のマップからy座標を見つける必要があります。重複する行が検出されます。

すでに削除されている行をチェックしないようにするには、削除するすべての行を保存してから削除してください。重複を避けるためにSetを使用して保存してください。

実用性に恵まれています。