test_hash.py

.gitignore

*.swp
*.pyc
*.pyo

test_hash.py

#!/usr/bin/python
# -*- coding: utf-8 -*-

import json

cars = json.loads(open('./fixtures/fipe_carro.json').read())
tree = {}

for v in cars:
    for name in v['translated_names']:
        for i in xrange(1, len(name) + 1):
            tree_node = tree.get(name[:i], [])
            tree_node.append(v)
            tree[name[:i]] = tree_node

test_hash_extended.py

#!/usr/bin/python
# -*- coding: utf-8 -*-

import json

cars = json.loads(open('../api/fixtures/fipe_carro.json').read())

class Tree(dict):

    def __init__(self, *args, **kwargs):
        self.current_values = []

    def __getitem__(self, key):
        node = super(Tree, self).__getitem__(key[0])
        if len(key[1:]) > 0:
            return node[key[1:]]
        return node.current_values

    def push(self, key, obj):
        node = self.get(key[0], Tree())
        node.current_values.append(obj)
        if len(key[1:]) > 0:
            node.push(key[1:], obj)
        self[key[0]] = node

    @classmethod
    def from_list(cls, objects, get_index):
        new_tree = cls()
        for obj in objects:
            key = get_index(obj)
            if hasattr(key, 'next'):
                for k in key:
                    new_tree.push(k, obj)
            else:
                new_tree.push(key, obj)
        return new_tree

tree = Tree.from_list(cars, lambda car: (name for name in car['translated_names']))


print tree['coupe-4']

test_hash_obj.py

#!/usr/bin/python
# -*- coding: utf-8 -*-
import json


class Tree(dict):
    def __setitem__(self, key, obj):
        """
        Pushes a new object in the tree.
        """
        for i in xrange(3, len(key) + 1):
            tree_node = self.get(key[:i], [])
            super(Tree, self).__setitem__(key[:i], tree_node)
            tree_node.append(obj)

    @classmethod
    def from_list(cls, objects, get_key):
        """
        Build tree form a list of objects.
        """
        tree = cls()
        for obj in objects:
            key_value = get_key(obj)
            if isinstance(key_value, list):
                for key in key_value:
                    tree[key] = obj
            else:
                tree[key_value] = obj
        return tree


cars = json.loads(open('../api/fixtures/fipe_carro.json').read())
tree = Tree.from_list(cars, lambda car: car['translated_names'])

print tree['attracti.']

test_nary.py

#!/usr/bin/python
# -*- coding: utf-8 -*-

from api.nary import Tree
import json

cars = json.loads(open('./fixtures/fipe_carro.json').read())
tree = Tree.from_list(cars, lambda vehicle: vehicle['translated_names'])

O problema da implementação que você fez é que continua gerando um objeto para cada nó da árvore. O que eu fiz foi gerar um único objeto que engloba a árvore. O resto é tudo nativo do python. Não entendi muito bem por que você sobrescreveu o getitem. A grande vantagem da implementação é usar o acesso à chaves de dicionários nativo do python.

Quanto ao barzinho, obrigado pelo convite.

Essa implementação é só uma outra possibilidade para tentar deixar mais eficiente a implementação com objetos. Eu sabia que lógicamente ia ficar menos eficiente, como você mesmo falou.

Estou pensando em formas diferentes de implementar essa mesma coisa. Até chegar a uma que balanceie entre uso de memória e velocidade.

Quanto ao bar eu acabei caindo lá (nem sabia que ia) pq, originalmente, eu sai pra comer algo. :)

Ah sim, eu tentei manter a forma de inserção da primeira implementação ( test_nary.py ). E usar a ideia de dicionários. Tô pensando em outro jeito aqui.

Analisando o problema tive outra ideia. As buscas na árvore nunca são menores que 3 caracteres. Com a ideia de implementar usando dict dá pra fazer uma otimização a mais e bem simples. Só colocar no dict chaves com três ou mais caracteres. Peguei a implementação de @vbmendes e mudei algumas coisas, mas a mudança mais interessante foi ter colocado essa otimização nas chaves.

Com isso a árvore em memória da implementação test_hash_obj.py gastou 22,2 mb de memória RAM.

Agora ficou mais natural usar a árvore:

from test_hash_obj import Tree
tree = Tree()
tree['casa'] = 'casa'
tree['casca'] = 'casca'
tree['casarao'] = 'casarao'
print tree

Eu tinha pensado nessa ideia de sobrescrever o setitem, só não tinha conseguido chegar a uma boa solução para a chave que seria setada, visto que um objeto pode ter mais de uma chave. Eu criei um projeto para centralizar esses testes. Vou comittar o que eu tenho aqui e te dar permissão de committer por que o gist não dá tanto poder assim.

Massa, cria ai!
Abs.

Criado. Já te coloquei como colaborador.