Питон: шаблон дикие соответствующие карты с мемоизацией


Вот мое мнение на шаблон Дикие карты совпадающие с мемоизацией.

Буду признателен за комментарии на ясность кода, а также предложены пути улучшения читабельности и ремонтопригодности (для больших проектов).

Кроме того, замечания о том, как изменить алгоритм лучше (сделать это снизу, а не сверху, например) тоже будут очень рады.

Последнее, что я ищу больше тестов, что приведет к усилению покрытия кода, особенно в пограничных случаях/граничные условия. Спасибо

Закомментированных секций для сбора и распечатки информации, которые я использовал при отладке. Код корректен и эти разделы больше не нужны.


class wild_card_pattern_matching:
    def __init__(self, p, s):
        self.m = [[None for _ in range(len(p) + 1)] for _ in range(len(s) + 1)]
        self.p = p
        self.s = s
        self.c = 0

    def match(self):
        def f(p,s,p_idx,s_idx):
            self.c += 1

            # end condition 1
            if p_idx == s_idx == 0:
                self.m[s_idx][p_idx] = True

            # end condition 2
            elif s_idx == 0:
                self.m[s_idx][p_idx] = f(p,s,p_idx-1,s_idx) and p[p_idx-1] == '*'

            # memo table init
            elif p_idx == 0:
                self.m[s_idx][p_idx] = False

            # use memo if possible
            elif self.m[s_idx][p_idx] != None:
                return self.m[s_idx][p_idx]

            # choose between ignoring * and "accepting" it
            elif p[p_idx-1] == '*': 
                self.m[s_idx][p_idx] = f(p,s,p_idx-1,s_idx) or f(p,s,p_idx,s_idx-1)

            # matching characters
            elif p[p_idx-1] == '?' or p[p_idx-1] == s[s_idx-1]: 
                self.m[s_idx][p_idx] = f(p,s,p_idx-1,s_idx-1)

            # pattern != string
            else: 
                self.m[s_idx][p_idx] = False

            return self.m[s_idx][p_idx]

        f(self.p,self.s,len(self.p), len(self.s))

        return self.m[-1][-1]

obj_ls = [wild_card_pattern_matching('*', '')]
obj_ls += [wild_card_pattern_matching('*', 'a')]
obj_ls += [wild_card_pattern_matching('*', 'b')]
obj_ls += [wild_card_pattern_matching('a*', 'ab')]
obj_ls += [wild_card_pattern_matching('*b', 'a')]
obj_ls += [wild_card_pattern_matching('a*a', 'aba')]
obj_ls += [wild_card_pattern_matching('*?*?', 'aa')]
obj_ls += [wild_card_pattern_matching('c*d?*', 'cda')]
obj_ls += [wild_card_pattern_matching('?*?*?*', 'xx0')]
obj_ls += [wild_card_pattern_matching('a', 'a')]
obj_ls += [wild_card_pattern_matching('', 'a')]
obj_ls += [wild_card_pattern_matching('******a*a', 'a')]
obj_ls += [wild_card_pattern_matching('******a*a', 'aa')]
obj_ls += [wild_card_pattern_matching('******?*a', 'a')]
obj_ls += [wild_card_pattern_matching('******a*a**', 'a')]
obj_ls += [wild_card_pattern_matching('******a*a*', 'ababaab')]
obj_ls += [wild_card_pattern_matching('******a*a*', 'ababaa')]

print '         string         pattern    result    counter'
print '='*55
for w in obj_ls:
    print '%15s%15s%10r%10d' % (w.s,w.p,w.match(),w.c)
#    for l in w.m:
#        print l


Комментарии
1 ответ

Взгляните на стиль и нейминг руководства, а именно; Пеп-8. Имена классов должны быть CamelCaseD и метод/атрибуты должны быть snake_case. Ваши переменные имеют названия s, p, c и т. д. что не сделать это ясно, на первый взгляд, что они собой представляют, ни одной строкой документации предоставляется для справки.


Кроме того, работает ваш код дает мне:

         string         pattern    result    counter
=======================================================
* True 2
a * True 4
b * True 4
ab a* True 5
a *b False 1
aba a*a True 6
aa *?*? True 5
cda c*d?* True 6
xx0 ?*?*?* True 7
a a True 2
a False 1
a ******a*a False 10
aa ******a*a True 10
a ******?*a False 10
a ******a*a** False 35
ababaab ******a*a* True 21
ababaa ******a*a* True 19

где я заметил, что ваш счетчик достиг \$35\$ за шаблон ******a*a**. В этом случае (и еще несколько подобных случаев), вы можете просто вернуться False если ваши скороговоркой, после удаления всех * персонажей еще больше, чем заданная строка. Потому что тогда ваша строка никогда не будет в состоянии покрыть узором.

Как прямо сейчас, вам нужно лишь * и ? символов; для любой длины символов и ровно один символ, указанный способ уменьшает вашу рекурсию много в нескольких случаях:

def match(self):
if len(self.s) < len(self.p.replace('*', '')):
return False

и результат:

         string         pattern    result    counter
=======================================================
[=======================SAME======================]
a False 1
a ******a*a False 0
aa ******a*a True 10
a ******?*a False 0
a ******a*a** False 0
ababaab ******a*a* True 21
ababaa ******a*a* True 19

Приведенный выше фрагмент также может быть помещен внутри рекурсивной f вызова. Я все еще должны выяснить, в какой секции он будет делать больше смысла, но в основном для каких-то определенных фиксированных матч с рисунком на строку, если остальные шаблон удовлетворяет указанным выше ограничением, вы можете просто пропустить остаток итераций.


Для тестов, использовать в Python собственного unittest модуль для создания глумится. Есть набор шаблонов и строк, и повторно запустить утверждения относительно ожидаемых значений.

3
ответ дан 7 февраля 2018 в 12:02 Источник Поделиться