概要

Int($0)を用いている ← 取り締まり対象

let input: [Int] = readLine()!.split(separator: " ").map { Int($0)! }

Int(String($0))を用いている ← 警察が推奨

let input: [Int] = readLine()!.split(separator: " ").map { Int(String($0))! }

あとがき

@koher さんがすでに自警団として活動なさっていたようです。
~~2時間くらい試行錯誤している時に見つけたかった~~

また、Swift 5.5以降ではInt($0)を用いても処理速度に違いが生じなくなるため、AtCoder側がSwift 5.5以降に対応すればどちらを使用しても問題なくなるそうです。

競プロerはSwiftでSubstringを直接Intに変換してはいけない

はじめに

AtCoderなどの~~競技プログラミングサービス~~無料オンラインゲームでは、以下のようにスペースで区切られた整数値の標準入力(Standard Input)を[Int]型に変換してアルゴリズムを実装していくケースが多々ある。

$ A_1\ B_1\ C_1 $
$ A_2\ B_2\ C_2 $
$ A_3\ B_3\ C_3 $
$ \vdots $
$ A_N\ B_N\ C_N $

入力は全て整数

Swiftにおいて、上記のような標準入力を[Int]型に変換しようとすると以下のようなコードが真っ先に思い浮かぶ。

Int($0)を用いている ← 取り締まり対象

let input: [Int] = readLine()!.split(separator: " ").map { Int($0)! }

ただ、これはreadLine()!.split(separator: " ").map{ Int($0)! }警察の取り締まり対象となる(罪名: TLE)。

当警察は、善良市民に対して以下のようなコードを用いることを推奨している。

Int(String($0))を用いている ← 当警察推奨

let input: [Int] = readLine()!.split(separator: " ").map { Int(String($0))! }

何が違反にさせているのか

String#split(separator:) -> [Substring]の各要素であるSubstringをInt型に変換する際、Stringを介した場合(Substring → String → Int)には高速化が図られている。

そのため、Substring → Intのように直接変換してしまうとStringを介する場合に比べて相対的に時間がかかる。

IntegerParsing.swift(Swift-5.2.1)

@inlinable // @specializable
@_semantics("optimize.sil.specialize.generic.partial.never")
public init?<S: StringProtocol>(_ text: S, radix: Int = 10) {
  _precondition(2...36 ~= radix, "Radix not in range 2...36")
  
  /*
   textがStringにダウンキャスト可能であれば高速処理が実行される
   ※ StringとSubstringは内部で互いに利用し合っているが、構造体の型自体に継承関係はない
  */
  if let str = text as? String, str._guts.isFastUTF8 {
    guard let ret = str._guts.withFastUTF8 ({ utf8 -> Self? in
      var iter = utf8.makeIterator()
      return _parseASCII(codeUnits: &iter, radix: Self(radix))
    }) else {
      return nil
    }
    self = ret
    return
  }
  ...
}

詳細は下記記事を参照↓

競プロerはSwiftでSubstringを直接Intに変換してはいけない

大体のことは上記記事に書いてあるため、Substringについて言及する。

Substringとは何か

参考①: Swift Language Guide(Strings and Characters)
参考②: apple / swift / docs / StringManifesto(GitHub)

元のString(またはそのSubstring)インスタンスのメモリアドレスを保持する部分文字列。

let greeting: String = "Hello, world!"
let index: String.Index = greeting.firstIndex(of: ",") ?? greeting.endIndex

// String → Substring への変換
// → 変数beginningは変数greetingを参照し続ける
let beginning: Substring = greeting[..<index]

// Substring → String への変換
// → 変数beginningのメモリをコピーすることで、変数greetingへの参照を断つ
let newString: String = String(beginning)

構造体	特徴
`String`	インスタンスを生成するたび(※)にメモリアドレスを新たに確保 ※ 同じ文字列を指す場合はメモリを共有する
`Substring`	インスタンスを生成しても元のメモリアドレスを再利用

The difference between strings and substrings is that, as a performance optimization, a substring can reuse part of the memory that’s used to store the original string, or part of the memory that’s used to store another substring. (Strings have a similar optimization, but if two strings share memory, they’re equal.) This performance optimization means you don’t have to pay the performance cost of copying memory until you modify either the string or substring. (- "Strings and Characters", Swift Language Guide より引用)

StringとSubstringの違いはパフォーマンスの最適化手法として、Substringは元のStringインスタンスや他のSubstringが格納されたメモリの一部を再利用できることにある。
Stringも類似の最適化手法が採用されているものの、(Substringは元の文字列が同じであれば、異なる部分を参照していてもメモリが共有されるのに対し、)Stringは同じ文字列(=equal) でしかメモリを共有できない。
ここでの「最適化手法」とは、メモリが共有されるのは文字列または部分文字列に変更が加わるまでであり、変更が加わればメモリがコピーされ、新たにメモリが確保される。

A substring holds a reference to the entire storage of a larger string, not just to the portion it presents, even after the original string's lifetime ends. Long-term storage of a Substring may therefore prolong the lifetime of large strings that are no longer otherwise accessible, which can appear to be memory leakage. (- "Substrings / Different type, shared storage", StringManifesto より引用)
SubstringはStringインスタンス(=元の文字列全体)を参照するため、元の文字列の一部しか利用しない場合であってもSubstringが生存し続ける限り文字列全体がメモリに残り続け、メモリリークが生じる可能性がある。

When assigning a Substring to a longer-lived variable (usually a stored property) explicitly of type String, a type conversion will be performed, and at this point the substring buffer is copied and the original string's storage can be released. (- "Substrings / Different type, shared storage", StringManifesto より引用)
これを避けるためにはSubstring → Stringに変換することでSubstringのバッファをコピーし、元のStringをガベージコレクションの対象にすればよい。

補足①: XCodeでの標準入力の受け取り方

AtCoderに提出する前に自作の.txtを用いてアルゴリズムの整合性を検証したい場合、まずは標準入力となる.txtファイルを作る。

.txtファイルの作成(例)

// .txtを生成する絶対パス
// "/Users/<ユーザ名>/Documents/Input.txt"のように絶対パスを記述しても良い
let path: String = NSHomeDirectory() + "/Documents/Input.txt"

// .txtの内容(=標準入力)
var text: String = ""

do {
  for i in 1 ... 500000 {
    // 改行する場合は改行コード(\n)を最後に挿入
    text += "\(i) \(i + 1) \(i + 2)\n"
  }
  
  // .txtへの書き込み
  try text.write(toFile: path, atomically: true, encoding: .utf8)
}
catch {
  print(error)
}

次に、作成した.txtファイルを標準入力として設定し、AtCoderに提出する処理を実行する。

Xcodeを用いた標準入力の受け取り

// 標準入力の受け取り
let _ = freopen("/Users/b150005/Documents/Input.txt", "r", stdin)

// AtCoderに提出する処理
AtCoderに提出する処理()

補足②: 実行時間の測定

実行時間の測定

let start: Date = Date()

// AtCoderに提出する処理
AtCoderに提出する処理()

let elapsed: TimeInterval = -start.timeIntervalSinceNow

// 経過時間の出力
print(elapsed)

補足③: メモリアドレスの確認

参考: Memory Address of value types and reference types

メモリアドレスの確認方法は、参照型と値型で参照方法が異なる。

型	確認対象	ソースコード
参照型	参照先	ObjectIdentifier(<参照型インスタンス>)
^	^	Unmanaged.passUnretained(<参照型インスタンス>).toOpaque()
^	参照先が同じかどうか	<参照型インスタンス①> === <参照型インスタンス②>
値型	インスタンスの格納先	withUnsafeMutablePointer(to: &<値型インスタンス>) { $0 } ※ 変数の前に`&(アンパサンド)`を付加することで値型インスタンスを参照渡しする

👮‍♀️<こんにちは、readLine()!.split(separator: " ").map{ Int($0)! }警察です

概要