Skip to content

Instantly share code, notes, and snippets.

@rafaelcaricio
Created March 9, 2012 23:24
Show Gist options
  • Save rafaelcaricio/2009266 to your computer and use it in GitHub Desktop.
Save rafaelcaricio/2009266 to your computer and use it in GitHub Desktop.
test_hash.py
*.swp
*.pyc
*.pyo
#!/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
#!/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']
#!/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.']
#!/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'])
@heynemann
Copy link

Kd a busca?

@rafaelcaricio
Copy link
Author

tree['fiat']

tree['1.8']

@heynemann
Copy link

Eh tree[termo] neh

@rafaelcaricio
Copy link
Author

rafaelcaricio commented Mar 9, 2012 via email

@heynemann
Copy link

O problema desse algoritmo é que ele ocupa muito mais memória que o outro.

Input: 10 palavras de 30 caracteres cada.

Árvore: Assumindo que não se repitam caracteres, são 300 nós da árvore de 1 caracter cada. Além de 300 ponteiros.

Total: 300 char + 300 ponteiros

Dicionario:
Para cada palavra de 30 caracteres vc estará guardando n(n-1)/2 combinações, ou seja 435 caracteres.

Para um total de 10 palavras isso corresponde a 4350 caracteres armazenados.

Além disso temos as referências de ponteiros, que são 300 ainda (30 combinações para cada palavra, com 10 palavras).

Total : 4350 chars + 300 ponteiros.

Se você contar que bola e boca ambas começam com "bo", o algoritmo de árvore fica mais eficiente ainda em ocupação de memória.

Quanto maiores as palavras maior fica a ocupação:

1.000 Palavras de 50 char (1.000 ponteiros):
Árvore: 1.000 * 50 <= 50.000 chars armazenados.
Dict: 1.000 * [(50 * 49) / 2] <= 1.225.000 chars armazenados

Mas eu curti pra kct Carício vc ter feito em casa esse teste ;) Parabéns. Meu irmão achou foda também.

O algoritmo do dict é REALMENTE mais simples. Mas ele gasta muita memória. Para vários dicts em memória acho que fica inviável.

Se a matemática acima tiver errada, desculpe. São 23:53, rs rs rs. Pode me corrigir :)

Abs,

@rafaelcaricio
Copy link
Author

Não entendi como você chegou no n(n-1)/2 . Tentei ver aqui, mas não consegui entender como.

Enfim, rodei aqui os dois algoritmos e verifiquei a memória gasta no meu Mac (Activity Monitor). Resultados:

  • A implementação usando o nary: 26,8 mb;
  • A implementação usando o hash nativo como tree: 22,7 mb;

Ou seja a implementação com o hash gastou menos memória que a implementação com o nary. Eu acredito que essa diferença (4,1 mb) é porque o nary usa objetos python como nó's. Objetos Python gastam mais memória 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 cabeça de sono já. Estou acordado desde ontem às 4 da manhã. :P

Abs.

@heynemann
Copy link

heynemann commented Mar 10, 2012 via email

@vbmendes
Copy link

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.

@rafaelcaricio
Copy link
Author

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.

@vbmendes
Copy link

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.

@vbmendes
Copy link

Quanto ao barzinho, obrigado pelo convite.

@rafaelcaricio
Copy link
Author

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. :)

@rafaelcaricio
Copy link
Author

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.

@rafaelcaricio
Copy link
Author

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.

@rafaelcaricio
Copy link
Author

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

@vbmendes
Copy link

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.

@rafaelcaricio
Copy link
Author

Massa, cria ai!
Abs.

@vbmendes
Copy link

Criado. Já te coloquei como colaborador.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment