ArrayとDictionaryの取り出し速度比較

概要

ある値とそのキーのペアを何らかのコンテナ型に保存し、取り出すことを考えます。

Swiftでは標準ライブラリとしてArrayとDictionaryというコンテナが用意されています。

// Arrayの場合
var elements: [(String, Int)] = [...]
if let value = elements.first { $0.0 == "key" }?.1 {
    ...
}

// Dictionaryの場合
var elements: [String: Int] = [...]
if let value = elements["key"] {
    ...
}

要素数Nのコンテナの中からあるキーに対応する値を取り出したいとき、
Arrayは目的の要素を探索するのにO(N)のコストがかかります。
一方でハッシュ値を用いるDictionaryの場合、目的の要素に対してO(1)でアクセスできます。

オーダーだけで比較するとDictionaryのほうが速そうですが、現実的な状況としてNが十分大きくない場合はArrayのほうが速いです。
ハッシュコンテナは複雑な動きを行うため、単純にそのオーバーヘッドで速度で劣る場合があります。

今回、要素数Nがどの程度までならArrayのほうが速いのか気になったので調べてみました。

計測実装

XCTestを用いて計測しました。計測対象データのキーは Any.Type で値は Int としています。なぜ Any.Type を選択したのかというと、単に計測したいと思ったコードで使用されていた型がこれだったからです。
Any.Type はHashableではなくそのままではDictionaryのキーとして使えないため、ラッパーを用意しています。

Any.TypeをHashableとして扱うためのラッパー

struct HashableType: Hashable {
    let type: Any.Type
    private let combineValue: Int
    init<H: Hashable>(_ type: H.Type) {
        self.type = type
        combineValue = "\(type)".hashValue
    }

    func hash(into hasher: inout Hasher) {
        hasher.combine(combineValue)
    }

    static func == (lhs: HashableType, rhs: HashableType) -> Bool {
        lhs.type == rhs.type
    }
}

なんとなく型名を文字列化する操作が重そうに思ったのでinit内で処理し、計測中に文字列化の操作は行われないようにしています。

テストコード

• タプルによるArray
• structによるArray
• Dictionary

でテストしてみました。

let measureRepeats = 100000
let typesCount = 25 //  or 50 or 100

func testTupleArray() {
    measureMetrics([.wallClockTime], automaticallyStartMeasuring: false) {
        var storage: [(Any.Type, Int)] = []
        let inputs = types.shuffled()
        inputs.enumerated().forEach { i, v in storage.append((v, i)) }

        var results: [Int] = []
        results.reserveCapacity(measureRepeats * inputs.count)

        startMeasuring()
        for _ in 0..<measureRepeats {
            for input in inputs {
                results.append(storage.first(where: { $0.0 == input })!.1)
            }
　        }
        stopMeasuring()

        XCTAssertEqual(results.prefix(inputs.count), Array(0..<inputs.count)[...])
    }
}

func testStructArray() {
    struct Box {
        var type: Any.Type
        var value: Int
    }
    measureMetrics([.wallClockTime], automaticallyStartMeasuring: false) {
        var storage: [Box] = []
        let inputs = types.shuffled()
        inputs.enumerated().forEach { i, v in storage.append(Box(type: v, value: i)) }

        var results: [Int] = []
        results.reserveCapacity(measureRepeats * inputs.count)

        startMeasuring()
        for _ in 0..<measureRepeats {
            for input in inputs {
                results.append(storage.first(where: { $0.type == input })!.value)
            }
        }
        stopMeasuring()

        XCTAssertEqual(results.prefix(inputs.count), Array(0..<inputs.count)[...])
    }
}

func testHashableTypeDictionary() {
    measureMetrics([.wallClockTime], automaticallyStartMeasuring: false) {
        var storage: [HashableType: Int] = [:]
        let inputs = hashableTypes.shuffled()
        inputs.enumerated().forEach { i, v in storage[v] = i }

        var results: [Int] = []
        results.reserveCapacity(measureRepeats * inputs.count)

        startMeasuring()
        for _ in 0..<measureRepeats {
            for input in inputs {
                results.append(storage[input]!)
            }
        }
        stopMeasuring()

        XCTAssertEqual(results.prefix(inputs.count), Array(0..<inputs.count)[...])
    }
}

types 及び hashableTypes は100個の型が予め定義されたArrayです。実際のコードはこちらからどうぞ。

テスト実行スキーマの設定

Xcodeのスキーマ設定からテスト実行時のビルド設定をReleaseとし、Debug executableのチェックを外し、Diagnosticsの機能を全て無効化します。
最適化オプションを有効にし、デバッグ関係の機能をすべて無効化することでできるだけ本番環境に近づけています。
この状態で ⌘+U を押下して実機iPad上でテストを実行します。

結果

テスト名	実行時間(N=25)	N=50	N = 100
testTupleArray	0.0272s	0.0748s	0.290s
testStructArray	0.0269s	0.0749s	0.290s
testHashableTypeDictionary	0.0702s	0.1240s	0.258s

XCTestの measure 関数は同じ処理を10回行った結果の平均をとるため、上の表の実行時間も10回中の平均となります。テストコード中に乱数を使用しているのもあり実行ごとに誤差は出ますが、比較結果が覆るほどの変化はありませんでした。

考察

要素数が50程度であればArrayのほうが十分に高速でした。要素数100となるとDictionaryのほうが速い結果です。
個人的にはNが100くらいだったらArrayのほうが速い、1000近くなると差が出てくるのだろうと思ってましたが100の時点ですでに抜かれてしまうようですね。
また、StructとTupleの差はありませんでした。

注意

計測コードでは10万回以上ものアクセスを行っているため差が出ていますが、実際のユースケースで短期間にこのようなアクセスがあるケースはまれだと思います。
計測不可能なレベルの速度差しか出ないため、プロダクトコードにおいては予想要素数に応じてコンテナを使い分けるよりもコードの書きやすさ、わかりやすさを重視して適切に使い分けていきましょう。

環境

• Xcode 11.6
• Swift 5.2.4
• iPad Pro (11-inch) (2nd generation) iOS(iPadOS) 13.5.1