Comment changer ma structure graphique (insertion très lente)?

Question

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

Maintenant, il existe plusieurs implémentations de Graph possibles et je ne pense pas que j'utilise le meilleur. J'ai une structure Graph et à l'intérieur, il y a un pointeur vers une liste liée de type Vertex. Chaque élément Vertex a une valeur, un pointeur vers le Vertex suivant et un pointeur vers une liste liée de type Edge. Chaque élément Edge a une valeur (donc je peux définir des poids et tout ce dont il a besoin), un pointeur vers le Edge suivant et un pointeur vers le propriétaire Vertex.

J'ai 2 fichiers d'exemple avec des données à traiter (en style CSV) et les insérer dans le graphique. Le premier est les données de l'utilisateur (un utilisateur par ligne); le second est les relations d'utilisateur (pour le graphique). Le premier fichier est rapidement inséré dans le graphique car je l'insère toujours en tête et il y a environ 18000 utilisateurs. Le deuxième fichier prend des âges mais j'insère toujours les bords en tête. Le fichier a environ ~ 520000 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 rapide, instantanément vraiment. Le problème est dans l'insertion.

Ce problème existe car j'ai un graphe implémenté avec des listes liées pour les sommets. Chaque fois que j'ai besoin d'insérer une relation, j'ai besoin de chercher 2 sommets, donc je peux les relier entre eux. C'est le problème ... Faire cela pour ~ 520000 relations, prend un moment.

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

Solution 1) Certaines personnes m'ont recommandé d'implémenter le graphique (partie des sommets) en tant que tableau au lieu d'une liste chaînée. De cette façon, j'ai un accès direct à chaque sommet et l'insertion va probablement diminuer considérablement. Mais, je n'aime pas l'idée d'allouer un tableau avec des éléments [18000]. Comment est-ce pratiquement? Mon échantillon de données a ~ 18000, mais que faire si j'ai besoin de beaucoup moins ou beaucoup plus? L'approche de liste liée a cette flexibilité, je peux avoir n'importe quelle taille que je veux tant qu'il y a de la mémoire pour cela. Mais le tableau ne fait pas, comment vais-je gérer une telle situation? Quelles sont vos suggestions? L'utilisation de listes chaînées est bonne pour la complexité de l'espace mais mauvaise pour la complexité temporelle. Et l'utilisation d'un tableau est bonne pour la complexité du temps mais mauvaise pour la complexité de l'espace.

Avez-vous des commentaires sur cette solution?

Solution 2) Ce projet nécessite également que je dispose d'un type de structure de données permettant une recherche rapide basée sur un index de noms et un index ID. Pour cela, j'ai décidé d'utiliser des tables de hachage. Mes tables sont implémentées avec un chaînage séparé comme résolution de collision et quand un facteur de charge de 0,70 est atteint, je recréerai normalement la table. Je base la taille de la table suivante sur ce .

Actuellement, les deux tables de hachage contiennent un pointeur vers le UserProfile au lieu de dupliquer le profil utilisateur lui-même. Ce serait stupide, changer des données nécessiterait 3 changements et c'est vraiment idiot de le faire de cette façon. Donc, je viens de sauvegarder le pointeur sur le UserProfile. Le même pointeur de profil utilisateur est également enregistré en tant que valeur dans chaque graphique Vertex. Donc, j'ai 3 structures de données, un graphique et deux tables de hachage et chacun d'eux pointe exactement le même UserProfile. La structure du graphe servira à trouver le chemin le plus court et ce genre de choses alors que les tables de hachage servent d'index rapide par nom et par ID.Ce que je pense pour résoudre mon problème de graphique est de, au lieu d'avoir la valeur des tables de hachage pointent vers UserProfile, je le pointe vers le Vertex correspondant. C'est toujours un pointeur, pas plus et pas moins d'espace est utilisé, je change juste ce que je veux montrer. Ainsi, je peux facilement et rapidement rechercher chaque Vertex dont j'ai besoin et les lier ensemble. Cela insérera les relations ~ 520000 assez rapidement.

J'ai pensé à cette solution parce que j'ai déjà les tables de hachage et je dois les avoir, alors, pourquoi ne pas en profiter pour indexer les sommets du graphique au lieu du profil de l'utilisateur? C'est à peu près la même chose, je peux toujours accéder au UserProfile assez rapidement, il suffit d'aller au Vertex puis au UserProfile.

Mais, voyez-vous des inconvénients sur cette deuxième solution par rapport au premier? Ou seulement des pros qui maîtrisent les avantages et les inconvénients de la première solution?

Autre solution) Si vous avez une autre solution, je suis tout ouïe. Mais s'il vous plaît expliquer les avantages et les inconvénients de cette solution au cours des 2 précédentes. Je n'ai vraiment pas beaucoup de temps à perdre avec cela en ce moment, je dois aller de l'avant avec ce projet, donc, si je le fais un changement, j'ai besoin de comprendre exactement quoi changer et si c'est vraiment le chemin à parcourir.

J'espère que personne ne s'est endormi en lisant ceci et a fermé le navigateur, désolé pour le grand testament. Mais j'ai vraiment besoin de décider quoi faire à ce sujet et j'ai vraiment besoin de faire un changement. Lorsque vous répondez aux solutions proposées, veuillez les énumérer comme je le faisais, je sais exactement de quoi parlez-vous et ne me confondez pas plus que je ne le suis déjà.

Answer 1

La première approche est la suivante Puisque le problème principal ici est la vitesse, je préférerais l'approche du tableau.

Vous devez, bien sûr, gérer la table de hachage pour la recherche d'index de noms.

Si j'ai bien compris, vous ne traitez les données qu'une seule fois. Il n'y a donc 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 des 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 bords, remplacez votre liste chaînée par un tableau. Ce tableau doit être incrémenté dynamiquement avec des pas de 50%.

Même avec l'espace "supplémentaire" alloué, lorsque vous incrémentez la taille avec des pas de 50%, la taille totale utilisée par le tableau ne doit être que légèrement plus grande qu'avec la taille de la liste chaînée.

J'espère pouvoir vous aider.