Publicado · en mejora
Guía de Programación dinámica · 6/6
Por ahora, este capítulo solo está disponible en inglés.
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 comentarios
Iniciar sesión · Inicia sesión para dejar un comentario.
Sé el primero en comentar.