開発環境

> swift --version
swift-driver version: 1.55.1 Apple Swift version 5.7 (swiftlang-5.7.0.113.202 clang-1400.0.16.2)
Target: x86_64-apple-macosx13.0

モチベーション

ある数に対して、その数がある配列のインデックスとして存在するかを確認するときは以下のようにしていた。

let numbers = [1, 2, 3, 4, 5]

numbers.indices.contains(0)  // true
numbers.indices.contains(5)  // false

気になりポイントとして、containsの計算量は $O(n)$ のため、時間計算量的に優しくない。

個人的な意見だが、endIndexを使ったほうがより良さそう。というのも、endIndexは時間計算量の明記は無いが、 $O(n)$ 以上に悪い時間計算量ではないだろうという予想。いやどうだろう、何も分からんがcontainsと同等かそれ以下だと思うのでcontainsよりマシだろう、という考え。

endIndexを使うときはstartIndexと併用して書く。ちなみに、startIndexはArrayの場合必ず0になる。*1

numbers.indices.contains(4)  // true
numbers.startIndex <= 4 && 4 < numbers.endIndex  // true

countでも同様の結果が得られそうだけど、endIndexと別でプロパティが用意されてるということは0-indexed以外のArrayも作れるのだろうか。分からん。今は必要ではないのでスルーしておく。

あまり考えずにcontainsを使っていて、あたまの片隅でモヤモヤしていたがちょっとスッキリしてよかった。

2022/06/24追記: 見てるところ違った！

ブログに社のメンバーからコメント貰えて問題が解決したので追記！

Array.Indicesの戻り値の型は Range<Int>で、Range<Int> で使用するcontainsはcontains(_:) | Apple Developer Documentation。こちらのcontainsには計算量の記載がなく、実装を見てみると以下と似たような処理*2をやっているので、Range<Int> のcontainsの計算量は $O(n)$ ではなさそう、ということが分かった。

numbers.startIndex <= 4 && 4 < numbers.endIndex  // true

参考

*1:https://developer.apple.com/documentation/swift/array/startindex

*2:startIndex, endIndexかlowerBound, upperBoundの違い

カルボナーラ街道

計測と観察

Swiftで配列のインデックスの存在確認はindices.contains()よりendIndexを使う方がより良い？

開発環境

モチベーション

2022/06/24追記: 見てるところ違った！

参考