使用 Swift 的多线程数组中项目的组合

Question

我正在编写一个小算法，我必须不重复地计算数组中项目的所有组合。到目前为止，我已经使用了下面的这段代码，但我现在需要加快这个过程，因为它花费的时间太长了。我试图用 Swift 实现并发（代码将在 Mac 上运行）但不幸的是它不起作用。

我使用的算法取自 http://www.geeksforgeeks.org/print-all-possible-combinations-of-r-elements-in-a-given-array-of-size-n/，然后从 C 转换为 Swift。你能帮我解决这个问题吗？

func printCombination(arr: [Int], r: Int) {
    trips.removeAll()
    var data: [Int] = []
    for _ in 1...r
    {
        data.append(Int())
    }
    combinationUtil(arr: arr, r: r, index: 0, data: data, i: 0)
}

func combinationUtil(arr: [Int], r: Int, index: Int, data: [Int], i: Int) {
    var data: [Int] = data
    if (index == r)
    {
        for j in 0..<r {
           array.append(data[j])

        }
        return
    }

    if (i >= arr.count) {
        return
    }

    data[index] = arr[i]
    combinationUtil(arr: arr, r: r, index: index + 1, data: data, i: i + 1)
    combinationUtil(arr: arr, r: r, index: index, data: data, i: i + 1)
}
    /* arr[]  ---> Input Array
   r      ---> Size of a combination to be printed
   index  ---> Current index in data[]
   data[] ---> Temporary array to store current combination
   i      ---> index of current element in arr[]     */

Answer 1

你在你的例子 "works fine" 中说了上面的代码，但我不明白是怎么回事，因为你引用了一些不在这个代码片段中的变量（trips 和 array ) 而你只是将越来越多的整数附加到 array.

就个人而言，我会放弃这种 C++/Java 代码的直译，而只关注如何在 Swift 中最好地实现这个概念性算法。这个想法是从数组中挑选一个值，将其添加到数据集中，然后再次递归调用例程，并删除所挑选的值。产生类似的东西：

func printCombinations(with combinationThusFar: [Int] = [], from array: [Int], size: Int, startingAt: Int = 0) {
    if size == 0 {
        print(combinationThusFar)
        return
    }

    for i in startingAt ... array.count - size {
        var remaining = array
        remaining.remove(at: i)
        printCombinations(with: combinationThusFar + [array[i]], from: remaining, size: size - 1, startingAt: i)
    }
}

然后：

let array = [1, 2, 3, 4, 5]
printCombinations(from: array, size: 3)

请注意，我还没有引入任何并发性，但是对于这样的算法，我认为没有理由这样做，因为这里没有任何计算密集型的东西。为了通过并发提高性能，您需要在每个线程上进行足够的工作以抵消管理多个线程的开销。如果你没有足够的代码运行ning 在每个分派的代码段上，并行制作这个运行代码实际上会使它变慢。

如果要将并发引入例程，最好的方法之一是使用 concurrentPerform。（有关示例，请参见。）但这在这里会很棘手（它最适合非递归算法）。此外，我认为这里没有必要这样做。

使用 Swift 的多线程数组中项目的组合

Combinations of items in array with multithreading using Swift

concurrency

multithreading

combinations

combinatorics

swift