Comment dois-je changer ma structure de graphique (insertion très lent)?

Question

Ce programme que je fais est sur un réseau social, ce qui signifie qu'il ya des utilisateurs et leurs profils. La structure des profils est UserProfile.

Maintenant, il y a différentes implémentations possibles Graphique et je ne pense pas que je suis en utilisant le meilleur. J'ai une structure Graph et à l'intérieur, il y a un pointeur sur une liste chaînée de type Vertex. Chaque élément de Vertex a une valeur, un pointeur vers la prochaine Vertex et un pointeur sur une liste chaînée de type Edge. Chaque élément a une valeur Edge (donc je peux définir des poids et tout ce qu'il est nécessaire), un pointeur vers la prochaine Edge et un pointeur au propriétaire de Vertex.

J'ai 2 exemples de fichiers avec des données à traiter (dans le style CSV) et l'insérer dans le graphique. Le premier est les données d'utilisateur (un utilisateur par ligne); le second est la relation de l'utilisateur (pour le graphique). Le premier fichier est rapidement inséré dans le graphique parce que j'insère toujours à la tête et il y a comme ~ utilisateurs 18000. Le second fichier prend une éternité mais j'insérer encore les bords à la tête. Le fichier a environ ~ 520 000 lignes de relations utilisateur et prend entre 13-15mins à insérer dans le graphique. J'ai fait un test rapide et la lecture des données est assez rapidement, instantanément vraiment. Le problème réside dans l'insertion.

Ce problème existe parce que j'ai un graphique mis en œuvre par des listes chaînées pour les sommets. Chaque fois que je besoin d'insérer une relation, je dois rechercher pour 2 sommets, donc je peux les relier entre eux. C'est le problème ... Faire cela pour ~ 520000 relations, prend un certain temps.

Comment dois-je résoudre ce problème?

Solution 1) Certaines personnes me recommandé de mettre en œuvre le graphique (la partie des sommets) comme un tableau au lieu d'une liste chaînée. De cette façon, j'avoir un accès direct à tous les sommets et l'insertion va probablement baisser considérablement. Mais, je n'aime pas l'idée d'allouer un tableau avec des éléments [] 18000. Comment est-ce pratiquement? Mes données d'échantillon a ~ 18000, mais si je dois beaucoup moins ou beaucoup plus? L'approche de la liste liée a cette flexibilité, je peux avoir quelque taille que je veux aussi longtemps que il y a la mémoire pour elle. Mais le tableau ne pas, comment vais-je gérer une telle situation? Quelles sont vos suggestions?

En utilisant des listes chaînées est bon pour la complexité de l'espace, mais mauvais pour la complexité du temps. Et en utilisant un tableau est bon pour la complexité du temps, mais mauvais pour la complexité de l'espace.

Les pensées au sujet de cette solution?

Solution 2) Ce projet exige aussi que j'ai une sorte de structures de données qui permet un accès rapide basé sur un index de nom et un indice d'identification. Pour cela, je décidé d'utiliser les tables de hachage. Mes tableaux sont mis en œuvre avec Enchaînement séparés comme résolution de collision et quand un facteur de charge de 0,70 est atteint, je recrée normalement la table. Je base la prochaine taille de la table sur cette http://planetmath.org/encyclopedia/GoodHashTablePrimes.html.

À l'heure actuelle, les deux tables de hachage tenir un pointeur vers la UserProfile au lieu de duplication à l'utilisateur lui-même profil. Ce serait stupide, l'évolution des données nécessiteraient 3 changements et il est vraiment stupide de le faire de cette façon. Je viens donc de sauver le pointeur sur le UserProfile. Le pointeur même profil d'utilisateur est également enregistré en tant que valeur dans chaque graphique Vertex.

Alors, j'ai 3 structures de données, un graphique et deux tables de hachage et chacun d'entre eux pointent vers la même UserProfile exacte. La structure graphique servira dans le but de trouver le chemin le plus court et des choses comme ça alors que les tables de hachage servent index rapide par nom et ID.

Qu'est-ce que je pense pour résoudre mon problème de graphique est, au lieu d'avoir le point de valeur tables de hachage au UserProfile, je signale à la Vertex correspondante. Il est encore un pointeur, ni plus ni moins d'espace est utilisé, je just changer ce que je tiens à.

Comme cela, je peux facilement et rapidement rechercher pour chaque Vertex j'ai besoin et de les relier entre eux. Cela insérera les relations ~ 520000 assez rapidement.

Je pensais à cette solution parce que je l'ai déjà les tables de hachage et je dois les avoir, alors, pourquoi ne pas en profiter pour indexer les sommets du graphe au lieu du profil de l'utilisateur? Il est fondamentalement la même chose, je peux toujours accéder au UserProfile assez rapidement, juste aller à la Vertex puis au UserProfile.

Mais, voyez-vous des inconvénients à cette deuxième solution contre le premier? Ou seulement des avantages qui accablent les avantages et les inconvénients sur la première solution?

Autre solution) Si vous avez une autre solution, je suis toutes les oreilles. Mais s'il vous plaît expliquer les avantages et les inconvénients de cette solution sur la précédente 2. Je n'ai vraiment pas beaucoup de temps à gaspiller ce moment, je dois passer avec ce projet, donc, si je fais faire ce un changement, je dois comprendre exactement ce qu'il faut changer et si c'est vraiment le chemin à parcourir.

Il faut espérer ne tomba endormi lecture et ce fermé le navigateur, désolé pour le grand testament. Mais je vraiment besoin de décider quoi faire à ce sujet et je vraiment besoin de faire un changement.

P.S:. En répondant à mes solutions proposées, s'il vous plaît les énumérer comme je l'ai fait, je sais exactement ce que vous parlez et ne confondez pas mon moi plus que je suis déjà

Answer 1

La première approche est la Depuis la principale question est la vitesse, je préfère l'approche du tableau ici.

Vous devriez, bien sûr, maintenir la table de hachage pour la recherche nom-index.

Si je comprends bien, vous ne traiter que les données une seule fois. Donc, il n'y a pas d'insertion de données dynamiques.

Pour faire face au problème de l'allocation d'espace, je recommande:

1 -. Relisez le fichier, pour obtenir le nombre de sommets

2 - allouer cet espace

Si vous données est dynamique, vous pouvez mettre en œuvre une méthode simple pour augmenter la taille du tableau dans les étapes de 50%.

3 - Dans les Arêtes, substituez vous liste chaînée pour un tableau. Ce tableau doit être dynamiquement incrémentée par pas de 50%.

Même avec le « extra » espace alloué, lorsque vous incrémenter la taille avec des étapes de 50%, la taille totale utilisée par le réseau ne devrait être légèrement plus grand que la taille de la liste chaînée.

J'espère que je pourrais aider.