Zenn
⛓️

[Swift] その配列の足し算は本当に必要ですか？ / chainのススメ

2023/06/01に公開
Swift
swiftalgorithms
tech

Swiftではしばしば、配列を2つ繋げて処理したいことがあります。例えば、以下のような場合です。

let array1 = getArrayFromSource1()
let array2 = getArrayFromSource2()

for item in array1 {
    doSomething(with: item)
}
for item in array2 {
    doSomething(with: item)
}

このような場合、array1 + array2に対してループを書くことで、コードがスッキリします。

// コードがスッキリ！
for item in array1 + array2 {
    doSomething(with: item)
}

これで良くなったように見えるのですが、実際には問題があります。

配列の足し算は重い

配列の生成は重たい操作です。というのも、要素数分のメモリを確保して書き込む必要があるからです。このため、特に大きな配列の足し算は非常に重たい操作になります。

そこで、上記のように配列を足し算してしまうと、愚直にループを2回書くのに比べて低速になってしまう、ということが起こります。

// 実はこう書いた方が高速
for item in array1 {
    doSomething(with: item)
}
for item in array2 {
    doSomething(with: item)
}

綺麗に書くだけのために足し算すると、熱ばかり無意味に生み出すことになり、あまり良くありません。では、こういう時はどうするのが良いのでしょうか。

chain()

一般に、forループに必要なのはSequenceへの適合です。Sequenceはイテレータの実装を必要としますが、配列を作り直す必要は本来ありません。
もしも「最初にarray1のイテレータを実行し、それがnilに到達したらarray2のイテレータを実行する」ことができれば、配列の足し算は不要です。

これをやってくれるのがSwift Algorithmsのchain()です。

import Algorithms

for item in chain(array1, array2) {
    doSomething(with: item)
}

chainは2つのS1: Sequence, S2: Sequenceを合成して、1つのChain2Sequence<S1, S2>型の値を返してくれます。Chain2Sequence<S1, S2>はSequenceに適合しているので、上のようにforループで使うことができます。

イメージとしては、並列に繋ぐのがzipなら直列に繋ぐのがchainです。

chainでは余分な領域を確保することがないため、ループを高速に実行することができます。

chainをプロジェクトに導入する

chainはSwiftの標準ライブラリには含まれておらず、AppleのOSSであるSwift Algorithmsをインポートして使う必要があります。

https://github.com/apple/swift-algorithms

導入方法は一般的なSwift Packageと変わりませんが、細かい手順が知りたい場合はこちらの記事などが参考になりそうです。

https://gaprot.jp/2022/09/12/swiftalgorithms/

chainのパフォーマンスを測定する

chainのパフォーマンスを測定するため、簡単なテストを入れたパッケージを用意しました。クローンしてコマンド一発なのでぜひお試しください。

https://github.com/ensan-hcl/swift_chain_performance

ここでは、比較的小さな配列を足し算した場合とchainを用いて結合した場合でパフォーマンスを比較します。

// 2つの配列を足し算して用いる場合
func testTake2ArrayAdditionPerformance() throws {
    measure {
        let a = Array(0 ..< 100)
        let b = Array(100 ..< 200)
        for _ in 0..<1000000 {
            takeSequence(a + b)
        }
    }
}

// 2つの配列をchainで結合して用いる場合
func testTake2ArrayAdditionPerformance() throws {
    measure {
        let a = Array(0 ..< 100)
        let b = Array(100 ..< 200)
        for _ in 0..<1000000 {
            takeSequence(chain(a + b))
        }
    }
}

takeSequenceの実装は次のようになっていて、単純にループを回して軽微な操作を行っています。

func takeSequence(_ sequence: some Sequence<Int>) {
    for i in sequence {
        _ = i + 1
    }
}

まず、2つの配列を結合する場合です。

* testTake2ArrayAdditionPerformance
measured [Time, seconds] average: 0.227, relative standard deviation: 3.636%, values: [
  0.232912, 
  0.233811, 
  0.224064, 
  0.219582, 
  0.211700, 
  0.234103, 
  0.215850, 
  0.237818, 
  0.230090, 
  0.226787
]

* testTake2ArrayChainPerformance
measured [Time, seconds] average: 0.0000233, relative standard deviation: 94.828%, values: [
  0.000089, 
  0.000023,
  0.000016,
  0.000015, 
  0.000015,
  0.000015,
  0.000015,
  0.000015,
  0.000015,
  0.000015
]

約9700倍高速でした。思ったより効いてきますね。

では、chainのパフォーマンスと、単にループを複数並べて実行する場合のパフォーマンスを比べるとどうなるでしょうか。次のようなテストを行ってみます。

func testTake2ArrayPerformance() throws {
    measure {
        let a = Array(0 ..< 100)
        let b = Array(100 ..< 200)
        for _ in 0..<1000000 {
            takeSequence(a)
            takeSequence(b)
        }
    }
}

結果は以下のようになりました。

* testTake2ArrayPerformance
measured [Time, seconds] average: 0.0000262, relative standard deviation: 94.323%, values: [
  0.000097, 
  0.000022,
  0.000016,
  0.000015,
  0.000015,
  0.000039,
  0.000016,
  0.000014, 
  0.000014,
  0.000014
]

なんと、chainを使った場合とほとんど変わりません。chainを使うことで、コードのシンプルさを犠牲にせず、良いパフォーマンスを得られることがわかります。

次に、3つの配列を結合する場合です。Chain3Sequenceは存在しないので、Chain2Sequence<Chain2Sequence<A, B>, C>みたいな型になります。

* testTake3ArrayAdditionPerformance

measured [Time, seconds] average: 0.574, relative standard deviation: 6.311%, values: [
  0.571852, 
  0.609838,
  0.535366,
  0.533511,
  0.517794,
  0.587197,
  0.644619, 
  0.573711,
  0.593577,
  0.573296
]

* testTake3ArrayChainPerformance
measured [Time, seconds] average: 0.0000257, relative standard deviation: 77.464%, values: [
  0.000085, 
  0.000024,
  0.000020, 
  0.000019, 
  0.000019, 
  0.000018, 
  0.000018,
  0.000018,
  0.000018, 
  0.000018
]

こちらも約22000倍高速です。面白いように効きますね。

ところが、実は4つ以上の配列になるとchainのパフォーマンスが急激に悪化します。

* testTake4ArrayAdditionPerformance
measured [Time, seconds] average: 0.919, relative standard deviation: 6.813%, values: [
  0.890148, 
  0.869612,
  0.909080, 
  0.890426, 
  0.892907, 
  1.090301, 
  0.968163, 
  0.916662, 
  0.882951, 
  0.882945
]

* testTake4ArrayChainPerformance_b
measured [Time, seconds] average: 0.276, relative standard deviation: 4.387%, values: [
  0.286580, 
  0.273148, 
  0.266839, 
  0.295965, 
  0.270032,
  0.276245,
  0.264713, 
  0.295149, 
  0.265702,
  0.261002
]

この場合、パフォーマンスの向上は3.3倍にとどまります。これでも十分良いのですが、3つまでの結果がほとんどゼロに近い値だったことを考えるとやや不思議な結果です。実際、単に4回ループを書く形なら先ほどと同様ほとんどゼロに近い値になるので、chainが4つ以上の配列の結合を苦手とする様子が伺えます。

逆転こそしないものの、5個の配列の和になるとパフォーマンスの向上は約2倍まで小さくなります。

まとめ

この記事では配列の足し算の代わりにchain()を利用することをオススメしました。2、3個の配列の足し算においては劇的にパフォーマンスが向上します。4個以上の場合のパフォーマンス向上の恩恵が小さくなるものの、それでも十分にパフォーマンスが向上しています。もちろん、通常の利用では2、3個での性能向上の時点で十分有用だと思います。

標準ライブラリに入っていてほしいレベルの使い勝手なので、ぜひぜひお試しください。

Discussion