動的計画法を試してみた

動的計画法とは、再帰的なロジックを、計算結果を都度記録するロジックで代替することで、計算速度を向上させるテクニックです。
競技プログラミングのテクニックの一つなのですが、高度なアルゴリズムを実装する開発だけではなく普通の業務システム開発にも応用できそうなので、紹介します。

今回は、フィボナッチ数列の計算を例に挙げます。
再帰的に処理した場合、数列が1つ増える度に呼び出し量が2倍になるため、オーダはO^2となります。また、再帰的に関数を呼び出すとその分メモリ(スタック)を消費するため、異常終了するリスクも高くなります。
しかし、動的計画法を用いた場合は、数列が1つ増えても計算が1回増えるだけなので、オーダはOとなります。
実際に45項目を計算した結果、再帰呼び出しでは約11000ミリ秒を要しましたが、動的計画法の場合は1ミリ秒未満でした。

【スペック・動作環境】

・OS:Windows8.1 64bit
・CPU:Inter(R) Core(TM) i5-4210U CPU @ 1.70GHz 2.40GHz
・メモリ:8.00GB
・ディスク:SSD 128GB
・言語:java8
・IDE:Eclipse Oxygen

【確認用プログラム】

【実行結果】


いかがでしたでしょうか。

業務システム開発に携わっている身としては競技プログラミングは少し縁遠い存在なのですが、再帰呼び出しは業務システム開発でも使うことがあります。
(直近ではGUIの開発で使いましたし、現在趣味で作っているプログラムでも再帰呼び出しの箇所が存在します)
再帰呼び出しを使用するとどうしても重くなったり異常終了したりすることがあるので、そのような場合に動的計画法の使用を検討できると実装の幅が広がると思いました。

続・singletonとstaticの違い

こちらの記事について社内外でちょっとした議論になったので、その内容をまとめてみました。
Singletonパターンを利用する理由は「外部からnewさせたくないから」だと思っていましたが、「そう書いた方がわかりやすいから」「staticではないメソッドも利用可能になるから」という理由の方が大きそうです。

【指摘】

・privateコンストラクタを持った時点でnewできない

newさせたくないだけなら、オブジェクト取得メソッドは不要。
Singletonパターンで無くても良い。

・Singletonパターンの思想の表現としてオブジェクト取得メソッドが必要

書籍ではSingletonパターンはオブジェクト取得メソッドが必要とされている。
確かに、privateでオブジェクトを1つ生成、外部にはメソッド経由で提供する、とすれば、「オブジェクトは1つのみ存在する」という思想をわかりやすく表現できる。
人によってstaticの方が分かりやすいかSingletonパターンの方が分かりやすいかは違うと思うが、オブジェクト指向に慣れた技術者であればSingletonパターンの方が設計思想が分かりやすいというのはありそう。

・Singletonパターンだとstaticではないメソッドも参照可能になる

Singletonパターンであればクラスへの参照ではなくオブジェクトへの参照となる。
そのため、staticではないメソッドの参照も可能となる。
具体的には、継承・オーバーライドができるというメリットがある。

【サンプルコード】

・StaticMemory.java

・SingletonMemory.java

・SingletonMemoryChild.java

・MemoryTestMain.java

【実行結果】


この話、社内でちょっとした議論になりました。
おかげで色々理解が深まりました。

議論のきっかけを作れるというのも、技術ブログの良い所だと思いました。

java:実務で使うテクニックでfizzbuzzを解いてみた

10年ほど前に流行ったプログラミングの問題として、fizzbuzzと呼ばれる問題があります。
この問題は、応募者のプログラミング経験の有無を見極める問題であり、問題の内容は以下の通りです。
・1から100までの数を出力する。
・3の倍数の時は代わりに”fizz”と出力する。
・5の倍数の時は代わりに”buzz”と出力する。
・3の倍数かつ5の倍数の時は代わりに”fizzbuzz”と出力する。

「実務ではfizzbuzzのようなプログラムを書くことは無いから解けなくても良い」という意見もあるようですが、個人的にはfizzbuzzで使うテクニックは実務でも使えると思っています。

以下では、実務でも使うテクニックを用いてfizzbuzzを解いてみます。
(言語はjavaです。今回の記事の趣旨上、トリッキーな解答は除外します。)

・剰余を用いた一般的な解答パターン

恐らく、これが一番自然な解答なのではないかと思います。
剰余を用いて、「n % m == 0」と記述することで、「m毎に何かをする」という記述が可能になります。
性能の観点で、一定のデータが溜まってからまとめてログ出力やデータベース書き込みを行うことがあるのですが、そのような処理を記述する時に使えます。
その他、テストデータを生成する時にも、この書き方を用いると楽になる場合があります。
(例えば、100個データを用意し、その内偶数のデータについては特定のフラグが立ったデータにする等)

・同じ分岐の記述を避けるパターン

先に挙げた解答では「3の倍数の時」「5の倍数の時」の分岐が2回ずつ出現し、若干冗長なので、このように同じ分岐の記述を避ける解答もあります。
同じ分岐を複数記述すると、保守性が低下します。
(例えば、「3の倍数」を「4の倍数」としたい時に、修正漏れが発生する可能性が出てくる)
プログラマーは保守性にも気を配るべきなので、個人的にはこちらの解答の方がよりプログラマーっぽいと思っています。

・除算と乗算を組み合わせるパターン

剰余を使わずとも、整数型は小数点以下切り捨てになるということを知っていれば、このような解答を記述することもできます。
除算で小数点以下の切り捨てが発生する場合、同じ数で乗算を行っても元の数に戻らないので、それを利用しています。
除算による切り捨てを実務で用いる場合もあり、例えば100未満の位を切り捨てしたい場合は、「n = n / 100 * 100」と記述したりします。逆に切り上げたい場合は、「n = (n + 99) / 100 * 100」となります。
現代のプログラミング言語では切り捨てや切り上げを行う便利な関数が用意されているのでこのような書き方をすることは少ないですが、このような書き方を知らないと他の人のプログラムを読んでいて困ることがあるので、知っておいた方が無難です。

・カウンターを持たせるパターン

fizz用のカウンターとbuzz用のカウンターを持たせて、カウンターを上手く制御すると、剰余や切り捨てを利用しなくても解答を記述できます。
実務では、カウンターの数字自体に意味がある場合にこのような書き方をします。
例えば、「ログ1→ログ2→ログ3→ログ1…とローテーションさせたい」という場合に、「ログ1」「ログ2」「ログ3」の数字部分にカウンターの値をそのまま用いることができます。


いかがでしたでしょうか。

今回紹介した問題は難しくないものですが、その解き方で個性やテクニックを発揮することができそうなので、今回は色々と解答を紹介してみました。
実務で役に立つ問題があれば、これからも紹介していきたいと思います!

型推論とは

型推論とは、メソッド内のローカル変数を初期値付きで(右辺がある状態で)宣言する際に、通常の型宣言の代わりに”var”という仮の型を使用できるという文法です。
“var”を用いた際は、コンパイル時に自動で型を判断し、その型への置き換えが行われます。

C#では3.0(2007/11)から導入されており、現在ではお馴染みの文法と言えるでしょう。
Javaでは長らく導入されていませんでしたが、10(2018/03)でついに導入されました。
今後はJavaの案件でも目にすることが増えると思います。

型推論を用いることで、冗長な型宣言をすっきりさせることができます。
C#の例で言うと、下記のコードで、定義時に”List”と型を指定している箇所は、”var”に書き変えることができます。

また、ソース修正で型を変えるような場合にも、”var”と記述した部分は変更する必要がなくなるので、ソース修正が楽になるというメリットもあります。


型はコンパイル時に決まるため、実行時に動的に型が変わることはありません。
例えば、下記のようなコードはコンパイルエラーになります。
((22,20): error CS0029: 型 ‘int’ を型 ‘System.Collections.Generic.List’ に暗黙的に変換できません。)
誤って意図しない型を代入しようとした場合はコンパイル時にエラーとして検知できるので、その意味では安心して使えます。

ちなみに、「型推論」と似た概念として「動的型付け」というものがあるのですが、こちらは途中で異なる型を代入すると変数の型そのものが変わり処理が続行されます。
例えば、JavaScriptでは動的型付けが採用されており、予約語も”var”を用いるため、「型推論」と混同されがちです。
「動的型付け」の方は誤って意図しない型を代入しても実行するまで気付くことができず、実行時に出るエラーが分かりにくいものだったり、そもそもエラーが出ないこともあるので、注意が必要です。


以上のように便利な型推論ですが、可読性を落とすデメリットもあります。
具体的に言うと、変数宣言時の型が一目瞭然ではない場合に用いると可読性を落とします。

例えば、下記のコードで変数宣言時の型を知るためには、”MyFunc”の仕様を知っている必要があります。
“MyFunc”のような独自の関数でなくても、チーム内での知名度が低い関数を用いる場合は注意が必要です。

また、”int”や”string”のような基本的な型に対して用いるのも、元々型宣言が冗長ではないという意味で型推論を使用するメリットが少ないので、他の開発者に違和感を抱かせてしまう可能性があります。


いかがでしたでしょうか?

「型推論」は便利ながらも、「動的型付け」のように実行時エラーを引き起こす原因を作ることはないので、安心して使える文法だと思います。
その使いやすさからJavaでも今後目にする機会が増えると思うので、このような文法があるということは頭に入れておいて損はないと思います。

Javaのバージョンは今でも上がり続けているので、新しい便利な文法があればこれからも紹介したいと思います!

スタック・キューの説明と使い所

データをメモリに一時的に保持する仕組みとして、スタックとキューがあります。
今回はスタックとキューについて、どのようなものなのかの説明と使い所を書いていきます。


スタックは先入れ後出し、キューは先入れ先出し方式でデータを保持します。
例えば、a,b,cの順番でデータを投入する場合、スタックはc,b,a、キューはa,b,cの順番でデータが取りだされます。
なお、スタックにデータを入れる操作はプッシュ、スタックからデータを取り出す操作はポップ、キューにデータを入れる操作はエンキュー、キューからデータを取り出す操作はデキューと呼びます。
以下、イメージ図です。

・スタック

・キュー


スタックが使われる代表的な場面としては、関数呼び出し時に戻り先を保持する場面が挙げられます。
例えば、以下のような構造になっている場合

関数g()が呼び出された時点でスタックに①のアドレス、関数h()が呼び出された時点でスタックに②のアドレスが戻り先として保持されます。
そして、関数h()が終了した時点でスタックから戻り先として②のアドレスが取り出され、関数g()が終了した時点でスタックから戻り先として①のアドレスが取り出されます。

余談ですが、以下のように再帰呼び出しになっている時は注意が必要です。
ループ終了条件を満たさないまま大量の再帰呼び出しを行った場合、戻り先アドレスのサイズがスタックのサイズを超えてしまい、プログラムが異常終了してしまいます。


キューが使われる代表的な場面としては、マルチスレッドの制御を行う場面が挙げられます。
1つのスレッドの処理が「①軽い処理→②重い処理」となっており、かつ①の処理を先に行ったスレッドが②の処理を先に行う必要がある場合、①と②の間にキューを入れて対応します。
①の処理は処理が終わるごとにキューの中にスレッドのオブジェクトを格納し、②の処理は処理が終わる毎にキューの中のスレッドのオブジェクトを取り出し次の処理に移ることで、①の処理と②の処理の速度差を吸収することができます。


いかがでしたでしょうか?

スタックやキューはITパスポートにも出題される基礎的な概念ですが、実際にプログラミングで意識する場面は少ないと思います。
今回の記事では、実際のプログラミングではどのような場面で意識するのかも参考のため書いてみました。