Как я могу получить количество различных значений в Python, не сохраняя большой набор значений

Question

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

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

Мне интересно, есть ли лучший способ сделать это? Может быть, некоторые другие встроенные структуры данных могут мне помочь? Спасибо!

Answer 1

Используйте Trie . Существует несколько библиотек Python, таких как Marisa-Trie . Или посмотрите этот ответ о переполнении стека, чтобы создать свой собственный Как создать TRIE в Python . Увеличивайте счетчик каждый раз, когда новое слово добавляется в Trie.

Вот простая реализация вложенного словаря. Он отслеживает общее количество слов и количество каждого слова.

END = 'end'

class Trie:

    def __init__(self, words_iterable):
        self.root = {}
        self.size = 0

        for word in iter(words_iterable):
            self.insert(word)

    def insert(self, word):
        current_dict = self.root
        for letter in word:
            current_dict = current_dict.setdefault(letter, {})

        if END not in current_dict:
            current_dict[END] = 0
            self.size += 1
        current_dict[END] += 1

    def count(self, word):
        current_dict = self.root
        for letter in word:
            current_dict = current_dict.setdefault(letter, {})
        return current_dict.get(END, 0)

    def __len__(self):
        return self.size

    def __str__(self):
        return str(self.root)

Примеры:

trie = Trie('one two one three four'.split())
trie.insert('four')

print(trie)

>>> {'o': {'n': {'e': {'end': 2}}}, 't': {'w': {'o': {'end': 1}}, 'h': {'r':
    {'e': {'e': {'end': 1}}}}}, 'f': {'o': {'u': {'r': {'end': 2}}}}}

len(trie)
>>> 4

trie.count('four')
>>> 2