Come dovrei cambiare la mia struttura del grafico (molto lento inserimento)?

Question

Il programma che sto facendo è di circa un social network, il che significa che ci sono gli utenti ei loro profili. La struttura dei profili è UserProfile.

Ora, ci sono varie implementazioni possibili Graph e non credo che sto utilizzando la migliore. Ho una struttura Graph e dentro, c'è un puntatore ad una lista concatenata di tipo Vertex. Ogni elemento Vertex ha un valore, un puntatore alla prossima Vertex e un puntatore a un elenco collegato di tipo Edge. Ogni elemento Edge ha un valore (in modo da poter definire i pesi e tutto ciò che è più necessario), un puntatore al prossimo Edge e un puntatore al proprietario Vertex.

Ho un 2 file di esempio con i dati da elaborare (in stile CSV) e inserire nella Graph. Il primo è l'dati utente (un utente per riga); il secondo è il rapporto utente (per il grafico). Il primo file è rapidamente inserito nel grafico causa ho sempre inserire alla testa e c'è come ~ 18000 utenti. Il secondo file prende le età, ma ho ancora inserire i bordi alla testa. Il file ha circa ~ 520000 linee delle relazioni degli utenti e richiede tra 13-15mins da inserire nel grafico. Ho fatto un test rapido e la lettura dei dati è abbastanza rapidamente, istantaneamente davvero. Il problema è l'inserimento.

Questo problema esiste perché ho un grafico implementato con liste collegate per i vertici. Ogni volta che ho bisogno di inserire una relazione, ho bisogno di ricercare per 2 vertici, in modo che io possa collegare insieme. Questo è il problema ... Fare questo per ~ 520000 rapporti, prende un po '.

Come devo risolvere questo problema?

Soluzione 1) Alcune persone mi consiglia di implementare il grafico (la parte vertici) come un array invece di una lista collegata. In questo modo ho accesso diretto a ogni vertice e l'inserimento è destinata probabilmente a scendere considerevolmente. Ma, non piace l'idea di assegnare un array con [18000] elementi. Come in pratica è questo? I miei dati campione ha ~ 18000, ma cosa succede se ho bisogno di molto meno o molto di più? L'approccio lista collegata ha che la flessibilità, posso avere qualsiasi dimensione che voglio finché c'è memoria per esso. Ma la matrice non, come faccio a gestire tale situazione? Quali sono i vostri suggerimenti?

Utilizzando liste collegate è un bene per lo spazio complessità ma un male per il tempo della complessità. E l'utilizzo di un array è un bene per il tempo della complessità, ma un male per complessità spaziale.

Come trovi questa soluzione?

Soluzione 2) Questo progetto richiede anche che ho una sorta di strutture di dati che consente di ricerca rapida sulla base di un indice di nome e un indice ID. Per questo ho deciso di usare Hash Tables. I miei tavoli sono realizzati con concatenazioni separate come la risoluzione di collisione e quando un fattore di carico di 0,70 è portata, normalmente ricreare la tabella. Baso la dimensione della tabella successiva su questo http://planetmath.org/encyclopedia/GoodHashTablePrimes.html.

Attualmente, entrambi Hash Tables tenere un puntatore alla UserProfile invece di duplicazione del profilo utente stesso. Sarebbe stupido, dati che cambiano richiederebbero 3 cambi ed è veramente stupido a farlo in quel modo. Così ho appena risparmio il puntatore al UserProfile. Il puntatore stesso profilo utente viene anche salvato come valore in ogni Vertex grafico.

Quindi, ho 3 strutture di dati, un grafico e due Hash Tables e ognuno di loro puntano allo stesso UserProfile esatto. La struttura Grafico servirà allo scopo di trovare il percorso più breve e cose del genere, mentre gli Hash Tables servono come indice rapido per nome e ID.

Quello che sto pensando di risolvere il mio problema Graph è, invece di avere il punto di valore Hash Tables al UserProfile, io punto al Vertex corrispondente. E 'ancora un puntatore, né più né meno spazio viene utilizzato, mi just cambiamento quello che indico.

In questo modo, posso facilmente e rapidamente di ricerca per ogni esigenza Vertex I e collegarli tra loro. Questo inserirà i ~ 520000 rapporti abbastanza rapidamente.

I pensato a questa soluzione perché ho già le tabelle hash e ho bisogno di avere loro, allora, perché non approfittare di loro per l'indicizzazione i vertici Grafico invece del profilo utente? E 'fondamentalmente la stessa cosa, posso ancora accedere al UserProfile abbastanza rapidamente, basta andare al Vertex e poi al UserProfile.

Ma, vedi eventuali svantaggi in questa seconda soluzione contro il primo? O solo professionisti che sopraffare i pro ei contro sulla prima soluzione?

Altro Solution) Se avete qualche altra soluzione, io sono tutto orecchi. Ma per favore spiegare i pro ei contro di questa soluzione rispetto alla precedente 2. Io davvero non ho molto tempo per essere spreco con questo proprio ora, ho bisogno di andare avanti con questo progetto, quindi, se sto facendo fare ad esempio un cambiamento, ho bisogno di capire esattamente cosa cambiare e se questo è davvero il modo di andare.

Speriamo che nessuno si è addormentato leggendo questo e ha chiuso il browser, mi spiace per il grande testamento. Ma ho davvero bisogno per decidere cosa fare su questo e ho davvero bisogno di fare un cambiamento.

P.S:. Quando rispondere alle mie soluzioni proposte, si prega di enumerarli come ho fatto quindi so esattamente cosa stai parlando e non confondere la mia auto più di quello che già sono

Answer 1

Il primo approccio è la velocità Dal momento che il problema principale è, io preferirei l'approccio array.

Si dovrebbe, ovviamente, mantenere la tabella di hash per la ricerca del nome-indice.

Se ho capito bene, si elabora solo il tempo di dati. Quindi non v'è alcun inserimento di dati dinamici.

Per affrontare il problema di allocazione di spazio, mi sento di raccomandare:

1 -. Leggi volta che il file, per ottenere il numero di vertici

2 - destinare tale spazio

Se i dati è dinamico, è possibile implementare un metodo semplice per incrementare la dimensione della matrice a passi di 50%.

3 - nei bordi, è sostituire lista collegata per un array. Questa matrice deve essere incrementato dinamicamente con passi di 50%.

Anche con lo spazio "extra" assegnato, quando si incrementa la dimensione con passi di 50%, la dimensione totale utilizzata dal array dovrebbe essere solo leggermente più grande rispetto alla dimensione della lista collegata.

Spero di poter aiutare.