週に一回は書きますよ 月に4つ記事を書けばノルマは満たされます。
上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。
フィボナッチ数列は、次の式で定義される数列です。
f(0) = 0
f(1) = 1
f(n+2) = f(n+1) + f(n)
この数列の特定の項、例えばf(55)とかを求めたいとします。

1.定義式をそのまま使う
これはやってはいけないとされています。やってもいいですが時間がかかります。
このアルゴリズムでは、f(55)を求めるのにf(54)を1回、f(53)を2回、f(52)を3回、f(51)を5回...
計算してしまいます。計算時間がf(n)の値そのものと同程度、おおよそO(1.6n)くらいかかります。

2.小さい数から順番に求める。
nの小さいときのf(n)の値を覚えておいて、その値を用いてf(n)の大きい方の値を順次求めていきます。計算時間はO(n)。

3.一般項
この漸化式には一般項が存在します。
α = (sqrt(5)-1)/2
β = -(sqrt(5)+1)/2
f(n) = (αn - βn)/sqrt(5)

これを代入すればすぐに求まります。


教科書には、1より2の方が速いですよ~と書いてあります。
実は3の方がO(1)で求まるので速いのでは。。

私は重要なことを忘れていました。桁数です。
3の一般項にある通り、この数列はべき乗で増えていきます。よって、桁数がO(N)のオーダー、具体的にはNが
log(10)/log(α) ~ 5
増えるごとに一桁増加します。
数が大きくなって、32bitや64bitといったコンピュータに扱いやすい数字を超えると、桁数に応じて計算時間がかかるようになります。

例えば、3をO(N)より速く求めるのには条件が必要です。
I. αnをO(N)より速く求めることができる
II.f(n)のすべての桁を正確に求めることが要求されない。
後者は、f(n)がO(N)桁になるので、すべての桁を表示するだけでO(N)かかるという話です。

しかしよく考えると、手順2すらO(N)の計算時間では計算できないことがわかります。f(n+2)をf(n+1)とf(n)の値から計算する場合、これらの項がO(N)の桁数を持っているので、足し算にO(N)の時間がかかります。よって、手順2の計算時間はO(N2)になります。

どちらが有利なのかわからなくなりました。手順3としても、もし問題がf(N)の値を正確に知りたいのだとすると、一般項から正確な値を出すのにどれだけの時間がかかるのかよくわかりません。

まとめ:
桁数が大きくなると、計算時間に桁数を考慮する必要があります。

感想:
3がO(1)で終わらないことに気づいたのに、同じ理論で2がO(N)で終わらないことには気づかず日記を書き始めました。そのため収拾がつかなくなっています。
スポンサーサイト
週末にStanford大学を見学にいきました。
が、しかし、肝心の

SLAC (Stanford Linear Accelerator Center)

を見に行くことをすっかり忘れていました。友人に見に行くようにいわれたのですが。

SLACとは線形加速器です。詳しくは省略。
迷路を解くアルゴリズムとしてDijkstra法があります。迷路の形と始点を指定すると、始点からほかの各点までの距離を答える、というアルゴリズムです。

これの複数人版を考えます。人がN人いて、それぞれが始点から終点まで動きます。複数人いるので、特定の道は同時には通れないとか何人までしか通れないとかしましょう。この条件で、人の合計移動距離を最小化してください、というのが問題です。

この問題は最小コストフローに帰着できます。わき出し点から始点に容量N、コスト負の大きい値となる道を引き、各道の距離をコストに割り当てればよい、という感じです。
ただし、それぞれの人がそれぞれ別々の始点から別々の終点に向かう場合はこれだけではうまくいきません。そのままだと、ある二人が終点を交換してしまった場合も解として認めてしまいます。

ところで、ダイクストラ法は、それぞれの道の距離が1で固定されている単純な幅優先探索による最短距離判定の拡張とみることができます。すると、道の距離が固定されている簡単な問題を人が複数人いるように改造したら、これは最小コストフローよりもう少し簡単な問題に帰着できるのでしょうか。

幅優先探索からダイクストラ法への展開がコスト1からコスト可変だったので、類推で最小コストフローから最大フローとかに変わるのでしょうか。
この類推はしかし、私には到底発展させられませんでした。最大フローはそもそもコストとかを全く考慮しないので、最大でどのくらい流れるかしかわかりません。一方元の問題は幅優先にしてもコストを常に意識し、最小コストを答えさせます。全く変換可能に見えません。
「N人を始点から終点まで運ぶことが可能でしょうか」、という問題にすれば最大フローに変換可能です。でもこの問題はそもそも最大フローです。やはり最短距離を求めないともとの問題とは似ても似つかなくなる気がします。
マイクロソフトは死んだに関連して
"considered harmful is considered harmful"なんてネタがあったのを思い出しました
"is dead is dead"これはすでに先人がいるのですが

"is dead is considered harmful"
"considered harmful is dead"
この辺はいるのでしょうか。
とくに"is dead is considered harmful"なんてのは考えている人がいるのではないかと思います。安易に死亡宣告を出さない方がいい、と。
週末なのでせんたっき(<-なぜか変換できない)と乾燥機をまわしています。

。。。
乾燥機ってあんまり乾燥できないんでしょうか。
うっすら湿っているんですが。
それとも乾燥機でからからにしてしまうと問題が多いので、ほぼ乾かした状態で干すと最適なのでしょうか。

コマンド
  1. どこかに部屋干し
  2. もう一度乾燥機にかけてみる

下のコマンドが自爆コマンドにしか見えません。
という訳で部屋干し。

雨が降っているのに週末だからってせんたっきを動かしてしまったのがそもそもの間違いなのでしょうか。

id:flatline氏の所にLabviewの話が。 せっかくなので、少し昔話をしてみましょう。

Labviewは計測器を操作するGUIがものすごくすぐに作れるのがよいところですね。 それから、一定の規模ならデータのvisualizeにも使えました。 データをテーブルで読み込んで、パラメータをスライダーで変化させつつグラフがどう変わるか見るみたいなことが簡単に。

バージョン5.1くらいのころは配列の実装に欠点がありました。 大きなデータを扱ったり、配列の確保と廃棄を頻繁にしたりすると遅くなるのです。 特定の値を持った配列を生成するのに、ループで値を決めつつ生成するよりも はじめにサイズを決めた配列を生成してその各要素に書き込みをしたほうが速いと いったバッドノウハウもありました。 今はもう大丈夫かもしれません。

プログラミング言語としてみると中途半端です。 データフロー形式で、普通に書くと関数型プログラミングをしている気分になりますが、 実は再帰できなかったり(V5.1の場合)、 GUIプログラミングのため途中に処理を追加しようとすると配線がスパゲッティになったりするのが がっかりです。

それから、関数型プログラミングの癖に、変数を共有して遠くから書き換えるとかいった汚い書き方ができます。 私は全然使いませんでしたが、これを使ってくれると配線のタイミングの問題が出てきたりして大変なことになります。 素人がスパゲッティを書きやすいプログラムであります。 素人の不思議なプログラムを読まないといけないとかそういう問題です。 この問題はVBなどにも通じるのでしょうか。 よくわかりません。

結論としては適材適所ですね。プログラム言語ではなくGUI作成/装置制御ソフトであると見ると精神的に安定します。

卒業の後は次のコンボがありまして
  • 世界樹の引きこもり
  • 学会口頭発表
  • 社会人
ちょっと日記パスとか思っていたら気がついたらこんな時期になっておりました。

そのままNDA式に日記更新頻度を下げてもよいかと思い放置していました。

しかし、筆不精というものは意外に厳しいです。

私の素の状態だと普通のコメントすらかけなくなってしまうくらい文章がかけなくなります。 これはいろいろとまずい。 本当は日記を書いていないせいではないかもしれませんが。

日常生活でもネタの切れが著しく悪くなった気がするので、ちょくちょく日記は書くことにします。

上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。