优化 Swift 中的嵌套 for 循环

Question

我得到了这种计算 UIImage 中白色像素的方法，我需要遍历所有像素以增加我找到的每个白色像素的计数器。我试图提高它的性能，但我没有找到更好的方法。有什么想法吗？

func whitePixelCount() -> Int {
    let width = Int(image.size.width)
    let height = Int(image.size.height)
    var counter = 0
    for x in 0..<(width*scale) {
        for y in 0..<(height*scale) {
            // We multiply per 4 because of the 4 channels, RGBA, but later we just use the Alpha
            let pixelIndex = (width * y + x) * 4

            if pointer[pixelIndex + Component.alpha.rawValue] == 255 {
                counter += 1
            }
        }
    }
    return counter
}

Component.alpha.rawValue 等于 3
scale 是 Int(image.scale)

pointer 来自：

guard let cfdata = self.image.cgImage?.dataProvider?.data,
    let pointer = CFDataGetBytePtr(cfdata) else {
        return nil
}

Answer 1

一般来说，big(o) 的性能可以通过将 for 循环替换为 while 循环来提高 while x < array.count && y < array2.count { insert code to do here }

另一种方法是将图像拆分为单独的组件并将它们发送到不同的线程并重新组合生成的数组。您需要使用 gcd * workitems async 来执行此操作。

Answer 2

一些观察：

确保您使用的是 optimized/release 版本，而不是未优化的调试版本。在我的设备上，调试构建需要大约 4 秒来处理 12 兆像素的图像，而发布构建需要 0.3 秒。
当您有一个 for 循环时，您可以将其并行化以利用 CPU 上的所有内核。通过跨步算法，for 循环快了将近 4 倍。

听起来不错，但不幸的是，问题在于处理图像的 0.3 秒，其中大部分是图像缓冲区的准备工作。（现在，在您的示例中，您没有将它重新渲染到预定义的像素缓冲区中，恕我直言，这有点危险，所以也许您没有这种开销。但是，无论如何，通常观察不到 10+ 毫秒的差异除非你正在处理数百张图像。）实际的 for 循环只占用了 16 毫秒的运行时间。因此，虽然将其减少到 4 毫秒几乎快了 4 倍，但从用户的角度来看，这并不重要。

无论如何，请随意在我的原始答案中查看下面跨步的并行算法。

提高 for 循环性能的一种非常简单的方法是使用 concurrentPerform 并行化例程：

例如，这是一个非并行例程：

var total = 0

for x in 0..<maxX {
    for y in 0..<maxY {
        if ... {
            total += 1
        }
    }
}

print(total)

您可以通过

将其并行化

翻转 x 和 y 循环，因为我们希望外循环是图像中的一行。这个想法是为了确保不仅每个线程都应该使用连续的内存块，而且我们希望最小化重叠量以避免“缓存晃动”。因此考虑：
```
for y in 0..<maxY {
    for x in 0..<maxX {
        if ... {
            total += 1
        }
    }
}
```
我们实际上并不打算使用上面的内容，但我们将在下一步中将其用作模型；

用 concurrentPerform:

替换外部 for 循环（现在是 y 坐标）

var total = 0

let syncQueue = DispatchQueue(label: "...")

DispatchQueue.concurrentPerform(iterations: maxY) { y in
    var subTotal = 0
    for x in 0..<maxX {
        if ... {
            subTotal += 1
        }
    }
    syncQueue.sync {
        total += subTotal
    }
}

print(total)

所以，想法是：

将外部 for 循环替换为 concurrentPerform;
与其尝试为 x 的每次迭代更新 total，不如为每个线程设置一个 subTotal 变量，并且只在最后更新 total（最小化来自此共享资源的多个线程）；和
使用一些同步机制（我在这里使用串行队列，但任何同步机制都可以）来更新total以确保线程安全。

我试图让示例尽可能简单，但甚至还有其他优化可以做：

不同的同步技术提供不同的性能。例如。您可以通过在协议扩展中定义 sync 方法（给出一个使用锁的好，安全的方式）像这样：

// Adapted from Apple’s `withCriticalSection` code sample

extension NSLocking {
    func sync<T>(_ closure: () throws -> T) rethrows -> T {
        lock()
        defer { unlock() }
        return try closure()
    }
}

然后你可以这样做：

let lock = NSLock()

DispatchQueue.concurrentPerform(iterations: maxY) { y in
    var subTotal = 0
    for x in 0..<maxX {
        if ... {
            subTotal += 1
        }
    }
    lock.sync {
        total += subTotal
    }
}

print(total)

随意尝试您想要的任何同步机制。但想法是，如果您要从多个线程访问 total，请确保以线程安全的方式进行。如果您想检查线程安全，请暂时打开“Thread Sanitizer”。

如果每个线程没有足够的工作（例如 maxX 不是很大，或者在这种情况下，算法是如此之快），并行例程的开销可以开始抵消让多个内核参与计算的好处。因此，您可以在每次迭代中“跨越”y 的多行。例如：

let lock = NSLock()

let stride = maxY / 20
let iterations = Int((Double(height) / Double(stride)).rounded(.up))

DispatchQueue.concurrentPerform(iterations: iterations) { i in
    var subTotal = 0
    let range = i * stride ..< min(maxY, (i + 1) * stride)
    for y in range {
        for x in 0 ..< maxX {
            if ... {
                subTotal += 1
            }
        }
    }

    lock.sync { count += subTotal }
}

优化 Swift 中的嵌套 for 循环

Optimizing nested for loops in Swift

for-loop

uiimage

ios

swift