使用功能方法查找最小值和最大值时出现性能问题

Question

我有一个子视图数组，我想找到最低标签和最高标签（~ min 和 max）。我尝试使用 Swift 的函数式方法并在我的知识允许的范围内尽可能多地对其进行优化，但是当我这样做时：

let startVals = (min:Int.max, max:Int.min)
var minMax:(min: Int, max: Int) = subviews.filter({[=10=] is T2GCell}).reduce(startVals) {
        (min([=10=].min, .tag), max([=10=].max, .tag))
}

我的性能仍然比好的 ol' for 周期更差（大约慢 10 倍）：

var lowest2 = Int.max
var highest2 = Int.min
for view in subviews {
    if let cell = view as? T2GCell {
        lowest2 = lowest2 > cell.tag ? cell.tag : lowest2
        highest2 = highest2 < cell.tag ? cell.tag : highest2
    }
}

为了完全准确，我还包括了测量代码的片段。请注意，人类可读时间的 "after-recalculations" 是在任何测量之外完成的：

let startDate: NSDate = NSDate()

// code

let endDate: NSDate = NSDate()

// outside of measuring block
let dateComponents: NSDateComponents = NSCalendar(calendarIdentifier: NSCalendarIdentifierGregorian)!.components(NSCalendarUnit.CalendarUnitNanosecond, fromDate: startDate, toDate: endDate, options: NSCalendarOptions(0))
let time = Double(Double(dateComponents.nanosecond) / 1000000.0)

我的问题是 - 我做错了吗，或者这个用例根本不适合函数式方法？

编辑

这是 2x 慢:

var extremes = reduce(lazy(subviews).map({[=13=].tag}), startValues) {
    (min([=13=].lowest, ), max([=13=].highest, ))
}

而这仅20%慢：

var extremes2 = reduce(lazy(subviews), startValues) {
    (min([=14=].lowest, .tag), max([=14=].highest, .tag))
}

缩小并压缩到非常好的性能时间，但仍然不如 for 循环快。

编辑 2

我注意到我在之前的编辑中遗漏了 filter。添加时：

var extremes3 = reduce(lazy(subviews).filter({[=15=] is T2GCell}), startValues) {
    (min([=15=].lowest, .tag), max([=15=].highest, .tag))
}

我回到了 2x 较慢的性能。

Answer 1

我能想到的一个问题是循环进行了两次。首先过滤器 returns 一个过滤后的数组，然后在 reduce 中循环。

filter(_:)

Returns an array containing the elements of the array for which a provided closure indicates a match.

Declaration

func filter(includeElement: (T) -> Bool) -> [T]

Discussion

Use this method to return a new array by filtering an existing array. The closure that you supply for includeElement: should return a Boolean value to indicate whether an element should be included (true) or excluded (false) from the final collection:

而在第二种情况下只有一个循环。

我不确定 'is' 作为 'as?' 运算符的执行时间是否有任何差异。

Answer 2

无法重现您的确切示例，但您可以尝试移开过滤器。以下代码在功能上应该等同于您上次尝试的代码。

var extremes4 = reduce(subviews, startValues) {
     is T2GCell ? (min([=10=].lowest, .tag), max([=10=].highest, .tag)) : [=10=]
}

因此您不会在子视图上迭代两次。请注意，我删除了 lazy，因为您似乎总是使用整个列表。

顺便说一句，恕我直言，函数式编程可能是一种非常有用的方法，但在为了 花哨的函数式方法 的唯一目的而牺牲代码清晰度之前，我会三思而后行。因此，如果 for 循环更清晰，甚至更快……就用它吧 ;-) 也就是说，这对您尝试用不同的方法来解决同一问题很有好处。

Answer 3

在优化构建中，reduce 和 for 的性能应该完全相同。然而，在未优化的调试版本中，for 循环可能会击败 reduce 版本，因为 reduce 不会被专门化和内联。可以删除过滤器，消除不必要的额外数组创建，但是创建数组会非常快（它所做的只是将指针复制到内存中）所以这并不是什么大问题，为了清楚起见，删除它更重要。

但是，我认为部分问题在于，在您的 reduce 中，您在 AnyObject 上调用 .tag 属性，而在您的 [=14] 中=]循环版，你调用的是T2GCell.tag。这可能会产生很大的不同。如果你打破过滤器，你可以看到这个：

// filtered will be of type [AnyObject]
let filtered = subviews.filter({[=10=] is T2GCell})

let minMax:(min: Int, max: Int) = filtered.reduce(startVals) {
    // so .tag is calling AnyObject.tag, not T2GCell.tag
    (min([=10=].min, .tag), max([=10=].max, .tag))
}

这意味着 .tag 将在运行时进行动态绑定，操作速度可能会变慢。

下面是一些演示差异的示例代码。如果你编译这将 swiftc -O 你会看到静态绑定（或者更确切地说不是动态绑定）reduce 和 for 循环执行几乎相同：

import Foundation

@objc class MyClass: NSObject {
    var someProperty: Int
    init(_ x: Int) { someProperty = x }
}
let classes: [AnyObject] = (0..<10_000).map { _ in MyClass(Int(arc4random())) }

func timeRun<T>(name: String, f: ()->T) -> String {
    let start = CFAbsoluteTimeGetCurrent()
    let result = f()
    let end = CFAbsoluteTimeGetCurrent()
    let timeStr = toString(Int((end - start) * 1_000_000))
    return "\(name)\t\(timeStr)µs, produced \(result)"
}

let runs = [
    ("Using AnyObj.someProperty", { 
        reduce(classes, 0) { prev,next in max(prev,next.someProperty) } 
    }),
    ("Using MyClass.someProperty", { 
        reduce(classes, 0) { prev,next in 
          (next as? MyClass).map { max(prev,[=11=].someProperty) } ?? prev 
        }
    }),
    ("Using plain ol' for loop", {
        var maxSoFar = 0
        for obj in classes {
            if let mc = obj as? MyClass {
                maxSoFar = max(maxSoFar, mc.someProperty)
            }
        }
        return maxSoFar
    }),
]

println("\n".join(map(runs, timeRun)))

我机器上的输出：

Using AnyObj.someProperty       4115µs, produced 4294310151
Using MyClass.someProperty      1169µs, produced 4294310151
Using plain ol' for loop        1178µs, produced 4294310151

使用功能方法查找最小值和最大值时出现性能问题

Performance issue while finding min and max with functional approach

functional-programming

ios

swift