Реализация дерева с Python 3


Это просто классическая реализация префиксного дерева с использованием Python 3.6, с типами. Я PHP-разработчик, так что это мои первые попытки с помощью Python.

Я знаю, что я могу улучшить читаемость моего кода, это немного сумбурно, но я изо всех сил найти правильный способ сделать это. Я уверен, что я пропускаю много способов обновления здесь :-)

from typing import Optional


class Trie:
    def __init__(self):
        self.root = Node(char=None, is_word=False)

    def add(self, word: str) -> None:
        current = self.root
        is_end_of_word = False

        for i in range(0, len(word)):
            char = word[i]
            if i == len(word) - 1:
                is_end_of_word = True

            if not current.children:
                node_to_insert = Node(char, is_end_of_word)
                current.add_child(node_to_insert)
                current = node_to_insert
                continue

            if char not in current.children:
                node_to_insert = Node(char, is_end_of_word)
                current.add_child(node_to_insert)
                current = node_to_insert
            else:
                current = current.children[char]

    def contains(self, word: str) -> bool:
        current = self.root

        for char in word:
            if not current.children:
                return False

            if char in current.children:
                current = current.children[char]
                continue
            else:
                return False

        if not current.is_word:
            return False

        return True

    def remove(self, word: str) -> None:
        current = self.root

        for i in range(0, len(word)):
            char = word[i]
            is_end_of_word = False

            if i == len(word) - 1:
                is_end_of_word = True

            if char in current.children:
                if current.children[char].is_word and is_end_of_word:
                    current.children[char].is_word = False
                    return
                current = current.children[char]
            else:
                return

    def retrieve_all_words(self) -> list:
        return self._retrieve_all_words(self.root, '', [])

    def _retrieve_all_words(self, current: 'Node', word: str, words: list) -> list:
        for child in current.children.values():
            word = word + child.char
            if child.is_word:
                words.append(word)

            if child.children:
                self._retrieve_all_words(child, word, words)
                word = word[:-1]
                continue

            word = word[:-1]

        return words


class Node:
    def __init__(self, char: Optional[str], is_word: bool):
        self.char = char
        self.is_word = is_word
        self.children = {}

    def add_child(self, node: 'Node'):
        self.children[node.char] = node


166
7
задан 25 марта 2018 в 11:03 Источник Поделиться
Комментарии
2 ответа

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

Давайте попробуем посмотреть, что можно улучшить/сделать более подходящие для Python.

Петли, как родной

Я настоятельно рекомендую Ned Batchelder's excellent talk "loop like a native". Одна идея заключается в том, что всякий раз, когда вы используете for i in range(len(iterable))вы, вероятно, делаете это неправильно. В вашем случае, вы могли бы использовать for i, char in enumerate(word):.

Конец слова

В конце слова обнаружение может быть сделано в одном операторе: is_end_of_word = i == len(word) - 1. Также, вы можете избавиться от определение до цикла и даже в петли, иногда, можно определить ее только за if char in current.children: потому что вы используете его только там.

Реорганизовать логику

Иногда, вы проверьте, если что-то пуст, а затем, если он содержит определенный элемент. Это может быть factorised из:

Кроме того, упрощение кода if (cond) return False else return Trueвы могли бы переписать contains:

def contains(self, word: str) -> bool:
current = self.root
for char in word:
if char not in current.children:
return False
current = current.children[char]
return current.is_word

Затем в _retrieve_all_wordsвы можете избавиться от continue С помощью простого else который делает вещи более четко. Затем, вы можете factorise общие код в конце 2 филиалы и получить более простой:

        if child.is_word:
words.append(word)
if child.children:
self._retrieve_all_words(child, word, words)
word = word[:-1]

Наконец, вы можете использовать += для упрощения word = word + child.char в word += child.char.

На этом этапе код выглядит как:

from typing import Optional

class Trie:
def __init__(self):
self.root = Node(char=None, is_word=False)

def add(self, word: str) -> None:
current = self.root

for i, char in enumerate(word):
if char in current.children:
current = current.children[char]
else:
is_end_of_word = i == len(word) - 1
node_to_insert = Node(char, is_end_of_word)
current.add_child(node_to_insert)
current = node_to_insert

def contains(self, word: str) -> bool:
current = self.root
for char in word:
if char not in current.children:
return False
current = current.children[char]
return current.is_word

def remove(self, word: str) -> None:
current = self.root
for i, char in enumerate(word):
if char not in current.children:
return
is_end_of_word = i == len(word) - 1
if current.children[char].is_word and is_end_of_word:
current.children[char].is_word = False
return
current = current.children[char]

def retrieve_all_words(self) -> list:
return self._retrieve_all_words(self.root, '', [])

def _retrieve_all_words(self, current: 'Node', word: str, words: list) -> list:
for child in current.children.values():
word += child.char
if child.is_word:
words.append(word)
if child.children:
self._retrieve_all_words(child, word, words)
word = word[:-1]
return words

class Node:
def __init__(self, char: Optional[str], is_word: bool):
self.char = char
self.is_word = is_word
self.children = {}

def add_child(self, node: 'Node'):
self.children[node.char] = node

t = Trie()
t.add("toto")
t.add("tutu")
t.add("foobar")
print(t)
print(t.retrieve_all_words())
print(t.contains("tot"))
print(t.contains("toto"))
print(t.contains("totot"))

Хранение вещей в другой формат

Вместо сохранения is_word атрибут, возможно, вы могли бы добавить магазин часовой, как None сказать, что у нас есть полное слово здесь. Это может быть записано так:

from typing import Optional

class Trie:
def __init__(self):
self.root = Node(char=None)

def add(self, word: str) -> None:
current = self.root

for char in list(word) + [None]:
if char in current.children:
current = current.children[char]
else:
node_to_insert = Node(char)
current.add_child(node_to_insert)
current = node_to_insert

def contains(self, word: str) -> bool:
current = self.root
for char in list(word) + [None]:
if char not in current.children:
return False
current = current.children[char]
return True

def remove(self, word: str) -> None:
current = self.root
for char in list(word) + [None]:
if char not in current.children:
return
elif char is None:
del current.children[char]
else:
current = current.children[char]

def retrieve_all_words(self) -> list:
return self._retrieve_all_words(self.root, '', [])

def _retrieve_all_words(self, current: 'Node', word: str, words: list) -> list:
for child in current.children.values():
if child.char is None:
words.append(word)
else:
word += child.char
if child.children:
self._retrieve_all_words(child, word, words)
word = word[:-1]
return words

class Node:
def __init__(self, char: Optional[str]):
self.char = char
self.children = {}

def add_child(self, node: 'Node'):
self.children[node.char] = node

t = Trie()
t.add("toto")
t.add("tutu")
t.add("foobar")
print(t)
print(t.retrieve_all_words())
print(t.contains("tot"))
print(t.contains("toto"))
print(t.contains("totot"))
t.remove("toto")
print(t.retrieve_all_words())
print(t.contains("toto"))

Обратно word = word + child.char

Что-то я должен упоминалось раньше, но заметил на конце.

В _retrieve_all_wordsдобавьте символ word только, чтобы удалить его позже. Это гораздо понятнее (и эффективнее?) просто написать word + char в тех местах, где вы на самом деле нужно поговорить с добавленной характер.

Тогда код становится:

def _retrieve_all_words(self, current: 'Node', word: str, words: list) -> list:
for child in current.children.values():
if child.char is None:
words.append(word)
elif child.children:
self._retrieve_all_words(child, word + child.char, words)
return words

4
ответ дан 25 марта 2018 в 05:03 Источник Поделиться

это мелочь, но API вы предоставляете не очень подходящие для Python. вместо того, чтобы использовать containsспособ, вы должны перегружать in. аналогичным образом, а не Определение return_all_wordsнеобходимо определить итерации, так что вы можете цикл через него, а затем список преобразования будет просто list(tried). это может показаться незначительным, но такой согласованности является то, что делает питон приятно использовать.

4
ответ дан 25 марта 2018 в 11:03 Источник Поделиться