Estoy tratando de construir una estructura de datos en forma de árbol usandoNode representación:

use std::cmp::Ordering;
use std::fmt::Debug;
use std::sync::Arc;

const BRANCH_FACTOR: usize = 32;

#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord)]
enum Node<T> {
    Branch {
        children: [Option<Arc<Node<T>>>; BRANCH_FACTOR],
        len: usize,
    },
    RelaxedBranch {
        children: [Option<Arc<Node<T>>>; BRANCH_FACTOR],
        sizes: [Option<usize>; BRANCH_FACTOR],
        len: usize,
    },
    Leaf {
        elements: [Option<T>; BRANCH_FACTOR],
        len: usize,
    },
}

patio de recre

LosRelaxedBrancha variante @ de la enumeración se utilizará raramente, a veces en absoluto. Dado que el tamaño de las enumeraciones en Rust se define por el tamaño de la variante más grande,RelaxedBranch aumenta en general la huella de memoria deNode drásticamente. El gran tamaño de esta enumeración provoca un impacto de rendimiento del 20%, lo cual no es aceptable en mi caso.

Como alternativa a las enumeraciones, he decidido probar los objetos de rasgos:

use std::cmp::Ordering;
use std::fmt::Debug;
use std::sync::Arc;

const BRANCH_FACTOR: usize = 32;

trait Node<T>: Debug + Clone + PartialEq + Eq + PartialOrd + Ord {}

#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord)]
struct Branch<T> {
    children: [Option<Arc<Node<T>>>; BRANCH_FACTOR],
    len: usize,
}

#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord)]
struct RelaxedBranch<T> {
    children: [Option<Arc<Node<T>>>; BRANCH_FACTOR],
    len: usize,
}

#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord)]
struct Leaf<T> {
    elements: [Option<T>; BRANCH_FACTOR],
    len: usize,
}

impl<T> Node<T> for Branch<T> {}
impl<T> Node<T> for RelaxedBranch<T> {}
impl<T> Node<T> for Leaf<T> {}

patio de recre

He descubierto rápidamente algo llamado seguridad de objeto de rasgo :) Esto no permite que los rasgos utilizados para los objetos de rasgo devuelvan objetos deSelf type, que es mi caso debido a la herencia deClone.

¿Cómo puedo representar un nodo de árbol sin tener la sobrecarga de enumeraciones?