Procurando por uma maneira eficiente de encontrar todas as relações em uma árvore genealógica

5

Pense na pergunta como uma árvore genealógica, na seção PS explicarei exatamente o que é, mas a árvore genealógica é mais fácil de imaginar: pai, filhos, crianças podem ter mais filhos , essas crianças podem ter mais filhos, etc.

1- Não tenho toda a informação na memória para percorrê-los. Com cada método chamado e atingindo o banco de dados, eu tenho apenas o pai em algum nível e seus filhos. Veja aqui é o alto nível do método que eu tenho e precisa de como usar algumas partes boas dele:

private void Foo(string fatherNode)
{
  // call some DB scripts and grab data you need to work with.
  int numberOfKids = // get it from the thing you populated from the DB call.
  for(int i = 1  to numberOfKids)
  {
     Node Child = // grab child[i] from the list we populated from DB calls
     //Add it to the treeView
  }
}

Bem, isso estava funcionando porque é um aplicativo GUI e com cada um você conhece o evento "click", estávamos realmente solicitando apenas um nível de informação, mas agora eu preciso de uma nova funcionalidade onde eu possa clicar em um botão Export e escreva TODO estrutura de toda esta árvore genealógica para um arquivo XML ... (assim você pode expandir esses nós e ainda ver a hierarquia da família)

2- Existem muitos dados. Um Pai pode ter 400 filhos, cada filho pode ter mais 10 filhos e cada um desses filhos pode ter mais 500 filhos ... então eu também preciso me preocupar em obter exceções de memória ...

3- Recursão? podemos carregar TODA essa hierarquia para a memória? Eu não penso assim .. lembre-se o objetivo é exportá-lo para um XML SO Talvez a maneira eficiente é escrever um bom algoritmo que em cada chamada escreve um nível de hierarquia para o arquivo e não carrega a coisa toda na memória. ..

Mas eu estou puxando meu cabelo e batendo minha cabeça na mesa e não consigo decifrar o código e descobrir isso. Então, quais são as suas sugestões de código pseduo? Eu estou usando o C # pelo caminho.

PS: Esta é realmente uma hierarquia de bioinformática clínica, então você diz Ok genomas humanos..ok agora há 27000 genes sob ele, Ok agora recebe gene234 e digamos o que são seus filhos, .. .

    
por Blake 09.08.2012 / 23:18
fonte

3 respostas

2

A solução direta

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

nunca puxa mais nós para a memória principal como a profundidade da árvore (o comprimento do caminho mais longo da raiz para a folha). Então, quando você escreve seu arquivo xml sequencialmente em disco (e não o mantém na memória principal), você não terá problemas, eu acho.

Você tem que adaptar isso com certeza ao tipo de estrutura XML que você tem em mente, mas espero que você veja que a memória não deve ser um grande problema.

    
por 09.08.2012 / 23:31
fonte
2

É por isso que eu desejo que tecnologias como RDF / XML sejam populares na plataforma .net.

Eu vejo duas opções:

  1. Se você precisar escrever a profundidade da árvore primeiro usando XML:

    Você identificou seu problema corretamente. A pilha tem o potencial de ficar muito grande e cada quadro de pilha ainda maior em uma árvore profundamente recursiva. A solução simples e mais lenta é emitir uma chamada de banco de dados para todos os nós da árvore. Então, ao invés de pegar todos os filhos, simplesmente pegue o nó em questão. Em um modelo suportado pelo banco de dados de sua árvore, quando você obtém o Child ren de um Father , não é necessário armazenar todo o nível de filhos na memória de uma só vez. Em vez disso, você pode recuperar e liberar cada uma delas ao "visitá-las". Isso faz sentido? Obviamente, isso aumentará o número de chamadas de banco de dados necessárias, mas é bastante eficiente em termos de memória.

    EDIT: Isto ^ é o que Doc Brown descreve em sua resposta ..

    Eu começaria por não me preocupar com a memória e simplesmente desenvolvê-la como você descreveu: um método de exportação recursivo onde você obtém um nível por vez e grava a árvore na profundidade XML primeiro. Em seguida, refaça isso se você realmente tiver problemas de memória. Apesar do tamanho dos seus dados, eu sinceramente não acho que você tenha problemas para exportar a árvore inteira. Se você tiver problemas de falta de memória, trabalhe em uma solução. Seu pior caso, no entanto, será o SPACE (N).

  2. Use o RDF corretamente (minha recomendação):

    Usando o RDF / XML, gravar os dados em espaço constante, SPACE (K), é trivial e basicamente resolve todos os seus problemas. Mas, RDF / XML é uma tecnologia altamente subutilizada, porque tem uma alta curva de aprendizado. Se você está disposto a mudar para o Java, existem inúmeras ferramentas para fazer modelos de RDF suportados por banco de dados, como o Apache's Jena , que fará esse trabalho é incrivelmente fácil. Se você está preso no C #, mas quer dar uma chance ao RDF, dê uma olhada na C # SemWeb Library .

    A idéia é que você escreva a estrutura dos dados juntamente com os dados reais em si para RDF / XML em um formato condensado n-triplos. Como a estrutura também é exportada, os dados podem ser serializados em todos os nós de uma vez, portanto, em espaço constante. Esta é a solução ideal, especialmente se você tiver um gráfico que pode nunca se encaixar em uma quantidade viável de memória (se o conjunto de dados for realmente tão grande quanto você afirma (;).

por 10.08.2012 / 00:28
fonte
1

Você não pode simplesmente usar uma boa e velha árvore k-ary? Carregue a árvore inteira na memória na inicialização. Em seguida, implemente algum tipo de mecanismo de evento para atualizá-lo se o DB for alterado após a inicialização. Você deve ser capaz de encontrá-lo em qualquer livro padrão de estruturas de dados e algoritmos. Eu usaria uma lista vinculada para o mecanismo de armazenamento subjacente, desde que você não saiba quantos filhos cada nó terá. A recursão não deve ser um problema para uma implementação de lista encadeada, uma vez que você basicamente terá apenas referências ao primeiro item de cada lista. Se você está preocupado com isso, você pode se certificar de usar a recursão de cauda, ou melhor ainda, implementar sua própria pilha para chamar as funções recursivas. No entanto, sem recursão, a travessia da árvore será muito complicada para ser um código bom e sustentável.

Não tenho certeza de como o arquivo System.Text.Xml do .NET armazena os nós. No entanto, se for baseado em array, isso não será tão eficiente (ou divertido?) Como apenas implementar uma árvore você mesmo.

Eu faria algo como (desculpe pela sintaxe do C ++, não me lembro de genéricos para C # fora do topo da minha cabeça).

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.
};

Em seguida, carregue uma Árvore de Membros da Família quando o aplicativo for iniciado. Então a travessia será uma brisa (se você for bom com recursão), e não será tão ruim na pilha. Você pode realmente calcular isso. De qualquer forma, o número importante é big-oh (n log * n) para o percurso. A memória é quase sempre irrelevante nesse tipo de coisa. Se a memória se tornar um problema, considere o uso de uma implementação de árvore sequencial. De qualquer forma, n log * n é mais do que aceitável, e há muitos percursos de árvore que o farão com eficiência. Além disso, você pode melhorar ainda mais se usar a regra de união ponderada (embora eu ache que você ficará bem). Uma vez que você tenha essa estrutura, a conversão xml será trivial.

    
por 10.08.2012 / 03:47
fonte

Tags