arrays - 在另一个数组中查找一个数组的值范围

Question

我在 SWIFT 中有一个数组

let a = [0.0, 0.00250, 0.0050, 0.00749, 0.01, 0.01251, 0.01499, 0.0175, 0.02, 0.022, 0.025] // is always a sequence (increasing)

我还有第二个数组

let b = [0.0, 0.004, 0.008, 0.012, 0.016, 0.02, 0.024, 0.028, 0.032, 0.036, 0.04, 0.044, 0.048, 0.052, 0.056] // is always a sequence (increasing)

我必须找到“b”的所有 >= a[0] & <= a[a.count-1] 的元素，并用这些值填充向量“c”。

这样

let c = [0.0, 0.004, 0.008, 0.012, 0.016, 0.02, 0.024] // ANSWER

执行此操作的最有效方法是什么？

Answer 1

因为你知道两个序列都是递增的，你只需要使用数组的第一个和最后一个元素a .使用这些，您可以使用 index(where:) 在 b 中查找相应索引的方法数组，满足谓词 >= (first of a)和 <= (last of a) .例如

if let aFirst = a.first, let aLast = a.last,
   let startIndex = b.index(where: { $0 >= aFirst }),
   case let endIndex = b.index(where: { $0 > aLast }) ?? a.endIndex {
    let c = b[startIndex..<endIndex] // note: this is an ArraySlice<Double>
                                     // wrap in Array(..) to construct a new array
    print(c) 
       // [0.0, 0.0040000000000000001, 0.0080000000000000002, 0.012, 0.016, 0.02, 0.024]
}

或者，正如@MartinR 所提议的，我们可以猜测，平均而言，我们将更快地实现第二个 index(where:) 的谓词。如果我们从 b 的末尾开始调用当检查满足 $0 <= aLast 的第一个元素时条件:

if let aFirst = a.first, let aLast = a.last,
   let startIndex = b.index(where: { $0 >= aFirst }),
   case let endIndex = b.reversed().index(where: { $0 <= aLast })!.base {
                    /* ^^^^^- as proposed by @MartinR */
    let c = b[startIndex..<endIndex]
    print(c) 
       // [0.0, 0.0040000000000000001, 0.0080000000000000002, 0.012, 0.016, 0.02, 0.024]
}

最后，这种方法(以及当前可用的其他答案中的 filter 方法)在 O(n) 中运行。 .一种更高效的方法是使用二进制搜索，它在 O(log n) 中运行。渐近地。正如@MartinR 所提到的，一个好的起点可能是来自 Rosetta 代码的二进制搜索 Swift 实现:

• http://rosettacode.org/wiki/Binary_search#Swift

如本问答中所述:

• How do I insert an element at the correct position into a sorted array in Swift?

---

回复评论:

... I also have another issue that I forgot to mention. I have another array y that has exactly the same number of elements as b. We can regard these as X and Y values of a signal. I have to choose the matching elements from y for the elements I choose in b.

最简单的解决方案是简单地应用计算出的 startIndex和 endIndex切出 y 的一部分数组(就像你切掉 ​​b 的一部分来构造 c 一样)。

let d = y[startIndex..<endIndex] 
// assumes y.count == b.count, and that these are not slices
// with non-matching indices

但是，我相信更好的方法是使用 zip .只需压缩 y和 b并使用结果构建一个元组数组，之后您可以将上面的谓词应用于 b压缩序列的成员:

let y = Array(1...b.count)

if let aFirst = a.first, let aLast = a.last,
   let startIndex = bAndY.index(where: { $0.0 >= aFirst }),
   case let endIndex = bAndY.index(where: { $0.0 > aLast }) ?? a.endIndex {
    let cAndD = bAndY[startIndex..<endIndex]
    print(cAndD)
        /* [(0.0040000000000000001, 2),
            (0.0080000000000000002, 3), 
            (0.012,                 4), 
            (0.016,                 5),
            (0.02,                  6), 
            (0.024,                 7)] */
}

自然地构建 cAndD array 会产生少量开销，但除非您正在编写一些真正的 HPC 应用程序，否则您不必担心这一点。