![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
int qscmp(const void *a, const void *b)
{
return strcmp(*(char **) a, *(char **) b);
}0 1 10 100 1000 10000 100000 100001 100002 100003 100004 100005 100006 100007 100008 100009 10001 100010 100011 100012
int qscmp(const void *a, const void *b)
{
const unsigned char *ca = *(const unsigned char **) a, *cb = *(const unsigned char **) b;
if (ca[0] != cb[0]) return ca[0] - cb[0];
if (ca[1] != cb[1]) return ca[1] - cb[1];
if (ca[2] != cb[2]) return ca[2] - cb[2];
if (ca[3] != cb[3]) return ca[3] - cb[3];
if (ca[4] != cb[4]) return ca[4] - cb[4];
if (ca[5] != cb[5]) return ca[5] - cb[5];
return ca[6] - cb[6];
}int qscmp(const void *a, const void *b)
{
const unsigned int *ca = *(const unsigned int **) a, *cb = *(const unsigned int **) b;
if (ca[0] != cb[0]) return ca[0] - cb[0];
return ca[1] - cb[1];
}| qsrot #1 | 340ms |
| qsort #2 | 286ms |
| qsort #3 | 278ms |
| ACrit32L0B1 | 186+20=206ms |
| ACrit32L0B2 | 145+17=162ms |
| ACrit32L0B4 | 127+15=142ms |
int qscmp(const void *a, const void *b)
{
const unsigned int *ca = *(const unsigned int **) a, *cb = *(const unsigned int **) b;
if (ca[0] != cb[0]) return ca[0] - cb[0];
if (ca[1] != cb[1]) return ca[1] - cb[1];
if (ca[2] != cb[2]) return ca[2] - cb[2];
if (ca[3] != cb[3]) return ca[3] - cb[3];
if (ca[4] != cb[4]) return ca[4] - cb[4];
return ca[5] - cb[5];
}| qsort | 328ms |
| ACrit32L0B1 | 203+21=224ms |
| ACrit32L0B2 | 175+18=193ms |
| ACrit32L0B4 | 160+16=176ms |
int qscmp(const void *a, const void *b)
{
const unsigned int *ca = *(const unsigned int **) a, *cb = *(const unsigned int **) b;
return ca[0] - cb[0];
}| qsort | 179ms | |
| ACrit32L0B1 | 176+22=198ms | 可変長モード |
| ACrit32L1B1 | 153+22=175ms | 固定長32bitキー専用クラス |
| ACrit32L0B2 | 137+15=152ms | 可変長モード |
| ACrit32L1B2 | 120+15=135ms | 固定長32bitキー専用クラス |
| ACrit32L0B4 | 112+11=123ms | 可変長モード |
| ACrit32L1B4 | 102+11=113ms | 固定長32bitキー専用クラス |
| init | 初期化 |
| deinit | 後始末 |
| ins | データの追加 |
| srch0 | 検索（キーを指定）：データを返す |
| srch1 | 検索（ソート順でn番目）：データを返す |
| srch2 | 検索（キーを指定）：nを返す（註1） |
| srch3 | 検索（キーを指定）：nを返す（註1） |
| srch4 | srch0の連続指定（註2） |
| srch5 | srch1の連続指定（註2） |
| del0 | 削除（キーを指定）：データを返す |
| del1 | 削除（ソート順でn番目）：データを返す |
| annl | キーの加工（アニーリング）（註3） |
| B1 | B2 | B4 | |
| pos:ビット位置 | 1 | 1 | 1 |
| ptr:ポインタ | 2 | 4 | 16 |
| num:そのポインタの先にいくつデータがあるか | 2 | 4 | 16 |
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
int main()
{
int i, sz = 16 * 1024, n = 10;
void **p = malloc(1024 * 1024 * sizeof (void *)), *q;
free(malloc(1026 * 1024 * 1024)); // 1GBくらいを確保して解放(意図しない断片化を防ぐため).
for (i = 0; i < n; i++)
p[i] = malloc(sz);
q = malloc(sz * 2);
for (i = 1; i < n; i += 2)
free(p[i]);
clock_t t0 = clock();
for (i = 0; i < 1000000; i++) {
free(q);
free(p[0]);
p[0] = malloc(sz);
q = malloc(sz * 2);
}
clock_t t1 = clock();
printf("%f[sec]\n", (double) (t1 - t0) / CLOCKS_PER_SEC);
return 0;
}AClass(MemMan) {
ACrit32L0B1 idxSiz; // 空きメモリブロック情報オブジェクトの、sizメンバをキーとするインデックス.
};| n=10 | n=65536 | |
| オリジナル（msvcrt.dllのmalloc/freeを使用) | 613ms | 4178ms |
| ACrit32L0B1を使ったmalloc/free | 306ms | 573ms |
| ACrit32L0B2を使ったmalloc/free | 320ms | 600ms |
| ACrit32L0B4を使ったmalloc/free | 459ms | 559ms |
| ACrit32L0B1 | 1529ms | |
| ACrit32L0B2 | 1068ms | |
| ACrit32L0B4 | 812ms | ACrit32ではこれが最速 |
| hash 582 | 951ms | |
| hash 512 | 895ms | |
| hash 1024 | 867ms | ハッシュ関数をカスタマイズしないのならここが限界 |
| ACrit32L0B1 | 1529ms | |
| ACrit32L0B2 | 1068ms | |
| ACrit32L0B4 | 812ms | ACrit32ではこれが最速 |
| hash 582 | 951ms | |
| hash 512 | 895ms | |
| hash 1024 | 867ms | ハッシュ関数をカスタマイズしないのならここが限界 |
| hash2 582 | 566ms | |
| hash2 512 | 507ms | |
| hash2 1024 | 482ms | ハッシュ関数をカスタマイズすればここまでいける |
