Erlangでフィボナッチ数列求めるやつを書いてみた。
1週間ぶりくらいの更新になります。
Orisanoです。最近Erlangと戦っています。
Sortを書いてみたの方はちょっと時間かかっちゃって更新できないので、
何気なく書いたフィボナッチ数列を求める記事で間を持たせたいと思います。
fib(0) -> 0; fib(1) -> 1; fib(N) -> fib(N - 1) + fib(N - 2).
とまあ最初こういう実装をしたらfib(100)ですらまともに帰ってこない。。。。(悲しみ
ま、当然ですよね。O(2^n)くらいになるのかな・・・自信ない。
追記:
ついでに、末尾最適化したコードも書きました
tailfib(0) -> 0; tailfib(1) -> 1; tailfib(N) -> tailfib(N, 0, 1). tailfib(2, P2, P1) -> P2 + P1; tailfib(N, P2, P1) -> tailfib(N - 1, P1, P2 + P1).
追記終了
なんかこのままじゃ悔しかったので
いろんなサイトを参考にしつつ、
logfib(0) -> 0; logfib(1) -> 1; logfib(2) -> 1; logfib(N) when N rem 2 =:= 0 -> Res1 = logfib(N div 2 + 1), Res2 = logfib(N div 2), Res2 * (Res1 * 2 - Res2); logfib(N) -> Res1 = logfib(N div 2 + 1), Res2 = logfib(N div 2), Res1 * Res1 + Res2 * Res2.
O(log n)で求めるコードを書いてfib(1000000)まではストレスなく
表示までしてくれるコードになりました。
10000000でも求めてはくれるのだが、表示にものすごい時間がかかる。
一応Erlangのプロセス辞書というものを使ってメモ化的なこともやってみました。
logfib(0) -> 0; logfib(1) -> 1; logfib(2) -> 1; logfib(N) -> Memo = get(N), if Memo =:= undefined -> Res1 = logfib(N div 2 + 1), Res2 = logfib(N div 2), if N rem 2 =:= 0 -> Res = Res2 * (Res1 * 2 - Res2); true -> Res = Res1 * Res1 + Res2 * Res2 end, put(N, Res); true -> Res = Memo end, Res.
今書いてるのが、プロセスを作って並列化するコードなのですが、
Erlangの強みを生かしたコードが書けるといいなって感じです。
今回はここまでにしたいと思います。
ではでは
ErlangでいろんなSortを書いてみる part1
2ヶ月ぶりの更新になります。
最近Haskellで様々なソートを
実装してみたというブログ記事を読みました。
自分がやったことある関数型言語って何があったかなと
思い出してみると、そういえば
「Erlang」
があったなとふと思い出しました。
それで僕もErlangでソートを実装してみるかと思い
実装してみたわけです。
sort([]) -> []; sort(List) -> Sorted = bubble_sort(List), [Min|More] = lists:reverse(Sorted), [Min|sort(lists:reverse(More))]. bubble_sort([]) -> []; bubble_sort(List) when length(List) == 1 -> List; bubble_sort([X,Y|More]) when X > Y -> [X|bubble_sort([Y|More])]; bubble_sort([X,Y|More]) -> [Y|bubble_sort([X|More])].
シェイカーソート:
shaker_sort([]) -> []; shaker_sort(List) when length(List) < 2 -> List; shaker_sort(List) -> Upped = shaker_sort(up, List), [Min|More] = lists:reverse(Upped), Downed = shaker_sort(down, More), [Max|Other] = lists:reverse(Downed), lists:reverse([Max|lists:reverse([Min|shaker_sort(Other)])]). shaker_sort(up, []) -> []; shaker_sort(up, List) when length(List) < 2 -> List; shaker_sort(up, [X,Y|More]) when Y > X -> [Y|shaker_sort(up,[X|More])]; shaker_sort(up, [X|More]) -> [X|shaker_sort(up, More)]; shaker_sort(down, []) -> []; shaker_sort(down, List) when length(List) < 2 -> List; shaker_sort(down, [X,Y|More]) when Y < X -> [Y|shaker_sort(down, [X|More])]; shaker_sort(down, [X|More]) -> [X|shaker_sort(down, More)].
選択ソート:
selection_sort([]) -> []; selection_sort(List) -> Min = lists:min(List), [Min|selection_sort(List -- [Min])].
挿入ソート:
insertion_sort([], Sorted) -> Sorted; insertion_sort([Head|More], Sorted) -> insertion_sort(More, insert(Sorted, Head)). insert([],Value) -> [Value]; insert([Head|_] = List,Value) when Head > Value -> [Value|List]; insert([Head|More], Value) -> [Head|insert(More, Value)].
今回はこの4つを実装しました。
実際に実装してみるとぜんぜん覚えてなくてびっくりしました。
他のソートを実装して、またブログに上げます。
では今回はこのへんで。
新年あけたから書いたコード
新年あけたので書いたコードはこちら
http://ideone.com/yZx1Ob
#include <stdio.h> int main(void) { int out[] = { 1095245889, 542724176, 542590286, 1380009305, 1680154657, 10}; printf(out,(1<<11)-~-(1<<1<<1<<1)*-~(1<<1<<1)); return (0); }
今年もよろしくお願いします。
AOJ0047 Cup Game
3つのカップがふせて置かれています。カップの置かれている場所を、順にA,B,C と呼ぶことにします。最初はA に置かれているカップの中にボールが隠されているとします。入れ替える2つのカップの位置を保存したデータがあります。このデータを読み込んで、最終的にどの場所のカップにボールが隠されているかを出力して終了するプログラムを作成してください。ただし、カップの位置を入れ替える際には、中に入っているボールも一緒に移動するものとします。
という問題を今回は短くしてみました。
#include <stdio.h> int main(void) { char cups[4] = {0}; char swap_a, swap_b; int i; cups[0] = 1; while (scanf(" %c,%c", &swap_a, &swap_b) != EOF){ if (cups[swap_a - 'A'] == 1){ cups[swap_b - 'A'] = 1; cups[swap_a - 'A'] = 0; continue; } if (cups[swap_b - 'A'] == 1){ cups[swap_a - 'A'] = 1; cups[swap_b - 'A'] = 0; } } for (i = 0; i < 4; i++){ if (cups[i] == 1){ break; } } printf("%c\n", 'A' + i); return (0); }
こんなかんじで若干残念に書いたわけですよ。
この時点で464byte
ここで色々犠牲にすることによって
p;main(s,a,b){for(;~scanf("%X,%X",&a,&b);p=(p<=s?s-p:p)%3)s=a+b-20;p=!printf("%c\n",65+p);}
91byteまで削ることができました。
結構無茶をしたので解説できないです。
この問題の1位は23byteで、"C"だけを返すソースで憤慨しました。
1月3日に訂正されたようです。情報有り難うございます。
まだまだ、頑張らないといけないです。
Code Golf イントロダクション
僕が趣味(?)としているコードゴルフについて
お書きしたいと思います。
コードゴルフとは
より少ないバイト数で所与の課題をプログラミングする遊び。
より少ない打(鍵)数を競うところがゴルフに似ているところからの命名。
とりあえず、プログラムのコードを短く書けば良いそれだけのこと。
見づらいとか、非生産的であるとか、役に立たないだとかと言われるけど、
僕はコードゴルフを通して得るものもあると思います。
何より"楽しい"。それで僕はいいと思っています。
とりあえずプログラムのコードを短く書いてみましょう。(唐突
例えば1〜Nまでの合計を出すプログラムを書くとしましょう。
#include <stdio.h>
int main(void)
{
int n;
int i;
int sum;
scanf("%d", &n);
sum = 0;
for (i = 1; i <= n; i++){
sum += i;
}
printf("%d\n", sum);
return (0);
}
これが一般的なソースだと思います。
これをどんどん短くしていこうと思います。
// #include <stdio.h> は省略可
main(){
// 型を指定しないと自動でintになるので省略可
int n, sum;
// まとめて宣言
scanf("%d", &n);
for (sum = 0; n; sum += n--);
// nの値が0になると終了
printf("%d\n", n);
return 0;
// 0を返さなければいけない
}
これで結構短くなりました(やったね!
しかし、まだまだ短く出来ます、この状態ではニワカです。
main(s,n){
// main関数の第1引数に渡すと1で初期化される。argcとして扱われる。
for(scanf("%d",&n);n-1;s+=n--);
// 1式にscanf渡して悪いと誰が言った。
printf("%d\n",s);
return 0;
// 0を返さなければいけない。
}
もうちょっと短くできる。
main(s,n){
for(scanf("%d",&n);n-1;s+=n--);
return !printf("%d\n",s);
// printfの戻り値は表示した文字数。否定して0を返すようにする。
}
とここまで短くすればよいでしょう。(なにが良いのかわからない
main(n){n=scanf("%d",&n)/printf("%d\n",n*-~n/2);}
これが僕が短くできる限界です。
このように最初のコードと比べると、見づらい、意味がわからない、短い。
こういうソースを見て「美しい!!」となる方はぜひCodeGolfをやってみてください。
そして、互いに競いあいましょう。
まだまだ僕もニワカなので努力しなければいけないです。