Club Delphi  
    FTP   CCD     Buscar   Trucos   Trabajo   Foros

Retroceder   Foros Club Delphi > Principal > OOP
Registrarse FAQ Miembros Calendario Guía de estilo Temas de Hoy

Coloboración Paypal con ClubDelphi

Respuesta
 
Herramientas Buscar en Tema Desplegado
  #1  
Antiguo 02-03-2022
Avatar de mamcx
mamcx mamcx is offline
Moderador
 
Registrado: sep 2004
Ubicación: Medellín - Colombia
Posts: 3.927
Poder: 26
mamcx Tiene un aura espectacularmamcx Tiene un aura espectacularmamcx Tiene un aura espectacular
Una manera de hacer una estructura de árbol simple y veloz!

Hace poco implemente en Rust una forma de hacer un "Tree" inspirado por APL.

Esta "limitada" a un árbol creado en pre-order, pero utiliza esto como ventaja para simplificar ENORMEMENTE la implementación y hacer su desempeño muy rápido.

Hice un articulo al respecto en https://www.elmalabarista.com/blog/2022-flat-tree/, pero quiero compartir el núcleo de la idea aquí, ya que se puede implementar en Delphi/pascal sin problemas.

El truco es que no se usa pointers ni listas enlazadas, solo 3 vectors:

Código PHP:
pub struct Tree<T> {
    
dataVec<T>,
    
levelVec<usize>,
    
parentVec<usize>,

Así un árbol como:

Código:
. Users
├── jhon_doe
├   ├── file1.rs
├   ├── file2.rs
├── jane_doe
└────── cat.jpg
se representa:

Código:
| DATA:   | Users | jhon_doe | file1.rs | file2.rs | jane_doe | cat.jpg |
|---------|-------|----------|----------|----------|----------|---------|
| NIVEL:  | 0     | 1        | 2        | 2        | 1        | 2       |
| PADRE:  | 0     | 0        | 1        | 1        | 0        | 4       |
Al usar vectores planos el desempeño es excelente. "Caminar" el árbol es muy eficiente: Por defecto, solo hay que recorrer el vector de "data" tal cual, sin brincar entre pointers.

"Caminar" los hijos, padres & hermanos es muy sencillo, al hacer esta observación de como están los datos:

Código:
. Users				
		 ⇡ padres siempre arriba del node

├── jhon_doe	= Index: 1, Nivel: 1

		 ⇩ hijos arrancan desde 
			jhon_doe + 1,
			nivel debe ser  > al de jhon_doe

├   ├── file1.rs ?: Nivel 2 es hijo!
├   ├── file2.rs ?: Nivel 2es hijo!
├── jane_doe	 ?: Nivel 1 es inferior, detente!

└────── cat.jpg
Hice varios benchmarks contra una de las mejores librerías de Rust (que ya de por si también ignora listas enlazadas y usa un vector para los datos, pero no para los nodos!) y hay mejores tremendas:


Código:
# 47.370 nodos, 10 niveles de profundidad, recorriendo hijos en la mitad del árbol:

#Competencia
Iter Tree children/Ego/4 #5
                        time:   [174.10 us 176.36 us 178.90 us]
                        thrpt:  [558.98 Kelem/s 567.01 Kelem/s 574.37 Kelem/s]

#Usando la idea
Iter Tree children/Flat/4 #5 
                        time:   [32.950 us 33.451 us 33.962 us]
                        thrpt:  [2.9445 Melem/s 2.9894 Melem/s 3.0349 Melem/s]

MacBook Air (M1, 2020) : 16GB
Ya que en otros lenguajes es aun menos común, imagino que sera mucho mayor la mejora!
__________________
El malabarista.

Última edición por mamcx fecha: 02-03-2022 a las 19:22:30.
Responder Con Cita
  #2  
Antiguo 03-03-2022
Avatar de ElKurgan
[ElKurgan] ElKurgan is offline
Miembro Premium
 
Registrado: nov 2005
Posts: 1.237
Poder: 20
ElKurgan Va camino a la fama
Thumbs up

Muchas gracias por el aporte. Un gran trabajo

Saludos
Responder Con Cita
  #3  
Antiguo 03-03-2022
Avatar de Neftali [Germán.Estévez]
Neftali [Germán.Estévez] Neftali [Germán.Estévez] is offline
[becario]
 
Registrado: jul 2004
Ubicación: Barcelona - España
Posts: 18.549
Poder: 10
Neftali [Germán.Estévez] Es un diamante en brutoNeftali [Germán.Estévez] Es un diamante en brutoNeftali [Germán.Estévez] Es un diamante en bruto
Interesante.
Gracias por compartirlo.
__________________
Germán Estévez => Web/Blog
Guía de estilo, Guía alternativa
Utiliza TAG's en tus mensajes.
Contactar con el Clubdelphi

P.D: Más tiempo dedicado a la pregunta=Mejores respuestas.
Responder Con Cita
  #4  
Antiguo 04-03-2022
Avatar de ecfisa
ecfisa ecfisa is offline
Moderador
 
Registrado: dic 2005
Ubicación: Tres Arroyos, Argentina
Posts: 10.508
Poder: 36
ecfisa is a splendid one to beholdecfisa is a splendid one to beholdecfisa is a splendid one to beholdecfisa is a splendid one to beholdecfisa is a splendid one to beholdecfisa is a splendid one to beholdecfisa is a splendid one to behold
Muchas gracias

Saludos
__________________
Daniel Didriksen

Guía de estilo - Uso de las etiquetas - La otra guía de estilo ....
Responder Con Cita
Respuesta



Normas de Publicación
no Puedes crear nuevos temas
no Puedes responder a temas
no Puedes adjuntar archivos
no Puedes editar tus mensajes

El código vB está habilitado
Las caritas están habilitado
Código [IMG] está habilitado
Código HTML está deshabilitado
Saltar a Foro

Temas Similares
Tema Autor Foro Respuestas Último mensaje
Arbol de estructura de base de datos elrayo76 Varios 1 02-09-2014 20:53:26
Tabla cíclica ó estructura de arbol... Xianto MS SQL Server 3 11-09-2008 12:37:18
Consulta SQL para estructura en arbol PatrickM SQL 10 16-04-2007 22:48:36
La mejor manera de hacer reportes con Qreport Coco_jac Impresión 6 29-04-2006 12:49:09
Ejercicio:hacer El Árbol GenealÓgico De Esta Familia FunBit Humor 0 01-12-2005 18:49:51


La franja horaria es GMT +2. Ahora son las 00:46:18.


Powered by vBulletin® Version 3.6.8
Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
Traducción al castellano por el equipo de moderadores del Club Delphi
Copyright 1996-2007 Club Delphi