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!