I thread DispatchQueue non impostano sempre i risultati corretti

Question

Sto provando a codificare il gioco MineSweeper, il codice seguente serve per impostare i numeri attorno alle mine. Per un test, scelgo il livello minimo 9 x 9 con 10 mine terrestri.

Per prestazioni più veloci, ho provato a utilizzare più thread durante l'impostazione dei numeri, ma un giorno ho scoperto che non sempre fornisce gli arrangiamenti dei numeri corretti, ho fatto un ciclo per crearlo 1000 volte e ho scoperto che 20 ~ 40 su 1000 sono sbagliati.

Qui ci sono diversi risultati errati, "*" rappresenta la mina, "0" significa nessuna mina in giro

il mio sbagliato: l'indice 1 dovrebbe essere "*"

10212*100
112*21211
0011101*1
000000111
000011100
01123*200
01*2**200
023432100
01**10000

num sbagliato: l'indice 0 dovrebbe essere "1"

0*212*100
112*21211
0011101*1
000000111
000011100
01123*200
01*2**200
023432100
01**10000

num sbagliato: l'indice 73 dovrebbe essere "1"

1*212*100
112*21211
0011101*1
000000111
000011100
01123*200
01*2**200
023432100
00**10000

Senza utilizzare DispatchQueue o impostare il valore di DispatchSemaphore su 1, fornisce la disposizione dei numeri corretta in 1000% 1000.

1*212*100
112*21211
0011101*1
000000111
000011100
01123*200
01*2**200
023432100
01**10000

Ecco il codice di esempio:

// actually indexes created randomly every time
let minesIndexArr = [59, 74, 1, 12, 50, 56, 75, 58, 5, 25]
var defaultCellArr = [String]()
var totalCellArr = [String]()
var count = 0

for _ 1...81 {
    defaultCellArr.append("0")
}

runLoop()

func runLoop() {
    if count == 1000 {
        return
    }
    totalCellArr = defaultCellArr
    setNums()
}

func setNums() {
    let group = DispatchGroup()
    let queue = DispatchQueue(label: "com.setnums", attributes: .concurrent)
    let semaphore = DispatchSemaphore(value: 10)
    for i in 0..<self.totalCellArr.count {
        semaphore.wait()
        group.enter()
        queue.async(group: group, execute: {
            if self.minesIndexArr.firstIndex(of: i) != nil{
                self.totalCellArr[i] = "*"
            }else{
                var num = 0
                let neighbourIndexes = self.getNeighbourIndex(i)
                for v in neighbourIndexes.values {
                    if self.minesIndexArr.firstIndex(of: v) != nil {
                        num += 1
                    }
                }
                self.totalCellArr[i] = String(num)
            }
                            
            group.leave()
            semaphore.signal()
        })
        
    }
    group.notify(queue: DispatchQueue.main) {
        printMap()
        count += 1
        self.runLoop()
    }
}

Answer 1

tl; dr

Stai usando questo semaforo diverso da zero per eseguire calcoli paralleli, vincolando il grado di concorrenza a qualcosa di ragionevole. Mi sento di raccomandare concurrentPerform.

Ma il problema qui non è come stai vincolando il grado di parallelismo, ma piuttosto stai usando le stesse proprietà (condivise da tutte queste attività simultanee) per i tuoi calcoli, il che significa che un'iterazione su un thread può mutarle proprietà mentre vengono utilizzate / modificate da un'altra iterazione parallela su un altro thread.

Quindi, eviterei di utilizzare qualsiasi proprietà condivisa (a parte la serie finale di schede). Usa solo variabili locali. E assicurati di sincronizzare l'aggiornamento di questo array finale in modo da non avere due thread che lo mutano allo stesso tempo.

---

Quindi, ad esempio, se volessi creare le schede in parallelo, probabilmente concurrentPerformle userei come descritto nella mia risposta precedente :

func populateBoards(count: Int, rows: Int, columns: Int, mineCount: Int, completion: @escaping ([Board]) -> Void) {
    var boards: [Board] = []
    let lock = NSLock()

    DispatchQueue.global().async {
        DispatchQueue.concurrentPerform(iterations: count) { index in
            let board = Board(rows: rows, columns: columns, mineCount: mineCount)
            lock.synchronize {
                boards.append(board)
            }
        }
    }

    DispatchQueue.main.async {
        lock.synchronize {
            completion(boards)
        }
    }
}

Nota, non sto facendo riferimento ad alcun ivar. Sono tutte variabili locali, che restituiscono il risultato in una chiusura.

E per evitare condizioni di competizione in cui più thread potrebbero provare ad aggiornare lo stesso array di schede, sto sincronizzando il mio accesso con un file NSLock. (Puoi utilizzare qualsiasi meccanismo di sincronizzazione desideri, ma blocca una soluzione molto performante, probabilmente migliore di una coda seriale di GCD o di un pattern lettore-scrittore in questo particolare scenario.) Questo synchronizemetodo è il seguente:

extension NSLocking {
    func synchronize<T>(block: () throws -> T) rethrows -> T {
        lock()
        defer { unlock() }
        return try block()
    }
}

Questa è una bella soluzione generalizzata (gestire chiusure che potrebbero restituire valori, generare errori, ecc.), Ma se è troppo complicato da seguire, ecco una resa minimalista che è sufficiente per i nostri scopi qui:

extension NSLocking {
    func synchronize(block: () -> Void) {
        lock()
        block()
        unlock()
    }
}

Ora, lo confesso, probabilmente utilizzerei un modello diverso per il consiglio. Definirei un Squareenum per i singoli quadrati della scacchiera, quindi definirei Boardun array (per righe) di array (per colonne) per tutti questi quadrati. Ad ogni modo, questo nella mia implementazione di Board:

enum Square {
    case count(Int)
    case mine
}

struct Board {
    let rows: Int
    let columns: Int
    var squares: [[Square]]

    init(rows: Int, columns: Int, mineCount: Int) {
        self.rows = rows
        self.columns = columns

        // populate board with all zeros

        self.squares = (0..<rows).map { _ in
            Array(repeating: Square.count(0), count: columns)
        }

        // now add mines

        addMinesAndUpdateNearbyCounts(mineCount)
    }

    mutating func addMinesAndUpdateNearbyCounts(_ mineCount: Int) {
        let mines = (0..<rows * columns)
            .map { index in
                index.quotientAndRemainder(dividingBy: columns)
            }
            .shuffled()
            .prefix(mineCount)

        for (mineRow, mineColumn) in mines {
            squares[mineRow][mineColumn] = .mine
            for row in mineRow-1 ... mineRow+1 where row >= 0 && row < rows {
                for column in mineColumn-1 ... mineColumn+1 where column >= 0 && column < columns  {
                    if case .count(let n) = squares[row][column] {
                        squares[row][column] = .count(n + 1)
                    }
                }
            }
        }
    }
}

extension Board: CustomStringConvertible {
    var description: String {
        var result = ""

        for row in 0..<rows {
            for column in 0..<columns {
                switch squares[row][column] {
                    case .count(let n): result += String(n)
                    case .mine: result += "*"
                }
            }
            result += "\n"
        }

        return result
    }
}

Ad ogni modo, genererei 1000 schede 9 × 9 con dieci mine ciascuna in questo modo:

exercise.populateBoards(count: 1000, rows: 9, columns: 9, mineCount: 10) { boards in
    for board in boards {
        print(board)
        print("")
    }
}

Ma sentiti libero di usare qualunque modello tu voglia. Ma suggerirei di incapsulare il modello per il Board nel suo tipo. Non solo astrae i dettagli della generazione di una scheda dall'algoritmo multithread per creare molte schede, ma evita naturalmente qualsiasi condivisione involontaria di proprietà da parte dei vari thread.

---

Detto questo, questo non è un ottimo esempio di codice parallelizzato perché la creazione di una scheda non è abbastanza intensiva dal punto di vista computazionale da giustificare l'overhead (certamente molto minore) di eseguirla in parallelo. Questo non è un problema che probabilmente trarrà vantaggio dalle routine parallelizzate. Forse vedresti un modesto miglioramento delle prestazioni, ma non tanto quanto potresti sperimentare da qualcosa di un po 'più intensivo di calcolo.