swift 数组 'contains' 功能就地优化

Question

我想知道 contains 函数的内置数组结构是否有任何优化。如果每次我运行它时它都对 contains 进行线性搜索，它最多是 O(n)，它变成 O(n^2) 因为我将循环遍历另一组点检查一下，但是如果它在第一次运行“包含”时以某种方式在幕后对数组进行排序，那么每个后续的“包含”都将是 O(log(n))。

我有一个数组，随着用户进入应用程序的深度越来越大，它会逐渐变大，而且我经常使用“包含”，所以我预计用户使用的时间越长，它就会减慢应用程序的速度申请。

如果阵列没有任何幕后优化，那么我应该构建自己的吗？ (例如，快速排序，每次添加到数组时都执行 insert(newElement:, at:)？)

具体来说，我正在使用

[CGPoint], 

CGPointArrayVariable.contains(newCGPoint) // run 100s - 10000s of times ideally every frame, (but realistically probably every second)

当我添加新的 CGPoints 时，我正在使用

CGPointArrayVariable += newCGPointSet.

所以，问题是:我可以继续使用内置的 .contains 函数吗(它足够快吗？)或者我应该构建自己的结构来优化 contains，并保持数组排序？ (也许插入排序比快速排序更适合使用，如果这是推荐的方向的话)

Answer 1

每一帧都做这样的事情会非常低效。

我建议重新考虑您的设计，以避免跟踪每一帧的信息量。

如果绝对有必要，构建您自己的使用 Dictionary 而不是 Array 的类型应该会更有效。

此外，如果它适用于您的用例，使用 Set 可能是最佳选择。