HYLOGICSスマートフォン用の表示で見るHYLOGICS今後は各分室にコンテンツを移して、ここは雑記や暮らしを中心としたライフログ的な何かにしていく予定です。〜CodeIQ解答編〜Perl前回の続きこのエントリは以下のエントリの続きになっています。http://blog.hylogics.com/entry/perl_fibonacci_1http://blog.hylogics.com/entry/perl_fibonacci_1前回のエントリではフィボナッチ数を求めるにあたり以下の問題が発生しました。順当に再帰で数列を書くと計算量が大きくなる(処理が遅くなる)。再帰した内容を配列に入れると処理は早くなるがメモリを逼迫する。今回はこれらを解決したいと思います。CodeIQ挑戦者求む!下3桁のみのフィボナッチ数列から、任意の項を素早く求めてください。アプリケーションエンジニアを募集する企業│CodeIQ与えられた課題は以下の通りです。普通にフィボナッチ数を求めると桁あふれが発生するので、下三桁のフィボナッチ数を求める。与えられたファイルに記載されたリストに沿ってフィボナッチ数を求める。ファイルの1行目は項の数、2行目以降は項のリストとなる。リストの並びはランダムである。それぞれ解法は以下の通りです。1000で余剰を求めて下三桁にする。ファイルのインポート処理とフィボナッチ数を求める処理を実装する。ファイルの1行目は除外して2行目以降をリストに入れる。リストをソートして最大値でフィボナッチ数を求めると計算量が少なくなる。上記を踏まえてコードを書いてみます。再帰を使わずにフィボナッチ数を求める処理を書いてみるとこんな感じでしょうか。0m0.001ssample.out.txtと比較してみます。sample.out.txt$一致しているので問題ないでしょう。解説ポイントは以下の通りです。(あえて)再帰を使わずループで書いたほうが計算量が少ないため早く終わる。リストの並びがランダムなので都度出力せず、一旦ハッシュに入れてからまとめて出力する。再帰が理解できているかの出題だと思っていたのですが、むしろループをべた書きした方が早かったです。再帰処理も一回改修して配列をハッシュにした上で不要になったモノを削除する処理を書いてはみましたが、それも要らなかったですね。遠回りして着地しましたが、徒労感がひしひしと。Linuxの構築時、/etc/yum.confによく書く設定の一つにex...2014-12-10Perlでフィボナッチ数列を求めてみるCodeIQ眺めてたらこんなお題があったのでやってみました。言語...2011-05-07【Linux】dfの出力結果をスクリプトで見やすくカスタマイズ小ネタです。はてなブログProSI系フリーランスやってます。日常で見つけたことや興味あることなど、色々書いてみようと思います。(1)分室TECHLOGICSはてなブログをはじめよう!kirineさんは、はてなブログを使っています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。