Una manera de hacer una estructura de árbol simple y veloz!

[mamcx]

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:

. Users
├── jhon_doe
├   ├── file1.rs
├   ├── file2.rs
├── jane_doe
└────── cat.jpg

se representa:

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

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

# 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!

[[ElKurgan]]

Muchas gracias por el aporte. Un gran trabajo

Saludos

[Neftali [Germán.Estévez]]

Interesante.
Gracias por compartirlo.

[ecfisa]

Muchas gracias

Saludos