Alla ricerca di un modo molto efficiente di memoria per trovare l'esportazione di tutte le relazioni in un albero genealogico

La soluzione semplice

void Export(Node currentNode)
{
  WriteContentToXmlFile(currentNode); // delete this if you have only content for leafs
  int numberOfKids = currentNode.GetNumberOfChildren();
  if(numberOfKids==0)
  {
      // add "WriteContentToXmlFile(currentNode)" here if you have only content for leafs
      return;
  }
  WriteStartingTagForASubTreeIntoXmlFile(); // for example, <subtree>
  for(int i = 1  to numberOfKids)
  {
     Node child = currentNode.GetChild(i);  // gets it from your database
     Export(child);
     // leaving the scope frees "child" from memory
  }
  WriteEndingTagForASubTreeIntoXmlFile(); //  for example, </subtree>
}

non trascina più nodi nella memoria principale come la profondità dell'albero (la lunghezza del percorso più lungo dalla radice a una foglia). Quindi, quando scrivi il tuo file xml in modo sequenziale su disco (e non tienilo nella memoria principale), non ti imbatterai in problemi, immagino.

Devi adattarlo sicuramente al tipo di struttura XML che hai in mente, ma spero che tu veda che la memoria non dovrebbe essere un grosso problema.

Ecco perché vorrei che tecnologie come RDF / XML fossero popolari sulla piattaforma .net ..

Vedo due opzioni:

1. Se devi scrivere prima la profondità dell'albero usando XML:

   Hai identificato il problema correttamente. Lo stack ha il potenziale per diventare molto grande e ogni frame dello stack ancora più grande in un albero profondamente ricorsivo. La soluzione semplice e più lenta è quella di emettere una chiamata al database per ogni nodo dell'albero. Quindi, piuttosto che ottenere tutti i bambini, è sufficiente ottenere il nodo in questione. In un modello con database backed del tuo albero, quando ottieni il Child ren di Father , non devi memorizzare l'intero livello di bambini nella memoria in una volta. Piuttosto, puoi recuperare e liberare ognuno come "lo visiti". Ha senso? Ovviamente questo aumenterà il numero di chiamate al database che ti servono, ma è abbastanza efficiente in termini di memoria.

   EDIT: Questo è ciò che Doc Brown descrive nella sua risposta ..

   Vorrei iniziare senza preoccuparmi della memoria e semplicemente svilupparla come hai descritto: un metodo di esportazione ricorsivo in cui si ottiene un livello alla volta e si scrive prima l'albero in XML. Quindi rielaborare se hai effettivamente problemi di memoria. Nonostante la dimensione dei tuoi dati, onestamente non penso che avrai un problema nell'esportazione dell'intero albero. Se si verificano problemi di memoria insufficiente, lavorare a una soluzione. Nel peggiore dei casi, tuttavia, sarà SPACE (N).

2. Utilizza RDF correttamente (il mio consiglio):

   Usando RDF / XML, scrivere i dati in uno spazio costante, SPACE (K), è banale e fondamentalmente risolve tutti i tuoi problemi. Ma, RDF / XML è una tecnologia molto sottoutilizzata perché ha una curva di apprendimento elevata. Se sei disposto a passare a Java, ci sono numerosi strumenti per creare modelli RDF supportati da database, come Apache's Jena , che renderà questo lavoro incredibilmente facile. Se sei bloccato su C #, ma vuoi dare un colpo a RDF, dai un'occhiata alla Libreria SemWeb C # .

   L'idea è di scrivere la struttura dei dati insieme ai dati effettivi stessi in RDF / XML in un formato a tre tripli condensati. Poiché la struttura viene anche esportata, i dati possono essere serializzati k nodi alla volta, quindi in uno spazio costante. Questa è la soluzione ottimale soprattutto se si dispone di un grafico che potrebbe non adattarsi mai a una quantità di memoria percorribile (se il set di dati è veramente grande come si afferma (;).

Non puoi semplicemente usare un buon vecchio albero k-ary? Carica l'intero albero in memoria all'avvio. Quindi implementare una sorta di meccanismo evento per aggiornarlo se il DB cambia dopo l'avvio. Dovresti riuscire a trovarlo in qualsiasi libro di Data Structures and Algorithms standard. Vorrei utilizzare un elenco collegato per il meccanismo di archiviazione sottostante, dal momento che non si sa quanti bambini avrà ciascun nodo. La ricorsione non dovrebbe essere un problema per un'implementazione di una lista collegata, dato che in pratica si avranno solo riferimenti al primo elemento di ogni lista. Se sei così preoccupato, puoi assicurarti di ricorrere alla ricorsione in coda o, ancora meglio, implementare il tuo stack per chiamare le funzioni ricorsive. Tuttavia, senza ricorsione, l'attraversamento dell'albero sarà troppo complicato per essere un codice buono e mantenibile.

Non sono sicuro di come la roba System.Text.Xml di .NET memorizzi i nodi. Tuttavia, se è basato su array, non sarà altrettanto efficiente (o divertente?) Come se stessi implementando un albero da solo.

Vorrei fare qualcosa di simile (mi dispiace per la sintassi in C ++, non ricordo i generici per C # in cima alla mia testa).

template <typename E> 
class TreeNode
{
public:
  E value();
  bool isLeaf();
  TreeNode* parent();
  TreeNode* lefmostChild();
  TreeNode* rightSibling();
  void insertFirst(TreeNode<E>*);
  void insertNext(TreeNode<E>*);
  void setValue(E&);
  ...

};

class FamilyMember
{
   //store all of your data for the family member in here.
};

Quindi caricare una Tree of FamilyMembers all'avvio dell'applicazione. Quindi attraversare sarà un gioco da ragazzi (se sei bravo con la ricorsione), e non sarà così male in pila. In realtà puoi calcolarlo. Ad ogni modo, il numero importante è big-oh (n log * n) per l'attraversamento. La memoria è quasi sempre irrilevante in questo tipo di cose. Se la memoria diventa un problema, considera invece l'utilizzo di un'implementazione ad albero sequenziale. Comunque, n log * n è più che accettabile, e ci sono un sacco di attraversamenti degli alberi che lo faranno in modo efficiente. Inoltre, puoi migliorarlo ancora di più se usi la regola dei pesi ponderata (anche se penso che starai bene). Una volta che lo hai in questa struttura, la conversione xml sarà banale.