arrays - 排序数组和查找更改 - 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: 我在原来的帖子中弄错了。而不是诠释。它们是 UInt8。

Answer 1

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

if data == storedArray {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
        $0.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
    }
}

更新

基准测试表明，与简单的循环相比，过滤器/映射版本的性能非常糟糕，因此这是一个仅使用 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
}

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