R.A. Epigonos et al.

[Programing] プログラミングの素人が不思議に思ったこと

プログラミングの素人が思ったことを書き留めていきます。

目次

コード検索

まぁ、自分の力量を超える仕事をする場合、コード検索することが良くあるわけ。で、こんなコードありますかというものをどこで聞けばいいのだろうか

  1. Open Source Code Search Engine - Koders
  2. Krugle - Transform Code into Profit.
  3. gonzui: ソースコード検索エンジン
  4. codefetch{
  5. Home | byteMyCode
  6. Codase - Source Code Search Engine
  7. Java Examples - JExamples.com
  8. DocJar: Search Open Source Java API
  9. Prospector Demo
  10. KickJava.com: Java API By Example, From Geeks To Geeks.
  11. Jarhoo
  12. All The Code - Source Code Search Engine
  13. Google ソースコード検索
  14. Source Code Search Engine - UCodit - New Search
  15. Code Search - O'Reilly Labs
  16. 目新しさに欠けるGoogle Code Search - SourceForge.JP Magazine
  17. 見つけて得するソースコード専用の検索エンジン - ＠IT
  18. 5 Great Code Search Engines! | The KnightKnetwork
  19. サンプルコードが見つかるかも？！知っておきたいコード検索エンジンまとめ | IDEA*IDEA
  20. はてなブックマーク - サンプルコードが見つかるかも？！知っておきたいコード検索エンジンまとめ | IDEA*IDEA
  21. サンプルコードが見つかるかも？！知っておきたいコード検索エンジンまとめ | IDEA*IDEA - 補天鳥保管庫
  22. 情報デザイン論2007　資料：検索、支援、公開 - 三上のブログ

自分の状態を他人に伝えられるプログラム

そんなのあれば良いなということ。今なら言える。ibusとか名前付きパイプとかサーバクライアント型とかいろいろあるだろうと。

malloc calloc reallocはどこまで出来るの。

メモリ確保関数と言うことで、3つある。で、メモリ確保するわけだが、大きなメモリを確保したいと言う場合、どのサイズまで確保できるのか気になる。

ツール、プログラムを補助してくれる

omake初めて知ったが、結構いい感じに使えそうなのでめもっておこう

  1. OMake つかって LaTeX コンパイルしたら簡単すぎて身長が5cm伸びた - 日記を書く[・ _ゝ・]はやみずさん

#hoge とか ## とかの話。

わけあって可変長配列をC言語で書くことになった。いろんな変数型に対応させるためになんか良いお手本無いかなぁと思って、gslで使っていたgsl_blockの実装を参考にしたところ、面白いものを見つけた。

#hogeは、関数型マクロの引数hogeを文字列として置き換えてくれる。ダブルコーテーションで引数hogeの内容を括って展開してくれると言うわけだ。と言うことでデバッグプリント用の関数を作ってみた。

#define DEBUG_PRINT_MEM(a)\
printf("# DEBUG: ");\
printf(#a);\
printf("\t(%p)\t=\t",(void *)&a);\
#define DEBUG_PRINT1(a)\
DEBUG_PRINT_MEM(a)\
printf("\n")
#define DEBUG_PRINT2(f,a)\
DEBUG_PRINT_MEM(a)\
printf(f,a);\
printf("\n")

使い方はこんなかんじで。

DEBUG_PRINT1(dma_array);
DEBUG_PRINT2("%u", dma_array->size);
DEBUG_PRINT1(dma_array->data);

で、こいつを使うと下のような感じになる。

# DEBUG: dma_array      (0xbfeb030c)    =
# DEBUG: dma_array->size   (0x804c0a0)     =        100
# DEBUG: dma_array->data   (0x804c0a4)     =

デバッグプリントしたい変数を引数に与えれば、ソース内の変数名と走らせたときの該当する変数のアドレスと内容が表示される。

  1. C言語 の define マクロの可能性 - 週記くらい(BTS開発記)
  2. C 言語 マクロ講座 # ## 編: uyota 匠の一手
  3. Ｃプログラミング診断室／不慣れ／マクロ
  4. gsl-1.9/templates_on.h - Google ソースコード検索
  5. gsl-1.9/block/init_source.c - Google ソースコード検索

時間がかかるので、各ステップで動作確認したい

開始から終了まで1月とか、計算に時間がかかる場合。こんなこと結構あるわけで、うまく計算が進んでいるか1月間もの間心配続きだ。そんな場合、動作チェック用のスレッドと計算用のスレッドを作り、適当な時間間隔で動作チェック用スレッドから計算用スレッドの状態を参照すればよいのではなかろうか。5分くらいで書いたのでなんだか危険な香りがぷんぷんするな。

#include <stdio.h>
#include <stdlib.h>
#include <sys/types.h>
#include <pthread.h>
typedef struct {
        pthread_t ctrl;
        pthread_t run;
        unsigned int s;
        size_t i;
        size_t i_num;
        double x_i;
        double y_i;
} param;
void param_new(param * p)
{
        p->s = 5;
        p->i_num = 100;
        return;
}
void param_print(param * p)
{
        printf("# p\t(% x)\n", &p);
        printf("# p->ctrl\t(% x)\t=\t% d\n", &p->ctrl, p->ctrl);
        printf("# p->run\t(% x)\t=\t% d\n", &p->run, p->run);
        printf("# p->i_num\t(% x)\t=\t% d\n", &p->i_num, p->i_num);
        printf("# p->i\t(% x)\t=\t% d\n", &p->i, p->i);
        printf("# p->x_i\t(% x)\t=\t% e\n", &p->x_i, p->x_i);
        printf("# p->y_i\t(% x)\t=\t% e\n", &p->y_i, p->y_i);
        return;
}
void param_free(param * p)
{
        return;
}
void *ctrl(void *p_)
{
        param *p = (param *) p_;
        int ch;
        char buf[10];
        char c[] = "q";
        char d[] = "q";
        printf("# ctrl start %d\n", &p);
        do {
                sleep(p->s);
                printf("% e\t", p->x_i);
                printf("% e\t", p->y_i);
                printf("% d\n", p->i);
        } while (p->run != 0);
        printf("# ctrl end %d\n", &p);
        return;
}
void *run(void *p_)
{
        param *p = (param *) p_;
        size_t i_num = p->i_num;
        size_t i = 0;
        double x_i = 0.0;
        double y_i = 0.0;
        for (i = 0; i < i_num; i++) {
                x_i = (double) i *0.1;
                y_i = x_i * x_i;
                p->i = i;
                p->x_i = x_i;
                p->y_i = y_i;
                sleep(1);
        }
        return;
}
int main(int argc, char **argv)
{
        int s = 0;
        void *result = (void *)NULL;
        param *p = (param *) calloc(1, sizeof(param));
        param_new(p);
        param_print(p);
        s = pthread_create(&p->ctrl, NULL, ctrl, (void *) p);
        if (s != 0) {
                fprintf(stderr, "pthread_create : %s\n", strerror(s));
        }
        s = pthread_create(&p->run, NULL, run, (void *) p);
        if (s != 0) {
                fprintf(stderr, "pthread_create : %s\n", strerror(s));
        }
        p->run = pthread_join(p->run, &result);
        p->ctrl = pthread_join(p->ctrl, &result);
        param_print(p);
        param_free(p);
        free(p);
        return 0;
}

まぁこんな感じかな。runが計算スレッド、ctrlがチェックスレッド。runではx_i=0から0.1刻みでy=x*xの計算を行っている。ここが時間がかかる処理に相当する。で、各ステップiごとにiとx_iとy_iを更新し、これをチェックスレッドが参照できる構造体pの各メンバに代入している。ctrlでは、p->s秒ごとにrunで代入したi,x_i,y_iをチェックして表示している。runの終了はpthrad_joinの戻り値が0になっているかどうかでチェック、ctrlスレッドの終了はrunスレッドが終了したら終了するように、runスレッド番号を参照し、これが0なら終了するようにしている。

アマチュアだから考えてしまう

グローバル変数は少なめに、と言われることがある。べつにグローバル変数が絶対にだめだと言うわけではないのだけれど、意味的にグローバル(プログラム全体が其の変数の内容を知らねばならない)であるべき変数と言うものはあるはず。もちろんそのような変数の数は少ないに越したことは無いはずだが、そのようなものを一括して扱いたいなぁと思うとこんなことになってしまう。

typedef struct {
        int N;
        double a;
        size_t b_num;
        double *b;
} param;
void param_new(param *p)
{
        p->N = 1;
        p->a = 10.1;
        p->b_num = 100;
        p->b = (double *)calloc(p->b_num,sizeof(double));
        return;
}
void param_free(param *p)
{
        free(p->b);
        return;
}
void param_print(param *p)
{
        size_t i = 0;
        size_t b_num = p->b_num;
        printf("# i\t=\t% d\n",i);
        printf("# a\t=\t% e\n",a);
        for(i=0;i<b_num;i++){
                printf("# b[%d]\t=\t% e\n",i,b[i]);
        }
        return;
}
int main(int argc, char **argv)
{
        param *p;
        p = (param *)calloc(1,sizeof(param));
        param_new(p);
        param_print(p);
        param_free(p);
        free(p);
        return 0;
}

プログラム全体で知っておかねばならないパラメータは構造体paramの内部で宣言しておいて、それらの初期値をparam_newで定義する。プログラム終了直前にparam_freeでparam_newの中でアロケートしたメモリをfreeする。param_printはparam_newではparamの内容チェック用。

これが良いのか悪いのかよくわからないけれど、こんな感じで書くことに最近はまってる。意外とgetoptしたときとか相性が良いと思うんだけどなぁ。

安全なfree

mallocした領域をfreeする場合、2度free(double free)してしまうと危険である。ということはよく言われているわけで。

free(hoge); hoge=NULL;

このようにしておくといいらしい。freeの後にfreeした領域hogeにNULLポインタを入れている。このようにすることで、もしこの後にfree(hoge)してもfree(NULL)であり、この場合のfreは何もしないことが保障されているから安全ということらしい。面倒な場合は

#define safe_free(hoge) free(hoge);hoge=NULL

のようにマクロを定義しておくといいかも。

2の倍数と3の倍数を除いた数列のi番目の数nを返す関数

メモリの少ないマシン上で素数判定プログラムを作るときに必要になったので。アルゴリズム自体はものすごく簡単。部分数列の考え方でOK。

使われ方はこんな感じ。これで1番目から100番目までの数列の要素が出力される。mainの中で使われているi_to_nという関数をどのように作るか。

int main( void )
{
        for(i=0; i<100; i++){
                printf("%d %d\n" ,i ,i_to_n(i));
        }
        return 0;
}

まずはホワイトボードに色々書き殴ってみる。

n       0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, ...
2の倍数 1, 0, 1, 0, 1, 0, 1, 0, 1, 0,  1,  0,  1,  0, ...
3の倍数 1, 0, 0, 1, 0, 0, 1, 0, 0, 1,  0,  0,  1,  0, ...
i          0,          1,    2,            3,      4, ...
i%2        0,          1,    0,            1,      0, ...
i/2        0,          0,    1,            1,      2, ...

つまり、2の倍数かつ3の倍数である6の倍数ごとに周期性がある。ある6の倍数から次の6の倍数までの中には必ず2つの、2の倍数でもなく3の倍数でもない数が存在する。6の倍数で部分数列をつくると、各々の部分数列に含まれる最初の各要素は、部分数列について6だけ差がある。このことは2番目の要素についても同じ。各部分数列の番号付けはi/2で出来る。部分数列内の要素の番号付けはi%2で出来る。ということでこんな感じ。

部分行列の1番目の数の数列の一般項
n = 1 + 6 * (i / 2 の商)
部分行列の2番目の数の数列の一般項
n = 5 + 6 * (i / 2 の商)

当然ながら、int型の演算における(i/2)は「iを2で割ったときの商」というれっきとした「意味」があるので、6*i/2を3*iのようにまとめてはいけない。ということで下のようにかける。

int i_to_n(int i)
{
        int n;
        if( 0 == (i % 2) ){
                n = 1 + 6 * (i / 2);
        }else{
                n = 5 + 6 * (i / 2);
        }
        return n;
}

入出力チェックが行われていないので軽く脳内チェック。nはint型なので、iが大きいと数学的にはおかしな結果が得られるはず。例えば、(INT_MAX)/3の辺りで。テストコードを書いてみる。

void check(void)
{
        int i = 0;
        int i_sta = INT_MAX/3 - 10;
        int i_end = i_sta + 20;
        for(i=i_sta;i<i_end;i++){
                printf("%10d %10d %10u\n",i, i_to_n(i), i_to_n(i));
        }
        return;
}

走らせると明らかにおかしな出力である。出力結果が採点されるので、これでは困る。

 715827872 2147483617 2147483617
 715827873 2147483621 2147483621
 715827874 2147483623 2147483623
 715827875 2147483627 2147483627
 715827876 2147483629 2147483629
 715827877 2147483633 2147483633
 715827878 2147483635 2147483635
 715827879 2147483639 2147483639
 715827880 2147483641 2147483641
 715827881 2147483645 2147483645
 715827882 2147483647 2147483647
 715827883 -2147483645 2147483651
 715827884 -2147483643 2147483653
 715827885 -2147483639 2147483657
 715827886 -2147483637 2147483659
 715827887 -2147483633 2147483663
 715827888 -2147483631 2147483665
 715827889 -2147483627 2147483669
 715827890 -2147483625 2147483671
 715827891 -2147483621 2147483675

注目すべき点はprintf関数でフォーマット指定する際にunsigned int型とすると、上手くいくという点である。少なくとも僕がテストコードを走らせている処理系では、printf文がint型とunsigned int型を処理する場合の違いは最上位ビットを負数を表現するフラグと考えるか否かだけの違いなので、こんな感じの事が起きる。とりあえずnが負数ならperror();exit();するという手もあるが、それだと十分にビットを使えていない(半分くらいのビットが無駄になる)し出力チェックは入力チェックに比べてコストがかかるので面白くない。このままの状態で出力だけunsigned intを使うのもいいが、それだと論理的でない機がする。まずはunsigned int型にして、論理的に正しく計算できる範囲を広げよう。

unsigned int i_to_n(unsigned int i)
{
        unsigned int n;
        if( 0 == (i % 2) ){
                n = 1 + 3 * i;
        } else {
                n = 5 + 3 * i;
        }
        return n;
}
void check(void)
{
        unsigned int i = 0;
        unsigned int i_sta = UINT_MAX/3 - 10;
        unsigned int i_end = i_sta + 20;
        for(i=i_sta;i<i_end;i++){
                printf("%10d %10u %10d %10u\n",i,i, i_to_n(i), i_to_n(i));
        }
        return;
}

で、出力結果が下のような感じ。

1431655755 1431655755        -29 4294967267
1431655756 1431655756        -27 4294967269
1431655757 1431655757        -23 4294967273
1431655758 1431655758        -21 4294967275
1431655759 1431655759        -17 4294967279
1431655760 1431655760        -15 4294967281
1431655761 1431655761        -11 4294967285
1431655762 1431655762         -9 4294967287
1431655763 1431655763         -5 4294967291
1431655764 1431655764         -3 4294967293
1431655765 1431655765          1          1
1431655766 1431655766          3          3
1431655767 1431655767          7          7
1431655768 1431655768          9          9
1431655769 1431655769         13         13
1431655770 1431655770         15         15
1431655771 1431655771         19         19
1431655772 1431655772         21         21
1431655773 1431655773         25         25
1431655774 1431655774         27         27

ここまでしてから、入力チェックを行って、エラー終了させる。どこにエラーの原因が潜んでいるか微妙なので、計算のたびにエラーチェックをさせる。

unsigned int uint_dvi(unsigned int a, unsigned int b)
{
        unsigned int a_dvi_b = a;
        if (a <= (UINT_MAX * b)) {
                a_dvi_b /= b;
        } else {
                errno = ERANGE;
                fprintf(stderr,"%u / %u",a,b);
                perror("#");
                exit(EXIT_FAILURE);
        }
        return a_dvi_b;
}
unsigned int uint_mul(unsigned int a, unsigned int b)
{
        unsigned int a_mul_b = a;
        if (a <= (UINT_MAX / b)) {
                a_mul_b *= b;
        } else {
                errno = ERANGE;
                fprintf(stderr,"%u * %u",a,b);
                perror("#");
                exit(EXIT_FAILURE);
        }
        return a_mul_b;
}
unsigned int uint_add(unsigned int a, unsigned int b)
{
        unsigned int a_plus_b = a;
        if (a <= (UINT_MAX - b)) {
                a_plus_b += b;
        } else {
                errno = ERANGE;
                fprintf(stderr,"%u + %u",a,b);
                perror("#");
                exit(EXIT_FAILURE);
        }
        return a_plus_b;
}
unsigned int i_to_n(unsigned int i)
{
        unsigned int n = i;
        //n /= 2;
        n = uint_dvi(n, 2);
        //n *= 6;
        n = uint_mul(n, 6);
        if (0 == (i % 2)) {
                //n += 1;
                n = uint_add(n, 1);
        } else {
                //n += 5;
                n = uint_add(n, 5);
        }
        return n;
}

で、こんな感じ。しっかりと落ちてくれている。まぁこれで、処理系依存がないだろうと思う。採点する人間の処理系を公開してほしいものだ。おかげで色々と考えさせられるが。

1431655755 4294967267
1431655756 4294967269
1431655757 4294967273
1431655758 4294967275
1431655759 4294967279
1431655760 4294967281
1431655761 4294967285
1431655762 4294967287
1431655763 4294967291
1431655764 4294967293
4294967292 + 5#: Numerical result out of range
1431655765

2と3と5の倍数以外の数列

この前書いた部分を多少変えてみる。

n       0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, ...
2の倍数 1, 0, 1, 0, 1, 0, 1, 0, 1, 0,  1,  0,  1,  0, ...
3の倍数 1, 0, 0, 1, 0, 0, 1, 0, 0, 1,  0,  0,  1,  0, ...
5の倍数 1, 0, 0, 0, 0, 1, 1, 0, 0, 0,  1,  0,  0,  0, ...
i          0,                1,            2,      3, ...
i%8        0,                1,            2,      3, ...
i/8        0,                0,            0,      0, ...

同様に考えると、部分数列と2と3と5の最小公倍数である30ずつにわけ、この部分数列には8つの2と3と5の倍数でない数(1, 7, 11, 13, 17, 19, 23, 29 )が8個含まれる。

unsigned int i_to_n_2_3_5(unsigned int i)
{
        unsigned int n = i;
        unsigned int lcm = 30;
        unsigned int the_number_of_un_multiples = 8;
        unsigned int tmp = i % the_number_of_un_multiples;
        n = uint_dvi(n, the_number_of_un_multiples);
        n = uint_mul(n, lcm);
        if (0 == tmp) {
                n = uint_add(n, 1);
        } else if (1 == tmp) {
                n = uint_add(n, 7);
        } else if (2 == tmp) {
                n = uint_add(n, 11);
        } else if (3 == tmp) {
                n = uint_add(n, 13);
        } else if (4 == tmp) {
                n = uint_add(n, 17);
        } else if (5 == tmp) {
                n = uint_add(n, 19);
        } else if (6 == tmp) {
                n = uint_add(n, 23);
        } else if (7 == tmp) {
                n = uint_add(n, 29);
        }
        return n;
}
unsigned int i_to_n(unsigned int i)
{
        return i_to_n_2_3_5(i);
}

冗長に見えるif文を配列を用いてまとめる。

unsigned int i_to_n_2_3_5(unsigned int i)
{
        unsigned int p[] = { 1, 7, 11, 13, 17, 19, 23, 29 };
        unsigned int lcm = 30;
        unsigned int the_number_of_un_multiples = (sizeof(p) / sizeof(p[0]));
        unsigned int n = i;
        n = uint_dvi(n, the_number_of_un_multiples);
        n = uint_mul(n, lcm);
        n = uint_add(n, p[i % the_number_of_un_multiples]);
        return n;
}

マジックナンバーを引数にする。

unsigned int i_to_n_2_3_5(unsigned int i,unsigned int lcm, unsigned int p[],unsigned int the_number_of_un_multiples )
{
        unsigned int n = i;
        n = uint_dvi(n, the_number_of_un_multiples);
        n = uint_mul(n, lcm);
        n = uint_add(n, p[i % the_number_of_un_multiples]);
        return n;
}
unsigned int i_to_n(unsigned int i)
{
        unsigned int p[] = { 1, 7, 11, 13, 17, 19, 23, 29 };
        unsigned int lcm = 30;
        unsigned int the_number_of_un_multiples = (sizeof(p) / sizeof(p[0]));
        return i_to_n_2_3_5(i,lcm,p, the_number_of_un_multiples );
}

i_to_nは何回も呼び出されるのでいちいち宣言するのは無駄。マジックナンバーをi_to_nが頻繁に呼び出されるループの外に持っていく。ついでに構造体にして引数の量を節約。

typedef struct {
        unsigned int *p;
        unsigned int lcm;
        unsigned int the_number_of_un_multiples;
} i_to_n_conf;
unsigned int i_to_n_2_3_5(unsigned int i, i_to_n_conf conf)
{
        unsigned int n = i;
        n = uint_dvi(n, conf.the_number_of_un_multiples);
        n = uint_mul(n, conf.lcm);
        n = uint_add(n, conf.p[i % conf.the_number_of_un_multiples]);
        return n;
}
unsigned int i_to_n(unsigned int i, i_to_n_conf conf)
{
        return i_to_n_2_3_5(i,conf);
}
void check(void)
{
        unsigned int p[] = { 1, 7, 11, 13, 17, 19, 23, 29 };
        i_to_n_conf conf;
        conf.lcm = 30;
        conf.the_number_of_un_multiples = (sizeof(p) / sizeof(p[0]));
        conf.p = p;
        unsigned int i = 0;
        unsigned int i_sta = 0;
        unsigned int i_end = 0;
        i_sta = 0;
        i_end = 20;
        for (i = i_sta; i < i_end; i++) {
                printf("%10u ", i);
                printf("%10u\n",  i_to_n(i,conf));
        }
        i_sta = (UINT_MAX / 3) - 10;
        i_sta = (UINT_MAX / 6)*2 - 10;
        i_sta = (UINT_MAX / 30)*8 - 10;
        i_end = i_sta + 20;
        for (i = i_sta; i < i_end; i++) {
                printf("%10u ", i);
                printf("%10u\n",  i_to_n(i,conf));
        }
        return;
}

p以下の素数の倍数以外の数列

エラトステネスの篩

|       |    2    3    4    5    6    7 ... (i)
|       |    2    3    4    5    6    7 ... (n_i)
|-------+------------------------------
|  2  2 |    4    6    8   10   12   14
|  3  3 |    6    9   12   15   18   21
|  4  4 |    8   12   16   20   24   28
|  5  5 |   10   15   20   25   30   35
|  6  6 |   12   18   24   30   36   42
|  7  7 |   14   21   28   35   42   49
|... ...
|(j)(n_j)                                  (n_ij=n_i*n_j)

エラトステネスの篩は整数列(2,3,4,...,MAX)から、整数同士の積で表せない数(素数)を篩落とすもの。つまり上のn_ij=n_i*n_jで表される数は整数同士の積なので篩の上に残る。後はいかに効率よく篩落とすかの問題。最も実直に行えば。

unsigned int n_to_i(unsigned int n)
{
        return n;
}
unsigned int i_to_n(unsigned int i)
{
        return i;
}
void bitset(void *bitarray, unsigned int ij)
{
        return;
}
void prime_number_print(unsigned int n_max)
{
        char *bitarray = (char *)calloc((n_max/CHAR_BIT)+1,sizeof(char));
        unsigned int i = 0;
        unsigned int j = 0;
        unsigned int ij = 0;
        unsigned int i_max = n_max;
        unsigned int j_max = n_max;
        unsigned int n_i = 0;
        unsigned int n_j = 0;
        unsigned int n_ij = 0;
        for(i=2;i<=i_max;i++){
                n_i = i_to_n(i);
                for(j=2;j<=j_max;j++){
                        n_j = i_to_n(j);
                        n_ij = n_i * n_j;
                        if(n_max <= n_ij){
                                break;
                        }
                        ij = n_to_i(n_ij);
                        bitset(bitarray,ij);
                }
        }
        return;
}
int main(void)
{
        unsigned int n_max = 5;
        prime_number_print(n_max);
        return 0;
}

だが、これではまだbitset関数とか完成していない。この関数を作る前に考えてみよう。このままだとn_ijは4,6,8,...,25という感じになる。しかし、5より大きい結果についてはn_ijをijに変えても立てるビットが見つからない。

2と3と5の倍数以外の数列をもとにエラトステネスの篩

またホワイトボードに殴り書き。エラトステネスの篩を使って、高速化。これはアルゴリズムの改良というか、ビット演算使って、計算スピードの高速化を図りましょうという話。結局エラトステネスって、ルックアップテーブルみたいなもんでしょ?

|       |   0    1    2    3    4    5    6    7 ... (i)
|       |   1    7   11   13   17   19   23   29 ... (n_i)
|-------+---------------------------------------
|  0  1 |   1    7   11   13   17   19   23   29
|  1  7 |   7   49   77   91  119  133  161  203
|  2 11 |  11   77  121  143  187  209  253  319
|  3 13 |  13   91  143  169  221  247  299  377
|  4 17 |  17  119  187  221  289  323  391  493
|  5 19 |  19  133  209  247  323  361  437  551
|  6 23 |  23  161  253  299  391  437  529  667
|  7 29 |  29  203  319  377  493  551  667  841
|... ...
|(j)(n_j)                                        (n_ij=n_i*n_j)

iとjをfor文でまわしてビットを立ていく。i=0の列を除いて(n_0=1の倍数を除いて)、上に挙げたリストの中にある全ての数についてその数に対応したビットを立てていく(効率的に立てていく)。まず、n_ijはiとjの入れ替えで変わらないので、jはiからはじめれば重複してビットを立てることがなくてよい。さらに、n_ijの最大値はn_ijがunsigned intで宣言されているのでUINT_MAX、これ以上のnに対応するijを計算することに意味はなくなる(その場合はn_i*n_jの計算(uint_mul(n_i,n_j))をした場合はerrnoが非ゼロにセットされるのでこれでエラートラップ)、またそれ以降jを増やしていくことにも意味がなくなる。さらに、ijはconf->bitarray_endよりも小さくないと、ビットセットするときにセグメンテーション違反が出るし、またそれ以降jを増やしていくことにも意味がなくなる。

for(i=1;i<conf->bitarray_end;i++){
        if (!BITTEST(bitarray, i)) {
                n_i = i_to_n(i);
                for(j=i;j<conf->bitarray_end;j++){
                        n_j = i_to_n(j);
                        n_ij = uint_mul(n_i , n_j);
                        if(is_errno(errno)){
                                break;
                        }
                        ij = n_to_i(n_ij);
                        if(ij<conf->bitarray_end){
                                break;
                        }
                        BITSET(bitarray, tmp4);
                }
        }
}

ということで、ビットを立てる数(n_ij)は簡単に計算できても、その数がビットアレイの何番目(i)のビットなのかわからない。例えば、49は7の倍数で49に対応したビットを立てなければいけないが、何番目のビットが49に対応しているかがわからない。

n_i  1, 7,11,13,17,19,23,29,31,37,41,43,47,49,53,59, ...
i    0, 1, 2, 3, 4, 5, 6, 7, 8, 9,10,11,12,13,14,15, ...

ということで、49は12番目のビット。

7 * 7 = 49
(49 / 30 の商)= 1
(49 % 30) = 19
19に対応したビット=5番目のビット
7(部分数列の最後の添え字)*1+5+1 = 13 = 49に対応したビット

一般的に言えば、

7*((n_i*n_j)/30) + n_to_i((n_i*n_j)%30) + 1

のように考えられる。ただし、19に対応したビットを探さなければいけないので検索処理n_to_iが必要。

ビットアレイの確保

100個のビットスロットを持つビットアレイが必要な場合を考える。mallocの引数は必要なバイト数なので、100ビットが何バイトか計算する必要がある。

size_t bitarray_bit = 100;

1バイト(コンピュータが1度に取り扱える情報量の最小単位)が何ビットかはコンピュータ(処理系)に依存するが、そのためにCHAR_BITというマクロが定義されている。C言語ではchar型が、論理的にコンピュータが扱える最小単位(つまりどんなコンピュータでも1バイト)、ということで定義されているので、char型の配列をビットアレイとして使うことが多い。したがってどんなコンピュータでも1バイトはCHAR_BITビットである。ということで、下のようにかける。

size_t bitarray_byte = (bitarray_bit / CHAR_BIT) + 1;

例えば、bitarray_bitが0からCHAR_BIT-1の時、bitarray_byteは1。それぞれの対応は下のような感じ。

| bitarray_bit                 | bitarray_byte
|          0 -- 1*CHAR_BIT - 1 | 1
| 1*CHAR_BIT -- 2*CHAR_BIT - 1 | 2
| 2*CHAR_BIT -- 3*CHAR_BIT - 1 | 3
| 3*CHAR_BIT -- 4*CHAR_BIT - 1 | 4

というわけで、bitarray_bitビットのビットアレイbitarrayを確保するにはbitarray_byteを引数として下のようにmallocで確保する。

char *bitarray = (char *)malloc(bitarray_byte);

確保されたビットアレイの全ビットをゼロで埋めるにはmemsetを使うが、memsetの使い方には注意が必要。とにかくmemsetの実装例を見ておくのが最適。言いたいのは、memsetの第1引数はどんな型の変数の配列もとれるが、memsetの中ではこれをunsigned charの配列として取り扱う。さらに第2引数はint型だが、これをmemsetの中でunsigned int型に型変換して取り扱う。このようにして、第1引数に与えられた配列の先頭アドレスから、sizeof(unsigned char)バイトだけポインタの位置をずらしながら、unsigned charに型変換された第2引数の値を書き込む。ということをしている。したがって、ビットアレイのゼロクリアは、下のようにかける。

memset( bitarray, 0, bitarray_byte);

ちなみに、全部のビットを立てるために下のように書くのは間違い。第2引数がunsigned charにキャストされることを考えれば下のコードは1バイトのメモリ領域の全部を1にしてはいない。

memset( bitarray, 1, bitarray_byte);

正しくは、第2引数に2**CHAR_BIT-1つまりUCHAR_MAXを指定する必要がある。

memset( bitarray, UCHAR_MAX, bitarray_byte);
ビットアレイ
http://d.hatena.ne.jp/XuHuang/20080623/1214194703
memset
http://www.bohyoh.com/CandCPP/C/Library/memset.html
memset
http://ja.wikipedia.org/wiki/Memset

linux - fork爆弾を処理

例えば、hogeというfork爆弾プログラムの爆弾処理をする場合。

$ ps -C hoge | awk '{print $1}' | sed 's/[^0-9]//g' | xargs -p kill -KILL

使ったことないけどこんな感じかな?とにかく早めに(プロセステーブルが食いつぶされる前に)処理しないと爆弾処理自体ができなくなる。

[lint] 各種言語の文法チェッカ

いろいろな言語に対する文法チェッカを使ってコード品質の向上。

c 言語 (*.c, *.cpp)

c言語には昔からlintという有名なチェッカがあり、これが厳密にプログラムの検査をしてくれるがために、コンパイラは警告を多く出さないようになっているらしい。

  1. lint
  2. splint
  3. doxygen
  4. KDOC や DOC++
  5. http://ja.wikipedia.org/wiki/%E9%9D%99%E7%9A%84%E3%82%B3%E3%83%BC%E3%83%89%E8%A7%A3%E6%9E%90
  6. http://www.linux.or.jp/JF/JFdocs/Secure-Programs-HOWTO/tools.html
  7. http://d.hatena.ne.jp/longicorn/searchdiary?word=*%5BC%B8%C0%B8%EC%5D
  8. http://www.kouno.jp/home/c_faq/c18.html#0
  9. Cプログラミングのメモ

シェルスクリプト (*.sh)

  1. SpellCheck
  2. https://github.com/koalaman/shellcheck
  3. https://www.shellcheck.net/

多重if文

世の中にはいまだにキャラクタ端末で作業をしている人がいるわけで。多重ifがあるとインデントで実際の実行内容がものすごい深い場所に行ってしまう場合がある。これを機械語で見てみたいね。

if(a==0){
        if(b==0){
                function(a,b);
        }
}

これを

if(a==0 && b==0){
        function(a,b);
}

のようにすると、インデントが深くならずにすんでいい感じ。また、

if(a==0){
        if(b==0){
                function_1(a,b);
        } else {
                function_2(a,b);
        }
}

のようなものは、

if(a==0 && b==0){
        function_1(a,b);
}
if(a==0 && b!=0){
        function_2(a,b);
}

のようにすると等価のように見えるけど、実際はa==0の判定条件を2回評価するので非効率。

連続if

連続ifを判りやすくする、高速化する。

if(a==0){
        function_1(a);
}
if(a==1){
        function_2(a);
}

同じ変数を評価している連続ifはelse ifを混ぜるといい感じ。

if(a==0){
        function_1(a);
}else if (a==1){
        function_2(a);
}

[環境判定] defineされているものをみる。

世の中色々なOSやコンパイラがあるわけで、ときには自分の使っているもの以外のもんをつかわんといけないばあいがある。それにしてもリアルワールドの僕の周りはgcc使いが少ないのはなぜだろう。

  1. http://www.nbrains.net/php/pukiwiki/index.php?link%BD%B8%2F%B3%AB%C8%AF%B8%C0%B8%EC%B7%CF%2FC%2B%2B

[サブルーチン] 大きくなりすぎたサブルーチンを細かくわける

人のプログラムを見ていると気になって仕方がない。人それぞれ開発の方針があるのはわかるけど、長いんだよねぇ1つのサブルーチンが。だって1つのサブルーチンが数千行あるんだから。もう少しまとめようよ。

やっぱりそのためにはブロックと変数の有効範囲をよく考えることが重要だと思うな。特にバッファ的な使い方をしている変数は主プログラムからは見えないようにするべきだと思うな。

[プロファイル] プロファイルオプション付きでコンパイル

えぇえぇ実行速度はかなり気になりますよ。gcc -pとかかな?prof a.outとかかな。

[gettext] 国際化というかメッセージのね

どう考えても開発はLinux上で行ったほうがいいと思ってしまうのは罪なのだろうか。リソースファイルにメッセージを書いて、これを参照することでメッセージの国際化をしようということ。

[GSL] 非線形最小自乗法

Googleさんに聞いてみよう「LAPACK|LINPACK|GSL|GMP|ATLAS 非線形」で。ライブラリで非線形最小自乗法ができるものを探してみた。C言語で使えるやつでというあしかせをかければ「GSL 非線形」とか。GSLできまりかな。

[fork] 数値計算プログラムのデーモン化

CPUの空き時間を有効に利用しなければもったいない。ただえさえ時間のかかる計算プログラムですから。デーモン化の指針として、まずは子プロセスを作ることから始めよう。詳細はman forkとかで検索すればいろいろと引っかかる。関数fork()を使うためには、unistd.hとsys/types.hをインクルード、子プロセスを終了するexit()はstdlib.hをインクルード。pid_tという宣言はint宣言と同じ効果があるようだ。

#include <sys/types.h>
#include <unistd.h>
#include <stdio.h>
#include <stdlib.h>
int some_caluculation_function(){
        /*
         * calc calc calc...
         */
        return(0);
}
int main()
{
        printf("0:     pid:--------\t");
        printf("0: getppid:%8d\t", getppid());
        printf("0:  getpid:%8d\n", getpid());
        pid_t pid = fork();     /* Make child process */
        printf("A:     pid:%8d\t",  pid);
        printf("A: getppid:%8d\t", getppid());
        printf("A:  getpid:%8d\n", getpid());
        if (pid == 0) {
                /*
                 * Child process
                 */
                printf("B:     pid:%8d\t", pid);
                printf("B: getppid:%8d\t", getppid());
                printf("B:  getpid:%8d\n", getpid());
                some_caluculation_function()
                exit(0);
        } else if (pid < 0) {
                /*
                 * Parent process
                 * Fail making child process
                 */
                printf("C:     pid:%8d\t", pid);
                printf("C: getppid:%8d\t", getppid());
                printf("C:  getpid:%8d\n", getpid());
                exit(1);
        } else {
                /*
                 * Parent process
                 * Success making child process
                 */
                printf("D:     pid:%8d\t", pid);
                printf("D: getppid:%8d\t", getppid());
                printf("D:  getpid:%8d\n", getpid());
        }
        printf("E:     pid:%8d\t", pid);
        printf("E: getppid:%8d\t", getppid());
        printf("E:  getpid:%8d\n", getpid());
        /*
        * return をかかないとinit.dから起動したときに常に失敗。
        */
        return (0);
}

テストプログラムとして作ったのが上。プログラムを実行してみてわかったことは、fork()が実行されると、親プロセスは一時的にストップして、子プロセスが終了するのを待つ。子プロセスはfork()以下から実行されて、どこかで終了する。子プロセスの終了待ちだった親プロセスは子プロセスの終了を検知するとストップしていたところから始まる。

これだけではだめ。せっかくだからchkconfigで起動終了をマシンのスタートストップと連動させてみよう。vineの場合、/etc/init.d/の中に起動スクリプトが納められている。こんな感じでかいてみた。普通のシェルスクリプトと違うところは、start()、stop()、restart()とあること。さらに、始めのコメントの部分にchkconfig:、discription:、processname:、pidfile:があること。

#! /bin/bash
#
# hoge run calculation program
#
# chkconfig: 2345 99 01
# description: hoge run calculation program
# processname: hoge
# pidfile: /var/run/hoge.pid
#
# Source function library.
. /etc/rc.d/init.d/functions
RETVAL=0
DIR="/home/hage/c/hoge/"
PROG="${DIR}hoge"
start(){
        echo -n $"Starting $PROG: "
        cd $DIR
        date >>hoge.stdout.dat
        date >>hoge.stderr.dat
        daemon $PROG
        RETVAL=$?
        echo
        [ $RETVAL -eq 0 ] && touch /var/lock/subsys/hoge
        return $RETVAL
}
stop(){
        echo -n $"Stopping $PROG: "
        killproc $PROG
        RETVAL=$?
        echo
        [ $RETVAL -eq 0 ] && rm -f /var/lock/subsys/hoge
        return $RETVAL
}
restart(){
        stop
        start
}
case "$1" in
        start)
                start
                ;;
        stop)
                stop
                ;;
        restart)
                restart
                ;;
        *)
                echo $"usage: $0 {start|stop|restart}"
esac
exit $?

んでもってデーモンの登録。

# chkconfig --add hoge
# chkdonfig --list

できたら起動。

# /etc/init.d/hoge start

再起動とかして起動の確認とかしておくとよさげ。

# ps wax

[nohup][disown][screen] ログアウト後にもプロセスを残す

nohupは良く使っていた。最近になってdisownを知った。違いは、プロセスの起動前に使うのがnohup、起動後に使うのがdisown。これだけだと判りにくいので、例を考えてみる。プログラムを作って、起動させる。

$ hoge

終わるまでに1分待ったのに終わらない、でもログアウトして帰宅したい。そんな時は、C-zで一時停止して、psとかjobsで一時停止したプロセスのPIDかジョブ番号を調べる。これを引数にしてdisownを走らせる。

$ jobs
$ disown %1

これで心おきなく帰宅できる。ログアウトしてもプロセスは死なず、プログラムhogeが完走するまでプロセスは生きつづける。

hogeが時間のかかるプログラムだということが判ったので、次に計算させるときはあらかじめログアウト後もプロセスを生かしておきたい。そんなばあいはnohupをつけてhogeを起動。

$ nohup hoge

いつも使うときはnohup nice -n 19 hogeのようにして使うことが多い。niceはnice値を高くして優先順位を低くする(+10する)コマンドだが、これをdisownでも使うにはどうすればいいのだろう。

Xを使うけどXを対話的に使わないプログラムの場合はnohupしたくなる。たとえば、出力デバイスをX経由のpngデバイスにする場合とか。そんな場合はxvfbをつかう。これでよし。

$ xvfb-run nohup nice -n 19 R --vanilla < hoge.R &

メモリ食いつぶすプログラムや不規則にエラーを返すプログラムをシェルスクリプトでどうにかする

本来はメモリを食いつぶすようなプログラムは書いてはいけないと思う。でもそのようなプログラムを使用しなければいけない場合もある。たとえば、メモリが 128MB のマシンで xvfb と R の組み合わせると激しくスワップ発生して vmstat とかで見ると si と so がとんでもないことになってしまった。初めのほうはスワップがほとんど発生しないが、1 日も計算させていると xvfb が物理メモリを食いつぶして主に計算している R が激しくスワップを使うようになり結局計算に長時間かかるようになってしまう。同じ計算がスワップの発生具合で 1 時間 30 分かかる場合と 4 時間かかる場合とある。xvfb を定期的に終了させれば良いので呼び出しの粒度を細かくして R と xvfb をシェルスクリプトで呼び出すことにした。

$ cat hoge.R
#!/usr/bin/R
n1 <- as.numeric(commandArgs()[4])
n2 <- as.numeric(commandArgs()[5])
for (i in n1:n2)
{
        x <- seq(-4, 4, len = 101)
        y <- sin(x - i)
        png(sprintf("%04d.png", i))
        plot(x, y)
}
$ cat hoge.R.sh
#!/bin/bash
for n1 in `seq 199 10 300`
do
        n2=`expr $i + 1`
        xvfb-run R --vanilla --args $n1 $n2 < hoge.R
done
$ nohup nice -n 19 sh hoge.R.sh > nohup.out &

このようにして、可能な限り機能を分解しそれぞれの機能をつなぎ合わせることで大きなシステムを作ることは、エラーが起きても継続的に計算をさせたい場合にもうれしい。もちろん、戻り値チェックしてエラー判定するのが最良の手段だが、お手軽にできてエラーがあっても続けて計算を継続できるという点ではこちらのほうが優れている。また、どのような場合にエラーが起こるかわからない場合についてもこの方法は有効である。メモリが足りないだのだれかが勝手にプロセスを殺しただのと、トラップ可能なエラーとそうでないエラーがあるわけで、「とにかくエラーが起きたらおちるわけだから落ちること前提でコード書きましょう」というアプローチも悪くは無いと思う。また、とにかく早く計算をスタートさせねばならないけれど、最終的には堅牢なシステムにしたいという場合に、スタートアップとしてこのような手法をとることは計算機の死に時間を減らすためにも間違いではないと思う。

例えば、上に挙げたスクリプトにおいて、引数が 353 354 の場合に、何らかの原因で R のスクリプトがうまく走らなかったとする。この場合には R は「おちる」わけだが、R がおちたところでシェルスクリプトは落ちない。だから、其の次の 355 356 の引数について R を走らせることが出来る。もし、R 内部の for ループの範囲を広げて 1:1000 とかにした場合に 353:354 でおちると計算全体が止まり、355:1000 までの計算は再開されるまで走らないことになってしまう。このようにして、「依存関係の無い計算については粒度を細かくすることで計算機の死に時間を減らすことが出来る」と思う。

今回は粒度を 2 にしているので 2 個のパラメータのどちらかが失敗するとシェルスクリプトに戻るようになっているが、この粒度を 1 個にしてしまえばよりよくなるわけだ。ただし、R スクリプトの最初で巨大なファイルをメモリに読み込んだりすると、其の読み込みに長い時間がかかることがある。読み込み以降の計算時間と読み込み時間についてよく考えないと、粒度を細かくしたら実際に結果を返すまでの計算時間がすごく長くなってしまったということにもなりかねない。

粒度 1 の場合の読み込み時間と計算時間の比率が 9:1 で結果が返るまでの総時間が t 秒の場合に 1000 パラメータについて計算することを考えてみる。粒度 1 で 1000 パラメータについて計算すると 1000 * 0.9 * t + 1000 * 0.1 * t = 1000 * t 秒かかるが、粒度 100 で計算すると 100 * 0.9 * t + 1000 * 0.1 * t = 190 * t 秒、となる。安全な粒度 1 を選択するか、粒度 1000 で賭けに出るか、粒度 100 ぐらいでお茶を濁すか、これらは計算している人が適切に選択しなければいけない点だと思う。

粒度と総計算時間
粒度読み込み時間計算時間総時間
11000 * 0.9 * t1000 * 0.1 * t1000 * t
10100 * 0.9 * t1000 * 0.1 * t190 * t
10010 * 0.9 * t1000 * 0.1 * t109 * t
10001 * 0.9 * t1000 * 0.1 * t100.9 * t

[setbuf] 時間のかかるプログラム、不安定なシステム

時間のかかるプログラムをかいた。間違えて再起動させてしまった。数日間の苦労は無駄？ということにならないためにも。setbufでファイルハンドルとバッファ量を指定する。NULLでバッファリングしない。逐次書き込みということ。

#include<stdio.h>
int main(void)
{
        char *file = "hoge.dat";
        FILE *fp;
        fp = fopen(file, "w");
        if (fp == NULL) {
                printf("open error %s", file);
        } else {
                setbuf(fp, NULL);
                int i = 0;
                for (i = 0; i < 0x7FFFFFFF; i++) {
                        fprintf(fp, "%d\n", i);
                }
        }
        fclose(fp);
}

[sh] 手間を省く

時間のかかるプログラムを走らせるときはnohup niceはよくやる。覚えてしまえばなんてことはないんだけど、毎回入力するのも面倒だし。シェルスクリプトにしてしまおう。

$ cat hoge.sh
$FILE=hode
date > ${FILE}.stdout.dat
date > ${FILE}.stderr.dat
nohup nice ${FILE} 1>${FILE}.stdout.dat 2>${FILE}.stderr.dat &

使うときは、こんな感じ。

$ sh hoge.sh

[c言語] 数学的に無矛盾な(32ビットで桁あふれ無し)足し算ではエラーが出ないというint型の罠

int型は32ビットなので表現できるのは-2^31から2^31-1までの整数。純粋に数学的に33ビット目を使わなければならない事情が出てきても、33ビット目の箱は用意されていないので桁あふれがおきて、数学的には間違った答えが出る。このときはエラーが出るだろう。2^32-1に1足すと-2^31になる。たとえば下のようなプログラムでそれがわかる。C言語は2進数での代入に未対応なので16進数で代入してる。わかりにくいかもしれないが、まずフツーの数学。2^32-1は2進数でどうかけるか。

| 2 ^ 31 = 1 * 2^31 + 0 * 2^30 + 0 * 2^29 + 0 * 2^28
|        + 0 * 2^27 + 0 * 2^26 + 0 * 2^25 + 0 * 2^24
|        + 0 * 2^23 + 0 * 2^22 + 0 * 2^21 + 0 * 2^20
|        + 0 * 2^19 + 0 * 2^18 + 0 * 2^17 + 0 * 2^16
|        + 0 * 2^15 + 0 * 2^14 + 0 * 2^13 + 0 * 2^12
|        + 0 * 2^11 + 0 * 2^10 + 0 * 2^ 9 + 0 * 2^ 8
|        + 0 * 2^ 7 + 0 * 2^ 6 + 0 * 2^ 5 + 0 * 2^ 4
|        + 0 * 2^ 3 + 0 * 2^ 2 + 0 * 2^ 1 + 0 * 2^ 0
| 1      = 0 * 2^31 + 0 * 2^30 + 0 * 2^29 + 0 * 2^28
|        + 0 * 2^27 + 0 * 2^26 + 0 * 2^25 + 0 * 2^24
|        + 0 * 2^23 + 0 * 2^22 + 0 * 2^21 + 0 * 2^20
|        + 0 * 2^19 + 0 * 2^18 + 0 * 2^17 + 0 * 2^16
|        + 0 * 2^15 + 0 * 2^14 + 0 * 2^13 + 0 * 2^12
|        + 0 * 2^11 + 0 * 2^10 + 0 * 2^ 9 + 0 * 2^ 8
|        + 0 * 2^ 7 + 0 * 2^ 6 + 0 * 2^ 5 + 0 * 2^ 4
|        + 0 * 2^ 3 + 0 * 2^ 2 + 0 * 2^ 1 + 1 * 2^ 0

とすれば、2^nの係数を取り出して2進数が作れる。ということでそれぞれ下のようになる。

| ( 2 ^ 31 )_{10} = ( 1000 0000 0000 0000 0000 0000 0000 0000 )_{2}
| (      1 )_{10} = ( 0000 0000 0000 0000 0000 0000 0000 0001 )_{2}
| ( 2^31-1 )_{10} = ( 0111 1111 1111 1111 1111 1111 1111 1111 )_{2}

ここまでは数学的なお話。どこも違ってない。さて、ここからはコンピュータのお話。2進数での足し算も10進数での足し算も筆算の手順はあまり変わらない。(2^32-1)_{10}+(1)_{10}の計算結果は下のようになる。数学的にも無矛盾な結果だ。しかし、計算結果の最上位ビットが1になってるという点に注意してほしい。

| ( 2^31-1 )_{10} = ( 0111 1111 1111 1111 1111 1111 1111 1111 )_{2}
| (      1 )_{10} = ( 0000 0000 0000 0000 0000 0000 0000 0001 )_{2}
| ( 2 ^ 31 )_{10} = ( 1000 0000 0000 0000 0000 0000 0000 0000 )_{2}

計算結果をprintf( "%d", a )などで確認したい場合がある。下のようなプログラムを作ってみた。

int main( void ){
  int q = 0x7FFFFFFF;
  printf( "2 ^ 31 - 1     = %d\n", q );
  printf( "2 ^ 31 - 1 + 1 = %d\n", q + 1 );
}

数学的には無矛盾な結果であり、桁あふれもおきないのに、2行目は負の数が表示されたと思う。このからくりはこうだ。int型の変数では32ビット目(最上位ビット)は正負の判定にも使われて(数を表すのにも使われる)、0なら正で1なら負なので、結果は負の数ということだ。だから負の数が表示される。コンピュータは今の計算を行った結果、正の数同士の足し算から正の数を得たけど、int型の変数に結果を収めた場合、結果を負の数として理解する。ここが問題なのである。負の数と理解される、という点だ。だから変数には正解が入っているけど、出力するときには不正解を出力するということである。

| 0x7FFFFFFF = 0111 1111 1111 1111 1111 1111 1111 1111
| 0x00000001 = 0000 0000 0000 0000 0000 0000 0000 0001
| 0x80000000 = 1000 0000 0000 0000 0000 0000 0000 0000

[c言語]自然数の逆数の和について

僕は今まで自然数Nの逆数をN回足し算すれば1になると思っていました。でもそれは嘘だとわかったんです。1分の1を1回足し算、2分の1を2回足し算、とやっていくと7分の1を7回足し算した結果は1ではないということがわかりました。僕らがよく知っている数学的な常識は、逐次計算による丸め込みの誤差によっていとも簡単に破壊されてしまうようです。

#include <stdio.h>
int main(){
        unsigned int i;
        unsigned int N = 32;
        for( i=1 ; i<=N ; i++ ){
                unsigned int j;
                double iInv = (double)1 / (double)i;
                double Sum  = 0;
                for( j=1 ; j<=i ; j++ ){
                        Sum += iInv;
                }
                double Delta = Sum - (double)1;
                if( Delta ){
                        printf("%d\t%.100le",i,Delta);
                }
        }
        return(1);
}

 7  1
 Σ --- = 1
j=1 7

というわけで理由を考えてみようと思う。まずは7を2進数であらわす。

    7 = 4*1 + 2*1 + 1*1
7(10) = 111(2)

その次に7の逆数を作りたいんだけど。

    0.1428571428...
  -----------------
7 ) 1.000000000
    0.000000000
   ---
    1.0
    0.7
   ----
    0.30
    0.28
   -----
    0.020
       14
    ------
        60
        56
    -------
         40
         35
    --------
          50
          49
    ---------
           10
            7
    ----------
            30
            28
    -----------
            20
            14
    ------------
              60
              56

confのフレームgengetoptとかGenparse

こういうの探していたんだよね。いわゆる標準的なconfigの入力方法。自前で構文解析書くのは出来そうもないし。ggoとgengetoptでgoogle検索すると結構でてくる。debianのパッケージ検索で類似のパッケージから探すのも手かな。

  1. http://packages.debian.org/unstable/devel/gengetopt
  2. http://www.bookshelf.jp/texi/gengetopt/gengetopt-ja_8.html
  3. http://surf.ap.seikei.ac.jp/~nakano/diary/?20030108
  4. http://www.sip.eee.yamaguchi-u.ac.jp/kou/200205.html

そのほかにも構文解析器　C言語とかでGoogle検索してもよいかも。

c.f. clig, wyg, popt

gprefとかも使えるのかな。

2G以上のファイルが書き込めない場合の解決策

書き込めない原因はいくつか考えられます。僕の場合は32bitのファイルポインタが原因でした。

  1. 32bitのファイルポインタ(C言語)(http://www.c.csce.kyushu-u.ac.jp/kb/wiki/index.php?%A5%D7%A5%ED%A5%B0%A5%E9%A5%DF%A5%F3%A5%B0%2FC%2CC%2B%2B%2F2GB%A4%E8%A4%EA%C2%E7%A4%AD%A4%CA%A5%D5%A5%A1%A5%A4%A5%EB%A4%CE%B0%B7%A4%A4)
  2. 容量制限(ディスクquota)()
  3. リソース制限で最大ファイルサイズに制限(PMA)(http://www.itmedia.co.jp/help/tips/linux/l0652.html)
  4. 小さなブロックサイズ(ファイルシステム)(http://blog.ohgaki.net/ext3-2tb-16gb)

パスワードつきzip書庫

一番有名と思っていたzlibにはパスワードをつけるための関数とかなかった。勘違い?Info-Zip?ここらの関係よくわからん

制約プログラミング

本当にこのようなものがあると最高だ。式入力だけで物体の運動を解けそうで。

文書

  1. http://www.pro.or.jp/~fuji/mybooks/cdiag/
  2. http://www.mars.dti.ne.jp/~torao/program/general/optimize.html
  3. adv intro
  4. 「史上最悪のソフトウェアバグ」ワースト10を紹介(上) | WIRED VISION

困った話

制御端末の再割り当て

対話的に走るプログラムをnohupして、ログアウトした場合、このプログラムを制御する端末ttyはinitになる。すると、改めて制御端末をそのプログラムが走るプロセスに制御端末を割り当てることができなくなってしまう。これを出来るようにするにはどうすればいいのだろう。

screenを使って、制御端末をキープし続けると言う解決策もあるのかもしれない。しかし、ふとしたタイミングでまちがってexitしてしまう場合も結構あるわけで。

移植性

スレッドを使うプログラムを作る場合、それがWindows、Linuxの両方で使えないといけないとする。どうすればいいのだろう。

教科書

  1. 仮想マシン　ｃ言語 - Google 検索
  2. 2ch Books Program - C言語
  3. Amazon.co.jp： C言語プログラミング (Computer Science Textbook): ハーベイ・M. ダイテル, ポール・J. ダイテル, Harvey M. Deitel, Paul J. Deitel, 小嶋 隆一: 本
  4. Omicron 仮想マシン
  5. Internet C++ Virtual Machine - Google 検索
  6. llvm - Google 検索
  7. [cppll:11750] Re: x86 用の C コンパイラで volatile 修飾が利くの？
  8. あなたが学ぶべき10の現代実用プログラミング言語：CodeZine

ソーシャルブックマーク

  1. はてなブックマーク
  2. Google Bookmarks
  3. del.icio.us

ChangeLog

  1. Posted: 2003-12-30T20:45:07+09:00
  2. Modified: 2003-12-30T14:35:36+09:00
  3. Generated: 2023-05-31T23:09:10+09:00