トップ «前の日記(2010-07-18) 最新 次の日記(2010-07-21)» 編集

はじめてのにき

ここの位置付け

2004|11|
2005|03|04|05|06|07|08|09|10|11|12|
2006|01|02|03|04|05|06|07|08|09|10|11|12|
2007|01|02|03|04|05|06|07|08|09|10|11|12|
2008|01|02|03|04|05|06|07|08|09|10|11|12|
2009|01|02|03|04|05|06|07|08|09|10|11|12|
2010|01|02|03|04|05|06|07|08|09|10|11|12|
2011|01|02|03|04|05|06|07|08|09|10|11|12|
2012|01|02|03|04|05|06|07|08|09|10|11|12|
2013|01|02|03|04|05|06|07|08|09|10|11|12|
2014|01|02|03|04|05|06|07|08|09|10|11|12|
2015|01|02|03|04|05|06|07|08|09|10|11|12|
2016|01|02|03|04|05|06|07|08|09|10|11|12|
2017|01|02|03|04|05|06|07|08|09|10|11|12|
2018|01|02|03|04|05|06|07|08|09|10|11|12|
2019|01|02|03|04|05|06|07|08|09|10|11|12|
2020|01|02|03|04|05|06|07|08|09|10|11|12|
2021|01|02|03|04|05|

ToDo:


2010-07-19

_ swap

http://d.hatena.ne.jp/nishiohirokazu/20100622/1277208908

http://d.hatena.ne.jp/nuc/20100716/p17

via http://twitter.com/gusmachine/status/18840198768

@gusmachine さんいいこと言うなあ…ってのはいいとして。

id:nuc さんは空間使用量が O(N**2) で増えていく、 と書いてあるけど、そうなん? と思ってしまった。 fibonacci の多倍長整数のオーダーが O(N) になるのか。

で…

fib_time.gif

2.77618e-13*x^2.55 の方が 2.10854e-10*x^2 よりどう見てもマッチしてるな。 特異的って感じもないと思う。

まぁ Haskell とか不思議の塊なので、深く考えるのはやめ。

で、メモリ。

fib_rss.gif

うーん O(N)。

まぁ Haskell とか不思議の塊なので、深く考えるのはやめ…

(02:10)

_ ちなみに

二つ目のグラフの a == 0.668326 だそうです。 そしてメモリの縦軸は kB 。 つまりメモリ使用量が 668 Bytes ずつ増えていく計算になるわけですが…謎。

もう少し上まで

fib_time2.gif

a               = 3.16989e-10      +/- 1.038e-11    (3.274%)
b               = 2.63344          +/- 0.007344     (0.2789%)
c               = 1.01622e-13      +/- 9.684e-15    (9.53%)

fib_rss2.gif

a               = 0.642804         +/- 0.007101     (1.105%)

ソースコード

http://github.com/shinh/test/commit/79d93f47d025f841ee9a7639bf3b493d918b86b0

(02:27)

_ wake

名前は

  • kati はやっちゃったから hikiwake かなぁ
  • てか wake って m ひっくりかえした make っぽいね
  • 作りはじめた時に眠かったのに作りたくなって無理矢理起きて作ってた

のでちょうどいいと思った

あと一日中雌豚先生の作業用 BGM 聞いてた結果、 たしかに違うかなーと思った。

(02:42)

_ bf.bef

書いた記憶があるのにどこにもないなぁと探しまわった。

見つかった…

http://d.hatena.ne.jp/shinichiro_h/20100121#1264012341

検索用: befunge brainfuck bfint.bef brainfuck.bef

(02:51)

_ WebKit

たいしたことじゃないけど

http://ss-o.net/webkit/extension/browser.html#Page5

個人的な感覚ではあの switch case は必要悪かなぁ。 分離されてるとかえって不便な気がする。

グローバル変数も過去の遺産っていうか省メモリやら キャッシュしたいやらでしょうがない面も強い、かな。 ただ省メモリ用のハッシュとキャッシュ用の static 変数でのハッシュは、 それぞれ class 作って抽象化しておけば、 いざ thread safe にしたいとか思った時にやりやすかったかもー という意味ではまぁ過去の遺産と言われてもしゃーないか。

http://ss-o.net/webkit/extension/browser.html#Page10

WebKit2 の説明はちょっと意味がわからなかった。 どっちの説明も「なので、」までは正しいと思うんだけど、 後半はどっちもそうなんじゃないか。 WebKit2 もたぶんタスクマネージャ見たら たくさん起動してるだろうし、 どっちも1つのアプリケーションの中でプロセスを分割してるし…?

Chrome は ... なので、使いまわせない。 WebKit2 は ... なので、使いまわせる。 とかがこの文脈で言える唯一のことじゃないかなぁ。

出てきたころは、 WebKit2 はまだ新しいので、 セキュリティうんぬんとか詳しいこと考えてるのかなーとかいうのは 言えたっぽいんだけど、 まぁ今はさっぱり動きとか見てないのでわからない。

(12:56)

_ SSE 命令

http://msirocoder.blog35.fc2.com/blog-entry-58.html

これは大変便利げな

(13:06)

_ wake の page

As of September 18, 2010 とか書いてあった。 未来に生きてるなー。

正解は July でした。

さっき昨日ビルドしたはずのファイルに ls -l して、 July とかでてきて、 えーと July って 5 月じゃないかにゃー ヘンだにゃーと思ったところで、 そもそも July は今月だと気付いた。

英語の月名は難しいよなあ…

(13:19)

_ ものはついでと申します

ruby1.9 (git-svn-id: http://svn.ruby-lang.org/repos/ruby/trunk@28675)

fib_time_rb.gif

a               = 1.02084e-10      +/- 2.187e-12    (2.143%)
b               = 2.47454          +/- 0.0404       (1.633%)
c               = 3.26532e-13      +/- 1.625e-13    (49.76%)

fib_rss_rb.gif

a               = 0.642804         +/- 0.007101     (1.105%)

コード

n = ARGV[0].to_i
fib = [1,1]
n.times{|i|
  fib << fib[i+1] + fib[i]
}

時間は O(N**2.47454) 。

なにか正直言って、 memory allocator がこんだけ order をいじるんだなぁということを知らなかった。

あと、 Haskell が線型のメモリしか使わないのは、 よく考えたら僕の脳内 Haskell はそいう動きしそうに思ったので、 さして不思議じゃないかなぁと。

java version "1.6.0_18"

fib_time_java.gif

a               = 1.81687e-10      +/- 3.693e-12    (2.033%)
b               = 2.16295          +/- 0.1003       (4.636%)
c               = 2.73763e-11      +/- 3.232e-11    (118.1%)

fib_rss_java.gif

a               = 0.000237798      +/- 5.535e-06    (2.328%)

時間は O(N**2.16295) とのことで、 オーダーのオーバヘッドは少ない。 ただそもそもなんか遅いんだけどな…

import java.math.BigInteger;
import java.util.ArrayList;

public class fib {
    public static void main(String[] args) {
        ArrayList<BigInteger> l = new ArrayList<BigInteger>();
        l.add(BigInteger.ONE);
        l.add(BigInteger.ONE);
        int e = new Integer(args[0]).intValue();
        for (int i = 0; i < e; i++) {
            l.add(l.get(i).add(l.get(i+1)));
        }
    }
}

Java 書いたの超ひさしぶりだー

(13:57)

_ C++

完璧言語 C++ ではどうか。

fib_time_cc.gif

a               = 5.4409e-11       +/- 1.265e-12    (2.325%)
b               = 1.84416          +/- 0.09885      (5.36%)
c               = 3.58202e-10      +/- 4.327e-10    (120.8%)

O(N**1.84416)! O(N**2) のアルゴリズムのオーダーを減らしてくれる memory allocator! すごいです!!

fib_rss_cc.gif

a               = 0.000188953      +/- 7.58e-06     (4.011%)

まぁ途中で memory allocator は サイズの大きい小さいで挙動を変えてるだろうし、 gmp もそいうのあるかもしれないし、 まぁ N**a とかでの fit はあまり意味ないんだろうと思う。

ソースコード。 gmpxx ってえらいですね。 GNU とは思えない。知らんかった。

#include <stdio.h>
#include <stdlib.h>

#include <iostream>
#include <vector>

#include <gmp.h>
#include <gmpxx.h>

using namespace std;

int main(int argc, char* argv[]) {
    vector<mpz_class> v;
    v.push_back(1);
    v.push_back(1);
    int e = atoi(argv[1]);
    for (int i = 0; i < e; i++) {
        v.push_back(v[i] + v[i+1]);
    }
    //cout << v[e] << endl;
}

これまでのあらすじ:

fib_time_all.gif

fib_rss_all.gif

Ruby すごくね

(14:57)

_ あとそうだ

これは GC のある言語に大変厳しいベンチマークなので、 公平性には欠けまくりだと思う。

なんでかっていうとメモリ使用量が増えるばっかりで、 全然 collection されないから。

聞いた話によると、コンパイラとかはこいう挙動をする、 GC 泣かせなアプリの一つらしい。 つまりソースコードを読んでがーとデータ構造作るんだけど、 作るばっかであんま解放する物は無い、というような。

(15:01)

_

適当に D も足しておいた。

時間は O(N**2.5833) ですって。

(16:21)

本日のツッコミ(全3件) [ツッコミを入れる]
_ 白のカピバラ (2014-05-24 01:33)

詳しい実験どうもありがとうございます。
はてなid:nuc です。不思議の塊に足を突っ込んで反省しております。
ちょっと追調査をしてみると、想像以上に環境依存なようです。

それはそうと gnuplot の fit なんですが、(誤差は実行時間に比例すると思われるのに)誤差項与えていないので高次項が支配的になってしまっていると思います。

_ シンX (2014-05-24 01:33)

配列不要の動的計画法を使えばいいだけの話のような……(とか言っちゃダメなのかな?) ;-)

_ shinh (2014-05-24 01:33)

もちろんそうなんですけど、いやしかし Haskell のヤツは O(N) の配列は作って無いので、えーとうーん、そっちの方のオーダーも調べてみた方がいいでしょうね…

お名前:
E-mail:
コメント:
人生、宇宙、すべての答え
本日のリンク元

2010年
7月
1 2 3
4 5 6 7 8 9 10
11 12 13 14 15 16 17
18 19 20 21 22 23 24
25 26 27 28 29 30 31
1.shinh(2014-05-24 01:33) 2.Gimite(2014-05-24 01:33) 3.シンX(2014-05-24 01:33)
search / home / index

全てリンクフリーです。 コード片は自由に使用していただいて構いません。 その他のものはGPL扱いであればあらゆる使用に関して文句は言いません。 なにかあれば下記メールアドレスへ。

shinichiro.hamaji _at_ gmail.com / shinichiro.h