最近 Vim を使い始めた。 Emacs の方が高機能なのかも知れないけど、指が攣りそうなので使いたくない。因みに、 hjkl 移動とかモードの切り替えには割りと慣れました。
出来れば全部 Vim に移行したいけど、 Cygwin 使いなので Cygwin のディレクトリ以外のファイルの編集が少し面倒。 Windows を捨てる日は近いかもしれない。
いつも通りリトルバスターズ！の4コマ漫画を読んだのだけど、見た目的な意味で"男の娘"の素質がある理樹が羨ましい。イベントとかでも女装して似合っている人を見ると羨ましいと思うのだけど、私は女装とか似合わないだろうなぁ……。
あと、次号から付いてくるリトルバスターズ！のフィギュアに期待してみる。
少し前に思い付いたアルゴリズムを利用して C 言語で連想配列を実装してみました。
どの程度優れたアルゴリズムなのか調べる為、 "1000000個のデータを連想配列に入れ、そのデータ全ての検索を実行する " というテストを以下のような環境で行いました。
テストの結果は以下の通りです。
メモリを食いすぎてデータ量をこれ以上増やすとOSごと落ちそうになりましたが、データ量の割には短時間で処理出来ているような気がします。
この実装はそのうちライブラリとして公開する予定です。もしかしたら別のアルゴリズムを利用して実装し直すかも知れませんが……。
<xsl:template match="*" mode="lang">
<xsl:choose>
<xsl:when test="attribute::xml:lang">
<xsl:value-of select="concat(' (', attribute::xml:lang, ')')"/>
</xsl:when>
<xsl:otherwise>
<xsl:if test="current() != /">
<xsl:apply-templates select=".." mode="lang"/>
</xsl:if>
</xsl:otherwise>
</xsl:choose>
</xsl:template>祖先ノードから継承した場合でもちゃんと処理出来るように、末尾再帰を使ってみました。
Stricter.org の FOAF 用 XSLT で使っています。
Stricter.org の FOAF 用 XSLT で使っていたのですが、都合が悪くなり別の記述に置き換えました。
という事で、ソフトウェアに書いておきました。
今までの結果から推測すると、全く期待出来ません。(実際、寄付がある方が珍しいんでしょうね。)
適当な辞書データを用意して何度もテストしつつ書き直しました。本当は確率をちゃんと計算するべきなのでしょうけど、それなりに改善したので気にしない事にします。
#define rotate(num,bit) \
((unsigned long)num<<(bit&31)|(unsigned long)num>>(32-bit&31))
int hash(int num,char *string,size_t string_size)
{
int count = 0;
unsigned int result = num;
while(count != string_size){
result = result^(string[count]*69);
result = rotate(result,result);
count++;
}
return (unsigned char)result;
}
#define rotate(num,bit) \
((unsigned long)num<<(bit&31)|(unsigned long)num>>(32-bit&31))
int hash(int num,char *string,size_t string_size)
{
int count = 0;
unsigned int result = num;
while(count != string_size){
result = result+string[count];
result = rotate(result,result);
count++;
}
return (unsigned char)result;
}
数値を取り替えるだけで大量のハッシュ関数を作れますね。結果はそれなりにばらけるように作ったつもりだけど、未検証です。
さっき提示した Cuckoo Hashing の改良案の問題点。
ハッシュテーブルの数だけハッシュ関数が必要になる。恐らく内部で扱う数値を取り替える事によって実現出来るのだが、似たような結果を出しにくいアルゴリズムを採用しないと大量のハッシュテーブルを生成してしまう事になる。
挿入処理で全てのハッシュテーブルを効率良く探索するアルゴリズムが書き難い。
最近、 Cuckoo Hashing というアルゴリズムを知ったのですが、このアルゴリズムには改良の余地があると思っています。
あるサイトの解説を見る限り、使うハッシュテーブルは2つという事になっていますが、これでは入るデータの量が限られてしまう上に、データの挿入で循環した時にハッシュテーブルの再構築が必要になります。
しかし、データの挿入で循環した時に新しくハッシュ関数を用意してそれに合わせて用意したハッシュテーブルにデータを入れてしまえばハッシュテーブルの再構築が必要無くなります。
データの検索に掛かる時間が一定であるという長所は失われますが、 Cuckoo Hashing の短所は解決出来ていると思います。検索速度も大して落ちないでしょうし。
という事で、自前のハッシュテーブルライブラリではこんなアルゴリズムを使ってみようかと思います。
色々考えた結果、環境変数QUERY_STRINGのパーサーで使うハッシュテーブルをライブラリとして実装する事にしました。高速化って、素晴らしい。
QUERY_STRINGのパーサーを書き直しquery_string.htypedef int errcode_t;
#define ERRCODE_SUCCESS 0
#define ERRCODE_FAILED_ALLOC 1
#define ERRCODE_INVALID_DATA 2
#define check_error(errcode_a,errcode_b) (errcode_a&errcode_b)
typedef struct query_string
{
char *key;
char *value;
size_t key_size;
size_t value_size;
} query_string_t;
extern errcode_t parse_query_string(char *,query_string_t **);
query_string.c#include <ctype.h>
#include <stdio.h>
#include <stdlib.h>
#include "query_string.h"
errcode_t decode_char(char **input,char *output)
{
char output_;
switch(**input){
case '%':
(*input)++;
if(isdigit(**input)){
output_ = ((**input)-'0')<<4;
}
else if(isxdigit(**input)){
output_ = (toupper(**input)-'A'+10)<<4;
}
else{
return ERRCODE_INVALID_DATA;
}
(*input)++;
if(isdigit(**input)){
output_ = output_|(**input-'0');
}
else if(isxdigit(**input)){
output_ = output_|(toupper(**input)-'A'+10);
}
else{
return ERRCODE_INVALID_DATA;
}
*output = output_;
break;
case '+':
*output = ' ';
break;
default:
*output = **input;
}
(*input)++;
return ERRCODE_SUCCESS;
}
errcode_t parse_query_string(char *input,query_string_t **output_)
{
size_t output_size = 0;
size_t string_size;
query_string_t *output = NULL;
char *string;
void *temp_pointer;
errcode_t errcode;
*output_ = NULL;
while(*input){
if(!(output_size&15)){
temp_pointer
= realloc(output,sizeof(query_string_t)*(output_size+32));
if(!temp_pointer){
return ERRCODE_FAILED_ALLOC;
}
output = (query_string_t *)temp_pointer;
}
string_size = 0;
string = NULL;
while(1){
if(!(string_size&15)){
temp_pointer = realloc(string,string_size+16);
if(!temp_pointer){
return ERRCODE_FAILED_ALLOC;
}
string = (char *)temp_pointer;
}
if(*input == '='){
string[string_size] = '\0';
input++;
break;
}
else if(*input == '&' || *input == '\0'){
return ERRCODE_INVALID_DATA;
}
else{
errcode = decode_char(&input,&string[string_size]);
if(errcode){
return errcode;
}
string_size++;
}
}
output[output_size].key = string;
output[output_size].key_size = string_size;
string_size = 0;
string = NULL;
while(1){
if(!(string_size&15)){
temp_pointer = realloc(string,string_size+16);
if(!temp_pointer){
return ERRCODE_FAILED_ALLOC;
}
string = temp_pointer;
}
if(*input == '='){
return ERRCODE_INVALID_DATA;
}
else if(*input == '&'){
string[string_size] = '\0';
input++;
break;
}
else if(*input == '\0'){
string[string_size] = '\0';
break;
}
else{
errcode = decode_char(&input,&string[string_size]);
if(errcode){
return errcode;
}
string_size++;
}
}
output[output_size].value = string;
output[output_size].value_size = string_size;
output_size++;
}
output[output_size].key = NULL;
output[output_size].value = NULL;
output[output_size].key_size = 0;
output[output_size].value_size = 0;
*output_ = output;
return ERRCODE_SUCCESS;
}
あと少し改良してからライブラリとして公開するかも知れません。
デスマーチ第2版 ソフトウェア開発プロジェクトはなぜ混乱するのかを買った。
まだ第1章しか読んでいないので、内容に関しては何とも言えない状態。
病院には行けなかったのですが、体温は37.0度以下になり、意識もはっきりとしています。助かりました。
かなり前からコンパイラⅡ ――原理・技法・ツール――を探していたのですが、どこの本屋を探しても無い上に、出版社に問い合わせたら再版の予定は無いと言われて仕舞いました。
この本を私に譲って下さる方は、何らかの方法で連絡して下さい。
風邪を引きました。
体温は38.0度を越え、コードを書けません。
という事で、明日は病院に行きます。