DispatchQueue 线程并不总是设置正确的结果
DispatchQueue threads don't always set the correct results
我正在尝试编写扫雷游戏，以下代码用于设置地雷周围的数字。为了测试，我选择了最低级别的 9 x 9 和 10 个地雷。
为了更快的性能，我在设置数字时尝试使用更多的线程，但是有一天我发现它并不总是给出正确的数字排列，我循环创建了1000次，发现20 ~ 1000 人中有 40 人是错误的。
这里有几个错误的结果，“*”代表地雷，“0”代表周围没有地雷
我的错误：索引 1 应该是“*”
10212*100
112*21211
0011101*1
000000111
000011100
01123*200
01*2**200
023432100
01**10000
错误的数字：索引 0 应该是“1”
0*212*100
112*21211
0011101*1
000000111
000011100
01123*200
01*2**200
023432100
01**10000
错误的数字：索引 73 应该是“1”
1*212*100
112*21211
0011101*1
000000111
000011100
01123*200
01*2**200
023432100
00**10000
在不使用 DispatchQueue 或将 DispatchSemaphore 的值设置为 1 的情况下，它给出了 1000%1000 中的正确数字排列。
1*212*100
112*21211
0011101*1
000000111
000011100
01123*200
01*2**200
023432100
01**10000
示例代码如下：
// 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()
}
}
tl;博士
您正在使用此 non-zero 信号量进行并行计算，将并发度限制在合理范围内。我会推荐 concurrentPerform.
但这里的问题不是你如何限制并行度，而是你使用相同的属性（由所有这些并发任务共享）进行计算，这意味着一个迭代一个当这些属性被另一个线程上的另一个并行迭代 used/mutated 时，线程可以改变这些属性。
所以，我会完全避免使用任何共享属性（除了最终的板阵列）。仅使用局部变量。并确保同步这个最终数组的更新，这样你就不会有两个线程同时改变它。
因此，例如，如果您想并行创建板，我可能会使用 concurrentPerform，如 :
中所述
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)
}
}
}
请注意，我没有引用任何 ivar。都是局部变量，在闭包中传回结果。
并且为了避免多个线程可能试图更新同一个面板数组的竞争条件，我将我的访问与 NSLock 同步。 （你可以使用你想要的任何同步机制，但锁定一个非常高效的解决方案，在这个特定场景中可能比 GCD 串行队列或 reader-writer 模式更好。）synchronize 方法如下：
extension NSLocking {
func synchronize<T>(block: () throws -> T) rethrows -> T {
lock()
defer { unlock() }
return try block()
}
}
这是一个很好的通用解决方案（处理可能 return 值的闭包、抛出错误等），但如果这太复杂而无法遵循，这里有一个足以满足我们目的的简约再现这里：
extension NSLocking {
func synchronize(block: () -> Void) {
lock()
block()
unlock()
}
}
现在，我承认，我可能会为董事会采用不同的模型。我会为棋盘的各个方块定义一个 Square 枚举，然后定义一个 Board ，它是所有这些方块的数组（对于行）的数组（对于列）。无论如何，这在我的实现中 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
}
}
无论如何，我会像这样生成 1000 个 9×9 板，每个板有 10 个地雷：
exercise.populateBoards(count: 1000, rows: 9, columns: 9, mineCount: 10) { boards in
for board in boards {
print(board)
print("")
}
}
但您可以随意使用您想要的任何模型。但我建议将 Board 的模型封装在它自己的类型中。它不仅从多线程算法中抽象出生成板的细节以创建大量板，而且自然地避免了各种线程无意地共享属性。
综上所述，这不是并行代码的一个很好的例子，因为创建一个板的计算强度不足以证明 运行 它并行的（公认的非常小的）开销是合理的.这不是一个可能从并行例程中获益很多的问题。也许您会看到一些适度的性能改进，但远没有您从计算密集型的东西中体验到的那么多。
我正在尝试编写扫雷游戏，以下代码用于设置地雷周围的数字。为了测试，我选择了最低级别的 9 x 9 和 10 个地雷。
为了更快的性能，我在设置数字时尝试使用更多的线程，但是有一天我发现它并不总是给出正确的数字排列，我循环创建了1000次，发现20 ~ 1000 人中有 40 人是错误的。
这里有几个错误的结果，“*”代表地雷，“0”代表周围没有地雷
我的错误：索引 1 应该是“*”
10212*100
112*21211
0011101*1
000000111
000011100
01123*200
01*2**200
023432100
01**10000
错误的数字：索引 0 应该是“1”
0*212*100
112*21211
0011101*1
000000111
000011100
01123*200
01*2**200
023432100
01**10000
错误的数字：索引 73 应该是“1”
1*212*100
112*21211
0011101*1
000000111
000011100
01123*200
01*2**200
023432100
00**10000
在不使用 DispatchQueue 或将 DispatchSemaphore 的值设置为 1 的情况下，它给出了 1000%1000 中的正确数字排列。
1*212*100
112*21211
0011101*1
000000111
000011100
01123*200
01*2**200
023432100
01**10000
示例代码如下：
// 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()
}
}
tl;博士
您正在使用此 non-zero 信号量进行并行计算，将并发度限制在合理范围内。我会推荐 concurrentPerform.
但这里的问题不是你如何限制并行度，而是你使用相同的属性（由所有这些并发任务共享）进行计算，这意味着一个迭代一个当这些属性被另一个线程上的另一个并行迭代 used/mutated 时，线程可以改变这些属性。
所以，我会完全避免使用任何共享属性（除了最终的板阵列）。仅使用局部变量。并确保同步这个最终数组的更新，这样你就不会有两个线程同时改变它。
因此，例如，如果您想并行创建板，我可能会使用 concurrentPerform，如
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)
}
}
}
请注意，我没有引用任何 ivar。都是局部变量，在闭包中传回结果。
并且为了避免多个线程可能试图更新同一个面板数组的竞争条件，我将我的访问与 NSLock 同步。 （你可以使用你想要的任何同步机制，但锁定一个非常高效的解决方案，在这个特定场景中可能比 GCD 串行队列或 reader-writer 模式更好。）synchronize 方法如下：
extension NSLocking {
func synchronize<T>(block: () throws -> T) rethrows -> T {
lock()
defer { unlock() }
return try block()
}
}
这是一个很好的通用解决方案（处理可能 return 值的闭包、抛出错误等），但如果这太复杂而无法遵循，这里有一个足以满足我们目的的简约再现这里：
extension NSLocking {
func synchronize(block: () -> Void) {
lock()
block()
unlock()
}
}
现在，我承认，我可能会为董事会采用不同的模型。我会为棋盘的各个方块定义一个 Square 枚举，然后定义一个 Board ，它是所有这些方块的数组（对于行）的数组（对于列）。无论如何，这在我的实现中 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
}
}
无论如何，我会像这样生成 1000 个 9×9 板，每个板有 10 个地雷：
exercise.populateBoards(count: 1000, rows: 9, columns: 9, mineCount: 10) { boards in
for board in boards {
print(board)
print("")
}
}
但您可以随意使用您想要的任何模型。但我建议将 Board 的模型封装在它自己的类型中。它不仅从多线程算法中抽象出生成板的细节以创建大量板，而且自然地避免了各种线程无意地共享属性。
综上所述，这不是并行代码的一个很好的例子，因为创建一个板的计算强度不足以证明 运行 它并行的（公认的非常小的）开销是合理的.这不是一个可能从并行例程中获益很多的问题。也许您会看到一些适度的性能改进，但远没有您从计算密集型的东西中体验到的那么多。