UMLモデリングツール

ソフトウェア

JUDE竹：http://objectclub.esm.co.jp/Jude/jude.html

今までPatternWeaverっていうのを使っていたんだけど、MacOSX 10.3にアップデートしたときに消しちゃったから良い機会だと思って別のを探してみた。そこで見つけたのがJUDEっていうやつ。Javaだから大抵の環境で動くし、”死ぬほど”遅くはない。

ただ、「ちょっとなぁ」と思うのはJavaのモデリングしか考えてないところ。UMLってはプログラミング言語には非依存で考えるべきだと思うから、モデリングツールにはプログラミング言語を意識しないか、オプション的な扱いにしたいのよね。まぁ、そんな気になるほどでも無いからOK。後はPDFで出力したい時がたまーにある*1んだけど、ぱっと見ではPDF出力はなさそう。

一応MacOSXではOmniGraffleっていうのがあって、かなり良い出来だと思う。でもあくまでスケッチ的な使い方であって、本気モデリングすると不足を感じることが多い。だから、ちょっと頭の整理をする程度だったらOmniGraffleを使ってる。

http://www.omnigroup.com/applications/omnigraffle/

でも開発系ツールは環境依存になるのが嫌なんだよなぁ。

*1:お客さんへのはったり効果大なんですよ（苦笑）

MacOSXでのsnprintf挙動への追記

プログラム

参考：http://d.hatena.ne.jp/kt-blackout/20040622#p1

上記の日記でMacOSXの[v]snprintfの最初の二つの引数にNULL, 0を与えると-1を返すと書いたが、これはMacOSX 10.2での話。最近MacOSX 10.3にしたのだが、こちらでは[v]snpritnfはメモリが足りなくても、「メモリが足りれば書き込まれたであろう値」を返すようになった。つまり以下のコードでは"len : 2"と表示される。

#include 

int
main(int argc, char *argv[])
{
    int len;
    len = snprintf(NULL, 0, "OK");
    printf("len : %d?n", len);
    return 0;
}

いま、このコードでlenが-1になる環境はどんなのがあるんだろう？　いまのところMacOSX 10.2しか見当たらない*1。これに依存するのはありなのか、なしなのか。

*1:sourceforgeのコンパイルファームでも実験した

最適化…、おそろしい。

プログラム

なんとなく、いろいろと最適化に挑戦してみた。勉強の為なのでネットで最適化を調べたりするのではなく、glibcのソースコードと自作のコードのアセンブリを見ながら地力で最適化に挑戦した。

あれこれ試していて、ふとRHLinux右下の時計に目をやると3時22分。げぇ、7時間もたってる。晩飯も、水分も、いっさいとってない…。われながら素晴しい集中力だ。

最適化に関してはここで書くような、面白いものは分からなかった。強いて言えば、次の二つのコードは上の方が弱冠速かった（ほんとに少しだけだけど）。

/* sbuffer_tっていうのは文字列用の構造体です */
void
chrrep(sbuffer_t *sbuf, char src, char dst)
{
    unsigned char *p = (unsigned char *)sbuf->string;

    for (; *p != '\0'; ++p)
        if (*p == src)  *p = dst;
}

void
chrrep(sbuffer_t *sbuf, char src, char dst)
{
    char *p = sbuf->string;

    for (; *p != '\0'; ++p)
        if (*p == src) *p = dst;
}


そんなことよりもglibcのstrstr()のコードが理解できん。明日以降にでもなんとか解読するつもり。そのコードの先頭のコメントにこんな挑戦的な文章がある。

/*
 * My personal strstr() implementation that beats most other algorithms.
 * Until someone tells me otherwise, I assume that this is the
 * fastest implementation of strstr() in C.
 * I deliberately chose not to comment it.  You should have at least
 * as much fun trying to understand it, as I had to write it :-).
 *
 * Stephen R. van den Berg, berg@pool.informatik.rwth-aachen.de */

こら、Stephen、コメント書け。嘘です。面白いから良いのです。ちょっとした（いや、大掛かりな）クイズだと思って解かせて頂きます。

ハッシュは"読み"間違えると遅いな

プログラム

最適化に関してネットで調べてたら「ハッシュは本当に速いのか*1」という記事を見つけたから、自分の作ってるライブラリでも実験してみた。

実験は100000件のユニークなキーを持つデータを全て追加して、全て削除するというもの。擬似コードで書くと

for (int i=0; i

こんな感じ。containerの型をハッシュテーブルと二分木のそれぞれについて調べた。あくまで俺の作ったものであり、一般論ではないのでむやみに信じない方がいいかも。とにかく、結果は下のようになった。Hashの後の括弧はハッシュテーブルの大きさ。1024に固定したものと、データ数と同じ大きさのものを用意してみた。

Bench-mark (count = 5000)
  Hash(1024)  : 0.0100
  Hash(5000)  : 0.0100
  BTree       : 0.0200

Bench-mark (count = 10000)
  Hash(1024)  : 0.0500
  Hash(10000) : 0.0200
  BTree       : 0.0400

Bench-mark (count = 50000)
  Hash(1024)  : 2.2000
  Hash(50000) : 0.1100
  BTree       : 0.2300

Bench-mark (count = 100000)
  Hash(1024)  : 8.2900
  Hash(100000): 0.2200
  BTree       : 0.4900

データ数が1024のハッシュはかなり悲惨な結果になっている。100,000件に対する応答が8秒は酷すぎる（多分俺の実装がだめ）。でも、データ数と同じ大きさのハッシュにしてやると、とっても安定する。計算してもらえば分かるけど、ハッシュ値がデータの数と同じならば処理時間も完全に比例する。

逆に、二分木（BTree）は常に安定して速い。現実問題としては100,000件のデータに対しても問題無いぐらいの速さだ（ものによるけど）。


さらに使用するメモリ量も見てみることにした。ライブラリ内のメモリ確保は全て専用の関数を通していて、デバッグモードでメモリの使用状況をダンプできるようにしてあったから、簡単に実験できた（こんなの計算してもいいんだけどね）。以下の結果は100,000件のデータ追加したときのコンテナのメモリ使用量。

Hash(1,024)   : 1,604,116(byte)
Hash(100,000) : 2,000,020(byte)
BTree         : 2,000,048(byte)

なんか微妙な結果だな。しかし、ひとつ言えるのはデータ総量が予測出来るのであれば、同じメモリでハッシュのほうが高速ということ。さらにメモリの節約などといってハッシュの大きさを小さくしても、メモリの節約結果の割りに、極端に遅くなる。

結論：

データの総量が予測出来るときはそのデータ量以上の大きさのハッシュ、予測出来ないときは二分木をつかうべし。


長々と、この当たり前の事導いただけか…。

*1:http://www.s34.co.jp/cpptechdoc/article/hash/

進数表現変換機を発掘した

プログラム

昔作って今でもちょっと愛用している進数表現変換機プログラムのソースを偶然見つけた。懐かしさを感じつつ、ちょっと修正して公開してみる。

http://members.jcom.home.ne.jp/j-klein/src-box/dconv.c

コンパイル&使用法はソースの先頭に書いたので、そちらを参照。一応2, 8, 10, 16進数から1 < X <= 36進数への変換が可能。入力値は引数で指定するが、何進数かは数字のフォーマットを見て判断する。2進数は数字の末尾に"b"を付け、8進数は"0"、16進数は"0x"ではじまり、10進数はそのまま。つまり…

 2進数：1b, 1001b, 111b, 1001b, 111111b ...
 8進数：037, 021, 03443, 0377777 ...
10進数：1, 23, 43, 4324, 999 ...
16進数：0x1, 0x0f, 0xab, 0xffff ...

みたいな感じ。変換できるのは正数のみで、最大32bit（10進数で4294967295, 16進数で0xffffffff）まで。オプションに関しては-hオプションと、ソース先頭の使用法サンプルを見れば分かるでしょう。一応ひとつだけ使用例を…

[~/work/] john% dconv -a 10 0x10 010 10b
   source |  binary |        octal |    decimal |       hexa
       10 |    1010 |          012 |         10 |        0xa
     0x10 |   10000 |          020 |         16 |       0x10
      010 |    1000 |          010 |          8 |        0x8
       10 |      10 |           02 |          2 |        0x2

おもしろプログラマの卵

独り言

俺の知り合いが最近プログラミングを始めた。一通りCを理解したから、いろいろと小さなプログラムを作っているらしく、それらをちょっと見せてもらった。その中になぞのコードが…

fd = open(...);

if (fd == -1)
    fd++;

...

な、なんだこれ?

本人に聞いたところ「参考書にopenの返り値が-1だとエラーだと書いてあったので、返り値を0に修正するコードにした」と自信満々に答えていた。ちなみに上記の謎の修正は各システムコールに対して行なわれていた。

ネタだといいのだが……。