在Swift中,一个有效的函数,它根据谓词将数组分成2个数组

Question

注意:我目前仍在使用Swift 2.2,但也对Swift 3解决方案开放

我正在寻找创建一个非常接近的函数filter,除了它保持不匹配的结果,并维护排序顺序.例如,假设您想过滤掉数组中可被3整除的数字,并且仍然保留不能被3整除的数字列表.

---

选项1:使用 filter

使用filter,您只能得到可被3整除的数字列表,原始列表保持不变.然后,您可以使用相反的谓词再次过滤原始列表,但这是不必要的第二遍.代码如下所示:

let numbers = [1,2,3,4,5,6,7,8,9,10]
let divisibleBy3 = numbers.filter { $0 % 3 == 0 } // [3,6,9]
let theRest = numbers.filter { $0 % 3 != 0 }      // [1,2,4,5,7,8,10]

确实,这是非常可读的,但是对于我而言,它执行2遍的事实似乎效率低下,特别是如果谓词更复杂的话.这是实际需要的两倍多的检查.

选项2:separate在Collection扩展中使用自定义功能

我的下一次尝试是扩展Collection并制作一个我打电话的功能separate.此函数将获取集合并一次一个地浏览元素,并将它们添加到匹配列表或不匹配列表中.代码如下所示:

extension Collection {
    func separate(predicate: (Generator.Element) -> Bool) -> (matching: [Generator.Element], notMatching: [Generator.Element]) {
        var groups: ([Generator.Element],[Generator.Element]) = ([],[])
        for element in self {
            if predicate(element) {
                groups.0.append(element)
            } else {
                groups.1.append(element)
            }
        }
        return groups
    }
}

然后我可以使用这样的函数:

let numbers = [1,2,3,4,5,6,7,8,9,10]
let groups = numbers.separate { $0 % 3 == 0 }
let matching = groups.matching       // [3,6,9]
let notMatching = groups.notMatching // [1,2,4,5,7,8,10]

这也很干净,但我唯一不喜欢的是我使用元组作为返回类型.也许其他人不同意,但我更喜欢返回与self链接相同的类型.但从技术上讲,你可以抓住其中任何一种,.matching或者.notMatching类型相同self,你可以将它们中的任何一种链接起来.

选项3:removeIf在Array扩展中使用自定义的变异函数

我separate返回一个元组的问题导致我尝试创建一个函数,self通过删除匹配项来修改它们并将它们添加到新列表中,并在结尾处返回匹配列表.返回的列表是您的匹配项,并且数组将被修剪掉这些值.订单在两个数组中都保留.代码如下所示:

extension Array {
    mutating func removeIf(predicate: (Element) -> Bool) -> [Element] {
        var removedCount: Int = 0
        var removed: [Element] = []

        for (index,element) in self.enumerated() {
            if predicate(element) {
                removed.append(self.remove(at: index-removedCount))
                removedCount += 1
            }
        }

        return removed
    }
}

它使用如下:

var numbers = [1,2,3,4,5,6,7,8,9,10]
let divisibleBy3 = numbers.removeIf { $0 % 3 == 0 }
// divisibleBy3: [3,6,9]
// numbers:      [1,2,4,5,7,8,10]

这个函数必须在扩展中实现Array,因为在特定索引处删除元素的概念不适用于常规Collections(一个Array被定义为public struct Array<Element> : RandomAccessCollection, MutableCollection,它直接定义remove(at:)函数,而不是从继承或协议中获取它) ).

选项4:选项2和3的组合

我是代码重用的忠实粉丝,在提出选项3后,我意识到我可能会重用separateOption 2中的功能.我想出了这个:

extension Array {
    mutating func removeIf(predicate: (Element) -> Bool) -> [Element] {
        let groups = self.separate(predicate: predicate)
        self = groups.notMatching
        return groups.matching
    }
}

它就像在选项3中一样使用.

我关注性能,所以我通过XCTest运行每个选项measure1000次迭代.这些是结果:

Option 1: 9 ms
Option 2: 7 ms
Option 3: 10 ms
Option 4: 8 ms

---

选项5:基于negaipro的答案

我知道partition,但我不会考虑它,因为它没有保留排序顺序.negaipro的答案基本上是partition,但它让我思考.我们的想法partition是交换与枢轴点匹配的元素,从而确保端点枢轴点一侧的所有内容都与谓词匹配,而另一侧则不然.我接受了这个想法并将行动改为"走到尽头".所以匹配从他们的位置删除并添加到最后.

extension Array {
    mutating func swapIfModified(predicate: (Element) -> Bool) -> Int {
        var matchCount = 0
        var index = 0
        while index < (count-matchCount) {
            if predicate(self[index]) {
                append(remove(at: index))
                matchCount += 1
            } else {
                index += 1
            }
        }

        return count-matchCount
    }
}

在我使用带有10个数字的数组的初始测试中,它与其他选项相当.但我关心的是线路的性能append(remove(at: index)).所以我再次尝试了所有的选项,阵列从1到1000,这个选项绝对是最慢的.

---

结论:

这些选项之间没有很大的性能差异.由于选项4比选项3快,并且重用了选项2中的代码,我倾向于抛弃选项3.因此,filter当我不关心未经过滤的结果时,我倾向于使用普通的旧版本(同样, ,因为我不关心过滤结果,因为它只是使用相反的谓词),然后使用separate或removeIf当我关心保持过滤和未过滤的结果时.

题:

那么,我是否遗漏了Swift内置的内容呢？有没有更好的方法来实现这一目标？我的扩展语法是否缺少任何东西(例如,任何可以使它将此概念应用于更多区域的东西)？

Answer 1

从技术上讲，这并不能保证保持秩序，但确实如此。

Dictionary(grouping: numbers) { $0.isMultiple(of: 3) }

https://github.com/apple/swift/blob/master/stdlib/public/core/NativeDictionary.swift

Answer 2

let objects: [Int] = Array(1..<11)
let split = objects.reduce(([Int](), [Int]())) { (value, object) -> ([Int], [Int]) in

    var value = value

    if object % 2 == 0 {
        value.1.append(object)
    } else {
        value.0.append(object)
    }

    return value
}

Answer 3

Swift 4 解决方案

分区（按：）

它对原始数组重新排序并返回满足谓词的子数组的起始索引。

在这个例子中，它返回 7。

0..<7 元素不能被 3 整除，7..n-1 元素可以被 3 整除。

 var numbers = [1,2,3,4,5,6,7,8,9,10]
 let partition = numbers.partition(by: { $0 % 3 == 0 })
 let divisibleBy3 = Array(numbers[..<partition]) //[3,6,9]
 let theRest = Array(numbers[partition...]) //[1,2,4,5,7,8,10]

Answer 4

有一个新的开源 Swift 算法序列和集合算法及其相关类型

\n

您可以从那里使用稳定的分区

\n

对可变集合执行稳定分区以及\n在已分区集合中查找分区索引的方法。

\n

标准库\xe2\x80\x99s 现有partition(by:)方法根据给定谓词将集合中的元素重新排序为两个分区，\xe2\x80\x99t\n不保证任一分区的稳定性。也就是说，每个分区中元素的顺序不一定与原始集合中的相对顺序相匹配。这些新方法扩展了现有方法partition(by:)。

\n

// existing partition(by:) - unstable ordering\nvar numbers = [10, 20, 30, 40, 50, 60, 70, 80]\nlet p1 = numbers.partition(by: { $0.isMultiple(of: 20) })\n// p1 == 4\n// numbers == [10, 70, 30, 50, 40, 60, 20, 80]\n\n// new stablePartition(by:) - keeps the relative order of both partitions\nnumbers = [10, 20, 30, 40, 50, 60, 70, 80]\nlet p2 = numbers.stablePartition(by: { $0.isMultiple(of: 20) })\n// p2 == 4\n// numbers == [10, 30, 50, 70, 20, 40, 60, 80]\n

\n

由于分区经常用于分而治之的算法，因此我们还\n包含一个接受范围参数的变体，以避免在改变切片时\n进行复制，以及现有标准库\n分区的基于范围的变体。

\n

这 partitioningIndex(where:)当在已分区的集合上调用时，

\n

let numbers = [10, 30, 50, 70, 20, 40, 60]\nlet p = numbers.partitioningIndex(where: { $0.isMultiple(of: 20) })\n// numbers[..<p] == [10, 30, 50, 70]\n// numbers[p...] = [20, 40, 60]\n

\n