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回の読み込みで済みます。