Algo式: 833 (Swift)

Task 833

• ままこ立ての問題
  • 初めて聞いた
• remove(at:)を使った実装
  • 自力で実装する際は素直にArrayを使った
  • remove(at:)の計算量がO(n)
  • 全体の計算量はO(n^2)
• 今回の制約だと計算量がO(n^2)でも、問題なし
  • 解説でも似た感じの実装でO(n^2)
• 配列の最後に追加する実装
  • 解説での実装からヒントを得た
  • 配列の中での位置さえ管理できれば配列から数字を取り除く必要がない
  • O(n)で計算できているはず
  • 競プロっぽい実装になった
  • メモリは使う
• ArraySlice
  • ArraySliceについて調べてみた
  • ArrayではstartIndexは常にゼロ
  • ArraySliceではstartIndexがゼロとは限らない
  • ArraySliceのpopFirst()ならO(1)
    • ほかの要素は移動せず、startIndexが1増えるだけ
    • メモリ上で移動していないのなら、メモリは使い続けそう
  • ArraySliceでもremove(at:)やremoveFirst()、reverse()などはO(n)
  • append(_:)は大体O(1)
    • ほかのインスタンスとメモリ上で共有していなければ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のドキュメントでは計算量の記載がない
  • Yong Cui氏の記事を見つける
  • ArrayやArraySliceはRandomAccessCollectionプロトコルに準拠
  • RandomAccessCollectionプロトコルに準拠していればcountの計算量はO(1)
  • SetはRandomAccessCollectionプロトコルに準拠していないただのCollectionで本来はO(n)だけど、Setでのcountの計算量はO(1)
  • Stringでのcountは上記記事によるとO(n)
    • ただ、記事中の表を見るとStringのパフォーマンス、変わっていないような？
    • Stringも配列と言えば配列だけど…
    • とはいえ、Stringは複雑で全体的に自信がない

提出

• 自力
• 配列の最後に追加
• ArraySlice
• count