Connaitre les amis des amis

Bzh

Bonjour,

Dans un projet de site communautaires, je souhaite pouvoir afficher les amis des amis et surtout le nombre d'amis d'amis.


Par exemple, si chaqu'un de mes amis direct possedent 10 amis et que j'ai 10 amis, je voudrais afficher :

Amis 10 et 100 personnes dans ta comunauté.

Mais voia, je n'arrive pas à organiser mes données dans la base.

J'arrive tout de suite à un temps de traitement très très lourd !

Comment pourrais-je organiser mes tables ?

En sachant qu'au finale, je souhaite afficher le nombre d'amis des amis de mes amis.

Koboneil

Bah je suppose que t'as une table MEMBRE. Il suffit de faire une table comme ça :

AMIS(id_membre, id_membre_amis);

Non ?

Bzh

Non, car dans ce cas, la recherche des amis des amis serait une requete dans une boucle de la première requete.


Si, la personne à 100 amis, cela nous fera au total 101 requetes. Ce qui est affligeant.

Et puis, imagine si l'on souhaite aussi compter les amis des amis des amis.

Cela nous ferait deux boucles imbriqués soit pour 100 amis:

1 * 100 ^ 100

Donc completement irréalisable !

LA GLOBULE

Ce que tu peux faire, c'est stocker dans un champ le nombre d'ami direct d'un utilisateur.
Si tu gères proprement ton truc avec des transactions SQL, çà peut le faire.

Bzh

Oui, j'étais entrain de creuser cette idée...

Merci

Lefounard

Si tu veux alleger en requete, tu vas perdre en memoire.
Il faut que tu trouve un compromis.
Si tu veux pousser ton programme, tu fais un graphe de ta communauté, ensuite si tu veux trouver les amis des amis du membre A, tu calcule l'arbre recouvrant de racine A et de chemin de longueur max 2 (ce qui correspond aux amis de tes amis).
L'implémentation n'est pas trop dur niveau mémoiré, tu peux faire ca sous forme de matrice, mais ca peut-etre lourd, si 10 000 membres.
On prends 1 bit pour dire (0 non ami, 1 ami), sur 10 000 inscrits, ca fait 10 000 ^2 bits, ca reste encore raisonnable.
Sinon, tu peux stocker sous liste d'adjacence.
Alors si a chaque fois que tu dois afficher les amis des amis, ca doit faire si ton algo doit se refaire.
Donc a la limite, tu lance l'algo juste quand quelqu'un modifie un ami, et apres tu stocke ton arbre d'amis dans un fichier xml ou bdd.
Ca parait plutot lourd tout ce que je raconte, c'est une posibilité.
Il y a surement des possibilité plus simples.
Ciao,

Michel_57

j'aurais aussi fait comme ça, tu mets pour chaque membre :
- un champ qui dit combien il a d'amis
- un champ qui dit la population totale de la communauté (amis des amis)

tu auras donc des requètes simples pour l'affichage, mais faudra rajouter les requètes pour modifier les nombres dans ces 2 nouveaux champs à chaque fois que quelqu'un ajoute ou supprime un ami.

ça semble facile comme ça mais peut-être y a-t-il un truc auquel on n'a pas pensé ^^

Lefounard

Supposons la table amitie
[id_membre1;id_membre2]

Compléxité en mémoire

On stocke par exemple [1;2] mais la suite on ne stockera par [2;1] car c'est une relation reciproque.
Si nous avons n membres, la table amitie dans le pire des cas stockera n*(n-1) tuples,
c'est a dire qu'un membre peut avoir au max n-1 amis.
Donc en termes d'occupations memoire dans le pire des cas
n*(n-1)*(nombre de champs dans la table = 2)*taille d'un champs = int(8))

On peut gagner en memoire,
si au lieu de stocker id_membre1;id_membre2.
On stocke id_membre; list_damis,
list_damis de la forme (id1;id2;.......)
le traitement sera legerement allourdi par un implode et explode
On devra ajouter aussi pareil un controle :
Par exemple, j'ajoute l'ami 2 du membre 1,
Lors de l'ajout de 2, je verifie que 1 n'est pas deja dans la liste d'amis de 2.
Cela permettra d'eviter des doublons dans la table
Occupation memoire : n * (taille du champ id_membre + taille list_damis)
La normalement on gagne en terme de memoire.


Compléxité en requete :

Prenons notre cas ou on doit connaitre seulement les amis des amis.
Donc deja on va reprendre toute la partir precedente et au lieu de stocker les id, on stocke les logins,
on perd un peu en memoire mais on gagne en requete et on evite lors de l'affichage de la communauté
de faire des selections inutiles pour recuperer les logins a partir des ids.

Donc pour recuperer la communauté d'une personne, il faut recuperer ses amis directe , simple select et recuperation de la liste.
Pour chaque amis , on recupere leur liste d'amis.
Donc au total, si k amis direct, ca fait k+1 requetes.
Je ne vois pas comment faire autrement, je t'ai fais gagner en terme de memoire.

C'est alors que je me rend compte qu'il sera preferable de perdre en memoire et gagner en requete.
Pour cela ajouter les amis des amis ta liste d'amis d'un membre.
Ca tombera a une seule requete a l'affichage, mais a l'insertion d'un amis, il faudra faire un update de chaque amis de la liste.
Si 500 dans l'entourage ca fait 500 UPDATE. Compliqué ton truc.

Sinon une idée, tu definie tes communauté par un nom, tu fais du hierarchique comme dans le routage.
C'est peut-etre le plus simple et le plus optimiser.

Lefounard

Systeme de Groupe :

Tables

membre
[login_membre]

table groupe
[nom_groupe, list(login_membre)]

table appartient_groupe
[login_membre,nom_groupe]

Probleme : on ne limite pas aux amis des amis, un groupe peut contenir toutes les membres du site dans un cas particulier

Inscription

Le membre n'appartient a aucun groupe au depart.


Ajout du premier ami

Lors de l'ajout du premier ami, le membre va se voir attribuer le groupe de la personne qu'il ajoute.
Sinon il peut creer un groupe ou il sera seul dedans. Il faut eviter ce cas de figure.
Dans le cas ou les deux amis n'ont pas de groupe, on invite le membre a creer un groupe.
Le membre peut creer son groupe.

Ajout d'un ami

Les amis s'echange les groupe auxquels il appartiennent, requete donc modere deux update et recuperation des groupes via un select dans table groupe


Affichage le l'entourage :
On affichage la liste des membres des groupe auquel le membre appartient

Le problème est de pouvoir limiter en terme de d'amis d'amis, c'est pour ca que dans ce cas de figure c'est surement le parcours d'un arborescence qui est peut-etre
le plus judicieux

Bzh

En tout cas, merci beaucoup...
C'est vraiment très interressant.

Je vais cogiter là dessu un peu avant de revenir proposer une première version.

Maintenant, si je reviens un petit peu sur ce que tu viens de dire, il est, et l'expérience me la confirmée, PRIMORDIALE de préférer des requetes SIMPLE avec une base de donnée en taille plus importante.

Un exemple, je reviens dessu parce que je le trouve parlant (HISTOIRE VRAI):

Une table amis (pas de doublons 40 000 enregistrements ):

id_ami_1, id_ami_2

la requete :

SELECT id_ami_1, id_ami_1 FROM amis WHERE id_ami_1 = 895 OR id_ami_2 = 895

temps d'éxécution : 0.125ms

DEUXIEME VERSION

table amis (table avec doublon donc 80 000 enregistrements AVEC UN INDEX SUR id_membre):

id_membre; id_ami

la requete:

SELECT id_ami FROM amis WHERE id_membre = 895

temps d'éxécution : 0.25ms


Donc MORALE :

Préférer une table avec plus d'enregistrement MAIS l'index bien pensé et une requete plus simple QU'UNE base plus légère MAIS une requete plus compliqué ( OR ).