Foros Club Delphi - 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> {
    data: Vec<T>,
    level: Vec<usize>,
    parent: Vec<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!