Javaで階乗を書かない方法

この記事の翻訳はかつてハブで公開されましたが、何らかの理由で最も重要な部分が舞台裏に残っていました。 以下は完全な翻訳です。



この記事は、「 Javaで階乗をどのように記述しますか？ 」という記事に触発されました。 申し訳ありませんが、コードで少しお話しします。主なアイデアがあり、最後にそれを表現します。



Javaで階乗を書く必要がある場合、ほとんどの人はおそらく何かで始めるでしょう など：

public static int factorial(int n) { if (n == 0) return 1; return n * factorial(n-1); }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

これをクラスでラップしてみましょう（Javaについてはまだ話している）。おそらく、それは何らかの補助（* Util）クラスになります。たとえば：

 public class FactorialUtil { public static int factorial(int n) { if (n == 0) return 1; return n * factorial(n-1); } }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

簡単ですね。



非再帰的なソリューションもあります。

 public class FactorialUtil { public static int factorial(int n) { int ret = 1; for (int i = 1; i <= n; ++i) ret *= i; return ret; } }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

注意深い読者は、結果が最大許容整数（整数型）よりも大きくなる可能性があることに気付くでしょう。おそらく、プログラムの要件に応じて、BigIntegerまたは少なくともlongを使用するように関数を書き換えたいと思うでしょう。 だから

 public class FactorialUtil { public static BigInteger factorial(int n) { BigInteger ret = BigInteger.ONE; for (int i = 1; i <= n; ++i) ret = ret.multiply(BigInteger.valueOf(i)); return ret; } }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

これまでのところ、1からnまでの同じ中間値を常に計算しているという事実を使用していないことに注意してください。 もちろん、これらの値をキャッシュすると、計算がずっと速くなる可能性があります。 一度計算した値は、たとえばHashMapで将来使用するために保存します。

 public class FactorialUtil { static HashMap<Integer,BigInteger> cache = new HashMap<Integer,BigInteger>(); public static BigInteger factorial(int n) { BigInteger ret; if (n == 0) return BigInteger.ONE; if (null != (ret = cache.get(n))) return ret; ret = BigInteger.valueOf(n).multiply(factorial(n-1)); cache.put(n, ret); return ret; } }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

簡単ですよね？

これらのメソッドにはそれぞれ長所と短所があります。したがって、このライブラリが将来複数回役立つ可能性が高いことを考えると、Javaライブラリで一般的な標準メカニズムを使用する価値があります。 実行時に使用するアルゴリズムを決定できるプラガブルモジュールシステムについて説明しています。低速でメモリ消費量が少ない、または高速でメモリ消費量が多いアルゴリズムです。 まず、プラグインギズモには初期化されたクラスとデフォルトの実装を返すsigltonが必要なので、Singletonでクラスを作り直す必要があります。



そのため、ファクトリのシングルトンをサポートすることを目的とするクラス（ファクトリクラス）を作成し、メソッドを実装するアルゴリズムにリンクします。 このクラスは、上に示した古いインターフェイスを提供し、新しい改良されたアルゴリズムを使用することもできます。

 public class FactorialUtil { private static FactorialUtil singleton; private FactorialAlgorithm algorithm; /** * Default (internal) constructor constructs our default algorithm. */ private FactorialUtil() { algorithm = new CachedFactorialImplementation(); } /** * New initializer which allows selection of the algorithm mechanism * @param algorithm */ public FactorialUtil(FactorialAlgorithm a) { algorithm = a; } /** * Default public interface for handling our factorial algorithm. Uses * the old standard established earlier for calling into our utility class. * @param n * @return */ public static BigInteger factorial(int n) { if (singleton == null) { // Use default constructor which uses default algorithm singleton = new FactorialUtil(); } return singleton.doFactorial(n); } /** * New mechanism which allows us to instantiate individual factorial * utilitiy classes and invoke customized factorial algorithms directory. * @param n * @return */ private BigInteger doFactorial(int n) { // Defer to our algorithm return algorithm.factorial(n); } }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

上記のクラスは、シングルトンを作成し、アルゴリズムクラスに制御を渡すことに注意してください。 さらに、アルゴリズムクラスを初期化するプライベートコンストラクター、および別のアルゴリズムを作成して使用する機能も備えています。



これは、アルゴリズムインターフェイスに依存します。

 public interface FactorialAlgorithm { BigInteger factorial(int n); }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

そして、前述の中間結果キャッシュを使用した実装は次のとおりです。

 public class CachedFactorialImplementation implements FactorialAlgorithm { static HashMap<Integer,BigInteger> cache = new HashMap<Integer,BigInteger>(); @Override public BigInteger factorial(int n) { BigInteger ret; if (n == 0) return BigInteger.ONE; if (null != (ret = cache.get(n))) return ret; ret = BigInteger.valueOf(n).multiply(factorial(n-1)); cache.put(n, ret); return ret; } }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

この構造の美しさをご覧ください！ つまり、非キャッシュの非再帰的な実装を簡単に追加できます。

 public class LoopedFactorialImplementation implements FactorialAlgorithm { @Override public BigInteger factorial(int n) { BigInteger ret = BigInteger.ONE; for (int i = 1; i <= n; ++i) ret = ret.multiply(BigInteger.valueOf(i)); return ret; } }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

Javaの観点から見ると、この設計の欠点は明らかです。実行時にアルゴリズムを選択することはできません。これはもともと私たちの主なアイデアでした。 つまり、明らかに、構成をロードし、それに応じてアルゴリズムを選択する必要があります。 たとえば、アルゴリズムを実装するクラスの名前を含むSystemプロパティを読み取ることができます。 理想的には、メインメソッドは次のようになります。

  public static void main(String[] args) { System.getProperties().setProperty("com.chaosinmotion.factorialalgorithm", "cachedAlgorithm"); System.out.println("5! = " + FactorialUtil.factorial(5)); }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

つまり、既存の実装をすべて含む連想配列が必要です。 それから、ファクトリメソッド内でシングルトンを作成する前に、目的のアルゴリズムを使用できます。



そのため、アルゴリズムを生成できるファクトリが必要です。 classMappingには、作成されたシングルトンファクトリの配列と、クラス名と実装マッピングの配列の両方を格納します。 したがって、アルゴリズムクラスのオブジェクトは、本当に必要になるまで作成しません（不要なコンストラクターを呼び出して、リソースを無駄に無駄にすることはありません）。

 /** * Factory class manages the factorial algorithms in our system. * @author wwoody * */ public class FactorialAlgorithmFactory { private static HashMap<String,FactorialAlgorithm> mapping = new HashMap<String,FactorialAlgorithm>(); private static HashMap<String,Class<? extends FactorialAlgorithm>> classMapping = new HashMap<String,Class<? extends FactorialAlgorithm>>(); private static FactorialAlgorithm defaultAlgorithm = new CachedFactorialImplementation(); /** Static initializer registers some of my known classes */ static { try { Class.forName("com.chaosinmotion.factorial.LoopedFactorialImplementation"); Class.forName("com.chaosinmotion.factorial.CachedFactorialImplementation"); } catch (ClassNotFoundException e) { // Should never happen. } } /** Get the default algorithm for computing factorials */ public static FactorialAlgorithm getDefaultAlgorithm() { if (defaultAlgorithm == null) { // Warning: this will fail if for whatever reason CachedFactorialImplementation // is not in the class path. defaultAlgorithm = getAlgorithm("cachedAlgorithm"); } return defaultAlgorithm; } /** Get the factorial algorithm specified by name */ public static FactorialAlgorithm getAlgorithm(String name) { FactorialAlgorithm f = mapping.get(name); if (f == null) { // We haven't created an instance yet. Get it from the class mapping. Class<? extends FactorialAlgorithm> c = classMapping.get(name); if (c != null) { // Create a new instance of the factorial algorithm specified try { f = c.newInstance(); mapping.put(name, f); return f; } catch (Exception e) { // Log the error Logger.getLogger("com.chaosinmotion.factorial"). warning("Unable to instantiate algorithm " + c.getCanonicalName() + ", named " + name); } } return getDefaultAlgorithm(); // return something. } else return f; } /** Register the class so we can construct a new instance if not already initialized */ public static void registerAlgorithm(String name, Class<? extends FactorialAlgorithm> f) { classMapping.put(name, f); } }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

FactorialUtilクラスを書き換えて、名前付きアルゴリズムを使用するようにします。

 public class FactorialUtil { private static FactorialUtil singleton; private FactorialAlgorithm algorithm; /** * Default (internal) constructor constructs our default algorithm. */ private FactorialUtil() { String name = System.getProperty("com.chaosinmotion.factorialalgorithm", "cachedAlgorithm"); if (name == null) { algorithm = FactorialAlgorithmFactory.getDefaultAlgorithm(); } else { algorithm = FactorialAlgorithmFactory.getAlgorithm(name); } } /** * New initializer which allows selection of the algorithm mechanism * @param algorithm */ public FactorialUtil(FactorialAlgorithm a) { algorithm = a; } /** * Utility to create by name. Calls into FactorialAlgorithmFactory to * actually get the algorithm. * @param name */ public FactorialUtil(String name) { algorithm = FactorialAlgorithmFactory.getAlgorithm(name); } /** * Default public interface for handling our factorial algorithm. Uses * the old standard established earlier for calling into our utility class. * @param n * @return */ public static BigInteger factorial(int n) { if (singleton == null) { // Use default constructor which uses default algorithm singleton = new FactorialUtil(); } return singleton.doFactorial(n); } /** * New mechanism which allows us to instantiate individual factorial * utilitiy classes and invoke customized factorial algorithms directory. * @param n * @return */ private BigInteger doFactorial(int n) { // Defer to our algorithm return algorithm.factorial(n); } }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

ファクトリに登録するCachedFactorialImplementationクラスとLoopedFactorialImplementationクラスに静的クラス初期化子を追加する必要もあります。

 public class CachedFactorialImplementation implements FactorialAlgorithm { static HashMap<Integer,BigInteger> cache = new HashMap<Integer,BigInteger>(); static { FactorialAlgorithmFactory.registerAlgorithm("cachedAlgorithm", CachedFactorialImplementation.class); } @Override public BigInteger factorial(int n) { BigInteger ret; if (null != (ret = cache.get(n))) return ret; ret = BigInteger.valueOf(n).multiply(factorial(n-1)); cache.put(n, ret); return ret; } }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

そして

 public class LoopedFactorialImplementation implements FactorialAlgorithm { static { FactorialAlgorithmFactory.registerAlgorithm("loopedAlgorithm", LoopedFactorialImplementation.class); } @Override public BigInteger factorial(int n) { BigInteger ret = BigInteger.ONE; for (int i = 1; i <= n; ++i) ret = ret.multiply(BigInteger.valueOf(i)); return ret; } }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

このアーキテクチャの最大の利点は、独自の要因実装をその場でFactorialUtilに接続できることです。 これを行うには、FactialAlgorithmインターフェイスを実装する独自のクラスを作成し、静的初期化ブロックのFactorialAlgorithmFactoryを介して登録します。

 public class RecursiveFactorialImplementation implements FactorialAlgorithm { static { FactorialAlgorithmFactory.registerAlgorithm("recursiveAlgorithm", RecursiveFactorialImplementation.class); } @Override public BigInteger factorial(int n) { if (n == 0) return BigInteger.ONE; return BigInteger.valueOf(n).multiply(factorial(n-1)); } }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

最後に、mainメソッドで、クラスがロードされていることを確認し、システムプロパティを設定します。

  public static void main(String[] args) { try { Class.forName("com.chaosinmotion.factorial.RecursiveFactorialImplementation"); } catch (ClassNotFoundException e) { // if this fails, no matter; we'll still use the default implementation. } System.getProperties().setProperty("com.chaosinmotion.factorialalgorithm", "recursiveAlgorithm"); System.out.println("5! = " + FactorialUtil.factorial(5)); }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

問題ありません！ さらに、このアーキテクチャにより、 これらのような、より洗練されたソリューションを接続できます。











この場所にたどり着いた多くのJavaプログラマーは、頭をうなずかせ、このアーキテクチャの優雅さに感心していると確信しています。 既に「コメントを残す」ボタンを押して「次のように書いてください」と言っている人もいます。 たとえば、さまざまなクラスの初期化子を、プロパティ（* .properties）を持つファイルまたはXMLファイルに配置できます。 または、システムプロパティの値がクラスの完全な名前である方が良いかもしれません。



そしてもちろん、ノートブックにずっとメモを書き、すでにこのブログからコードの一部をコピーしている人もいます（はい、このコードはすべて動作しています。私は自分のマシンでテストしました）。



でもね、ついに私の要点です。



これはすべてがらくたです。



すべての行。



確かに、状況によっては、プラグインアーキテクチャが有用であり、必要な場合もあります。 しかし、これは非常にまれです-とてもまれなので、面白くありません。 99％のケースで、そのようなコードを見たとき、それは完全にそして完全に役に立たなかった。 それはコードの本当の目的を隠し、Javaの2行3行のヘルパーメソッドを数十行から数百行の独善的なでたらめなでたらめに置き換えます。 気分が良くなるかもしれませんが、ペストのように、将来の開発者がクリーンアップするか、ほとんどの場合避けなければならないい混乱を生み出します。



そして最も興味深いのは、何か気づいたことはありますか？ この議論を通して、何かに気づきましたか？



負の数を処理したことはありません。











賢いJava開発者は、いつ停止すべきかを知っています。 人生は雲の中に城を建てるには短すぎます。 彼は、ループを使用した単純なソリューションで十分であることを知っており、もちろん、負の数を処理します。 （まあ、ご存知ですか？入力で負の数を指定すると、再帰的な解決策は無限ループに入ります。）



本当に賢いJava開発者は、問題をさらに深く掘り下げ、階乗がガンマ関数の特殊なケースであることを知ることができます 。 おそらく、正しい解は上記のコードの一部ではなく、ガンマ関数のスターリング近似です。

 static double Gamma(double z) { double tmp1 = Math.sqrt(2*Math.PI/z); double tmp2 = z + 1.0/(12 * z - 1.0/(10*z)); tmp2 = Math.pow(z/Math.E, z); // ooops; thanks hj tmp2 = Math.pow(tmp2/Math.E, z); return tmp1 * tmp2; }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

しかし、これはすでに問題領域に依存しています-実際には考えもしていなかったので、すべての工場を作りました。











Java開発者に対する私の最大の不満は、彼らが本当に悪い習慣をたくさん開発していることです。 仕様は不明です。 彼らはいつかコードを異なる方向に拡張する必要があると考えています。 したがって、彼らは肥大化した建築のナンセンスの束を書いて、いつかこの余分なゴミが突然彼らを助けて人生を楽にすると信じています。 また、言語としてのJavaを使用すると、これを迅速かつ便利に行うことができるため、将来のいつか私たちの生活を簡素化するアーキテクチャを簡単に構築できます。



しかし、未来は決して楽になりませんよね？



1年後、彼らは問題の領域を理解したと思った時点で書かれたこの余分な荷物をすべて引き裂いていたので（単純なコードのように、最初のように）要因の例）、彼らは必要に応じて再考することができたが、誰も理解できない山積みのナンセンスの束に対処せざるを得ない。



そして、このヒープを介して結び目を解くか、少なくともこのメカニズムがどのように機能するかを理解するのではなく、溶岩流の古典的な例のように、単にアーキテクチャにパッチを平手打ちします。 たとえば、プラグインアルゴリズムの作成方法がわからないため、FactoryUtilクラスを再定義するか、FactoryUtilクラスを再作成して、そこにさらに100つか2つの（誤解された）コードを追加します。 ）コード。











ですから、「いつか便利になる」、「システムがまだ十分に柔軟性がない」、「コードに再利用可能性がある」、または（神！）「クールだから」-早く家に帰ってください。 漫画を見る。 または、「 開始 」をレンタルします。



正当な理由がないのに、余分な作業を作成するのを止めてください。