排序数组并查找更改 - Swift

Question

好的，所以我有一个不断以快速接收数组的流。这就是我想要做的...

如果数组相同，则什么都不做。如果不同，则创建一个新数组，将 nil 作为除已更改的值之外的每个值。

示例：

传入数组1：[1,1,1,1]

传入数组2：[1,1,2,1]

我要创建：[nil, nil, 2, nil]。仅标记更改。

我做了一些有用的东西，我只是觉得它效率不高。这是最好的方法吗？

var storedArray = [Int](count: 10, repeatedValue: 0) //array for comparing

func incomingArray(data: [Int]) {
    if data == storedArray {return} //do nothing if its the same
    var tempArray = [Int?](count: 10, repeatedValue: nil) //nil array
    for index in 0...9 {
        if storedArray[index] != data[index] {
            tempArray[index] = data[index] //replace the temp array index               
            }
        }
    //send the completed tempArray to do work  ....

    storedArray = incomingArray //save the stored as the current data
    }

所以上面的代码有效。只是效率不高。对此有更好的想法吗？

谢谢

更新 1：我在原文中弄错了post。而不是诠释。它们是 UInt8。

Answer 1

这里有一些让这段代码更快的想法：

1) 不要使用 Int? 的数组，而是使用普通的 Int，而不是将元素标记为 nil，而是将它们标记为一些特殊的整数值。我不知道那个值是多少，也许 0 可以，或者 -1，或者 Int.max.

Update: The above change gives me a ~ 10% performance increase

2) 回收你的结果数组。这样就可以跳过下面的代码了：

var tempArray = [Int?](count: 10, repeatedValue: nil)

或者更好，让调用者通过 inout 参数传入它，这样您就不必担心它的所有权。

Update: The above change gives me a ~ 50% performance increase

这里是这个问题中建议的所有版本的代码：

import UIKit
import XCTest

var storedArray1 = [Int?](count: 10, repeatedValue: 0) //array for comparing
func processIncomingArray1(data: [Int]) {
    var tempArray = [Int?](count: 10, repeatedValue: nil) //nil array
    for index in 0...9 {
        if storedArray1[index] != data[index] {
            tempArray[index] = data[index] //replace the temp array index
        }
    }
    storedArray1 = tempArray
}

var storedArray2 = [Int](count: 10, repeatedValue: 0)
func processIncomingArray2(data: [Int]) {
    var tempArray = [Int](count: 10, repeatedValue: Int.max)
    for index in 0...9 {
        if storedArray2[index] != data[index] {
            tempArray[index] = data[index]
        }
    }
    storedArray2 = tempArray
}

var storedArray3 = [Int](count: 10, repeatedValue: Int.max)
func processIncomingArray3(data: [Int], inout result: [Int]) {
    for index in 0...9 {
        if result[index] != data[index] {
            result[index] = data[index]
        }
    }
}

// Given two sequences, return a sequence of 2-tuples (pairs)
public func zip<A: SequenceType, B: SequenceType>(a: A, b: B)
    -> ZipSequence<A, B>
{
    return ZipSequence(a, b)
}

// Lazy sequence of tuples created from values from two other sequences
public struct ZipSequence<A: SequenceType, B: SequenceType>: SequenceType {
    private var a: A
    private var b: B

    public init (_ a: A, _ b: B) {
        self.a = a
        self.b = b
    }

    public func generate() -> ZipGenerator<A.Generator, B.Generator> {
        return ZipGenerator(a.generate(), b.generate())
    }
}

// Generator that creates tuples of values from two other generators
public struct ZipGenerator<A: GeneratorType, B: GeneratorType>: GeneratorType {
    private var a: A
    private var b: B

    public init(_ a: A, _ b: B) {
        self.a = a
        self.b = b
    }

    mutating public func next() -> (A.Element, B.Element)? {
        switch (a.next(), b.next()) {
        case let (.Some(aValue), .Some(bValue)):
            return (aValue, bValue)
        default:
            return nil
        }
    }
}



func differences<T: Equatable>(lhs: [T], rhs: [T]) -> [Int] {
    // indexedPairs is a sequence of (index, (left-hand val, right-hand val))
    let indexedPairs = enumerate(zip(lhs,rhs))
    // the lazy may or may not help here, benchmark to find out...
    return lazy(indexedPairs).filter { (index, pair) in
        // only return different pairs
        pair.0 != pair.1
        }.map {
            // only return the index not the values
            [=11=].0
        }.array
}

var storedArray4 = [Int](count: 10, repeatedValue: Int.max)
func processIncomingArray4(data: [Int]) {
    let diffs = differences(storedArray4, data)
    if !diffs.isEmpty {
        // send new data and diff indices for further processing
        // then overwrite the old array
        storedArray4 = data
    }
}


func differences5<T: Equatable>(lhs: [T], rhs: [T]) -> [Int] {
    var diffs: [Int] = []
    // still using zip, since this guards against the two
    // arrays being of different sizes - doesn’t seem to
    // impact performance
    for (i,(l,r)) in zip(indices(lhs),zip(lhs,rhs)) {
        if l != r { diffs.append(i) }
    }

    return diffs
}

var storedArray5 = [Int](count: 10, repeatedValue: Int.max)
func processIncomingArray5(data: [Int]) {
    let diffs = differences5(storedArray4, data)
    if !diffs.isEmpty {
        // send new data and diff indices for further processing
        // then overwrite the old array
        storedArray5 = data
    }
}


class WhosebugTests: XCTestCase {

    func testPerformanceExample1() {
        var data = [1,2,3,4,5,6,7,8,9,10]
        self.measureBlock() {
            for i in 1...100000 {
                processIncomingArray1(data)
            }
        }
    }

    func testPerformanceExample2() {
        var data = [1,2,3,4,5,6,7,8,9,10]
        self.measureBlock() {
            for i in 1...100000 {
                processIncomingArray2(data)
            }
        }
    }

    func testPerformanceExample3() {
        var data = [1,2,3,4,5,6,7,8,9,10]
        self.measureBlock() {
            for i in 1...100000 {
                processIncomingArray3(data, &storedArray3)
            }
        }
    }

    func testPerformanceExample4() {
        var data = [1,2,3,4,5,6,7,8,9,10]
        self.measureBlock() {
            for i in 1...100000 {
                processIncomingArray4(data)
            }
        }
    }

    func testPerformanceExample5() {
        var data = [1,2,3,4,5,6,7,8,9,10]
        self.measureBlock() {
            for i in 1...100000 {
                processIncomingArray5(data)
            }
        }
    }

}

Answer 2

如果您关心性能，首先要寻找的是隐藏循环。这是一个：

if data == storedArray {return}

这大概是为了提高效率——如果两个数组相等，就什么都不用做。但实际上，这可能会弄巧成拙。这种比较不是恒定时间——它遍历元素并比较它们。因为你以后无论如何都要遍历它们，所以这可能不会给你太多。

您可能会争辩说它节省了您分配新数组的时间，但这会引出下一个问题，即您真的需要创建一个包含所有这些 nil 值的数组吗？为什么不将不同的索引数组生成到数组中呢？这样，差异的接收者将只需要遍历差异（可能只有几个）而不是整个数组。

将数组与处理和存储区分开来可能是有意义的。这是一个接受两个数组和 returns 不同索引数组的函数：

func differences<T: Equatable>(lhs: [T], rhs: [T]) -> [Int] {
    // indexedPairs is a sequence of (index, (left-hand val, right-hand val))
    let indexedPairs = enumerate(zip(lhs,rhs))
    // the lazy may or may not help here, benchmark to find out...
    return lazy(indexedPairs).filter { (index, pair) in
        // only return different pairs
        pair.0 != pair.1
    }.map {
        // only return the index not the values
        [=11=].0
    }.array
}

注意这是一个纯函数——也就是说，它接受输入并产生结果而不引用任何外部状态。这使得作为独立函数进行测试和调试变得更加容易。

然后您可以根据它重写您的原始函数：

func incomingArray(data: [Int]) {
    let diffs = differences(storedArray, data)
    if !diffs.isEmpty {
        // send new data and diff indices for further processing
        // then overwrite the old array
        storedArray = data
    }
}

更新

基准测试表明，与简单循环相比，filter/map 版本的性能非常糟糕，因此这是一个仅使用 for…in:

的 differences 版本

func differences<T: Equatable>(lhs: [T], rhs: [T]) -> [Int] {
    var diffs: [Int] = []
    // still using zip, since this guards against the two
    // arrays being of different sizes - doesn’t seem to
    // impact performance
    for (i,(l,r)) in zip(indices(lhs),zip(lhs,rhs)) {
        if l != r { diffs.append(i) }
    }

    return diffs
}

一些快速测试表明，如果输入很大且差异的数量很小，此版本会获得显着的加速，但如果数组大部分不同，则执行相同。

Answer 3

我想我有最好的答案。而不是整个空的 nil 数组。我将我的临时数组设为布尔值。然后，如果值发生变化，则将其索引标记为 true。

这是一个例子。

传入数组1：[1,1,1,1]

传入数组2：[1,1,2,1]

然后我导出完整数组加上一个 bool 数组：[false, false, true, false]。

然后我只是检查是否有变化并提取值。事实证明，它的工作速度比其他答案快得多。我还回收了临时数组以加快速度。我的猜测是，由于它的值只能为 true 或 false，所以它比 NIL/UInt8 快很多。

感谢大家的帮助。如果有任何其他想法出现，请告诉我。

排序数组并查找更改 - Swift

Sorting Arrays and Finding Changes - Swift

arrays

sorting

optimization

swift