Arboles b en python
Diego Andrés Sanabria Martin
Estoy intentando implementar arboles b en python, me gusta mucho ese
lenguaje pero ya varias veces he tenido un problema: tengo una clase,
y cuando la instancio por segunda vez pasa una de estas dos cosas: o
el segundo objeto es una copia exacta del primero (misma dirección de
memoria, si modifico los atributos de un objeto obviamente los del
otro cambian) o tienen los mismos datos (en este caso las direcciones
de memoria son distintas, pero los atributos tienen los mismos
valores, si los modifico en uno no se modifican en el otro), esto
puede tener dos razones: una: es un posible bug del interprete o dos:
hay un inconveniente entre la silla y la maquina :P. Deseo saber cual
de las dos es, y si es la primera, como se reporta un bug? es decir,
como logro que sepan que es lo que esta psando?
Gracias, se que no es muy claro pero no lo puedo explicar mejor.
--
http://www.el-directorio.org
El sitio de linux y el Software Libre en Colombia
Debian Colombia
http://www.debiancolombia.org
"I know that it will hurt, I know that it will break your heart, the
way things are, and the way they've been.
Don't spread the discontent, don't spread the lies, don't make the
same mistakes with your own life."
Natalie Merchant
"Los sueños de la razón producen monstruos."
Goethe
"Si no sabes ser fuerte pero tampoco sabes ser débil,
entonces serás derrotado"
Szun Tzu
Andres Pinzon
> el segundo objeto es una copia exacta del primero (misma dirección de
> memoria, si modifico los atributos de un objeto obviamente los del
> otro cambian) o tienen los mismos datos (en este caso las direcciones
> de memoria son distintas, pero los atributos tienen los mismos
> valores, si los modifico en uno no se modifican en el otro), esto
> puede tener dos razones: una: es un posible bug del interprete o dos:
> hay un inconveniente entre la silla y la maquina :P.
Podrias poner algo de código de ejemplo para ver que/como lo estas haciendo?
saludos,
--
---------
Andrés Pinzón [http://www.andrespinzon.com]
Bioinformatics Center, Colombia EMBnet node
Biotechnology Institute - National University of Colombia
http://bioinf.ibun.unal.edu.co
Tel +57 3165000 ext 16961 Fax +571 3165415
----------
Diego Andrés Sanabria Martin
pagina=[]
hijos=[]
pad=None
"""def __repr__(self):
return str(self.pagina)"""
def insertar(self,dato,min,max,padre=None):
tmp=[]
# Guarda el supuesto puntero al padre
self.pad=padre
if len(self.pagina)==max:
self.pagina.append(dato)
self.pagina.sort()
for i in range(0,max/2):
tmp.append(self.pagina.pop())
dato=self.pagina.pop()
if self.pad==None:
self.pad=Arbol()
/************************************************************************/
en este punto self.pad y self tiene los mismos datos pero distinta
posicion en memoria
/************************************************************************/
self.pad.pagina=[]
self.pad.hijos=[]
/************************************************************************/
Vacio la pagina y los hijos de self.pad pero no afecta los de self.
/************************************************************************/
self.pad.insertar(dato,min,max)
self.pad.hijos.append(self)
arboltmp=Arbol()
arboltmp.pagina=[]
arboltmp.hijos=[]
for a in len(tmp):
print tmp
arboltmp.insertar(tmp.pop(),min,max)
self.pad.hijos.append(arboltmp)
return self.pad
else:
pass
print "Ud quiere insertar el dato "+str(dato)+" pero ya
esta llena la pagina"
#elif len(self.pagina)<min and len(self.pagina)!=0:
# print "Esta pagina tiene una cantidad de datos menor de
lo permitido"
else:
# Guarda el dato
self.pagina.append(dato)
# Ordena la lista
self.pagina.sort()
return self
class ArbolB:
dmax=None
dmin=None
raiz=Arbol()
def __init__(self, d):
self.dmax=2*d
self.dmin=d
def insertar(self,dato):
self.raiz=self.raiz.insertar(dato,self.dmin,self.dmax)
def __repr__(self):
return str(self.raiz.pagina)
Guarda el codigo sin los comentarios en un archivo y desde el
interprete importalo,
ahora haces lo siguiente:
a=ArbolB(2)
b=ArbolB(3)
a.insertar(8)
a
b
Cada linea es una instruccion.
Óscar López
Me gustaría ver la implementación de tu algoritmo en pseudo-código.
¿Lo sacaste de algún libro o sitio en particular? . Esto nos podría
ayudar a encontrar dónde está el problema.
Aclarando que muy poco sé de Python, los síntomas que describes
suenan a que no estás instanciando correctamente los objetos, más
parece que los estuvieras clonando/copiando o creando nuevas
referencias a objetos ya existentes en memoria. Me inclino a creer que
no es un bug del intérprete :-P.
Saludos,
-Óscar.
Óscar López
Ya encontre la causa del problema. En una clase, los campos que
declaras por fuera del constructor, son tomados como miembros de clase
(estaticos). En el caso del B-Tree, todas las operaciones sobre el
arbol se hacian sobre *el mismo* campo `raiz' , por eso los cambios en
una instancia de la clase ArbolB afectaban a todas las demas
instancias. La version corregida del codigo quedaria asi:
---
#! /usr/bin/python
class Arbol :
def __init__(self) :
self.pagina = []
self.hijos = []
self.pad = None
def insertar(self, dato, min, max, padre = None) :
tmp = []
self.pad = padre
if len(self.pagina) == max :
self.pagina.append(dato)
self.pagina.sort()
for i in range(0, max/2) :
tmp.append(self.pagina.pop())
dato = self.pagina.pop()
if self.pad == None :
self.pad = Arbol()
self.pad.pagina = []
self.pad.hijos = []
self.pad.insertar(dato, min, max)
self.pad.hijos.append(self)
arboltmp = Arbol()
arboltmp.pagina = []
arboltmp.hijos = []
for a in len(tmp) :
arboltmp.insertar(tmp.pop(), min, max)
self.pad.hijos.append(arboltmp)
return self.pad
print "Ud quiere insertar el dato " + str(dato) + " pero la
pagina ya esta llena"
else :
self.pagina.append(dato)
self.pagina.sort()
return self
class ArbolB :
def __init__(self, d) :
self.dmax = 2*d
self.dmin = d
self.raiz = Arbol()
def insertar(self, dato) :
self.raiz = self.raiz.insertar(dato, self.dmin, self.dmax)
def __repr__(self) :
return str(self.raiz.pagina)
---
Nos cuentas cuando termines la implementacion de este B-Tree,
-Oscar.
Óscar López
constructor se encarga de inicializar los arreglos) :
self.pad.pagina = []
self.pad.hijos = []
arboltmp.pagina = []
arboltmp.hijos = []
Como dije en el primer correo, sería bueno mirar los algoritmos que
vas a utilizar, yo veo que hay lugar para algunas mejoras. Por ejemplo,
los parámetros min y max del árbol siempre son los mismos, podrías
hacerlos miembros de instancia de la clase Arbol y pasarlos en el
constructor; no estás pasando el parámetro `padre' en ningún
momento. También creo que la parte de la inserción cuando se ha
llenado una página se podría hacer de manera más sencilla.
Finalmente, considera usar una estructura de datos ordenada, así no
tienes que llamar sort() luego de cada inserción.
-Óscar.
Diego Andrés Sanabria Martin
Lo de las lineas que sobran es por el error que estaba cometiendo de
las variables estaticas, lo de los parametros, la verdad despues con
un poco más de tiempo lo arreglo, pero lo del parametro 'padre', ya la
estoy pasando, en una versión más desarrollada del código, y en cuanto
al pseudocódigo, una profesora me enseño como funcionan los arboles b,
y yo estoy intentando implementarlo en python, sin ningún
pseudocodigo, se que no es muy bueno pero mis problemas son de tiempo.
Gracias!!!