arrays - 知道过滤元素是一个序列，如何用另一个 Swift 数组过滤一个 Swift 数组？速度很重要

Question

我有一个包含 10,000 个结构的 Swift 数组:

struct Book {
    var id: Int?
    var name: String?
    var pages: Int?
    var words: Int?
}

var firstArray: [Book] = [] // contains 10,000 elements

我有第二个 Int 类型的 Swift 数组，有 5,000 个元素:

var secondArray: [Int] = [] // contains 5,000 elements

我想通过删除其中 id 字段 (Book.id) 不包含在 secondArray 中的所有元素来过滤 firstArray。

知道 Book.id 对于 firstArray 中的每个元素都是唯一的，在一个序列(从小到大)中也是如此。例如。 1、2、3、6、8、10、14、15、16、40、50、51等(部分数字可跳过)

secondArray 也是唯一的并且在一个序列中(从小到大)

在 Swift 4 中过滤 firstArray 的最快方法是什么？

知道数组是一个序列，过滤应该在我们处理数组时变得更快，对吗？这意味着如果我们在 firstArray 的中途，我们将只循环遍历 firstArray 的一半以在 secondArray 中搜索匹配项。 secondArray 也是如此，因为每次找到匹配时数组都会变小。这一切都有意义吗？

希望有人知道如何做到这一点。我已经在 Android (Kotlin) 上看到过这种做法，但如何在 Swift 中做到这一点？

我认为在 Kotlin 中是这样的:

firstArray?.let { dataFirstArray ->
        secondArray?.let {
            firstArray = ArrayList(dataFirstArray.asSequence().filter { dataSecondArray -> dataSecondArray in it }.toList())
        }
    }

Answer 1

如果 id 始终存在，请不要将其设为可选。

struct Book {
    var id: Int
    var name: String?
    var pages: Int?
    var words: Int?
}

最简单的过滤方式是一行:

func filter1(firstArray:[Book],secondArray:[Int]) -> [Book]
{
    return firstArray.filter{secondArray.contains($0.id)}
}

我还尝试通过这样做来利用数组排序的事实:

func filter2(firstArray:[Book],secondArray:[Int]) -> [Book]
{
    var j = 0;

    return firstArray.filter{
        while(j < secondArray.count && secondArray[j] < $0.id)
        {
            j += 1
        }
        if(j < secondArray.count && $0.id == secondArray[j])
        {
            j += 1
            return true
        }
        return false
    }
}

根据评论的建议，我也尝试使用Set:

func filter3(firstSet:Set<Book>,secondSet:Set<Int>) -> Set<Book>
{
    return firstSet.filter{secondSet.contains($0.id)}
}

使用以下代码测试:

var firstArray: [Book] = (0..<10000).map{Book(id: $0, name: nil, pages: nil, words: nil)}.filter {_ in Int.random(in: 0...1) == 0}
var secondArray: [Int] = (0..<10000).filter{_ in Int.random(in: 0...1) == 0}

var timestamp = Date().timeIntervalSince1970
let result1 = filter1(firstArray: firstArray, secondArray: secondArray)
print(Date().timeIntervalSince1970 - timestamp)

timestamp = Date().timeIntervalSince1970
let result2 = filter2(firstArray: firstArray, secondArray: secondArray)
print(Date().timeIntervalSince1970 - timestamp)

timestamp = Date().timeIntervalSince1970
let result3 = filter3(firstArray: firstArray, secondSet: Set(secondArray))
print(Date().timeIntervalSince1970 - timestamp)

测试结果:

2.687404155731201
0.0014042854309082031
0.002758026123046875

希望对你有帮助