LoginSignup
16
14

More than 5 years have passed since last update.

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

Last updated at Posted at 2015-10-29

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

問題の概要(Java版)

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

問題その1(自作クラスにて)

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

expression = terms.reduce(&:or)

のようにしたところで、とたんに固まってしまいました。性質上、論理式の各項は一度生成すれば書き換えないものなので、長さが徐々に増える項が次々と作成されていって1O(n2)の処理となってしまっていたのでした。そこで新たなメソッドを作って、「複数の項を一気に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)∨ca∨(b∨c)を区別せずに、まとめて(a∨b∨c)という1つの項として扱うように系を組んでいました。 

16
14
4

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
16
14