ブログトップ 記事一覧 ログイン 無料ブログ開設

DELPHIER＠はてな このページをアンテナに追加 RSSフィード Twitter

2012/03/31

tiny hash table

practice, programming, algorithm

Cでコードを書いているとハッシュテーブル*1が欲しくなることが多々あります。というわけで小さいのを書いてみました。


ハッシュテーブルについて

ハッシュテーブルは、あるキーをハッシュ関数を使ってマッピングし、それに対応する値を関連付けるためのデータ構造です。連想配列として使われたり、ハッシュマップと呼ばれたりもします。ハッシュ関数によってキーをインデックスに変換し（これをハッシュと呼ぶ）、それに対応する配列の要素（スロットまたはバケツと呼ばれる）に値を入れておきます。そこそこメモリを使いますが、その分高速に動作します。


探索において、木構造などの二分探索をベースとした実装では、キーの比較回数がlog2(N)となりますが、ハッシュテーブルでは大抵これよりも小さくなります。比較回数がこれよりも多くなるような状況、つまり衝突が多発する状況では、衝突が多発しないようなハッシュ関数を選択するか、バケツを大きくするか、木構造など二分探索をベースとした実装を用いるなどの回避策があります。ほぼWikipediaな内容ですみません。


thtblの特徴


工夫したところ

オープンアドレス法だと、ポインタの管理とは別に、その値が「空」「削除済み」「使用中」を区別する必要があります。ポインタと他にマーキング用のデータを用意するのは面倒だしメモリも使いそうで嫌だったので、ポインタのアドレッシングの仕組みを利用してポインタのみで管理することにしました。大抵のOSでは、カーネルランドとユーザランドでそれぞれアドレス空間が分かれています。以下のページを見ると、大抵のOSではカーネルランドが大きい番地を占めていることが分かります。


というわけで、以下のように区別することにしました。私はカーネルランドで動作するものは書かないので。

  • 空 → NULL
  • 削除済み → 0xffffffff または 0xffffffffffffffffLLU
  • 使用中 → 上記以外

GNU hashtabというハッシュテーブルライブラリも似たようなことをしていて、mallocなどは1を返さないという前提の元に実装されています。小さい番地は大抵何らかのアプリのスタックが使っているので、確かにその前提はたいてい成立するんでしょうね。


実行結果

いくつかのハッシュ関数、いくつかのバケツの大きさで衝突させまくりで挿入だけベンチマークをとってみました。衝突率の低さだけが性能の決定的要素ではなく、比較関数のコストも重要な要素だよ、ということがよく分かる結果になっていますね。

128

string

searches: 128, collisions: 204 (1.593750%)

0.000243 [sec]

zackw

searches: 128, collisions: 416 (3.250000%)

0.000212 [sec]

FNV-1a

searches: 128, collisions: 51 (0.398438%)

0.000214 [sec]

1024

string

searches: 1024, collisions: 5048 (4.929688%)

0.001869 [sec]

zackw

searches: 1024, collisions: 1920 (1.875000%)

0.001591 [sec]

FNV-1a

searches: 1024, collisions: 503 (0.491211%)

0.001523 [sec]

8192

string

searches: 8192, collisions: 43510 (5.311279%)

0.013948 [sec]

zackw

searches: 8192, collisions: 51554 (6.293213%)

0.012849 [sec]

FNV-1a

searches: 8192, collisions: 3827 (0.467163%)

0.011939 [sec]

16384

string

searches: 16384, collisions: 849376 (51.841797%)

0.042020 [sec]

zackw

searches: 16384, collisions: 38040 (2.321777%)

0.024676 [sec]

FNV-1a

searches: 16384, collisions: 6266 (0.382446%)

0.024592 [sec]

32768

string

searches: 32768, collisions: 1692528 (51.651855%)

0.083191 [sec]

zackw

searches: 32768, collisions: 23370 (0.713196%)

0.047768 [sec]

FNV-1a

searches: 32768, collisions: 17951 (0.547821%)

0.049201 [sec]

65536

string

searches: 65536, collisions: 2047008 (31.234863%)

0.141463 [sec]

zackw

searches: 65536, collisions: 121870 (1.859589%)

0.098748 [sec]

FNV-1a

searches: 65536, collisions: 45944 (0.701050%)

0.100855 [sec]

1048576

string

searches: 1048576, collisions: 30468520 (29.057045%)

2.362834 [sec]

zackw

searches: 1048576, collisions: 3814406 (3.637701%)

1.755987 [sec]

FNV-1a

searches: 1048576, collisions: 515284 (0.491413%)

1.933815 [sec]



その他

実装にあたり参考にしたページなど。

Permalink | コメント(1) | トラックバック(0) | 11:54 tiny hash tableを含むブックマーク tiny hash tableのブックマークコメント

*1：http://en.wikipedia.org/wiki/Hash_table

B005GRZC28
Shoes [ハッシュパピー] Hush Puppies カジュアル M-1...
Hush Puppies(ハッシュパピー)
B007VIPSNI
Shoes [コンバース] CONVERSE CONVERSE ALL STAR FRENC...
CONVERSE(コンバース)
idトラックバック

2012/03/20

画像の色数を求めたりヒストグラムを作るためのソートをいろいろ実装してみた

algorithm, practice, programming

画像の色数を求めるにはハッシュ的なものを使うよりもソートした方が速いという話です。


また、ヒストグラムを高速に作ろうとすると色の深度に応じてメモリを食います。RGBそれぞれが8ビットだと64MBほどメモリを食います。対してソートでやろうとすると、画素数分だけで済むのでメモリ的にも優しいです。


そんなわけで、ソートです。上記ではクイックソートを使ってますが、クイックソートが最善手とは限りません。最近はメモリが豊富なので、バケツソートや分布数え上げソートや基数ソートも十分実用的です。どれがいいだろう、というわけでいくつか試してみました。クイックソート、分布数え上げソート、基数ソートを手持ちのMac Book Airで試してみました。コードはこちら。


4バイトの符合なし整数をソートするという簡単なコードです。以下のソートを比べています。


結果としては、概ねワード単位の基数ソートが最も速かったです。つうわけで、画像処理ではワード単位の基数ソートを使うのがよさそうです。基数ソートは少しだけ工夫しました。基数ソートでは、普通は単位毎に結果をコピーするのですが、ダブルバッファリングすることでその手間をなくしました。画素数が大きくなればなるほど効いてくるはずです。以下は、Mac Book Air 2.13 GHz Intel Core 2 Duo, Memory 4 GB 1067 MHz DDR3で実行した結果です。まずは実機での結果。

QVGA 24bpp 320x 240 (size = 76800, range = 16777216)

qsort : 0.023937 [sec]

quick_sort : 0.022483 [sec]

counting_sort : 0.211722 [sec]

counting_sort2 : 0.146360 [sec]

counting_sort3 : 0.133482 [sec]

radix_sort : 0.006259 [sec]

radix_sort2 : 0.005574 [sec]

radix_sort3 : 0.005545 [sec]

radix_sort4 : 0.004007 [sec]

VGA 24bpp 640x 480 (size = 307200, range = 16777216)

qsort : 0.105436 [sec]

quick_sort : 0.092361 [sec]

counting_sort : 0.184831 [sec]

counting_sort2 : 0.184686 [sec]

counting_sort3 : 0.169230 [sec]

radix_sort : 0.025758 [sec]

radix_sort2 : 0.024495 [sec]

radix_sort3 : 0.023203 [sec]

radix_sort4 : 0.015684 [sec]

XGA 24bpp 1024x 768 (size = 786432, range = 16777216)

qsort : 0.288884 [sec]

quick_sort : 0.260471 [sec]

counting_sort : 0.274694 [sec]

counting_sort2 : 0.272200 [sec]

counting_sort3 : 0.257774 [sec]

radix_sort : 0.069239 [sec]

radix_sort2 : 0.066146 [sec]

radix_sort3 : 0.060907 [sec]

radix_sort4 : 0.040482 [sec]

Nexus S 24bpp 480x 800 (size = 384000, range = 16777216)

qsort : 0.134426 [sec]

quick_sort : 0.118140 [sec]

counting_sort : 0.198503 [sec]

counting_sort2 : 0.198470 [sec]

counting_sort3 : 0.182864 [sec]

radix_sort : 0.033405 [sec]

radix_sort2 : 0.031146 [sec]

radix_sort3 : 0.029891 [sec]

radix_sort4 : 0.019964 [sec]

Mac Book Air 24bpp 1440x 900 (size = 1296000, range = 16777216)

qsort : 0.492288 [sec]

quick_sort : 0.439028 [sec]

counting_sort : 0.376246 [sec]

counting_sort2 : 0.370595 [sec]

counting_sort3 : 0.353696 [sec]

radix_sort : 0.113894 [sec]

radix_sort2 : 0.110131 [sec]

radix_sort3 : 0.102530 [sec]

radix_sort4 : 0.069099 [sec]

iMac 24bpp 2560x1440 (size = 3686400, range = 16777216)

qsort : 1.493648 [sec]

quick_sort : 1.320081 [sec]

counting_sort : 0.833016 [sec]

counting_sort2 : 0.819314 [sec]

counting_sort3 : 0.810189 [sec]

radix_sort : 0.332729 [sec]

radix_sort2 : 0.316817 [sec]

radix_sort3 : 0.292213 [sec]

radix_sort4 : 0.200232 [sec]

同じマシンでWindows XP on Virtual Boxで実行した結果がこちら。

QVGA 24bpp 320x 240 (size = 76800, range = 16777216)

qsort : 0.016000 [sec]

quick_sort : 0.000000 [sec]

counting_sort : 0.485000 [sec]

counting_sort2 : 0.765000 [sec]

counting_sort3 : 0.719000 [sec]

radix_sort : 0.000000 [sec]

radix_sort2 : 0.031000 [sec]

radix_sort3 : 0.000000 [sec]

radix_sort4 : 0.016000 [sec]

VGA 24bpp 640x 480 (size = 307200, range = 16777216)

qsort : 0.093000 [sec]

quick_sort : 0.047000 [sec]

counting_sort : 0.687000 [sec]

counting_sort2 : 0.844000 [sec]

counting_sort3 : 0.828000 [sec]

radix_sort : 0.062000 [sec]

radix_sort2 : 0.047000 [sec]

radix_sort3 : 0.047000 [sec]

radix_sort4 : 0.047000 [sec]

XGA 24bpp 1024x 768 (size = 786432, range = 16777216)

qsort : 0.234000 [sec]

quick_sort : 0.188000 [sec]

counting_sort : 0.656000 [sec]

counting_sort2 : 0.781000 [sec]

counting_sort3 : 0.812000 [sec]

radix_sort : 0.188000 [sec]

radix_sort2 : 0.235000 [sec]

radix_sort3 : 0.171000 [sec]

radix_sort4 : 0.109000 [sec]

Nexus S 24bpp 480x 800 (size = 384000, range = 16777216)

qsort : 0.125000 [sec]

quick_sort : 0.063000 [sec]

counting_sort : 0.625000 [sec]

counting_sort2 : 0.719000 [sec]

counting_sort3 : 0.813000 [sec]

radix_sort : 0.047000 [sec]

radix_sort2 : 0.046000 [sec]

radix_sort3 : 0.047000 [sec]

radix_sort4 : 0.047000 [sec]

Mac Book Air 24bpp 1440x 900 (size = 1296000, range = 16777216)

qsort : 0.359000 [sec]

quick_sort : 0.282000 [sec]

counting_sort : 0.563000 [sec]

counting_sort2 : 0.906000 [sec]

counting_sort3 : 0.969000 [sec]

radix_sort : 0.297000 [sec]

radix_sort2 : 0.281000 [sec]

radix_sort3 : 0.250000 [sec]

radix_sort4 : 0.156000 [sec]

iMac 24bpp 2560x1440 (size = 3686400, range = 16777216)

qsort : 0.719000 [sec]

quick_sort : 0.766000 [sec]

counting_sort : 0.765000 [sec]

counting_sort2 : 1.234000 [sec]

counting_sort3 : 1.188000 [sec]

radix_sort : 0.797000 [sec]

radix_sort2 : 0.640000 [sec]

radix_sort3 : 0.563000 [sec]

radix_sort4 : 0.390000 [sec]


次は、画像処理向けの高速なmemcmp、memcpy、bzeroあたりをやってみましょうかね。

Permalink | コメント(0) | トラックバック(0) | 12:07 画像の色数を求めたりヒストグラムを作るためのソートをいろいろ実装してみたを含むブックマーク 画像の色数を求めたりヒストグラムを作るためのソートをいろいろ実装してみたのブックマークコメント

bswap

programming

今日のコード。Windows XPとMac OS X 10.6.8で動作することを確認しています。


バイナリプログラミングをやっていると、エンディアンに応じてバイトオーダーをひっくり返す（バイトスワップ）というのがよくあります。バイトスワップは高速にやろうと思うと中々厄介で、マクロにすると分かりづらいし、ライブラリ関数にするとインライン展開が効かなくなります。というわけでいい方法がないのか少しだけ調べてみました。


ここまでのまとめ。


なかなか面倒そうだな、ということが分かりました。でも、こんなよくあることは誰かがうまいことやってくれているはずです。ということでさらに調べてみると、以下のようなコードが見つかりました。


コードを眺めてみると以下のようになっているようです。


Cだけで書くならこんな感じでヘッダに書くのが定石みたいですね。まるで魔法のようですが、自分で計算してもコンパイルして実行してもちゃんと動きます。特に、bswap_32。右シフトも左シフトも論理和も論理積もすべて二回ずつなのでとても美しい感じがします。

static inline uint16_t bswap_16(uint16_t x) {
  return (x >> 8) | (x << 8);
}

static inline uint32_t bswap_32(uint32_t x) {
  x= ((x << 8) & 0xFF00FF00) | ((x >> 8) & 0x00FF00FF);
  return (x >> 16) | (x << 16);
}

static inline uint64_t bswap_64(uint64_t x) {
    union {
        uint64_t ll;
        uint32_t l[2];
    } w, r;
    w.ll = x;
    r.l[0] = bswap_32 (w.l[1]);
    r.l[1] = bswap_32 (w.l[0]);
    return r.ll;
}

bswap_32、普通に考えたらこうですよね。

static inline uint32_t bswap_32(uint32_t x) {
  return
		(((x & 0x000000ff) >> 0x00) << 0x18) |
		(((x & 0x0000ff00) >> 0x08) << 0x10) |
		(((x & 0x00ff0000) >> 0x10) << 0x08) |
		(((x & 0xff000000) >> 0x18) << 0x00);
}

んで、こうなって・・・

static inline uint32_t bswap_32(uint32_t x) {
  return
		((x & 0x000000ff) << 0x18) |
		((x & 0x0000ff00) << 0x08) |
		((x & 0x00ff0000) >> 0x08) |
		((x & 0xff000000) >> 0x18);
}

こうですよね。

static inline uint32_t bswap_32(uint32_t x) {
  return
		(x << 0x18) |
		((x & 0x0000ff00) << 0x08) |
		((x & 0x00ff0000) >> 0x08) |
		(x >> 0x18);
}

さっきのbswap_32よりも、論理和が一回多くなります。それだけですけど、それを減らせるってのがさっきのbswap_32のすごいところ。Graphic Gems Iにはこういうことが一杯書いてありそうだな。

Graphics Gems I (Graphics Gems - IBM)

Graphics Gems I (Graphics Gems - IBM)

Permalink | コメント(2) | トラックバック(0) | 08:57 bswapを含むブックマーク bswapのブックマークコメント

*1：https://sites.google.com/site/instructionsx86/bswap

*2：http://msdn.microsoft.com/ja-jp/library/a3140177(v=vs.80).aspx

idトラックバック

2012/03/16

Topological sort

practice, algorithm

トポロジカルソート*1を書いてみました。C言語、D言語、Lua、Rubyで。


トポロジカルソートが何に使えるかというと、makeの依存性解決などで使えます。yamakeというビルドシステムを作る上で、参考にしているシステムとしてninja*2のソースコードを見ていたのですが、自分でもできそうだと思ってやってみました。ninjaではトポロジカルソートっぽいことはやってませんが。


実装は簡単でしたが、依存性解決にトポロジカルソートが使えるということを探すまでに少し時間がかかりました。最初は循環参照検出*3のFloyd's cycle-finding algorithmにたどり着きましたが、makeの依存性のような二次のものには対応できないのでさらに探していたらなんとか見つかったという感じです。

Permalink | コメント(0) | トラックバック(0) | 08:11 Topological sortを含むブックマーク Topological sortのブックマークコメント

*1：http://en.wikipedia.org/wiki/Topological_sorting

*2：http://martine.github.com/ninja/

*3：http://en.wikipedia.org/wiki/Cycle_detection

idトラックバック

2011/08/07

some points for HTTP client on native applications (1)

programming

はじめに

HTTP は利用頻度が高いネットワークプロトコルの一つだと思います。HTTP サーバを書くことはそんなに多くないと思いますが、HTTP クライアントは何らかの形で利用したり実装したりしたことがある人は多いのではないでしょうか。今回は、ネイティブアプリでの HTTP クライアントを利用・実装することに焦点を絞ります。


多少経験のあるプログラマなら、HTTP クライアントを自分で実装したいとはあまり思わないはずです*1。HTTP は、仕組みとしてはシンプルですがいざ実装しようとすると中々大変です。ソケットを使ってデータ転送をする処理や、HTTP リクエストの妥当性検証*2や生成、レスポンスの解析、ステータスコードの正しいハンドリング、データのバッファリング・・・。さらに、国際化ドメイン名、キープアライブ、リダイレクト、認証*3、プロキシ解決*4、プロキシ越え、HTTPS なんかも考え始めると頭が爆発しそうになるからです。フルスタックの HTTP クライアントを実装するのは非常に大変です。


ライブラリを使おう

そうなると、偉大なる先達が作ってきたものを利用しようという方向に頭が働きます。幸い、HTTP クライアントのライブラリは数多く存在します。


libcurl を使おう

大抵の場合、libcurl で事足ります。マルチプラットフォーム対応している優れものです。ただし、libcurl には以下の機能・問題がないので注意が必要です。


というわけで、プロキシに Digest 認証が必要な環境で HTTPS 通信がしたい、という場合、現状の libcurl を利用することはできません。上記で挙げたプラットフォーム標準搭載のライブラリは、どれもうまく処理してくれます。


プロキシ解決

プロキシ環境をサポートする場合、まず最初にやるべきことはプロキシ解決です。プロキシ解決は、どのプロキシサーバを利用するかを決定します。ないならないで利用しません。Internet Explorer や Google Chrome を利用している方なら、ステータスバーに「プロキシを解決しています」というメッセージが表示されていることに気づいている方もいると思いますが、あれのことですね。


プロキシ解決は、アプリケーション固有のプロキシ設定を用いる場合と、プラットフォームが持つ設定を踏襲する場合があります。前者はここでは特に触れず、後者に焦点を絞ります。


Windows や Mac OS X では、プロキシ解決を以下の手順で行うことができます。

  1. プロキシの自動検出
  2. プロキシの自動構成

プロキシの自動検出は、Web Proxy Autodiscovery Protocol ( WPAD ) に基づいて行われます。大雑把にいうと、DHCP または DNS サーバに置いてある自動構成スクリプトファイルを持ってくる感じです。


WinINet なら、DetectAutoProxyUrl() を呼び出すことでこれが行えます。オプションとして、DHCP を用いるか、DNS の A レコードを用いるか、どちらもかを選択できます。呼び出すと、以下のような通信が発生します。


DHCP サーバがこれに応答するように構成されていない場合、 この API の実行に10秒以上かかることがあります。エラーコードは ERROR_NO_TOKEN ( 1008 ) などです。また、1 秒程度で完了することもあります。


DNS サーバがこれに応答するように構成されていない場合、 この API の実行に 5 秒程度かかることがあります。エラーコードは WSAHOST_NOT_FOUND ( 11001 ) などです。


自力で実装するなら、ちょっとした DHCP クライアントを書く必要があるってことですね。また、自動構成スクリプトのダウンロード自体にも HTTP が必要という罠があります。


こうして、自動検出が完了したら次は自動構成スクリプトを解釈します。

次回へ続きます。

Permalink | コメント(0) | トラックバック(0) | 00:14 some points for HTTP client on native applications (1)を含むブックマーク some points for HTTP client on native applications (1)のブックマークコメント

apache のミラーサイトに facebook が!

---> Attempting to fetch apr-1.4.2.tar.bz2 from http://mirror.facebook.net/apache/apr

Permalink | コメント(0) | トラックバック(0) | 00:05 apache のミラーサイトに facebook が!を含むブックマーク apache のミラーサイトに facebook が!のブックマークコメント

*1：ソケット覚えたての頃ならともかく

*2：正しく実装しなければ HTTP ヘッダインジェクションなどをまねきます

*3：Basic なら Base64、Digest なら MD5、NTLM なら DES が必要になります

*4：WPAD、自動構成スクリプトなど

idトラックバック

2011/07/31

大工のようなプログラマ

私の父は大工である。二級建築士で、大抵は二階建ての木造住宅を建てている。


私が学生のころ、たまに小遣い稼ぎとして父の手伝いをしていた。建前、床張り、ベニヤ張り、天井張りなどのハードワークがメインだ。特に天井張りはよく覚えている。普段はひとりでこなしているというのだが、どうやって二本の手ででかい石膏ボードを天井に添え、電動ドリルを持ってビスを打ち込んでいくのだろうと不思議に思ったものである。


少なくとも、二級建築士免許だけを持っていても絶対にできないだろう。ある程度の筋力・技術・経験が不可欠だと思う。これは、基本情報技術者などの試験の合格していてもプログラミングができるという訳ではない、ということに似ていると思う。


私は仕事をはじめてから手伝いをしなくなったが、少し前に建前の手伝いにいった。真夏の炎天下での肉体労働は過酷であったが、私は手伝いを終えてビールを飲みながら、大工のようなプログラマになりたいと思った。


これは、企画・見積・設計・実装・試験といった全工程に関わり、チームへの指示を出し、自らも各作業を行いながら、小中規模の価値のあるソフトウェアを、出来る限り作り続けていきたい、ということである。私の感触では、大規模開発だとこういった振る舞い・細部に至る丁寧な作り込み・めまぐるしい市場の変化への対応が難しそうなので、今はあまり興味が湧いていない。あとグラフィックデザイナーとしては作業できない。大工の人だって、電気・水道工事などは別の人が担当するからそういうのがあってもいいよね。他にも、企画・見積・設計・試験・効果の高いチームプレーなど苦手はことはたくさんある。


中学三年のときにPCに触れ、ゲームプログラミングをはじめてからもうすぐ１５年になる。大工のようなプログラマになるにはもう少し時間がかかりそうだ。だが不可能ではないと感じているし、もうすぐそうなれるという予感はしている。


今回の手伝いは、学生のころと違い小遣いはもらえなかったが、自分を見つめ直すいい機会になったし体も少し鍛えられたので大儲けだったと思う。

Permalink | コメント(0) | トラックバック(0) | 02:23 大工のようなプログラマを含むブックマーク 大工のようなプログラマのブックマークコメント

idトラックバック
プロフィール

izariuo440

izariuo440 はてなダイアリープラス利用中

ひたすらプログラミングしている。DELPHIからC++、C++ から C に以降しつつあります。1982/11/02生まれ、三重県出身。すでにDELPHIERではない、という説もある。

日記の検索

カレンダー
<< 2012/06 >>
日 月 火 水 木 金 土
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
最近のコメント
最近のトラックバック
最新タイトル
カテゴリー
ページビュー
208073
izariuo440のブックマーク