Соотношение Python difflib, quick_ratio и real_quick_ratio - PullRequest
Новая
       7

Соотношение Python difflib, quick_ratio и real_quick_ratio

0 голосов
/ 23 мая 2018

Я использовал difflib SequenceMatcher,

И я обнаружил, что функция ratio слишком медленная.Читая документацию , я обнаружил quick_ratio и real_quick_ratio, которые должны быть быстрее (как следует из названия) и служат верхней границей.

Однако документации не хватает описания допущений, которые они делают, или ускорения, которое они предлагают.

Когда я должен использовать любую версию и чем пожертвовать?

1 Ответ

0 голосов
/ 23 мая 2018

Взгляд

Начиная с вспомогательного метода _calculate_ratio

def _calculate_ratio(matches, length):
    if length:
        return 2.0 * matches / length
    return 1.0

коэффициент

ratio находит совпадения и делит их на общую длинуОбе строки раз 2: 

    return _calculate_ratio(matches, len(self.a) + len(self.b))

quick_ratio

Это на самом деле то, что говорит исходный комментарий: 

    # viewing a and b as multisets, set matches to the cardinality
    # of their intersection; this counts the number of matches
    # without regard to order, so is clearly an upper bound

, а затем 

    return _calculate_ratio(matches, len(self.a) + len(self.b))

real_quick_ratio

real_quick_ratio находит самую короткую строку, деленную на общую длину строк, умноженную на 2: 

    la, lb = len(self.a), len(self.b)
    # can't have more matches than the number of elements in the
    # shorter sequence
    return _calculate_ratio(min(la, lb), la + lb)

это реальная верхняя граница.

Заключение

real_quick_ratio ничего не делает, чтобы посмотреть на строки, чтобы увидеть, есть ли какие-либо совпадения, он только вычисляет верхнюю границу на основе длины строки.

Теперь я не специалист по алгоритму, но если вы считаете, что ratio слишком медленный, чтобы выполнить работу, я рекомендую использовать quick_ratio, поскольку он адекватно относится к проблеме.

Примечание по эффективности

Из строки документации 

    .ratio() is expensive to compute if you haven't already computed
    .get_matching_blocks() or .get_opcodes(), in which case you may
    want to try .quick_ratio() or .real_quick_ratio() first to get an
    upper bound.
...