Como devo alterar minha estrutura de gráficos (inserção muito lenta)?

Question

Esse programa que estou fazendo é sobre uma rede social, o que significa que existem usuários e seus perfis. A estrutura dos perfis é UserProfile.

Agora, existem várias implementações de gráficos possíveis e acho que não estou usando o melhor. eu tenho um Graph estrutura e dentro, há um ponteiro para uma lista vinculada do tipo Vertex. Cada Vertex elemento tem um valor, um ponteiro para o próximo Vertex e um ponteiro para uma lista vinculada do tipo Edge. Cada Edge elemento tem um valor (para que eu possa definir pesos e o que for necessário), um ponteiro para o próximo Edge e um ponteiro para o Vertex proprietário.

Eu tenho 2 arquivos de amostra com dados para processar (no estilo CSV) e inserir no gráfico. O primeiro são os dados do usuário (um usuário por linha); O segundo é as relações do usuário (para o gráfico). O primeiro arquivo é inserido rapidamente no gráfico porque eu sempre insiro na cabeça e há ~ 18000 usuários. O segundo arquivo leva muito tempo, mas ainda insiro as bordas na cabeça. O arquivo possui cerca de ~ 520000 linhas de relações de usuário e leva entre 13-15 minutos para inserir no gráfico. Fiz um teste rápido e a leitura dos dados é rapidamente, instantaneamente realmente. O problema está na inserção.

Esse problema existe porque tenho um gráfico implementado com listas vinculadas para os vértices. Toda vez que preciso inserir uma relação, preciso procurar 2 vértices, para que eu possa vinculá -los. Este é o problema ... fazer isso por ~ 520000 relações, leva um tempo.

Como devo resolver isso?

Solução 1) Algumas pessoas me recomendaram para implementar o gráfico (a parte dos vértices) como uma matriz em vez de uma lista vinculada. Dessa forma, tenho acesso direto a todos os vértices e a inserção provavelmente cairá consideravelmente. Mas, não gosto da ideia de alocar uma matriz com [18000] elementos. Quão praticamente é isso? Meus dados de amostra têm ~ 18000, mas e se eu precisar de muito menos ou muito mais? A abordagem da lista vinculada tem essa flexibilidade, eu posso ter o tamanho que eu quiser, desde que haja memória. Mas a matriz não, como vou lidar com essa situação? Quais são suas sugestões?

O uso de listas vinculadas é bom para a complexidade do espaço, mas ruim para a complexidade do tempo. E o uso de uma matriz é bom para a complexidade do tempo, mas ruim para a complexidade do espaço.

Algum pensamento sobre esta solução?

Solução 2) Este projeto também exige que eu tenha algum tipo de estrutura de dados que permita uma pesquisa rápida com base em um índice de nome e um índice de identificação. Para isso, decidi usar tabelas de hash. Minhas tabelas são implementadas com encadeamento separado como resolução de colisão e quando um fator de carga de 0,70 é alcance, normalmente recrio a tabela. Eu baseio o próximo tamanho da tabela sobre isso http://planetmath.org/encyclopedia/goodhashtableprimes.html.

Atualmente, ambas as tabelas de hash seguram um ponteiro para o UserProfile em vez de duplicar o próprio perfil do usuário. Isso seria estúpido, a mudança de dados exigiria três alterações e é realmente burro para fazê -lo dessa maneira. Então eu apenas salvo o ponteiro para o UserProfile. O mesmo ponteiro do perfil de usuário também é salvo como valor em cada gráfico Vertex.

Então, eu tenho 3 estruturas de dados, um gráfico e duas tabelas de hash e cada uma delas apontando para o mesmo exato UserProfile. A estrutura do gráfico servirá ao objetivo de encontrar o caminho mais curto e coisas assim, enquanto as tabelas de hash servem como índice rápido por nome e ID.

O que estou pensando em resolver meu problema gráfico é, em vez de ter o valor das tabelas de hash apontar para o UserProfile, Eu aponto para o correspondente Vertex. Ainda é um ponteiro, não mais e não é usado menos espaço, eu apenas mudo o que aponto.

Assim, posso procurar facilmente e rapidamente cada vértice de que preciso e vinculá -los. Isso inserirá as relações ~ 520000 rapidamente.

Pensei nessa solução porque já tenho as tabelas de hash e preciso tê -las, então, por que não tirar proveito deles para indexar os vértices do gráfico em vez do perfil do usuário? É basicamente a mesma coisa, ainda posso acessar o UserProfile muito rapidamente, basta ir para o Vertex E então para o UserProfile.

Mas você vê algum contras nesta segunda solução contra a primeira? Ou apenas profissionais que dominam os prós e os contras da primeira solução?

Outra solução) Se você tem outra solução, sou todos ouvidos. Mas explique os prós e contras dessa solução em relação aos 2. Antes. Eu realmente não tenho muito tempo para desperdiçar com isso agora, preciso seguir em frente com este projeto, então, se estou fazendo isso para fazer isso Uma mudança, preciso entender exatamente o que mudar e se esse é realmente o caminho a percorrer.

Espero que ninguém adormeceu lendo isso e fechou o navegador, desculpe pelo grande testamento. Mas eu realmente preciso decidir o que fazer sobre isso e realmente preciso fazer uma mudança.

PS: Ao responder às minhas soluções propostas, enumere -as como eu, para que eu saiba exatamente do que você está falando e não se confunda mais do que já sou.

Answer 1

A primeira abordagem é a questão principal aqui, é a velocidade, eu preferiria a abordagem da matriz.

Obviamente, você deve manter a tabela de hash para a pesquisa de nome-índice.

Se eu entendi corretamente, você apenas processa os dados uma vez. Portanto, não há inserção dinâmica de dados.

Para lidar com o problema de alocação espacial, eu recomendaria:

1 - Leia depois do arquivo, para obter o número de vértices.

2 - aloce esse espaço

Se você é dinâmico, você poderá implementar algum método simples para incrementar o tamanho da matriz em etapas de 50%.

3 - Nas bordas, substitua sua lista vinculada para uma matriz. Essa matriz deve ser incrementada dinamicamente com etapas de 50%.

Mesmo com o espaço "extra" alocado, quando você aumenta o tamanho com as etapas de 50%, o tamanho total usado pela matriz deve ser marginalmente maior do que com o tamanho da lista vinculada.

Espero poder ajudar.