# Algo式: 833 (Swift)

## [Task 833](https://algo-method.com/tasks/833)

- [ままこ立て](https://ja.wikipedia.org/wiki/ままこ立て)の問題
  - 初めて聞いた
- [`remove(at:)`](https://developer.apple.com/documentation/swift/array/1641390-remove)を使った実装
  - 自力で実装する際は素直に`Array`を使った
  - `remove(at:)`の計算量がO(*n*)
  - 全体の計算量はO(*n*^2)
- 今回の制約だと計算量がO(*n*^2)でも、問題なし
  - [解説][editorial]でも似た感じの実装でO(*n*^2)
- 配列の最後に追加する実装
  - 解説での実装からヒントを得た
  - 配列の中での位置さえ管理できれば配列から数字を取り除く必要がない
  - O(*n*)で計算できているはず
  - 競プロっぽい実装になった
  - メモリは使う
- [`ArraySlice`](https://developer.apple.com/documentation/swift/arrayslice)
  - `ArraySlice`について調べてみた
  - `Array`では[`startIndex`は常にゼロ](https://developer.apple.com/documentation/swift/array/1541237-startindex)
  - `ArraySlice`では[`startIndex`がゼロとは限らない](https://developer.apple.com/documentation/swift/arrayslice/1539049-startindex)
  - `ArraySlice`の[`popFirst()`ならO(1)](https://developer.apple.com/documentation/swift/arrayslice/1687956-popfirst)
    - ほかの要素は移動せず、`startIndex`が1増えるだけ
    - メモリ上で移動していないのなら、メモリは使い続けそう
  - `ArraySlice`でも`remove(at:)`や`removeFirst()`、`reverse()`などはO(*n*)
  - [`append(_:)`は大体O(1)](https://developer.apple.com/documentation/swift/arrayslice/3126964-append)
    - ほかのインスタンスとメモリ上で共有していなければO(1)
    - 共有していたら、それぞれメモリを利用する必要が出てコピーにO(*n*)
    - メモリ上で隣接できなくなるともっと広いところにO(*n*)で移動する必要がでる
    - `Array`よりも`ArraySlice`の方が移動する必要が多そう
  - 先頭に要素をO(1)で追加する必要がなければ、キューとして使えそう
- `count`の計算量
  - `isEmpty`はO(1)、`count`はO(*n*)だと思い込んでいた
  - `ArraySlice`で実装の際、`startindex`と`endIndex`の差でO(1)で計算できた
  - `Array`や`ArraySlice`での`count`のドキュメントでは[計算量の記載がない](https://developer.apple.com/documentation/swift/arrayslice/2944655-count)
  - [Yong Cui氏](https://betterprogramming.pub/check-swift-array-is-empty-f15e63bf1026)の記事を見つける
  - `Array`や`ArraySlice`は[RandomAccessCollection](https://developer.apple.com/documentation/swift/randomaccesscollection)プロトコルに準拠
  - RandomAccessCollectionプロトコルに準拠していれば`count`の計算量はO(1)
  - `Set`はRandomAccessCollectionプロトコルに準拠していないただの[Collectionで本来はO(*n*)](https://developer.apple.com/documentation/swift/collection#2848969)だけど、[`Set`での`count`の計算量はO(1)](https://developer.apple.com/documentation/swift/set/3018378-count)
  - `String`での`count`は上記記事によるとO(*n*)
    - ただ、記事中の表を見ると`String`のパフォーマンス、変わっていないような？
    - `String`も配列と言えば配列だけど…
    - とはいえ、`String`は複雑で全体的に自信がない

[editorial]: https://algo-method.com/tasks/833/editorial

### 提出

- [自力](https://algo-method.com/submissions/352908)
- [配列の最後に追加](https://algo-method.com/submissions/352926)
- [`ArraySlice`](https://algo-method.com/submissions/352963)
- [`count`](https://algo-method.com/submissions/352987)