Можно ли сделать более эффективным многопоточный код? (двойной для l oop O (n ^ 2)) - PullRequest
Новая
       39

Можно ли сделать более эффективным многопоточный код? (двойной для l oop O (n ^ 2))

0 голосов
/ 22 января 2020

Я использую алгоритм минимального расстояния редактирования для поиска похожей строки.

Моя тема кода - поиск пары с ближайшими увлечениями среди входных данных. 

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 или более), производительность моей функции хуже (очень медленно)

Пожалуйста, дайте мне знать, если есть какие-либо улучшения.

1 Ответ

2 голосов
/ 22 января 2020

Вы можете значительно улучшить свою первоначальную попытку. Честно говоря, как это ни удивительно, существует серьезный риск того, что ваше текущее исполнение может быть даже менее эффективным, чем непараллельная версия. Оцените и сравните, и сравните.

Что касается проблем, они разнообразны:

  1. Наличие большего количества вызовов async не всегда лучше. Необузданные async вызовы будут вводить все виды неэффективности. Во-первых, количество рабочих потоков довольно ограничено (в настоящее время 64). Во-вторых, в любом случае нет никакой полезности в превышении количества доступных ядер на вашем устройстве.

    Вместо этих вызовов async мы часто достигаем concurrentPerform. Часто это самый эффективный способ распараллеливания for l oop. Это никогда не превысит число доступных параллельных потоков, разрешенных вашим оборудованием.

    Итак, рассмотрим непараллельное представление: 

    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 l oop для нас. В любом случае, по этой схеме я фактически делаю 10 000 асин c вызовов (не 50 м из них). И concurrentPerform гарантирует, что у меня не будет потока, пока я это делаю.

  2. Честно говоря, даже 10 000 итераций - это слишком много. Недостаточно работы для каждого потока, и накладные расходы для каждого потока будут складываться. Фактически, выгоды от распараллеливания подпрограммы будут отрицательно компенсированы всеми этими издержками.

    Типичное решение - «пройти» через вычисления. Например, при 10000 итераций можно пройти 200 итераций для 50 значений i каждая или что-то в этом роде. Например: 

    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 {
            ...
        }
    }
}

    Итак, ранее мы сократили количество вызовов с 50 м async до 10 000 итераций concurrentPerform, и теперь у нас осталось всего 200 итераций. Этого более чем достаточно для достижения значительного параллельного увеличения производительности, но с незначительными накладными расходами.

  3. Ваш код не является поточно-ориентированным. Вы обновляете min и couples из нескольких потоков. Да, вы используете барьер, но каждый l oop имеет свою собственную очередь, и барьер предназначен только для этой текущей очереди, а не для всех очередей. У вас есть гонка данных. Вы должны синхронизировать свой доступ к этим переменным.

    Поскольку с синхронизацией связаны накладные расходы, я мог бы предложить вам go сделать шаг вперед и выяснить, как минимизировать необходимую синхронизацию. Например, каждый отправленный блок может рассчитать свое собственное локальное значение минимального расстояния, а затем в конце блока только тогда следует проверить локальное минимальное расстояние по отношению к мастер-минимальному расстоянию.

Вот несколько советов, которые помогут вам максимально повысить производительность параллельных вычислений. На моем MacBookPro вышеприведенные результаты дали расчет, который был в 9,9 раза быстрее, чем непараллельное воспроизведение.

...