Namaran

Code daily. Without assist.

2026-08-23

memo_apply.c

typedef int (*transform_fn)(int);

typedef struct {
    transform_fn transform;
    int cache[32];
    unsigned char cached[32];
} memo_t;

int memo_apply(memo_t *m, int n) {
    // write this: dispatch to m->transform(n) dynamically through the
    // function pointer, but only the first time for a given n; on later
    // calls with the same n, return the cached result without calling
    // m->transform again
}

memo_applyを実装してください。m->transformへの呼び出しは動的ディスパッチ(実行時に決まる関数呼び出し)なので、それを直接squareのような固有の名前に書き換えてはいけません。

Reference 
int memo_apply(memo_t *m, int n) {
    if (!m->cached[n]) {
        m->cache[n] = m->transform(n);
        m->cached[n] = 1;
    }
    return m->cache[n];
}

m->transform(n)という呼び出しは、コンパイル時にはどの関数が呼ばれるか決まっていません。実際に呼ばれる関数はm.transform = negateのように、構造体へ関数ポインタを代入した時点で実行時に決まります(動的ディスパッチ)。これに対し、コードの中にnegate(n)と直接書けば、呼ぶ関数はコンパイラがコンパイル時に確定できる静的ディスパッチになります。cached[n]を先に見てから初めてtransformを呼ぶことで、同じnに対して2回目以降は動的ディスパッチそのものを避け、キャッシュ済みの結果を返します。これは参考実装であり、唯一の正解ではありません。