リリース・改善中
動的計画法 ガイド · 6/6
この章は現在、英語でのみ提供しています。
Many everyday tools run a DP inside, often under a different name. This chapter surveys them, shows two small examples and lists the mistakes that most often break DP code.
O(ND) time for D differences.A CLI can suggest a fix for a mistyped command using edit distance with a rolling row.
def edit_distance(s: str, t: str) -> int:
prev = list(range(len(t) + 1))
for i, a in enumerate(s, start=1):
cur = [i] + [0] * len(t)
for j, b in enumerate(t, start=1):
cur[j] = prev[j - 1] if a == b else 1 + min(prev[j], cur[j - 1], prev[j - 1])
prev = cur
return prev[-1]
def suggest(word: str, commands: list[str], max_distance: int = 2) -> str | None:
best = min(commands, key=lambda c: edit_distance(word, c))
return best if edit_distance(word, best) <= max_distance else None
print(suggest("stauts", ["status", "commit", "push", "stash"])) # status
print(suggest("deploy", ["status", "commit", "push", "stash"])) # NonePython's difflib.get_close_matches is similar, but it ranks by a SequenceMatcher similarity ratio, not minimal edit distance.
A monitor sees responses as "fast" or "slow" and guesses whether the server was "ok" or "degraded" at each moment. Viterbi keeps, for each state at time t, the best path probability and a back pointer.
def viterbi(observations, states, start, trans, emit):
best = [{s: (start[s] * emit[s][observations[0]], None) for s in states}]
for obs in observations[1:]:
prev = best[-1]
best.append({
s: max((prev[p][0] * trans[p][s] * emit[s][obs], p) for p in states)
for s in states
})
state = max(states, key=lambda s: best[-1][s][0])
path = [state]
for layer in reversed(best[1:]):
state = layer[state][1]
path.append(state)
return path[::-1]
states = ("ok", "degraded")
start = {"ok": 0.9, "degraded": 0.1}
trans = {"ok": {"ok": 0.95, "degraded": 0.05}, "degraded": {"ok": 0.2, "degraded": 0.8}}
emit = {"ok": {"fast": 0.9, "slow": 0.1}, "degraded": {"fast": 0.3, "slow": 0.7}}
print(viterbi(["fast", "fast", "slow", "slow", "slow", "fast"], states, start, trans, emit))
# ['ok', 'ok', 'degraded', 'degraded', 'degraded', 'degraded']Real implementations add log probabilities, because long products of small numbers underflow to zero.
functools.cache never evicts, so a long-running service can grow without limit; use lru_cache(maxsize=...) or clear it.from functools import cache, lru_cache
@cache
def total(items: tuple[int, ...]) -> int:
return sum(items)
try:
total([1, 2, 3])
except TypeError as error:
print("lists cannot be cache keys:", error)
print(total((1, 2, 3))) # 6
@lru_cache(maxsize=1024) # evicts least recently used entries
def score(word: str) -> int:
return sum(map(ord, word))
score.cache_clear() # or free everything explicitly
コメント 0件
ログイン · ログインするとコメントできます。
最初のコメントを書いてみましょう。