Mantendo uma lista de nós com requisitos desafiadores

5

Essa é uma pergunta sobre o design de uma coleção de nós ordenados que têm alguns requisitos que eu estou tentando satisfazer.

Na área de problemas com a qual estou lidando, temos rotas que são uma coleção ordenada de nós. Uma rota terá entre 1000 e 25000 nós. Um nó em si é um objeto complexo.

Eu preciso ser capaz de persistir os nós, idealmente para um banco de dados relacional (já que o aplicativo mais amplo é entregue atualmente usando uma arquitetura que usa um banco de dados relacional para persistência). Eu tenho dois requisitos separados que apresentam dificuldades em como modelar os dados.

  1. Eu preciso ser capaz de inserir nós (ou ponteiros para nós) no meio da lista e reorganizar a lista na hora.
  2. Eu preciso recuperar a lista em sua ordem sequencial correta com um índice eficiente e a capacidade de acesso aleatório.

A única maneira que eu acho que posso satisfazer o primeiro requisito é modelar os dados como uma lista encadeada, onde cada nó aponta para o próximo nó na lista, o que permitiria que a lista fosse editada e reorganizada em tempo real.

A única maneira que eu acho que posso satisfazer o segundo requisito seria ordenar a lista sequencialmente, de modo que cada nó tenha uma referência à sua posição na lista e ordene / acesse a lista pela posição.

Existe algum outro método que eu possa usar para satisfazer os dois requisitos ou estou preso a construir um híbrido que empregue ambos os métodos em vários momentos, dependendo do contexto operacional e que mantenha os dois tipos de referência em sincronia?

    
por AlexC 06.10.2011 / 10:55
fonte

3 respostas

2

Um híbrido na forma de matrizes vinculadas parece um compromisso entre as duas estruturas. Você ainda acessa rapidamente o índice, sobrecarga relativamente baixa com inserções aleatórias e muito baixo ao inserir em lotes.

A Wikipédia nomeou esta uma lista de links unrolled

    
por 06.10.2011 / 12:41
fonte
1

Você pode satisfazer ambos os requisitos modelando rotas como matrizes. Em um RDBMS, você pode configurar uma tabela como esta:

-- Table "route_steps"
id         NUMERIC   -- ID for this row
route      NUMERIC   -- FK:  Which route?
position   NUMERIC   -- Relative position of this step in the route
node       NUMERIC   -- FK:  Which node?

A inserção de uma etapa na rota seria feita por INSERT ing uma nova linha e com um gatilho BEFORE incrementando a position em todas as linhas com position maior ou igual ao da nova linha . A exclusão seria o oposto: DELETE da linha que contém a etapa desejada e que um gatilho AFTER decrementasse a position de qualquer etapa na mesma rota com um% maiorposition do que a que acabou de ser excluída. Como tudo isso acontece em uma transação, toda a operação se torna atômica.

O acesso aleatório fica puxando uma linha de route_steps por position :

SELECT node FROM route_steps
  WHERE route = id_of_route_of_interest
  AND position = position_of_interest

A rota inteira pode ser recuperada em sequência com:

SELECT position, node FROM route_steps
  WHERE route = id_of_route_of_interest
  ORDER BY position ASC

A indexação adequada tornará essas duas operações muito rápidas e também ajudará o UPDATE s feito pelos acionadores INSERT e DELETE a encontrar as linhas que precisam ser atualizadas.

Existem alguns problemas de integridade com os quais você precisará lidar, mas quando você tiver mais do que isso, provavelmente descobrirá o que eles são.

Pessoalmente, não vejo qualquer vantagem em um modelo híbrido. Você ainda terá que manter algo parecido com uma matriz para acelerar o acesso aleatório usando os métodos descritos acima. Com isso já em vigor, não parece haver muito sentido em realizar o trabalho adicional de manter a lista vinculada apenas porque é eficiente.

    
por 06.10.2011 / 14:34
fonte
0

Eu gostaria de dar uma olhada em Boost.graph para lidar com isso. Pode parecer um exagero à primeira vista, mas a longo prazo você verá mais e mais benefícios.

    
por 06.10.2011 / 11:54
fonte