より効率的なマルチスレッドコードを作成することは可能ですか？（double forループO（n ^ 2））

debugcn 投稿 Dev

イングォンジェームズキム

類似の文字列を見つけるために最小編集距離アルゴリズムを使用します。

私のコードの主題は、入力データの中で最も趣味が近いカップルを見つけることです。

Hobby type
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

// * All of the person have 10 hobby. 
// * Hobby can not be duplicated.

// Input Data format
// 1000.txt
1000                   // number of data
N D R P Y X V B M T    // each line is person's hobbies
P J Z E X W H S M N
F U G L C T Q S O P
A D Q S F E N P Y G
K P D F G Q U I V H
D E I S N L C K H G
D I R K J V Q H M Z
Y A R D F T N P W O
R A G Z F M J K I Y
P E K W H S F Z G R
U J O T I B R Y E H
M A Z N S J H X T P
...
...

// This is Couple Model
struct Couple {
  let firstIdx: Int
  let firstArray: String

  let secondIdx: Int
  let secondArray: String

  let value: Int
}


// This function finds the couple with the closest hobbies among the input data.
func findCouple() {
    guard
      // Utility.makeData's return value is purified Input data. ex) N D R P Y X V B M T -> BDMNPRTVYX
      let data = Utility.makeData(using: "1000") 
      let count = Int(data[0]) else { return }

    var couples = [Couple]()
    var min = data[1].count

    // make GCD Group for handle each queue.
    let group = DispatchGroup()  

    for i in 1..<count {
      // Pivot for hobby compare
      let hobby = data[i]

      // make custom queue for multi-threading
      let queue = DispatchQueue(label: "idx.\(i).queue", attributes: .concurrent)

      queue.async(group: group) {
        for j in (i + 1)..<data.count {
          // This is the subject of comparison.
          let hobby2 = data[j]

          // Calculate for find similarly string
          let newMin = hobby.minimumEditDistance(other: hobby2)

          queue.async(group: group, qos: .userInitiated, flags: .barrier) {
            // If find more similarly string bundle
            if min >= newMin {
              min = newMin
              // Store the couple
              couples.append(
                Couple(firstIdx: i, firstArray: hobby, secondIdx: j, secondArray: hobby2, value: min)
              )
            }
          }
        }
      }
    }

    group.notify(queue: DispatchQueue.global()) {
      let similarCouples = couples.filter({$0.value == min}
      // I want to print like
      // 1-3 : index of persons
      // ASDFZXCVNM : 1 persons's hobby
      // ASDFXCVBJK : 2 persons's hobby
    }
}

入力データのサイズが十分に大きい場合（10000以上）、関数のパフォーマンスが最悪になります。（非常に遅い）

改善点がありましたらお知らせください。

ロブ

あなたは間違いなくあなたの最初の試みで大いに改善することができます。率直に言って、意外に思われるかもしれませんが、現在のレンディションが非並列バージョンよりも効率が悪い可能性があるという深刻なリスクがあります。両方をベンチマークして比較します。

問題に関しては、それらは多様です：

async通話数が多いほど良いとは限りません。制限のないasync通話は、あらゆる種類の非効率性をもたらします。まず、ワーカースレッドの数は非常に限られています（現在は64）。第二に、とにかく、デバイスで利用可能なコアの数を超えることには有用性がありません。

これらのasync呼び出しではなく、私たちはしばしばに手を伸ばしconcurrentPerformます。多くの場合、これはforループを並列化するための最も効率的な方法です。これは、ハードウェアで許可されている使用可能な同時スレッドの数を超えることはありません。

したがって、並列化されていないレンディションについて考えてみましょう。
```
for i in 0 ..< 9_999 {
    for j in i+1 ..< 10_000 {
        ...
    }
}
```
単純に次のように並列化します。
```
DispatchQueue.concurrentPerform(iterations: 9_999) { i in
    for j in i+1 ..< 10_000 {
        ...
    }
}
```
また、concurrentPerform呼び出し元のスレッドをブロックするため、すべてをバックグラウンドキューにディスパッチする可能性があります。
```
DispatchQueue.global().async {
    DispatchQueue.concurrentPerform(iterations: 9_999) { i in
        for j in i+1 ..< 10_000 {
            ...
        }
    }

    DispatchQueue.main.async {
        // now update UI with the results of the above
    }
}
```
のasync内部では呼び出しを使用していないことに注意してください。これconcurrentPerformは、外部forループのすべての並列化を実行するためです。とにかく、このパターンでは、私は効果的に10,000の非同期呼び出しを行っています（そのうちの50mではありません）。そしてconcurrentPerform、それをしている間、スレッドが爆発しないようにします。
ただし、率直に言って、10,000回の反復でさえ多すぎます。スレッドごとに十分な作業がなく、スレッドごとのオーバーヘッドが合計されます。実際、ルーチンを並列化することの利点は、このオーバーヘッドのすべてによって逆に相殺されます。

典型的な解決策は、計算を「ストライド」することです。たとえば、10,000回の反復では、iそれぞれ50個の値に対して200回の反復を実行するなど、歩き回ることができます。例えば：
```
let stride = 50
DispatchQueue.concurrentPerform(iterations: 200) { iteration in
    let startIndex = iteration * stride
    let endIndex = min(9_999, startIndex + stride)
    for i in startIndex ..< endIndex {
        for j in i+1 ..< strings.count {
            ...
        }
    }
}
```
したがって、以前は50mのasync呼び出しから10kの反復にconcurrentPerform減少していましたが、現在は200の反復になっています。これは、並列化されたパフォーマンスを大幅に向上させるには十分すぎるほどですが、オーバーヘッドはごくわずかです。
コードはスレッドセーフではありません。複数のスレッドから更新minしcouplesています。はい、バリアを使用していますが、各ループには独自のキューがあり、バリアはその現在のキューに対してのみであり、キュー間ではありません。データの競合があります。これらの変数へのアクセスを同期する必要があります。

同期にはオーバーヘッドが伴うため、さらに一歩進んで、必要な同期を最小限に抑える方法を理解することをお勧めします。たとえば、ディスパッチされた各ブロックは、最小距離の独自のローカル値を計算し、ブロックの最後で、マスター最小距離に対してローカル最小距離をチェックする必要があります。