Swift数组中最大值及其索引的有效算法

Question

我写了一个算法是 Swift，用于在 Swift 数组中查找最大值及其索引。这是受到 Matlab & Octave 中的“max.m”函数的启发。

这里的专家能否提出一种在速度方面改进该算法的方法？我的意思是它可以做得更快，或者您认为这是大型阵列（有时是 15000 个样本）的合理方法。

public func max (y: [Double]) -> (Int, Double) {

let inLen = y.count

var out = Double()
var outp = Int()

if (1 == inLen) { // if only one element
    out = y[0]
    outp = 0
} else if (0 == inLen) { // if no elements
    out = -1
    outp = -1
} else {
    out = y[0]
    outp = 0
    for ii in 1...inLen-1 {
        if (out<y[ii]){
            out = y[ii]
            outp = ii
        }
    }
}
return (outp, out)
}

// Call the function

let y: [Double] = [3, 4, 5, 6, 7, 8, 9, 100, 100, 11, 12, 13, 14, 15, -8, -7, -7, 99]
let (ind, value) = max(y: y)
print(ind) // 7
print(value) // 100.0 

Answer 1

对原始代码进行Code Review

以下是我要做的改变。所有这些都有点粗糙（我没有检查所有这些是否编译），但会让你走上正确的轨道。

1. 使代码通用

   public func max (y: [Double]) -> (Int, Double) {
   

   变成：

   public func max<T: Comparable>(y: [T]) -> (Int, T) {
   

2. 删除无用的参数关键字y，并重命名y为有意义的名称

   public func max<T: Comparable>(_ array: [T]) -> (Int, T) {
   

3. 在结果中添加关键字：

   public func max<T: Comparable>(_ array: [T]) -> (index: Int, value: T) {
   

4. Array将其添加为or的扩展RandomAccessCollection，完全取代对参数的需要：

   extension Array where Element: Comparable {
       public func max() -> (index: Int, value: Element) {
           // ...
       }
   }
   

5. 内联不必要的变量inLen，或者至少命名它更好，就像count

6. out将and重命名outp为更好的名称，例如maxValueandmaxIndex

7. 不要在 Swift 中使用 yoda 比较。=不是 Swift 中的表达式，因此不存在意外导致 if 语句中赋值而不是比较的风险。它会触发编译器错误。另外，省略

   if (1 == count) {
   

   应该

   if (count == 1) {
   

8. 省略 if 语句中不需要的括号：

   if count == 1 {
   

9. 以更符合逻辑的顺序重新排列计数检查。不要将其排序为 1, 0, 1+，而是将其排序为 0, 1, 1+。

10. 尽早返回，而不是使用 if/elseif/else 跳过代码块以获得共同的返回。代替：

    extension Array where Element: Comparable {
        public func max() -> (index: Int, value: Element) {
            var maxValue = Double()
            var maxIndex = Int()
    
            if count == 0 { // if no elements
                maxValue = -1
                maxIndex = -1
            } else if count == 1 { // if only one element
                maxValue = self[0]
                maxIndex = 0
            } else {
                maxValue = self[0]
                maxIndex = 0
                for i in 1...inLen-1 {
                    if (maxValue < self[i]){
                        maxValue = self[i]
                        maxIndex = i
                    }
                }
            }
            return (index: maxIndex, value: maxValue)
        }
    }
    

    尝试这个：

    extension Array where Element: Comparable {
        public func max() -> (index: Int, value: Element)? {
            var maxValue = Double()
            var maxIndex = Int()
    
            if count == 0 { return (index: -1, value: -1) } 
            if count == 1 { return (index: 0, value: self[0]) }
    
            maxValue = self[0]
            maxIndex = 0
            for i in 1...count-1 {
                if (maxValue < self[i]) {
                    maxValue = self[i]
                    maxIndex = i
                }
            }
            return (index: maxIndex, value: maxValue)
        }
    }
    

11. maxValue现在您可以删除和的前向声明maxIndex

    extension Array where Element: Comparable {
        public func max() -> (index: Int, value: Element) {
            if count == 0 { return (index: -1, value: -1) } 
            if count == 1 { return (index: 0, value: self[0]) }
    
            var maxValue = self[0]
            var maxIndex = 0
            for i in 1...count-1 {
                if (maxValue < self[i]) {
                    maxValue = self[i]
                    maxIndex = i
                }
            }
            return (index: maxIndex, value: maxValue)
        }
    }
    

12. 避免重写类似的内容1 ... x-1，而是使用..<: for i in 1 ..< count {

13. 在这种情况下，最好使用 self.indices，它可以实现相同的效果：

    for i in self.indicies {
    

14. 如果您需要索引以及与这些索引关联的值，请使用enumerated()：

    for (index, value) in self.enumerated() {
    

15. 切勿在 Swift 中使用像-1和那样的哨兵值""。我们有表达值缺失的选项。使用它们：

    extension Array where Element: Comparable {
        public func max() -> (index: Int, value: Element)? {
            if count == 0 { return nil } 
            if count == 1 { return (index: 0, value: self[0]) }
    
            var maxValue = self[0]
            var maxIndex = 0
            for (index, value) in self.enumerated() {
                if (maxValue < value) {
                    maxValue = value
                    maxIndex = index
                }
            }
            return (index: maxIndex, value: maxValue)
        }
    }
    

16. 我还会使用元组赋值来缩短一些：

    extension Array where Element: Comparable {
        public func max() -> (index: Int, value: Element)? {
            if count == 0 { return nil } 
            if count == 1 { return (index: 0, value: self[0]) }
    
            var (maxIndex, maxValue) = (0, self[0])
            for (index, value) in self.enumerated() {
                if (maxValue < value) {
                    (maxIndex, maxValue) = (index, value)
                }
            }
            return (index: maxIndex, value: maxValue)
        }
    }
    

17. 现在我们使用元组赋值，我们可以看到我们可以将 maxValue 和 maxIndex 组合成一个元组，然后直接返回：

    extension Array where Element: Comparable {
        public func max() -> (index: Int, value: Element)? {
            if count == 0 { return nil } 
            if count == 1 { return (index: 0, value: self[0]) }
    
            var maxElement = (index: 0, value: self[0])
            for (index, value) in self.enumerated() {
                if (maxElement.value < value) { maxElement = (index, value) }
            }
            return maxElement
        }
    }
    

调用新方法的方法如下：

let array: [Double] = [3, 4, 5, 6, 7, 8, 9, 100, 100, 11, 12, 13, 14, 15, -8, -7, -7, 99]

if let (maxIndex, maxValue) = array.max() {
    print("The max element is \(maxValue) at index \(maxIndex)")
}
else {
    print("The array is empty, and has no max element or index.")
}

理想化的 Swift 方法

let array: [Double] = [3, 4, 5, 6, 7, 8, 9, 100, 100, 11, 12, 13, 14, 15, -8, -7, -7, 99]

if let (maxIndex, maxValue) = array.enumerated.max{ $0.element < $1.element } {
    print("The max element is \(maxValue) at index \(maxIndex)")
}
else {
    print("The array is empty, and has no max element or index.")
}

MartinR 的方法经过改进

以下是 MartinR 方法的包装，可以更轻松地与其他 Swift 代码集成：

func max(of array: [Double]) -> (index: Int, value: Double)? {
    var maxValue = Double()
    var maxIndex = vDSP_Length()
    vDSP_maxviD(array, 1, &maxValue, &maxIndex, vDSP_Length(array.count))

    if maxValue == -Double.infinity { return nil }

    return (index: Int(maxIndex), value: maxValue)
}

Answer 2

您可以使用vDSP_maxviD)() Accelerate 框架中的函数。vDSP 函数使用 vDSP_Length (aka UInt) 来表示数组计数和索引，因此您必须将索引转换Int为 Swift 互操作性。

import Accelerate

let array: [Double] = ...

var elem = 0.0
var vdspIndex: vDSP_Length = 0
vDSP_maxviD(array, 1, &elem, &vdspIndex, vDSP_Length(array.count))
let idx = Int(vdspIndex)

print("max:", elem, "at index:", idx)

结果证明，对于 15,000 个元素的数组（在以 Release 模式编译的 iMac 上），这比显式循环快 5 倍。