1

当在 iOS 上运行的 Swift 中的数组上运行 for 循环时，我想利用整个 CPU，因为我觉得这在理论上应该可以加快计算速度。然而我的结果是相反的，在一个DispatchQueue而不是多个DispatchQueues 上运行所有东西，实际上执行得更快。我将提供一个示例，并想知道为什么单线程方法更快，如果可能的话，我仍然可以通过正确利用多个 cpu 内核来降低计算所需的时间？

对于那些只想查看我的意图代码的人可以跳过，因为下一节仅详细说明我的意图和方法。

我在示例中提供的意图：

我正在确定地图上的一条线（汽车行驶的轨迹，每秒的纬度和经度）是否在某个预定义的区域内，地图上的多边形（整个区域的纬度和经度）。为此，我有一个函数可以计算单个点是否在多边形内。我正在使用 for 循环来遍历汽车行驶轨迹中的每个位置，并使用该函数检查该点是否在多边形内。如果每个跟踪的位置都在多边形内，则整个跟踪的汽车行程都发生在所述区域内。

我将 iPhone X 用于开发目的，并利用整个 CPU 来加速计算。

我的做法：

在提供的示例中，我有 3 个变体，导致计算所需的以下时间（以秒为单位）：

Time elapsed for single thread variant: 6.490409970283508 s.
Time elapsed for multi thread v1 variant: 24.076722025871277 s.
Time elapsed for multi thread v2 variant: 23.922222018241882 s.

第一种方法是最简单的，即不使用多个DispatchQueue.

第二种方法利用DispatchQueue.concurrentPerform(iterations: Int). 我觉得这可能是满足我需求的最佳解决方案，因为它已经实施并且似乎是为我的确切目的而设计的。

DispatchQueue第三种方法是我自己的，它根据操作系统报告的活动 CPU 内核的数量将阵列的大致相等的部分安排到在 s 上运行的 for 循环。

我也尝试过使用inout参数（通过引用调用）的变体，但无济于事。时间保持不变，因此我没有提供更多代码来混淆问题。

我也知道，一旦我发现一个不在多边形内的点，我就可以返回该函数，但这不是这个问题的一部分。

我的代码：

    /**
    Function that calculates wether or not a 
    single coordinate is within a polygon described
    as a pointlist. 
    This function is used by all others to do the work.
    */
    private static func contains(coordinate: CLLocationCoordinate2D, with pointList: [CLLocationCoordinate2D]) -> Bool {
        var isContained = false
        var j = pointList.count - 1
        let lat = coordinate.latitude
        let lon = coordinate.longitude
        for i in 0 ..< pointList.count {

            if (pointList[i].latitude > lat) != (pointList[j].latitude > lat) &&
                (lon < (pointList[j].longitude - pointList[i].longitude) * (lat - pointList[i].latitude) / (pointList[j].latitude - pointList[i].latitude) + pointList[i].longitude) {
                isContained.toggle()
            }
            j = i
        }
        return isContained
    }

///Runs all three variants as are described in the question
    static func testAllVariants(coordinates: [CLLocationCoordinate2D], areInside pointList: [CLLocationCoordinate2D]) {
        var startTime = CFAbsoluteTimeGetCurrent()
        var bool = contains_singleThread(coordinates: coordinates, with: pointList)
        var timeElapsed = CFAbsoluteTimeGetCurrent() - startTime
        print("Time elapsed for single thread variant: \(timeElapsed) s.")

        startTime = CFAbsoluteTimeGetCurrent()
        bool = contains_multiThread_v1(coordinates: coordinates, with: pointList)
        timeElapsed = CFAbsoluteTimeGetCurrent() - startTime
        print("Time elapsed for multi thread v1 variant: \(timeElapsed) s.")

        startTime = CFAbsoluteTimeGetCurrent()
        bool = contains_multiThread_v2(coordinates: coordinates, with: pointList)
        timeElapsed = CFAbsoluteTimeGetCurrent() - startTime
        print("Time elapsed for multi thread v2 variant: \(timeElapsed) s.")
    }

    private static func contains_singleThread(coordinates: [CLLocationCoordinate2D], with pointList: [CLLocationCoordinate2D]) -> Bool {
        var bContainsAllPoints = true
        for coordinate in coordinates {
            if !contains(coordinate: coordinate, with: pointList) {
                bContainsAllPoints = false
            }
        }
        return bContainsAllPoints
    }

    private static func contains_multiThread_v1(coordinates: [CLLocationCoordinate2D], with pointList: [CLLocationCoordinate2D]) -> Bool {
        let numOfCoordinates = coordinates.count
        var booleanArray = Array(repeating: true, count: numOfCoordinates)
        DispatchQueue.concurrentPerform(iterations: numOfCoordinates) { (index) in
            if !contains(coordinate: coordinates[index], with: pointList) {
                booleanArray[index] = false
            }
        }
        return !booleanArray.contains(false)
    }

    private static func contains_multiThread_v2(coordinates: [CLLocationCoordinate2D], with pointList: [CLLocationCoordinate2D]) -> Bool {
        let numOfCoordinates = coordinates.count
        let coreCount = ProcessInfo().activeProcessorCount

        func chunk<T>(array: [T], into size: Int) -> [[T]] {
            return stride(from: 0, to: array.count, by: size).map {
                Array(array[$0 ..< Swift.min($0 + size, array.count)])
            }
        }

        let segments = chunk(array: coordinates, into: numOfCoordinates/coreCount)

        let dg = DispatchGroup()
        for i in 0..<segments.count {
            dg.enter()
        }

        var booleanArray = Array(repeating: true, count: segments.count)

        for (index, segment) in segments.enumerated() {
            DispatchQueue.global(qos: .userInitiated).async {
                for coordinate in segment {
                    if !contains(coordinate: coordinate, with: pointList) {
                        booleanArray[index] = false
                    }
                }
                dg.leave()
            }
        }

        dg.wait()
        return !booleanArray.contains(false)
    }

示例数据

我已经为那些希望有数据运行测试的人上传了两个 json 文件。这是导致我记录时间的相同输入。

追踪到的乘车：链接到 json 文件 区域/区域：链接到 json 文件

4

1 回答 1

1

我解决了这个问题，感谢社区。这个答案包含了评论部分带来的各种结果。

有两种方法，一种是使用指针，这是比较通用的方法。另一个更具体到我的问题，并利用 GPU 来查看多个点是否在预定义的多边形内。无论哪种方式，这里都有两种方式，因为代码比文字更能说明问题；）。

使用指针（注意：基本的“contains/containsWithPointer”函数可以在问题中找到）：

private static func contains_multiThread(coordinates: [CLLocationCoordinate2D], with pointList: [CLLocationCoordinate2D]) -> Bool {
        let numOfCoordinates = coordinates.count
        var booleanArray = Array(repeating: true, count: numOfCoordinates)
        let coordinatePointer: UnsafeBufferPointer<CLLocationCoordinate2D> = {
            return coordinates.withUnsafeBufferPointer { pointer -> UnsafeBufferPointer<CLLocationCoordinate2D> in
                return pointer
            }
        }()
        let pointListPointer: UnsafeBufferPointer<CLLocationCoordinate2D> = {
            return pointList.withUnsafeBufferPointer { pointer -> UnsafeBufferPointer<CLLocationCoordinate2D> in
                return pointer
            }
        }()
        let booleanPointer: UnsafeMutableBufferPointer<Bool> = {
            return booleanArray.withUnsafeMutableBufferPointer { pointer -> UnsafeMutableBufferPointer<Bool> in
                return pointer
            }
        }()

        DispatchQueue.concurrentPerform(iterations: numOfCoordinates) { (index) in
            if !containsWithPointer(coordinate: coordinatePointer[index], with: pointListPointer) {
                booleanPointer[index] = false
            }
        }

    return !booleanArray.contains(false)
}

使用 GPU：

private static func contains_gpu(coordinates: [CLLocationCoordinate2D], with pointList: [CLLocationCoordinate2D]) -> Bool {
        let regionPoints = pointList.compactMap {CGPoint(x: $0.latitude, y: $0.longitude)}
        let trackPoints = coordinates.compactMap {CGPoint(x: $0.latitude, y: $0.longitude)}

        let path = CGMutablePath()
        path.addLines(between: regionPoints)
        path.closeSubpath()

        var flag = true
        for point in trackPoints {
            if !path.contains(point) {
                flag = false
            }
        }

        return flag
    }

哪个函数更快取决于系统、点数和多边形的复杂性。我的结果是多线程变体大约快 30%，但是当多边形相当简单或点数达到数百万时，差距缩小，最终 gpu 变体变得更快。谁知道，对于这个特定的问题，将两者结合起来可能会得到更好的结果。

于 2019-03-07T12:32:31.493 回答