Veröffentlicht · wird verbessert
Dynamische Programmierung-Anleitung · 6/6
Dieses Kapitel ist vorerst nur auf Englisch verfügbar.
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 Kommentare
Anmelden · Melde dich an, um einen Kommentar zu schreiben.
Schreib den ersten Kommentar.