2007年11月 8日 (木)

擬似的末尾再帰最適化

なんか中国語みたいなタイトルになってますがお気にせずに。
コンパイラには(インタプリタにも?)末尾再帰の最適化がありますが、擬似的に手動でかけないかとやってみた。ちなみに言語はC言語。

こういう0~nまでの和を出す再帰関数を最適化してみる。

long long func(int n)
{
    if (n == 0)
        return 0;
    else
        return n + func(n-1);
}

自分の理解だとスタックを積まないで関数の先頭にgotoするというのが末尾再帰の最適化。なので、再帰するところで関数を呼び出さずに値を更新して先頭に戻ればよい。

long long func2(int n)
{
    long long ans = 0;
f:
    if (n == 0) {
        return ans;
    }
    ans += n;
    n--;
    goto f;
}

精度があんまりよくないclock関数で、テキトーにテストする。

int main()
{
    clock_t start, end;
    int i;

    start = clock();
    for (i = 0; i < 10000; i++) {
        func(65536);
    }
    end = clock();
    printf("%f\n", (double)(end - start) / (double)CLOCKS_PER_SEC);

    start = clock();
    for (i = 0; i < 10000; i++) {
        func2(65536);
    }
    end = clock();
    printf("%f\n", (double)(end - start) / (double)CLOCKS_PER_SEC);

    return 0;
}

Mac OS X, gcc 4.0.1で実験した結果が以下。

[~]% gcc test.c
[~]% ./a.out
12.750000
1.950000
[~]% gcc -O2 test.c
[~]% ./a.out
1.770000
0.740000
[~]% gcc -O3 test.c
[~]% ./a.out
1.900000
0.250000

結構違いがでた。たぶん他の環境でも擬似的に最適化した方が速いと思う。
あと、最適化した方はスタックオーバフローしない。
今回は簡単な関数でやったけど、末尾再帰の部分と関数先頭を少し書き換えるだけなので、他の再帰関数にも結構簡単に適用できる方法かもしれない。

一応まとまったファイルは「test.c」です。コメントゼロでごめんなさい。

| | コメント (0) | トラックバック (0)

2007年10月 5日 (金)

シンボルテーブルのFUNCについて

naoyaさんのところで見かけて気になったので調べてみた。

などをみてみると、シンボルテーブルのTypeのFUNCはリンクの辺りで必要そう。

そこで、

int add(int x, int y)
{
    return x + y;
}

int sub(int x, int y)
{
    return x - y;
}

をfunc.cとして作成して、

$ gcc -S func.c

としてアセンブリコードを作成。

.globl add
    .type   add, @function

となっているところを

,globl add
    .type    add, @notype

と変更する。それから共有ライブラリを作成する。共有ライブラリを参考に

$ gcc -fPIC -g -c -Wall func.s
$ gcc -shared -Wl,-soname,libfunc.so.1 -o libfunc.so.1.0.1 func.o -lc
$ ln -s libfunc.so.1.0.1 libfunc.so.1
$ ln -s libfunc.so.1.0.1 libfunc.so

一応共有ライブラリのaddの属性の確認をする。

$ readelf -s libfunc.so | grep add
     6: 000003cc    11 NOTYPE  GLOBAL DEFAULT   10 add
    49: 000003cc    11 NOTYPE  GLOBAL DEFAULT   10 add

確かにNOTYPEとなっています。
次にこの共有ライブラリを使用するプログラムをmain.cとして作成します。

     1  #include <stdio.h>
     2
     3  int add(int, int);
     4  int sub(int, int);
     5
     6  int main()
     7  {
     8      int x, y;
     9
    10      x = 8;
    11      y = 4;
    12
    13      printf("%d\n", add(x, y));
    14      printf("%d\n", sub(x, y));
    15
    16      return 0;
    17  }

さて、ここからが本番です。

$ export LD_LIBRARY_PATH=.
$ gcc main.c -L. -lfunc
$ ./a.out
セグメンテーション違反です

となりました。main.cのaddをしている行を消して、

$ gcc main.c -L. -lfunc
$ ./a.out
4

となりsubの実行結果が表示されます。なので、シンボルテーブルのTypeのFUNCは動的リンクに必要にであることが分かりました。mainにFUNCをつける必要はないみたいですね。FUNCじゃなくてEXPO(export)とかの方が分かりやすかったりするのかなとか思ったりしました。

| | コメント (0) | トラックバック (1)

2007年8月 4日 (土)

C言語で知らなかったこと

たいしたことじゃないんですけど、C言語での書き方で新しく知ったので書いてみる。
まずはサンプルをprintfの引数に注目。

#include <stdio.h>

int main()
{
    int i;

    printf("%d\n", (i = 3, i * 3));
    printf("%d\n", (assert(i == 3), 10));

    return 0;
}

というプログラムの実行結果が

9
10

となる。
一個目のprintfの引数で、

  1. iに3が代入される
  2. 3が代入されているiに3をかける

といったように()の中の式がちゃんと評価されている。んでもって最後のが()の最終的な評価の値になっている。
これはSolaris付属?のCコンパイラでも動いたので、GNUの拡張ってわけでもなさそう。

使える場面は、とりあえず二個目のprintfで書いたような、assertを絡めるときくらいしか思いつかないけど、おもしろいうごきだと思う。

| | コメント (2) | トラックバック (0)

2007年7月21日 (土)

はてなスター設置その後

前回の記事にてはてなスターの設置についてのエントリーを書きました。
なにやらブックマークしてくれる人がいたりはてなスター日記のほうにもほんのちょっと取り上げていただいている様子

そのコメントの中に、「ただし、このブログでは、Main Index(トップページ)にのみ設置している模様。」というものがありました。気づいてなかった・・・

というわけでいじってみました。不格好な方法かもしれないけれど解決しました。
まず、なんで一記事単位表示だとうまくいかないかについて書きます。

はてなスターが必要とする情報は、タイトルとpermalinkURLだけです。はてなスターでは、以下のように、h3要素の中にリンクが含まれている場合に、それをタイトルとpermalinkである、と判断します。
はてなスターをブログに貼り付けるより

とあるようにh3要素の中にリンクが必要になっているのですが、一記事単位はタイトルがリンクになっていないのです。

それで解決法ですが、

記事の検出をしているのは「Hatena.Star.EntryLoader」というオブジェクトの「loadEntries」メソッドです。このコードを上書きすることで、はてなスターに正しく記事のタイトルとpermalinkを認識させることができます。
はてなスターをブログに貼り付けるより

とのことですので、同ページにのっているものを参考に

<script type="text/javascript" src="http://s.hatena.ne.jp/js/HatenaStar.js"/>
<script type="text/javascript">
  Hatena.Star.Token = 'd1b02052474b7e28330ad1fbba7513eb57a1ebfe';
</script>
<script type="text/javascript">
  Hatena.Star.EntryLoader.loadEntries = function () {
        var entries = [];
        //var headers = document.getElementsByTagName('h3');
        var c = Hatena.Star.EntryLoader;
        var headers = c.getHeaders();
        for (var i = 0; i < headers.length; i++) {
            var header = headers[i];
            var a = header.getElementsByTagName('a')[0];
            var uri;
            if (a) {
              uri = a.href;
            }
            else {
              uri = Ten.DOM.getElementsByTagAndClassName("a","permalink",document)[0].href
            }
            var title = '';
            var cns = header.childNodes;
            title = c.scrapeTitle(header);
            var cc = c.createCommentContainer();
            header.appendChild(cc);
            var sc = c.createStarContainer();
            header.appendChild(sc);
            entries.push({
                uri: uri,
                title: title,
                star_container: sc,
                comment_container: cc
            });
        }
        return entries;
  }
</script>

というスクリプトをメモのところに置きました。無理やりなので、ココログかはてなスターの仕様が変わったらすぐダメになりそうで怖いです。
ちなみに

<script type="text/javascript">
  Hatena.Star.Token = 'd1b02052474b7e28330ad1fbba7513eb57a1ebfe';
</script>
<script type="text/javascript">
  Hatena.Star.EntryLoader.loadEntries = function () {

の</script><script type="text/javascript">のところを無駄かと思って消したらうまくいきませんでした。これは

外部ブログの認証にはブログトップページにトークンの記述が必要です

はてなスターをブログに貼り付けるより

とうことなのだと思います。

| | コメント (0) | トラックバック (0)

2007年7月14日 (土)

C言語でAdapter

Adapterパターンは、あるものとあるものを繋ぐために間に何かをはさむパターン。

Adapterに関して言えば、オブジェクト指向言語より手続き型言語の方が一個関数を定義するだけなので、作りやすいと思う。

例えばmallocというメモリ領域を動的にとる関数が標準ライブラリで提供されているが、引数が確保したいバイト数になっている。そのため、int型を10個分確保したいときは、

int *array = malloc(sizeof(int) * 10);

の様に書かないといけないのでちょっと面倒だ。そこで、型と数の二つを引数で与えるとその分のメモリ領域を取れるようにしたいと思ったとする。

そのとき新たに関数を作ると、

  1. 一から関数を作るのは作るための労力がかかる
  2. もしもmallocが変わったときに対応する必要がでてくるかもしれない

Adapterパターンを使えば以上の問題に対応することができる。具体的には、

#define malloc2(type, number) (malloc(sizeof(type) * (number)))

という内部でmallocを使う新しい関数(マクロ)を作る。そうすると、

int *array = malloc2(int, 10);

のように望んでいた使い方ができる関数ができる。

| | コメント (0) | トラックバック (0)

2007年7月 1日 (日)

C言語でIterator

C言語でSingleton
C言語でSingleton 2
に続いてIteratorをC言語で実装してみます。

とりあえず、これをみてください。

#include <stdio.h>
#include "book_shelf.h"
#include "iterator.h"
#include "book.h"

int main()
{
    BookShelf bookShelf;
    Iterator  it;

    bookShelf = new_BookShelf(4);
    bookShelf->appendBook("Around the World in 80 Days");
    bookShelf->appendBook("Bible");
    bookShelf->appendBook("Cinderella");
    bookShelf->appendBook("Daddy-Long-Legs");

    it = bookShelf->iterator();
    while (it->hasNext()) {
        Book book = (Book)it->next();
        printf("%s\n", book);
    }

    return 0;
}

実行結果が

Around the World in 80 Days
Bible
Cinderella
Daddy-Long-Legs

ループを回すのに配列の大きさを意識しなくていいことと、裏の仕組みを後で書きかえれる事が利点。
今回はファイルが多いので、zipファイルでまとめて公開。
「Iterator.zip」をダウンロード
展開すると下のリストのように展開されます。とりあえず、まとめてコンパイルすれば実行形式ファイルはつくれます。

  • main.c : 上のやつ
  • iterator.h : Iterator構造体の定義
  • aggregate.h : Aggregate構造体の定義
  • book.h : Book変数の定義
  • book_shelf.h : BookShelf構造体の定義
  • book_shelf.c : BookShelfの実装
  • book_shelf_iterator.h : BookShelfIterator構造体の定義
  • book_shelf_iterator.c : BookShelfIteratorの実装

この書き方はJavaでの実装をそのままC言語に落としただけだから、C言語っぽくはないのだと思う。

gccだと、

tree_stmt_iterator si;

for (si = tsi_start (node); !tsi_end_p (si); tsi_next (&si))
  {
    if (!first)
 newline_and_indent (buffer, spc);
    else
      first = false;
  dump_generic_node (buffer, tsi_stmt (si), spc, flags, true);
  }
}
http://gcc.yokinihakarae.com/S/824.html#L862

のように使用するIteratorを使っている。内部的には連結リストになっていて、リストの先頭をtsi_startで取得して、それをtsi_nextでたどっていく。NULLをさすようになったらtsi_end_pが真を返すようになる。みたいな感じ。

詳しくは、
http://wikiwiki.jp/aloha/?cmd=read&page=ssa_op_iter
なりを参考にソースを読んでください。(とGCC 解読室 Wiki*の宣伝)

| | コメント (0) | トラックバック (1)

2007年6月20日 (水)

C言語でSingleton 2

前の記事 に続きC言語でSingletonをやってみます。
今度は使えそうな香りがするようなものになっていると思います。

今回も「Java言語で学ぶデザインパターン」が元ネタです。
簡単に言うと数字をカウントするオブジェクトをSingletonで実装するっていう課題です。

ではヘッダファイルから、
[singleton.h]

typedef struct {
    /* int ticket; */
    int (*getNextTicketNumber)();
} *Singleton;

Singleton get_instance();

前回と違いSingletonの中身が構造体 (といってもintを返す関数へのポインタだけですが) になっています。

続いてSingleton、
[singleton.c]

#include <stdlib.h>
#include "singleton.h"

static int          ticket = 1000;
static Singleton singleton;

static int inc()
{
    return ticket++;
}

Singleton get_instance()
{
    if (!singleton) {
        singleton = malloc(sizeof(*singleton));
        singleton->getNextTicketNumber = inc;
    }
    return singleton;
}

ticketとinc()がstaticなのがポイントで、これらは他のファイルから呼ぶことができません。なので、ticketを直接アクセスすることはできず、get_instance()から得られるSingleton型の変数を通してしかアクセスできなくなります。

最後にメイン、
[main.c]

#include <stdio.h>
#include "singleton.h"

int main()
{
    int i;

    for (i = 0; i < 10; i++) {
        printf("%d\n", get_instance()->getNextTicketNumber());
    }

    return 0;
}

です。get_instance()->getNextTicketNumber()みたいな表記を試しにしてみたら特に異状なく動作しました(gcc4)。

実行結果は

1000
1001
1002
1003
1004
1005
1006
1007
1008
1009

です。こうやってカプセル化を実現するのはありかと思います。

| | コメント (0) | トラックバック (0)

2007年6月17日 (日)

C言語でSingleton

Java言語で学ぶデザインパターンを参考にやってみた。

まずはヘッダファイル。
singleton.h

typedef int *Singleton;

Singleton get_instance();

Singletonという型を宣言。実際に利用するときはint *ではなくなる可能性が高い。
get_instance()でオブジェクトを取得する。

続いてsingeton自体となるファイル。
singleton.c

#include <stdlib.h>
#include "singleton.h"

static Singleton singleton;

Singleton get_instance()
{
    /* ロックする */
    if (!singleton) {
        singleton = malloc(sizeof(*singleton));
    }
    /* ロック解除 */
    return singleton;
}

singletonの宣言にstaticを付けることで、外部のファイルからアクセスできなくする。
get_instanceではそれで領域がとれていなかったらとるようにして、singletonを返す。
スレッドの事とかを考慮して、ロックを掛ける必要がでてくる事も出てくるかもしれない。

最後に利用するファイル。
main.c

#include <stdio.h>
#include "singleton.h"

int main()
{
    Singleton obj1;
    Singleton obj2;

    printf("Start.\n");
    obj1 = get_instance();
    obj2 = get_instance();
    if (obj1 == obj2) {
        printf("obj1とobj2は同じインスタンスです。\n");
    }
    else {
        printf("obj1とobj2は同じインスタンスではありません。\n");
    }
    printf("End.\n");

    return 0;
}

実行結果は

Start.
obj1とobj2は同じインスタンスです。
End.

一応意図どおりできました。
ただ、mainの方で、
Singleton s;
s = malloc(sizeof(*s));
みたいな事は防げないので、厳密にはSingletonではないのだろうな。
あとfreeしてないのも問題か

| | コメント (0) | トラックバック (0)

2007年3月10日 (土)

Perlで図形言語

最近SICPという本をを読んでいます。
図形言語のところまで一応読み終わりました。

参考にしているサイトの一つがひげぽん OSとか作っちゃうかMona-なのですが、
図形言語の終わりの辺りにて

これを PerlやHakellなどのほかの言語で書く人が現れたら面白そうですね。

とあり、確かに面白そうだと思いPerlでやってみました。

とりあえず、できたものは↓です。
Sicp_picture


コードは

#!/usr/bin/perl -w
use strict;
use Tk;
require "picture.pl";

my @segments = (&make_segment(&make_vect(0.00, 0.80), &make_vect(0.15, 0.65)),
                        &make_segment(&make_vect(0.15, 0.65), &make_vect(0.25, 0.70)),
                        &make_segment(&make_vect(0.25, 0.70), &make_vect(0.35, 0.80)),
                        &make_segment(&make_vect(0.35, 0.80), &make_vect(0.35, 1.00)),
                        &make_segment(&make_vect(0.65, 1.00), &make_vect(0.70, 0.80)),
                        &make_segment(&make_vect(0.70, 0.80), &make_vect(0.65, 0.70)),
                        &make_segment(&make_vect(0.65, 0.70), &make_vect(0.75, 0.70)),
                        &make_segment(&make_vect(0.75, 0.70), &make_vect(1.00, 0.40)),
                        &make_segment(&make_vect(1.00, 0.20), &make_vect(0.65, 0.45)),
                        &make_segment(&make_vect(0.65, 0.45), &make_vect(0.70, 0.00)),
                        &make_segment(&make_vect(0.65, 0.00), &make_vect(0.50, 0.20)),
                        &make_segment(&make_vect(0.50, 0.20), &make_vect(0.35, 0.00)),
                        &make_segment(&make_vect(0.25, 0.00), &make_vect(0.35, 0.55)),
                        &make_segment(&make_vect(0.35, 0.55), &make_vect(0.30, 0.60)),
                        &make_segment(&make_vect(0.30, 0.60), &make_vect(0.25, 0.50)),
                        &make_segment(&make_vect(0.25, 0.50), &make_vect(0.00, 0.40)));

my $width  = 300;
my $height = 300;
my $top = MainWindow->new();
my $canvas = $top->Canvas(width => $width, height => $height);

my $frame = &make_frame(&make_vect(0, 0), &make_vect(300, 0), &make_vect(0, 300));
my $func = &segments_painter($canvas, @segments);
my $func2 = &flip_vect($func);
my $func3 = &below($func2, $func2);
my $func4 = &beside($func2, $func3);
&$func4($frame);

$canvas->pack();
MainLoop();

こんな感じ。
間単に説明すると、
"picture.pl"が図形を操作するためのライブラリ。
始めに、@segmentsが線の集合を宣言。
ウィンドウと描画領域を作り、そこにに線を描いていく。

 

図形描画にはTkを使用しました。
基本的にはSICPに載っていたコードや、練習問題で作ったコードを
Perlに翻訳していっただけです。

描画処理のタイミングの問題か、再帰的に行う描画(こういうの)は
うまくいきませんでした。
まあ、結構面白かったし、Perlのリファレンスに慣れることができたし良かったです。

| | コメント (0) | トラックバック (0)

2007年2月10日 (土)

ThunderbirdからGmail経由で携帯メールを送る

昨日、前の研究室の先輩方に会いに行ったときに話題になった話に、
「メールクライアントから携帯としてメールを送りたい」
というのがあった。

その先輩は現在Gmailの

Gmail を使用して他のメール アドレスからメールを送信します

を利用しているとの事。そういう機能があるのは知っていたが、
使ったことは無かったので参考になった。

だが、それを行うためには
Webブラウザを立ち上げ、Gmailへのログインを行う必要がある。
それをOutlookなどのメールクライアントから行いたいという話だった。

気になったのでフィルタからどうにかならないかとか試してみた結果、
とりあえずThunderbird(1.5.0.9)でできたので記事にします。

前置き終了。結構長かったな。



どうすればいいかというと、
基本的にはGmailヘルプセンター(お、Pythonで書いてある)の通り。
そこのアカウント設定のメールアドレスを登録してある別のメールアカウントのものにすれば上手くいった。
下の図のような感じ。

Gmail_setting



| | コメント (0) | トラックバック (0)