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'])

, no tinha pensado nos objetos ;) Verdade. O n(n-1)/2 o seguinte: 4 + 3 + 2 + 1 + 0 = 10 5 \* 4 / 2 = 10 5 + 4 + 3 + 2 + 1 + 0 = 15 6 *5 / 2 = 15 6 + 5 + 4 + 3 + 2 + 1 + 0 = 21 7 \* 6 / 2 = 21 Repara q se vc agrupar o menor com o maior d sempre o nmero: (Array com 7 nmeros): 6 + 5 + 4 + 3 + 2 + 1 + 0 = (6 + 0) + (5 + 1) + (4 + 2) + (3) ou seja: 6 \* 3 + 3 ou 6 \* 6/2 + 6/2 = 7 \* 6/2 = 7 \* (6/2) = n * (n-1) / 2 Sacow? :) Abs, Bernardo Heynemann 2012/3/10 Rafael Carcio < reply@reply.github.com

…

No entendi como voc chegou no n(n-1)/2 . Tentei ver aqui, mas no consegui entender como. Enfim, rodei aqui os dois algoritmos e verifiquei a memria gasta no meu Mac (Activity Monitor). Resultados: - A implementao usando o nary: 26,8 mb; - A implementao usando o hash nativo como tree: 22,7 mb; Ou seja a implementao com o hash gastou menos memria que a implementao com o nary. Eu acredito que essa diferena (4,1 mb) porque o nary usa objetos python como n's. Objetos Python gastam mais memria do que uma string. Valeuu.. fique empolgado com o problema. :P hehehe Vou dormir e amanh vou tentar pensar em formas de otimizar os algoritmos. Vou dormir tb, pois estou com dor de cabea de sono j. Estou acordado desde ontem s 4 da manh. :P Abs. --- Reply to this email directly or view it on GitHub: https://gist.github.com/2009266

Boa Carício. Eu tinha implementado isso com objetos python também mas essa sua solução pareceu mais natural. Eu forkei e fiz uma sugestão usando um objeto que abstrai a árvore em si que é uma subclasse de dicionário e usa a sua ideia. Dá uma olhada lá: https://gist.github.com/2014896

Pelos meus testes, a implementação demorou cerca de 1/6 do tempo que a implementação usando objetos para buscar e metade do tempo para gerar a árvore.

Ae Vinícius,

É, eu estava comentando sobre essas implementações com Flávio Ribeiro e ele me disse que pra desenvolver pra embarcados ele herdava muito de objetos builtins do python para economizar memória e ter melhor performance. Dai tive a ideia de herdar de dict também assim como você tb pensou. Só que eu pensei desse jeito ai que implementei no arquivo test_hash_extended.py que foi um pouco diferente da que você fez.

Não rodei nenhum teste de performance ainda, pois são 4 e meia da manhã e eu acabei de chegar morrendo de sono de um bar. hahaha Mas tive que implementar essa ideia ai pra mostrar a você depois que vi que você implementou algo na mesma linha só que diferente. hehehe Se acordar antes de mim... roda ai os uns testes de performance. :D

Sei que rodei aqui e percebi que com essa nova implementação test_hash_extended.py o uso de memória ficou entre a implementação só com 1 dict e a implementação com objetos. No meu monitor marcou 26,4 mb usados. Diminuiu só 0,4 mb.

Amanhã vou tentar ter outra ideia. ahahaah

Muito bom ver que você também se interessou pela coisa. :D

Abs.

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.