演算のたびに新オブジェクトを作ることによる問題

Java界ではけっこう有名な問題を、Rubyのプログラミング中に踏んでしまいました。

問題の概要（Java版）

JavaではStringがイミュータブル（一度生成したら、値を変えることができない）なので、文字列連結を行った場合には「現在の文字列をコピーして新たな文字列を生成する」という処理が必要になります。そのため、単純にn個の文字列を連結で生成していくと、*O(n²)*だけのコピー処理が必要となり、非効率になります。以前、自分も触れましたが、「大量の文字列連結を行う場合にはStringBuilderを使う」ということは、Javaではよく知られています。

問題その1（自作クラスにて）

Rubyで論理式を処理するようなシステムを作っていて、そして別に作ったプログラムから数千個の項を生成していました（それ自体は問題なく動作していました）。そして、最後に

expression = terms.reduce(&:or)

のようにしたところで、とたんに固まってしまいました。性質上、論理式の各項は一度生成すれば書き換えないものなので、長さが徐々に増える項が次々と作成されていって¹、*O(n²)*の処理となってしまっていたのでした。そこで新たなメソッドを作って、「複数の項を一気にOR/AND連結できる」ようにすることで、一瞬で終了できるようになりました。

問題その2（Ruby添付のライブラリにて）

そして、目的の式ができることが確認できたところで、この式に現れる変数のリストが必要となりました。同じ変数は一度でいいので、これは「集合」だからと、標準添付のsetライブラリを使ってみることにしました。ところが、これが失敗だったということに、あとで気づくことになりました。

変数自身は別として、それ以外の項だと、その項が持つ変数リストは「自分自身が要素として持つ項に含まれる変数の総和」なので、再帰的に書くことができます。とりあえず、こう書いてみました。

失敗例

def variables
  @terms.map(&:variables).reduce(&:|)
end

さっきと全く同じパターンではまってしまいました。さらに、さっきと同じ手法で回避しようにも、Setには「他のセットを破壊的にマージする」ようなメソッドが存在せず、要素を1つ1つ追加する以外にない、という悲しい結論にたどり着くこととなりました。結局、破壊的操作もやりやすい配列を使って

改善後

def variables
  @terms.map(&:variables).flatten.uniq
end

とすることで、スムーズに動作するようになりました。

で、このQiita投稿を書くときにsetライブラリの説明を読んでみたら、「Arrayの持つ演算機能とHashの高速な検索機能を合わせ持ちます」とありました。つまり、集合演算に限れば充分Arrayでも可能だということで、今回の例では「高速な検索機能」を活かすこともできず、破壊的変更がやりづらいというSetのデメリットが際立つ結果となってしまいました。

1. あとで行う処理の都合上、(a∨b)∨cとa∨(b∨c)を区別せずに、まとめて(a∨b∨c)という1つの項として扱うように系を組んでいました。 ↩