Swift 3のStringのViewに対して、Intでsubscript出来ない理由

以下の記事の理由が分かったのでその説明を書きます。SwiftのString全般についてはもう少し調べて、後日まとまった記事書きたいと思っています。

Stringには、以下の4つのViewがありますが、Character Viewを例にします。

  • Character View (var characters: String.CharacterView)
  • Unicode Scalar View (var unicodeScalars: String.UnicodeScalarView)
  • UTF-16 View (var utf16: String.UTF16View)
  • UTF-8 View (var utf8: String.UTF8View)

例えば、以下のような5文字の文字列sから先頭3文字を取りたい時に以下の冗長とも見える書き方が必要な理由はなぜだろう?という話でした。

let s = “12345”
let start = s.startIndex
let end = s.index(start, offsetBy: 3)
let sTo3 = s.characters[start..<end]
print(sTo3)
// → 23

普通に考えると、わざわざindexを取得せずに、Intでこう書きたくなってしまいます。

print(s.characters[0..<3])

(subscript使わずに以下のように書くことも出来ますが、「先頭3文字取得」というより「Intでsubscript」したいというのが本題です。)

s.characters.prefix(3)

理由は、高コストな処理であることを意識させ、かつ効率の良い要素アクセスが可能なAPIとなっていること

こちらの記事の後ろの方の「インデックス」の項に理由が書いてありました。(Swift 2.2のコードなので注意してください。)

まず、上に書いた例の場合は、Intアクセスが出来たとしても走る処理は変わりません。

一方、以下のようにCharacter Viewをループ処理する場合を考えてみます。

for c in s.characters {
print(c)
}

仮にIntでのsubscript操作が出来ると以下のように書いてしまうことがありそうです。

for i in s.characters.count {
let c = s.characters[i]
print(c)
}

文字列のViewにはランダムアクセス出来ず、正しく文字の境界を判別するために始端か終端から辿る必要があります。

そのため、実際には次の処理が走ります。O(n²)の処理となってしまいます。カジュアルにIntでのsubscript操作が出来るとそれが隠蔽されてパフォーマンスの悪いコードを意図せず書くことに繋がってしまうので、それを意識させるようなAPIになっているということだと思います。

for i in 0..<s.characters.count {
let index = s.characters.index(s.startIndex, offsetBy: i)
print(s.characters[index])
}

これを意識していると、次のような効率の良いコードへの書き換えなどの発想も出てきやすいです。
(もちろん今回はシンプルな例なので、そもそもこんなことせずに普通に初めの例で書くのが自然です。)

var index = s.characters.startIndex
repeat {
print(s.characters[index])
index = s.characters.index(after: index)
} while index != s.characters.endIndex

別の例として、仮にカジュアルにIntでのsubscript操作が出来ると、例えば最後のCharacter取得したい時、以下のコードを書いてしまうでしょう。

s.characters[s.characters.count - 1]

効率を意識すると、次の書き方が良いです。

s.characters.last!
// 別解(記述が冗長だがパフォーマンス的にはどれも悪く無い)
s.characters.suffix(1).first!
s.characters[s.index(before: s.characters.endIndex)]
s.characters.suffix(from: s.characters.index(before: s.endIndex)).first!

後者は末尾から1つ遡るだけのごく軽い処理ですが、前者は文字列全体スキャンが2つ走ります。

  1. s.charactersのcount
  2. s.charactersを先頭から辿って最後の要素にたどり着く

こういった良くない処理を招くことを防ぎ、かつやりたい処理などによっては末尾からの効率良い走査など可能なAPIとなっている、ということです。

まとめると、具体的には特に以下のことをしないように配慮されたAPIだということです。

  • 端から無駄に何回も再スキャンを繰り返してしまうこと
  • 終端からのスキャンの方が効率が良いのに始端からスキャンしてしまうこと

countがO(n)なのは良いのか?

ついでに、以下のコンパイルの通るcount処理について、カジュアルにアクセス出来るプロパティがO(n)で良いのか?と思うかもしれません。

s.characters.count

これについては、Swift API Design Guidelinesに、O(1)で無いプロパティはそのことをドキュメンテーションコメントに書くように明記されています。

Document the complexity of any computed property that is not O(1)
People often assume that property access involves no significant computation, because they have stored properties as a mental model. Be sure to alert them when that assumption may be violated.

また、countの定義にも、RandomAccessCollectionで無い場合は、O(n)となる、と明記されています。

Complexity: O(1) if the collection conforms to RandomAccessCollection; otherwise, O(n), where nis the length of the collection.

というわけで、これも問題無しですね。ただ、これに関してはうっかりカジュアルにO(n)のcountアクセスをしてしまうことが起こりやすくなっているので、開発者が「気を付ける」しかなさそうです。

extensionメソッドなどで便利にする時は、どのような定義が良いか

というわけで、Indexでsubscript操作するAPIとなっていることはしっくり来たのですが、そうは言ってもIntでカジュアルに文字列アクセスしたい場面もあると思います。また、冒頭に出した「5文字の文字列sから先頭3文字を取りたい時」などは、Intアクセスが出来たとしても走る処理は変わりません。

高コストなアクセスであることを明示したsubscriptか、あるいはメソッド定義があると良いかなと思いました。

subscript版

以下の記事の「文字列に対してRange<Int>によるsubscript操作を可能に」に書きました。

ラベルで高コストであることを明示しましたが、ドキュメンテーションコメントで明示する、という方法もありかもしれません。ただ、SwiftのString APIであえてそれが無くしているので空気を読んで止めた方が良い気がしました。

以下の記事では、まさにそういった安易なsubscriptを追加してしまったので、リポジトリのソースは改めました。

メソッド版

こんな感じですかね( ´・‿・`)

Arrayに変換

extensionなど使わず、かつIndex意識せずにライトに対応したい場合は、Arrayに変換するという方法もあります。あまりキレイとは言えないので、各所に書くようなら、上の2つのような方法にした方が良いかなと思っています。

String(Array(s.characters)[1..<3])
// → 23

NSStringにキャスト

SwiftのStringの不理解で扱いに困った時の手っ取り早い手段として、NSStringにキャストしてしのぐ、という業もあります。ただ、FoundationフレームワークのNSプレフィックス系の型を返すAPIは、SwiftのNSプレフィックス無しの型に自動ブリッジされるようになったので、substringのfrom・to使う場合はキャストが2回必要になって微妙です( ´・‿・`)

((s as NSString).substring(from: 1) as NSString).substring(to: 2)
// → 23

NSRange指定ならまだマシですね。

(s as NSString).substring(with: NSRange(location: 1, length: 2))

ただ、Swiftの世界にNSプレフィックス系の型持ち込むのはなるべく避けたいですね( ´・‿・`)


C++; // 管理人: 岩永さんから、前回の記事について色々コメントいただけたので、貼っておきます。以上の内容につながるアドバイスなど色々有用な情報いただけました。StringからIndex取れることへの違和感などまた新たな疑問も生まれましたが、もう少し勉強しながら考えたいと思います。