Cで配列とハッシュの速度比較

なんか面白そうなのあったので

cでもやってみた。

1000程度だとほとんど誤差程度しか差分が現れない。
10000でようやく数値的には意味のある値(数10ms)になったが
人が感じられる程度の差分は無いと思う

100000を超えると配列を使うのは現実的では無さそう

ただやはり境界が100くらいというのは言語関係無く共通なのかな？

環境とか

• Core i5-13400
• fedora 40 + xfce
• gcc 14.2.1

コンパイルオプションの指定はなし

コード

メモリ解放漏れは最大が取れるなら最大の２倍も取れるでしょうという
ことでご容赦

details

#include <search.h>
#include <stdarg.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <unistd.h>

#define MESUREMENT_TIMES 10
#define ARRAY_SIZE(a) (sizeof(a) / sizeof(a[0]))

#define ERR_RETn(c)                                                                                \
    do {                                                                                           \
        if (c)                                                                                     \
            goto error_return;                                                                     \
    } while (0)

typedef struct {
    int sign;
    int s;
    int ms;
} diff_t;

FILE *fp;
struct timespec bef_ts = {0};
uint64_t *arr = NULL;
uint64_t *target = NULL;

diff_t diff_ms(struct timespec *cur, struct timespec *last) {
    diff_t elapse;
    if (cur->tv_sec > last->tv_sec) {
        elapse.sign = 1;
        if (cur->tv_nsec < last->tv_nsec) {
            elapse.s = cur->tv_sec - last->tv_sec - 1;
            elapse.ms = (cur->tv_nsec + (int)1e9 - last->tv_nsec) / (int)1e6;
        } else {
            elapse.s = cur->tv_sec - last->tv_sec;
            elapse.ms = (cur->tv_nsec - last->tv_nsec) / (int)1e6;
        }
    } else if (cur->tv_sec == last->tv_sec) {
        elapse.s = 0;
        elapse.sign = (cur->tv_nsec - last->tv_nsec);
        elapse.ms = abs(elapse.sign / (int)1e6);
    } else {
        elapse.sign = -1;
        if (cur->tv_nsec > last->tv_nsec) {
            elapse.s = last->tv_sec - cur->tv_sec - 1;
            elapse.ms = (int)((last->tv_nsec + (int)1e9 - cur->tv_nsec) / (int)1e6);
        } else {
            elapse.s = last->tv_sec - cur->tv_sec;
            elapse.ms = (int)((last->tv_nsec - cur->tv_nsec) / (int)1e6);
        }
    }
    return elapse;
}

double diff(struct timespec *cur, struct timespec *last) {
    double ns = cur->tv_nsec - last->tv_nsec;
    double s = cur->tv_sec - last->tv_sec;
    return (ns / 1e9) + s;
}
void checkpoint(char *s, ...) {
    va_list ap;
    struct timespec ts;
    diff_t elapse;
    char sign;

    clock_gettime(CLOCK_MONOTONIC, &ts);

    elapse = diff_ms(&ts, &bef_ts);
    sign = (elapse.sign < 0) ? '-' : ' ';
    fprintf(fp, "%08ld.%03ld (%c%d.%03d) ", ts.tv_sec, ts.tv_nsec / (int)1e6, sign, elapse.s,
            elapse.ms);
    va_start(ap, s);
    vfprintf(fp, s, ap);
    va_end(ap);
    fprintf(fp, "\n");
    bef_ts = ts;
}

void prepare_target(uint64_t size, uint64_t num) {
    srand(time(NULL));
    if (target)
        free(target);
    target = malloc(sizeof(uint64_t) * num);

    for (uint64_t i = 0; i < num; i++) {
        target[i] = rand() % size;
    }
}

static void swap64(uint64_t *arr, uint64_t a, uint64_t b) {
    uint64_t tmp;
    tmp = arr[a];
    arr[a] = arr[b];
    arr[b] = tmp;
}

void shuffle(uint64_t *arr, uint64_t num) {
    for (uint64_t i = num - 1; i > 0; i--) {
        uint64_t j = rand() % (i + 1);
        swap64(arr, i, j);
    }
}
void prepare_array(uint64_t num) {
    if (arr)
        free(arr);
    arr = malloc(sizeof(uint64_t) * num);
    for (uint64_t i = 0; i < num; i++) {
        arr[i] = i;
    }

    shuffle(arr, num);
}
uint64_t digit(uint64_t n) {
    if (n == 0)
        return 1;

    int digits = 0;
    while (n != 0) {
        n /= 10;
        digits++;
    }

    return digits;
}
void prepare_hash(uint64_t num) {
    ENTRY item;
    uint64_t maxlen;

    hdestroy();
    hcreate(num);

    maxlen = digit(num) + 1;

    for (size_t i = 0; i < num; i++) {
        item.key = malloc(maxlen);
        item.data = (void*)(intptr_t)i;
        sprintf(item.key, "%ld", i);
        if (!hsearch(item, ENTER)) {
            fprintf(fp, "entry error at %ld\n", i);
            break;
        }
    }
}
void prepare(uint64_t size, uint64_t num) {
    fp = stdout;

    prepare_target(size, num);

    // checkpoint("create array start");
    prepare_array(size);
    // checkpoint("create array end");
    // checkpoint("create hash start");
    prepare_hash(size);
    // checkpoint("create hash end");

    // fprintf(fp, "created arr:%d target:%d\n", size, num);
}

void search_array(uint64_t size, uint64_t num) {
    bool found;
    for (uint64_t i = 0; i < num; i++) {
        found = false;
        for (uint64_t j = 0; j < size; j++) {
            if (target[i] == arr[j]) {
                found = true;
                break;
            }
        }
        if (!found) {
            fprintf(fp, "ERROR array not found %ld\n", i);
            break;
        }
    }
}
void search_hash(uint64_t size, uint64_t num) {
    ENTRY e, *ep;
    uint64_t maxlen = digit(size) + 1;
    e.key = malloc(maxlen);
    for (size_t i = 0; i < num; i++) {
        sprintf(e.key, "%ld", target[i]);
        ep = hsearch(e, FIND);
        if (!ep) {
            fprintf(fp, "ERROR hash not found %ld\n", i);
            break;
        }
    }
}

void one_shot(int argc, char *argv[]) {
    uint64_t size, num;
    ERR_RETn(argc < 3);
    size = strtoul(argv[1], NULL, 0);
    num = strtoul(argv[2], NULL, 0);
    ERR_RETn(size < 1);
    ERR_RETn(num < 1);

    prepare(size, num);

    checkpoint("search array start");
    search_array(size, num);
    checkpoint("search array end");
    checkpoint("search hash start");
    search_hash(size, num);
    checkpoint("search hash end");
error_return:
    return;
}

void measurement(void) {
    uint64_t sizes[] = {1, 3, 10, 30, 100, 300, 1000, 3000, 10000, 30000, 100000};
    uint64_t times[] = {1, 3, 10, 30, 100, 300, 1000, 3000, 10000, 30000, 100000};
    double results;
    struct timespec st, en;

    for (size_t i = 0; i < ARRAY_SIZE(sizes); i++) {
        for (size_t j = 0; j < ARRAY_SIZE(times); j++) {
            prepare(sizes[i], times[j]);
            fprintf(fp, "%ld,%ld", sizes[i], times[j]);
            results = 0;
            for (int k = 0; k < MESUREMENT_TIMES; k++) {
                clock_gettime(CLOCK_MONOTONIC, &st);
                search_array(sizes[i], times[j]);
                clock_gettime(CLOCK_MONOTONIC, &en);
                results += diff(&en, &st);
            }
            fprintf(fp, ",%.9f", results / MESUREMENT_TIMES);

            results = 0;
            for (int k = 0; k < MESUREMENT_TIMES; k++) {
                clock_gettime(CLOCK_MONOTONIC, &st);
                search_hash(sizes[i], times[j]);
                clock_gettime(CLOCK_MONOTONIC, &en);
                results += diff(&en, &st);
            }
            fprintf(fp, ",%.9f\n", results / MESUREMENT_TIMES);
        }
    }
}

int main(int argc, char *argv[]) {
    if (argc < 3) {
        measurement();
    } else {
        one_shot(argc, argv);
    }

    return 0;
}

出力結果

details

1,1,0.000000031,0.000000152
1,3,0.000000029,0.000000243
1,10,0.000000054,0.000000666
1,30,0.000000121,0.000001673
1,100,0.000000248,0.000005097
1,300,0.000000374,0.000012336
1,1000,0.000001179,0.000050634
1,3000,0.000005697,0.000139783
1,10000,0.000011645,0.000409750
1,30000,0.000034812,0.001313685
1,100000,0.000114073,0.003979638
3,1,0.000000022,0.000000126
3,3,0.000000030,0.000000159
3,10,0.000000046,0.000000446
3,30,0.000000120,0.000001262
3,100,0.000000358,0.000004056
3,300,0.000001087,0.000011900
3,1000,0.000004979,0.000041226
3,3000,0.000020515,0.000134226
3,10000,0.000083170,0.000410151
3,30000,0.000261332,0.001216504
3,100000,0.000888538,0.004152858
10,1,0.000000037,0.000000075
10,3,0.000000054,0.000000162
10,10,0.000000091,0.000000430
10,30,0.000000250,0.000001319
10,100,0.000000915,0.000003990
10,300,0.000002664,0.000013525
10,1000,0.000010807,0.000040401
10,3000,0.000045350,0.000130197
10,10000,0.000165781,0.000397184
10,30000,0.000500475,0.001336311
10,100000,0.001707325,0.003981892
30,1,0.000000047,0.000000075
30,3,0.000000060,0.000000175
30,10,0.000000324,0.000000528
30,30,0.000000688,0.000001349
30,100,0.000002512,0.000005038
30,300,0.000008548,0.000015865
30,1000,0.000028979,0.000051311
30,3000,0.000089342,0.000155535
30,10000,0.000303279,0.000512690
30,30000,0.000824252,0.001645404
30,100000,0.002835062,0.005596204
100,1,0.000000039,0.000000100
100,3,0.000000160,0.000000198
100,10,0.000000720,0.000000537
100,30,0.000001926,0.000001833
100,100,0.000005432,0.000005812
100,300,0.000017055,0.000017848
100,1000,0.000053706,0.000058616
100,3000,0.000158879,0.000173975
100,10000,0.000509449,0.000555394
100,30000,0.001480433,0.001676905
100,100000,0.004944289,0.005615320
300,1,0.000000277,0.000000122
300,3,0.000000549,0.000000226
300,10,0.000001588,0.000000578
300,30,0.000003622,0.000001654
300,100,0.000012053,0.000005242
300,300,0.000038476,0.000015903
300,1000,0.000129649,0.000056131
300,3000,0.000377646,0.000170716
300,10000,0.001249664,0.000585261
300,30000,0.003791034,0.001809174
300,100000,0.012464885,0.005750113
1000,1,0.000000348,0.000000098
1000,3,0.000001089,0.000000199
1000,10,0.000002970,0.000000637
1000,30,0.000012303,0.000001788
1000,100,0.000041307,0.000005736
1000,300,0.000113882,0.000018028
1000,1000,0.000378125,0.000060821
1000,3000,0.001159312,0.000186087
1000,10000,0.003910250,0.000639451
1000,30000,0.011734500,0.001894953
1000,100000,0.038917484,0.006215640
3000,1,0.000002051,0.000000086
3000,3,0.000003796,0.000000184
3000,10,0.000009639,0.000000598
3000,30,0.000036472,0.000001915
3000,100,0.000103678,0.000006201
3000,300,0.000361020,0.000018522
3000,1000,0.001187638,0.000064373
3000,3000,0.003493065,0.000200109
3000,10000,0.011534802,0.000692156
3000,30000,0.034421020,0.002011138
3000,100000,0.114641280,0.006765641
10000,1,0.000002465,0.000000098
10000,3,0.000014811,0.000000192
10000,10,0.000040636,0.000000661
10000,30,0.000129825,0.000002239
10000,100,0.000367694,0.000006934
10000,300,0.001161516,0.000021346
10000,1000,0.004012819,0.000076283
10000,3000,0.011734686,0.000220734
10000,10000,0.039153386,0.000732755
10000,30000,0.116551649,0.002141106
10000,100000,0.387051434,0.007175098
30000,1,0.000012782,0.000000212
30000,3,0.000031477,0.000000220
30000,10,0.000104605,0.000000980
30000,30,0.000417403,0.000002396
30000,100,0.001148609,0.000008925
30000,300,0.003720401,0.000027286
30000,1000,0.011448437,0.000087526
30000,3000,0.034788369,0.000277084
30000,10000,0.116952803,0.000850633
30000,30000,0.354279434,0.002604656
30000,100000,1.174327502,0.008274492
100000,1,0.000008825,0.000000109
100000,3,0.000114416,0.000000260
100000,10,0.000472452,0.000000703
100000,30,0.001109289,0.000002328
100000,100,0.003634627,0.000011034
100000,300,0.012217811,0.000033727
100000,1000,0.041109538,0.000104681
100000,3000,0.118619820,0.000385387
100000,10000,0.393740725,0.001116501
100000,30000,1.191279676,0.003728296
100000,100000,3.941975097,0.012143427