Haskell2011年7月5日火曜日Haskellで有名アルゴリズム実装(4)第4弾。今日は、素数列挙のアルゴリズム。ある数が素数かどうかの判定は、擬多項式時間でできます。n]内の素数を列挙するには、普通にやるとO(n*sqrt(n))かかります。エラトステネスの篩というアルゴリズムを使用すると、O(n)で計算できます。Haskellのエラトステネスは美しいです。0]これで十分な場合がほとんどですが、100万までの素数列挙とかすると、上の実装ではたえられません。3*p,..とpおきに消していけるからで、上の方法だとすべての要素をなめているので遅いです。加えてリストは参照にO(n)かかるので遅いです。ある素数に対して必要な要素だけ参照する+高速に参照することができるデータ構造に変換する。100万くらいの素数列挙なら、Setを使えば十分でしょう。あとは、thunkがメモリを圧迫するのを防ぐ+遅延評価によるスタックオーバーを防ぐため正格評価を用います。10000000]など)の素数列挙をしたい場合は、工夫が必要です。遅延評価の機構をいれないようにするで達成できるかと思います。Haskellのページに戻る。アルゴリズム2011年7月3日日曜日Haskellでメモ化する(中級)前回のpostで、Haskellでメモ化する方法について書きました。そのとき、疑問点として、「なんで、メモ化と不動点が繋がってるねん!なんでやねん!」というのがありました。その疑問が解決したので中級編を書きます。不動点コンビネータを利用してやりたいことは、「任意の関数が与えられたときに、その計算をメモ化する関数を作成する」ということのようです。この発想にはびっくりです。どれだけ抽象度の高いことをやるんだよ。imparative、あんど、object-orientedな思想に育てられた(毒された?)普通のプログラマーである私には思いもよらない発想でした。メモ化と、不動点コンビネータについて少しおさらいをします。フィボナッチ数列をメモ化再帰で解くプログラムを書いてみます。!!)これは、list-comprehensionを用いて以下のように書くこともできます。(n-2)と、とりあえず、関数がgivenであれば、その関数をメモ化してあげることは出来ます。次に、不動点コンビネータについて。Haskellでは、Control.Monad.Fixに不動点コンビネータが定義されています。これを使ってもいいですが、勉強のために自分で実装してみます。再帰関数を不動点コンビネータに書きかえる方法についてはここのページがとても分かりやすいです。フィボナッチ関数を不動点コンビネータで書きなおします。(x-2))と書けます。(x-2))の不動点となっています。(x-2))と書けるというわけです。(詳しくは上のお勧めページ参照。)と、準備はここまで。Int)型の任意の関数をメモ化することにします。引数にそのままメモ化したい再帰関数を渡してしまうと意味がない(メモ化機構を入れられない)ので、メモ化したい関数を不動点にとるような関数を引数として渡してあげます。f)とすると、fを渡すという意味です。ここまで来ると、なんとなくできそうな感じがします。なんとなく実装したのが、これ。!!)計算自体は正しいですが、メモ化が機能していないようです。前にも書きましたが、Haskellの場合、グラフ簡約のメモ化(ここでいうメモ化は、グラフ簡約されて同じ計算がされないという意味のメモ化)が働く場合と働かない場合があります。この形は前に見たことがあります。引数をやめて実体を無限リストとして定義してあげればグラフ簡約が働くはず。!!)これで、「与えられた関数をメモ化関数に変換する関数」が出来ました。実際に確かめてみます。300値も正しく、高速化もされていることが確認できました。高速化については、無限平衡二分木を用いた方法が紹介されています。Stateモナドを用いた方法があるようです。他にもData.ArrayのArrayが使えるんじゃないかなあ、とにらんでいます。この辺が出来たら、上級編を書きたいです。Postsmemset()とmemcpy()恥ずかしながら、Cのmemset()とmemcpy()を今まで使ったことがなかった。みたいな話を聞いたことがあったので、「あーじゃ要らない機能なんだー。editorialに投稿された解答がmems...便利なPythonライブラリ(5)retryデコレータつけるだけで、リトライしてくれるという便利ライブラリ。失敗するかもしれない不安定な関数に@retryをつけると成功するまで実行してくれる。ret...S3のファイルを一般公開するAWSのS3のファイルを一般公開する方法について説明します。2つの場合に分けて説明します。本番中ゴリ押し解を思いつくには思いついたのだが、C++でマルチスレッドの処理を書いたことが無くて、ごにょごにょやってるうちにタイムアップとなってしまった。C++...C#入門(9)Action、Func、Predicateの違いAction、Func、Predicateについて簡単に整理しておく。メソッドへのDelegate。メソッドへのDelegate。スライド区間に対するクエリ処理の種類とそれに対するアルゴリズムをいくつか紹介します。「スライド区間」の定義ですが、窓関数のようなものを想像してください。まではコンピュータの力を使って正多面体をt色以下で塗るパターン数を数えていました。今回は手計算で計算してみようと思います。そのためにはまず回転を表す対称群をうまく列挙するために回転軸について考える必要があります。見聞きする木の用語を整理しておく。節点vから最も離れた節点をwとする。w)の長さをvの離心数と呼ぶ。記号で表すときは、ε(v)と書く。使って遊んでみました。いった便利な機能を提供してくれるテストフレームワークです。repor...キャッシュヒット率の測定perfというツールを使ってキャッシュヒット率を測定してみた。キャッシュの影響なんてたかが知れていると甘くみていたら、痛い目るので要注意。知らない用語がちらほらあったので、簡単にまとめておく。