[Swift] Swift-Collections の紹介 (Deque)

Swift

Apple が提供している swift-collections を説明します。

環境&対象

以下の環境で動作確認を行なっています。

  • macOS Big Sur 11.2.3
  • Xcode 12.4
MEMO
macOS で説明してますが、iOS でも同様に使用できます。

swift-collections

Apple が github 経由で公開しているライブラリを使うことで、集合を表す要素(コレクション)を 3つ 追加することができます。

github は、こちら

Swift Package Manager 経由で設定することで、以下の3つのコレクションを使用することができます。

  • Deque<Element>
  • OrderedSet<Element>
  • OrderedDictionary<Element>

それぞれ、<Element> と Generics を使用していますので、内部にさまざまな型を保持することができます。

特徴的な操作について Array および C++ コード とのパフォーマンス比較も公開されています。

MEMO
C++ のコードは、C++ のテンプレートを使用して実装されています。
Swift ユーザーからすると実質的な選択肢にはなり得ませんが、潜在的な上限(下限)を図るのに有効だと思います。

測定に使用された C++ のコードも公開されています。

公開されたデータを見ながら、どのコレクションをどのような時に使うと効率的なのかを考察していきます。

なお、Swift.org の Blog でも説明されています。

Deque

Array のように使えるコレクションです。(Deque は デック と発音するようです)

以下のような特徴を持つコレクションです。

  • 順序は保存されます
  • 変更可能(mutable)
  • 整数のインデックスを使ってランダムアクセス可能
  • 区間を置き換えることが可能(RangeReplaceableCollection のことです)
  • 特に、最初と最後への追加と削除を効率的に行うことが可能

例えとして、FIFO キューを効率的に実装できるとされています。Deque については、その実装について 追加と参照の2つの視点でのパフォーマンス測定結果が公開されています。

Deque の使い方

Deque 向けに用意されたメソッドは、以下のものです。下記以外にも MutableCollection や RangeReplaceableCollection のメソッドも使えます。

  • prepend: リストの一番最初に要素を追加
  • append: リストの一番最後に要素を追加
  • popFirst: リストの一番最初の要素を取得(&削除)
  • popLast: リストの一番最後の要素を取得(&削除)
Deque example

パフォーマンス測定:Deque への要素追加

Deque は、先頭と最後に要素を追加することを低コストで行えるようなコレクションです。

先頭への要素追加は prepend メソッドで処理されます。そのパフォーマンス(実行時間)を測定・比較しています。

結果のグラフは、こちらです。

横軸に要素数。縦軸が処理時間のグラフです。(縦軸・横軸ともに、指数的に増えていくグラフになっています)

特徴的な箇所を書いてみます。(数字はグラフから目分量で読んでいます)

  • 要素数が、32 あたりまでは、Deque, Array, std::deque のパフォーマンスはあまり変わらない
  • 要素数が 64 を超えてくると、Array の prepend のコストが上昇を始め、要素数 128k あたりでは、Deque, std::deque が 10ns 以下で処理できる時に、Array は、10μs 以上かかるようになる

Prepend は、Deque が有利な操作です。処理時間が O(1) の Deque に対して、O(n) となるのが Array です。

パフォーマンス測定:Deque への参照

要素を追加するだけでなく、参照するときのパフォーマンスもコレクション選定に重要です。ランダムアクセス時のパフォーマンス測定も公開されています。

結果のグラフは、こちらです。

特徴的な箇所を書いてみます。

  • Deque, Array は、要素数 16 くらいまでは、同等のパフォーマンス。std::deque は圧倒的に速い。
  • 要素数 16〜64 を経由して、Array と std::deque が同等のパフォーマンスとなり、Deque のみ掛かる時間が増える。目視では、Deque 3μs 程度の時、Array, std::deque は、1.7μs 程度。
  • 要素数が 64k を超えると、Deque, Array, std::deque のパフォーマンスは一致し始める。

Deque は、要素保存のための領域を連続的に取らないので、ランダムアクセスは、圧倒的に Array が有利なはずですが、処理時間をみると(個人的な感覚ですが)圧倒的な差異としては現れていない気もします。

ただし、ランダムアクセスを多用することが想定されるならば無視できない差になりそうです。

考察

Prepend は、Deque, std::deque が得意な操作で、参照(ランダムアクセス)は、Array が得意な操作です。

Prepend については、要素数が 256 を超えるあたりから、処理時間の差が顕著になります。Deque が O(1) の処理時間であることに対して、Array は、O(n) であることの特徴がでてきます。

参照(ランダムアクセス)については、要素数 1 の時の Deque, std:deque と Array との差がもっとも大きそうですが、ユースケースとしてその要素数が支配的になることは少ないと想像します。

要素数がさらに増えても、処理時間に固定的な差がみられます。ただし、Deque の処理時間も O(1) に見えます。この固定的な差は、要素数 128K まで続きます。(以降は大きな差異は見られません)

月並みな結論ですが、以下のような選定基準になりそうです。

  • 要素数が 256 を超えるかどうか → 超えないならいずれを選んでも大差ない
  • prepend を高速に使うために、ランダムアクセス時の処理時間追加を許容できるか
MEMO
Deque は、prepend を高速に行うために、内部要素を連続領域に確保していないことを明示しています。

まとめ:Deque @ swift-collections

Deque @ swift-collections
  • Apple から Swift のコレクションを拡張する swift-collections が公開されている
  • リストの先頭と最後に対して追加削除を効率的に行う Deque が用意されている
  • FIFO(First-In-First-Out) キューの作成に最適
  • 要素数のパフォーマンス比較も公開されているので、導入するかどうかを個々のユースケースで比較することも可能

説明は以上です。
不明な点やおかしな点ありましたら、こちらまで。

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です