已发布·持续改进
动态规划 指南 · 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 条评论
登录 · 登录后即可发表评论。
来发表第一条评论吧。