どう書く:素因数分解

曇り、風が強い。台風15号が近づいているらしい。台風は現在台湾で猛威をふるうだけふるって日本にのんびり向かってきているらしい。ひょええ。今日は強風のテニスの日。曇りなのは気持ちいいな。すっかり秋な感じ。

がくぞー師匠から素因数分解のプログラムを書けってお題を頂いたので謹んで書かせていただきました。とりあえず一番書きなれたJavaで。ソースコード

採用したアルゴリズムは、与えられた数を最小の素数で割り、余りを常に最小の素数で割り続けていく、最終的には抽出した素数をすべて掛け算すると与えられた数になるという方法。文系的な説明ですみません。コードのポイントを説明するよ。

コンストラクタを隠し、ファクトリーメソッド経由でインスタンスを生成している

インスタンス生成時に不正データ(この場合与えられた数字が2より小さい)を除外したいと思ったが、コンストラクタがエクセプションを投げるのは気が引けたのでファクトリーメソッドにした。ちなみに不正データの場合nullを返すというパターンがあるけれど、Javaではコンスタクタはnullを返すことができないので、コンストラクタで不正を通知するにはエクセプションを使うしかない。

I think constructor must not throw exceptions. In this case, the factory method is used to avoid making illegal creation of the class with invalid argument (less than 2). BTW, in java, constructor can't return null. Have to use exception when errors detected in constructor.

インナークラス FactorizationFolder

これはデータモデルクラス。抽出した素数を格納しておく。

Inner class FactorizationFolder. This is data model class. It stores data.

冗長メソッド findTheSmallestFactor

findFactorはfindTheSmallestFactorという別のメソッドを呼ぶだけの一見無駄なメソッドになっているがこれはわざと意図してやった。最初はfindFactorメソッドに実装を書いていたが、後からこの形に書きなおした。なぜ、わざわざこのような冗長なコードに変更したのか、よろしければ是非推測して欲しいです。

The verbose method findTheSmallestFactor. The findFactor method only calls the findTheSmallestFactor method. It seemingly looks waste but I think it's need. It had written simply at first, written this way afterwards. Please think about it why.

foldLeft メソッド

他の言語ではよくでてくるけどJavaだと余りお目にかかる機会の少ないfoldLeftは畳み込みと呼ばれる手法。やりたいことは要素すべての合計値を計算したい、というだけの、見た目ほどにはたいしたことないもの。52~55行目の計算をJavaで普通にやるとこうなる。

int result = 1;
for (final Map.Entry<Integer, Integer> entry : primes.entrySet()) {
  result *= entry.getKey() * entry.getValue();
}
return result;

こっちの方がぜんぜん見やすいじゃん、という意見はとてもよくわかるけれど、このコードで僕が一番気に食わないのはint resultをfinalにできない事。畳み込みを使うと変数を追い出すことができるのでこっちを使いました。(結局foldLeftメソッド内で同じ事(R r = init がfinalにできない)をしているのではあるけれど、使用側から追い出せるので良しとした)

Fold is like a higher order function. The foldLeft method combine a function and a list. Writing simply the 52 to 55 lines like this. You may think it's better but what I'm annoyed in the simple code is that can't mark "int result" final.

gist → https://gist.github.com/1224843



[ 編集 | 凍結 | 差分 | 添付 | 複製 | 名前変更 | リロード ]   [ 新規 | 一覧 | 単語検索 | 最終更新 | ヘルプ ]
Last-modified: 2011-09-20 (火) 06:47:21 (3561d)