Как использовать LRU-кеш для не хэш-списков? - PullRequest
Новая
       83

Как использовать LRU-кеш для не хэш-списков?

0 голосов
/ 12 марта 2020

Расстояние Левенштейна для символов в строках может быть вычислено с помощью lru_cache: 

from functools import lru_cache
from itertools import zip_longest

@lru_cache(maxsize=4095)
def ld(s, t):
    """
    Levenshtein distance memoized implementation from Rosetta code:
    https://rosettacode.org/wiki/Levenshtein_distance#Python
    """
    if not s: return len(t)
    if not t: return len(s)
    if s[0] == t[0]: return ld(s[1:], t[1:])
    l1 = ld(s, t[1:])      # Deletion.
    l2 = ld(s[1:], t)      # Insertion.
    l3 = ld(s[1:], t[1:])  # Substitution.
    return 1 + min(l1, l2, l3)

Например 

>>> ld("hello how are the you ?", "how Halo how you are the ?")
13

Однако, если я хочу отслеживать расстояние между 2 списками слов вместо символов в строках, без lru_cache работает: 

from functools import lru_cache
from itertools import zip_longest

#@lru_cache(maxsize=4095)
def ld(s, t):
    """
    Levenshtein distance memoized implementation from Rosetta code:
    https://rosettacode.org/wiki/Levenshtein_distance#Python
    """
    if not s: return len(t)
    if not t: return len(s)
    if s[0] == t[0]: return ld(s[1:], t[1:])
    l1 = ld(s, t[1:])      # Deletion.
    l2 = ld(s[1:], t)      # Insertion.
    l3 = ld(s[1:], t[1:])  # Substitution.
    return 1 + min(l1, l2, l3)

Использование: 

 >>> ld("hello how are the you ?".split(), "how Halo how you are the ?".split())

Однако без кеш LRU, он не будет работать с длинным списком слов.

А с LRU-кешем выдает необратимую ошибку типа: 

>>> ld("hello how are the you ?".split(), "how Halo how you are the ?".split())

---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-7-1de95d00ebae> in <module>
----> 1 ld("hello how are the you ?".split(), "how Halo how you are the ?".split())

TypeError: unhashable type: 'list'

Мои вопросы:

  • Можно ли составить список строк Сравнение может быть таким, что lru_cache можно использовать?
  • Если невозможно как-то составить список слов sh, как мне go эффективно рассчитать расстояние, чтобы найти расстояние между двумя списками слов? Только через Dynami c программирования?

1 Ответ

2 голосов
/ 12 марта 2020

Поскольку вы изменяете не списки, а только нарезку, вы можете передавать кортежи, которые можно хэшировать. 

s = "hello how are the you ?".split()
t = "how Halo how you are the ?".split()
ld(tuple(s), tuple(t))

В противном случае вы можете избежать использования функций lru_cached, используя циклы с дополнительным пространством, где вы можете запомнить расчеты

...