ダイクストラ法（最短経路問題）
ダイクストラ法 (Dijkstra's Algorithm) は最短経路問題を効率的に解くグラフ理論におけるアルゴリズムです。 スタートノードからゴールノードまでの最短距離とその経路を求めることができます。 アルゴリズム 以下のグラフを例にダイクストラのアルゴリズムを解説します。 円がノード，線がエッジで，sがスタートノード，gがゴールノードを表しています。 エッジの近くに書かれている数字はそのエッジを通るのに必要なコスト（たいてい距離または時間）です。 ここではエッジに向きが存在しない（＝どちらからでも通れる）無向グラフだとして扱っていますが， ダイクストラ法の場合はそれほど無向グラフと有向グラフを区別して考える必要はありません。 ダイクストラ法はDP（動的計画法）的なアルゴリズムです。 つまり，「手近で明らかなことから順次確定していき，その確定した情報をもとにさらに遠くまで確定していく
FRPの実装 - osiire’s blog
前にも触れたけど、これ((http://conal.net/papers/simply-reactive/)を元にOCamlでFRP（っぽいもの）が実現できる機能をconcurrent cellに追加した。ほぼできたと思う。あとはテスト（バグがないか、メモリリークはないか、速度はどうか）といったところ。もし興味がある強者がいらっしゃったら、 svn checkout svn://svn.forge.ocamlcore.org/svnroot/ccell からチェックアウトして下さいまし。 とにかく、このFRPの実装は落とし穴が多かった。最初は簡単かもと思って始めたのに、まず論文に書いてあるHaskellの実装をOCamlに直すところで躓き（主に止まらない）、Futureの意味を理解するのに躓き、論文のままだとpull評価の値を評価しないと延々とメモリが食われる問題にどう対処するか悩み（しか
超簡単にオモチャ LWT を実装してみた - camlspotter’s blog
OCaml は現時点でマルチコア対応じゃないので、マルチスレッドにしてもマルチコアの恩恵を享受することができません。ですので、OCaml で thread を使う旨みというのは、関数を並行に走らせる事ができるってことだけです。でも並行に走らせる事が出来ればいろいろ便利ですよね。 でもマルチスレッドプログラミングで一番困るのが排他制御。これを上手くやってやらないと、OCaml で type safe なはずなのに、 segfault という事になります。もちろん OCaml プログラマは普段から type safety に慣れきっているので、 type system で保障されない排他制御を完璧に書けるはずがないのです。心が折れます。 そこで、light weight thread。こいつは実は thread じゃありません。要は同一スレッド内でタスク関数をとっかえひっかえ asynchro
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
サービス終了のお知らせ
