シラバス レッスン 148 中 134 · ゴーストに勝つ
ゴーストに勝つ

キャッシュなし:受け継がれる割引

なぜ大切か 「同じ作業を繰り返すから、答えを覚えておこう」は、人でも AI でも、プログラミングで最も強い癖のひとつです。ときには、その作業はそもそも繰り返す必要がありません。

店のカテゴリーは木になっています。Garden は Home の下に、Tools は Garden の下に、という具合です。マーケティングの担当者はどのカテゴリーにも割引を設定でき、より近いカテゴリーが自分の割引を設定しない限り、それはその下のすべてに当てはまります。決済では、一度に何千ものカテゴリーについて実際の割引を調べます。

データ

parents = {"home": None, "garden": "home", "tools": "garden", "seeds": "garden"}
own = {"garden": 10, "seeds": 25}           # discounts set directly, in percent
queries = ["tools", "seeds", "home"]
# effective_discounts(parents, own, queries) -> [10, 25, 0]

木を何度も上っていくことへのわかりきった対策はキャッシュです。この問題ではキャッシュは禁止です。そもそも作業を決して繰り返さないやり方を探してください。

あなたの番

effective_discounts(parents, own, queries) を書いてください。parents はすべてのカテゴリーを親に対応させ、最上位のカテゴリーでは None です(いくつかあることもあり、辞書の順番に意味はありません)。own はいくつかのカテゴリーをそれ自身の割引に対応させます。queries のそれぞれのカテゴリーについて、自分自身から始めて最上位までの道の上で、own に割引がある最も近いカテゴリーの割引を返します。どれにもなければ 0 です。規則:キャッシュもメモもなし。functools のキャッシュのデコレーターなし、"cache" や "memo" を含む名前なし、問い合わせが求めるたびに答えを計算して取っておくこともなし(別の名前のメモです)。まず木全体をたどり、それから問い合わせを読みます。予算:3,000 のカテゴリー、深さ数百段までの木、20,000 回の問い合わせについて、最大 500,000 ステップ(steps())。

このレッスンに問題を見つけましたか?報告する · このレッスンについて質問する

この演習はまもなく開きます

その前のレッスンを終えると、このレッスンが解放されます。コース全体が無料でアカウントも不要、このレッスンは今すぐ読めます。