TLE を出さないために、プログラムの実行時間をテストする (Swift)

皆さんクリスマスケーキの予約は済みましたか？

私は 24日,25日 受け取りの予約は一杯で取れませんでした。

TL;DR

• TLE (Time Limit Exceeded) は XCTWaiter で timeout を指定してテストする
• 実行時間のテストは Release ビルド (-Onone) で行う

なぜプログラムの実行時間をテストするのか

今年に入ってから AtCoder を始めとした競技プログラミングコンテストに Swift で参加する方が少しづつ増えてきており、自分も2年前に C++ で挑んでは言語の壁に膝をついたリベンジとばかりに Swift で競プロを楽しめる日々を噛み締めています。

競技プログラミングでは課題に沿ったプログラムを正確に書くことと同時に、既定の時間内に正解にたどり着くよう効率的なプログラムを書くことも求められます。

例えば、 ABC085C - Otoshidama だと実行時間制限が 2秒となっており制約が 1 <= N <= 2000 なので、x, y, z を全パターン試す全探索アルゴリズムだと O(N^3) となり簡単に 実行時間超過 (TLE: Time Limit Exceeded) してしまいます。

1秒につき 10^7 程度が計算量の目安とされています。2000^3 は 8 * 10^9 なので大体 800 秒くらいかかる計算になります。

自分が書いたプログラムが TLE するかどうかは常に気を払わないといけない関心事の一つです。

しかしプログラムが正しい出力をするかどうかのほうに意識が優先してしまいがちですし、修正を繰り返すうちに当初イメージしていた計算量から外れてしまうことも考えられます。

プログラムを修正するたびに手動で入力値を与えてテストを行うのも大変面倒なので、ユニットテストを書いて後は ⌘ + U をしたら勝手にテストを実行してくれるようにしたい所です。

Xcode 上でプログラムの実行時間を計測する

プログラムの実行時間をテストするコードを書いてみましょう。

まず、ターミナルで swift package init --type executable を実行すると Command Line Tool の SPM プロジェクトが作成されます。

このプロジェクトには print("Hello, world!") とだけ書かれた main.swift ファイル1つと、実行して Hello, world! と標準出力されるかをテストするファイル1つのみが含まれています。

.
├── Package.swift
├── README.md
├── Sources
│   └── temp
│       └── main.swift
└── Tests
    └── tempTests
        └── tempTests.swift

// main.swift
print("Hello, world!")

// abcTests.swift
import XCTest
import class Foundation.Bundle

final class abcTests: XCTestCase {
    func testExample() throws {
        ...
        let fooBinary = productsDirectory.appendingPathComponent("abc")

        let process = Process()
        process.executableURL = fooBinary

        let pipe = Pipe()
        process.standardOutput = pipe

        try process.run()
        process.waitUntilExit()

        let data = pipe.fileHandleForReading.readDataToEndOfFile()
        let output = String(data: data, encoding: .utf8)

        XCTAssertEqual(output, "Hello, world!\n")
    }
    ...
}

テストを実行すると ✅ のテスト成功マークが表示されます。

次に TLE するプログラムをテストしてみます。

// 重たい処理
print((0 ..< Int.max).reduce(0, { $1 + 1 }))

テストを実行します。

残念ながら自分が使っている PC では一生結果が返ってこない上に、CPU が 99.9% に張り付いて Mac のファンが回り始めるので適度なところで止めます。

この残念なテストを修正しましょう。

2秒でタイムアウトするようにテストを書き換えます。

// abcTests.swift
import XCTest
import class Foundation.Bundle

final class abcTests: XCTestCase {
    func testExample() throws {
        ...
        let fooBinary = productsDirectory.appendingPathComponent("abc")

        let process = Process()
        process.executableURL = fooBinary

        let pipe = Pipe()
        process.standardOutput = pipe

        // 2. TLE したプロセスを kill する
        addTeardownBlock {
            if process.isRunning {
                process.terminate()
            }
        }

        // 1-1. プロセスを別スレッドで実行する
        let exp = expectation(description: "run")
        DispatchQueue.global().async {
            try! process.run()
            process.waitUntilExit()
            exp.fulfill()
        }

        // 1-2. プロセスの終了を非同期で待つ。2秒でタイムアウト。
        let result = XCTWaiter.wait(for: [exp], timeout: 2)
        switch result {
        case .completed:
            let data = pipe.fileHandleForReading.readDataToEndOfFile()
            let output = String(data: data, encoding: .utf8)!
            XCTAssertEqual(output, "Hello, world!\n")
        case .timedOut:
            XCTFail("TLE: Exceeded timeout of 2 seconds")
        default:
            XCTFail("Unrecognized error.")
        }
    }
    ...
}

次の2点が変更点です。

• XCTWaiter を使って非同期に実行結果を待つ。2秒でタイムアウトさせる。
• TLE したプロセスはテストの終了とともに強制的に kill する

再度テストを実行します。

今度はきっかり2秒でテストが終了しました。CPU もファンも無事です。

abcTests.swift:37: error: -[abcTests.abcTests testExample] : failed - TLE: Exceeded timeout of 2 seconds

実際のところ、テストを実行する PC とコンテストの実行環境は全く異なるためこの 「2秒」という数字を正確に受け取ることに意味はありません。テストでは 1秒かかったがコンテストに提出してみたら 0.5秒未満だったということはザラにあります。おおよそ「計算量オーダーが合っている」という尺度で見てください。

テストを Release ビルド設定に変更する

1つ重要な指摘として、Xcode のテスト実行はデフォルトでは Debug ビルドバイナリ で行う、というものがあります。

Debug ビルドと Release ビルドでは Swift コンパイラの最適化レベルが異なり、プログラムの実行速度に雲泥の差が出ることがままあります。

コンテストの実行環境では Release ビルドされたプログラムが検証されるので条件を近づけるために、Release ビルド設定でテストを実行するように変更します。

Edit Scheme (⌘ + <) - Test - Info - Build Configuration で Release を選択

これで Release ビルドされた実行ファイルを使ってテストが行われるようになりました。

注意点としては、Release ビルドではデバッグが出来なくなるのでブレークポイント等を置きたい場合は Debug ビルドに戻してください。

コンテストの度にこれらの準備するの面倒じゃない？

そんなあなたには atcoder-cli-swift がオススメです (宣伝)

AtCoder のコンテストID から SPM プロジェクトを自動生成してくれる便利な CLI ツールです。

テストコードもコンテストページのサンプル入出力を元に自動で補完されますし、サンプルに無いテストを自分で追加することも簡単に出来ます。

➜ accs new abc001
Finished.
➜ tree abc001
abc001
├── Package.swift
├── README.md
├── Sources
│   ├── A
│   │   └── main.swift
│   ├── B
│   │   └── main.swift
│   ├── C
│   │   └── main.swift
│   └── D
│       └── main.swift
└── Tests
    ├── ATests
    │   └── ATests.swift
    ├── BTests
    │   └── BTests.swift
    ├── CTests
    │   └── CTests.swift
    ├── DTests
    │   └── DTests.swift
    └── TestLibrary
        └── TestLibrary.swift

11 directories, 11 files

まとめ

本記事では Xcode で競技プログラミングをする上であると便利なテストの実施方法と、TLE のテストの記述方法・実行時間計測時の Swift コンパイラの最適化フラグの注意点について解説しました。たまーに TLE を未然に検知することができるのでそのときは5分(1ペナ)得をした気分になれます。

ついでに弊社 Wantedly 21新卒 Advent Calendar 2021 の宣伝をします。

どれも良い記事ばかりなのですが、特に データ分析・集計で気をつけている8つのこと が個人的にオススメです。

プロダクト開発をしているとデータ分析・集計を行うことは避けられないですが、意外と基本的なことが無意識のうちに落ちていたり客観的な視点を見失いがちなので、分析がうまく行かない時にふと立ち止まって見直したい良いまとめだと思います。