Namaran

Code daily. Without assist.

2026-09-08

user_cache.c

#include <stdio.h>

static int queries = 0;

static int load_score(int user_id) {
    queries++;
    return user_id * 10;
}

int main(void) {
    int author_of[] = {2, 0, 2, 1, 0, 0};
    int cache[3] = {0};
    for (int i = 0; i < 6; i++) {
        int id = author_of[i];
        if (cache[id] == 0) {
            cache[id] = load_score(id);
        }
    }
    printf("%d queries\n", queries);
}

これは何を出力するでしょうか?

Answer

5 queries です。

cache は、ユーザーIDごとに読み込んだ結果を覚えておき、同じユーザーを二度読まないための配列です。まだ読んでいないことを 0 で表しているので、cache[id] == 0 のときだけ load_score を呼びます。

ところが load_score(0) の結果は 0 * 10 で 0 です。ID 0 のユーザーを読み込んでも cache[0] は 0 のままなので、次に ID 0 が来たときも未取得と判定され、もう一度読み込まれます。

順に追うと、ID 2 で1回目、ID 0 で2回目のクエリが走り、2度目の ID 2 はキャッシュから返ります。ID 1 で3回目、残る2つの ID 0 で4回目と5回目です。異なるユーザーは3人なので、キャッシュが効いていれば 3 queries でした。

取得結果が取りうる値を未取得の印にすると、印と結果の区別がつかなくなります。取得済みかどうかを bool loaded[3] のような別の配列で持つか、結果が取りえない値を印にすれば、ID 0 も1回の読み込みで済みます。