Verbindungen in Freundeslisten zeigen

Diese Seite verwendet Cookies. Durch die Nutzung unserer Seite erklären Sie sich damit einverstanden, dass wir Cookies setzen. Weitere Informationen

  • Verbindungen in Freundeslisten zeigen

    Hi,

    auf meiner Page habe ich eine Freundesliste. Und diese möchte ich nun mit einer Funktion erweitern und zwar soll Angezeigt werden ob ich einen User über andere User kenne.

    Z.b. gehe ich auf das Profil von x der ein Freund von y ist der wiederum ein Freund von mir ist.

    Nun hätte ich gerne eine Anzeige:

    Ich -> y -> x

    Diese Funktion habe ich bei Studivz gefunden falls ihr das kennt.

    Ich frage mich wie ich das Speichern bzw. berechnen soll. Ich kann ja nicht die ganze freunde tabelle x mal durchsuchen.

    Falls jemand einen kleinen wink in die richtige Richtung oder Lösungsalgorithmus hätte wär das echt geil !

  • Hi, ist nicht getestet, aber sicherlich als Wink zu verwenden ;)

    Brainfuck-Quellcode

    1. ------ friends -------------
    2. nick1 nick2
    3. ----------------------------
    4. ICH freund1
    5. ICH freund2
    6. ICH freund3
    7. freund1 freundesfreund


    Quellcode

    1. SELECT nick2 FROM friends f1 JOIN friends f2 ON f1.nick1 = f2.nick2
    2. WHERE f2.nick2 = "freundesfreund" AND f1.nick1 = "ICH";

  • Ein Problem mit dem ich mich ein wenig beschäftige. Dachte immer, so schwer kann es nicht sein, studiVZ kann das ja auch :twisted:
    Also das Problem kommt aus der Graphentheorie, das Netzwerk von Freunden ist ein ungerichteter ungwichteter Graph ohne Kreis (Wald). Das Problem ist also in dem Graphen einen Weg von A nach B finden, also haben wir das gleiche Problem wie die Routenplaner von Bus und Bahn. Die benutzen mit ziemlicher Sicherheit den Algorithmus von Dijkstra (oder Abwandlungen). Der Dijkstra-Algorithmus bezieht sich auf kantengewichete Graphen aber das macht nichts, den ungewichtete Graphen sind eine Untermenge bei denen das Gewicht überall gleich groß ist.
    Du musst dich also ein wenig in die Graphentheorie einarbeiten (da kommst du auf keinen Fall drum herum) und dann das Vorgehen von Dijkstra verstehen. Es gibt Optimierungen (A*) die uns aber nicht helfen - meiner Meinung nach kann man mit Knotengewichten optimieren, Menschen mit vielen Freunden werden höher gewichtet, aber da werde ich ganz zum Schluss drüber nachdenken.

    P.S. Ich habe gehört Oracle Datenbanken können das bereits.
    ~ mfg SeBa

    Ich beantworte keine PMs zu Computer-/Programmierproblemen. Bitte wendet euch an das entsprechende Forum.

    [Blockierte Grafik: http://i.creativecommons.org/l/by-sa/3.0/80x15.png]

  • Wieso wird die Datenbank groß? Wenn du eine Adjazenzmatrix oder Inzidenzmatrix (oder Liste) speicherst, ist das reltiv effizient. Ich denke das erzeugt weniger Daten als die gleiche Anzahl Leute in einem Forum verursachen würden, also wahrscheinlich ein Bereich den eine DB locker verkraftet).

    Die Daten sind nicht das Problem, sie werden einem quasi mundgerecht serviert, da die User selber anklicken wen sie mögen. Das einzige was kompliziert ist, ist einigermaßen Effizent den kürzesten Weg durch die Daten zu finden.
    ~ mfg SeBa

    Ich beantworte keine PMs zu Computer-/Programmierproblemen. Bitte wendet euch an das entsprechende Forum.

    [Blockierte Grafik: http://i.creativecommons.org/l/by-sa/3.0/80x15.png]

  • Die sind recht einfach zu verstehen (eine ausführliche Erklärung gibt, wie immer, bei Wikipedia).

    Jeder Knoten im Graphen hat einen Namen (in unserem Fall die UserID). In der Adjazenzliste wird nun zu jedem Knoten eine Liste angelegt in der alle Nachbarn gespeichert werden. Da wir ungerichtete Graphen betrachten (wenn a mit b befreundet ist, ist b auch mit a befreundet), brauchst du für jede Freundschaft nur zwei Zahlen zu speichern.

    Bei der Adjazenzmatrix wird eine Tabelle angelegt und markiert wer mit wem benachbart ist, was aber datenbanktechnisch schlecht zu realisieren ist. Lässt sich aber leichter vorstellen. Da ausschließlich mit Zahlen gearbeitet wird und ein Vergleich von zwei Zahlen recht einfach für den Computer ist, lässt sie sich auch bei sehr vielen Datensätzen noch schnell suchen.
    ~ mfg SeBa

    Ich beantworte keine PMs zu Computer-/Programmierproblemen. Bitte wendet euch an das entsprechende Forum.

    [Blockierte Grafik: http://i.creativecommons.org/l/by-sa/3.0/80x15.png]

  • Guten Abend :] Ich habe folgende Datenbankstruktur

    Quellcode

    1. Tabelle `friends`
    2. -----------------------------
    3. freund_id | freund_von
    4. -----------------------------
    5. 1 | 2
    6. 255 | 1337
    7. [...]

    Es werden also immer die beiden User-IDs gespeichert - wenn User A (hat UID 1) nun User B (hat UID 255) in seine Freundesliste fügt, wird oben ein neuer Eintrag angelegt nach diesem Schema:

    Quellcode

    1. Tabelle `friends`
    2. -----------------------------
    3. freund_id | freund_von
    4. -----------------------------
    5. 255 | 1
    6. [...]

    Die Tabelle geht so weiter. So, nun wollte ich d0nuts Code probieren und habe ihn angepasst

    Quellcode

    1. SELECT * FROM friends f1 JOIN friends f2 ON f1.freund_von = f2.freund_id WHERE f2.freund_id = '1337' AND f1.freund_von = '1' LIMIT 1

    (Werte "1337" und "1" sind in diesem Fall nur ein Beispiel)
    Wenn ich diese Abfrage ausführe, folgt immer kein Resultat :(

    Könnt ihr mir helfen?

  • Hallo t_R,

    zum einen muß man jeden Eintrag in beide Richtungen setzen.
    Also "freund_id" 1 ist der "freund_von" 2,
    aber auch umgekehrt "freund_id" 2 ist der "freund_von" 1.

    Schließlich weiß man nie, auf welcher Seite der Tabelle eine ID zu suchen ist.
    Bei Deinem Beispiel steht in der SQL-Abfrage: freund_id='1337',
    in der Tabelle gibt's aber 1337 nur auf der rechten Seite, unter freund_von.


    freund_id | freund_von
    1 | 2
    2 | 1
    255 | 1337
    1337 | 255
    ...

    Zum anderen hat sich d0nUt mit den Bezeichnern bißchen verhaspelt.

    Es müßte heißen:

    SQL-Abfrage

    1. SELECT nick2 FROM friends f1
    2. JOIN friends f2
    3. ON f1.nick2 = f2.nick1
    4. WHERE f2.nick2 = "freundesfreund"
    5. AND f1.nick1 = "ICH";


    bzw. analog dazu für Deine Tabelle:

    SQL-Abfrage

    1. SELECT * FROM friends f1
    2. JOIN friends f2
    3. ON f1.freund_von = f2.freund_id
    4. WHERE f2.freund_von = '1337'
    5. AND f1.freund_id = '1'
    6. LIMIT 1


    Am besten immer Skizzen zeichnen :)

    f1->freund_id = 1337
    f1->freund_von \
    . . . . . . . . (verknüpfung)
    f2->freund_id /
    f2->freund_von = 1


    CU!
    Nichts auf der Welt ist so gerecht verteilt wie der Verstand. Jeder glaubt, er hätte genug davon.
    --------------------------------------------------(Rene Descartes)

  • Äh, ne, 2 Abfragen würden da nicht reichen.
    Die Komplexität der Tabellen-Verkettungen steigt quadratisch.

    Person A könnte "freund_id" sein, oder aber "freund_von".
    Person B könnte ebenfalls "freund_id" sein, oder aber "freund_von".

    Und schon mußt Du 4 Abfragen stellen, nämlich:

    Quellcode

    1. SELECT * FROM friends f1
    2. JOIN friends f2
    3. ON f1.freund_id = f2.freund_id
    4. WHERE f2.freund_von = '1337'
    5. AND f1.freund_von = '1'
    6. LIMIT 1
    8. SELECT * FROM friends f1
    9. JOIN friends f2
    10. ON f1.freund_von = f2.freund_id
    11. WHERE f2.freund_von = '1337'
    12. AND f1.freund_id = '1'
    13. LIMIT 1
    15. SELECT * FROM friends f1
    16. JOIN friends f2
    17. ON f1.freund_id = f2.freund_von
    18. WHERE f2.freund_id = '1337'
    19. AND f1.freund_von = '1'
    20. LIMIT 1
    22. SELECT * FROM friends f1
    23. JOIN friends f2
    24. ON f1.freund_von = f2.freund_von
    25. WHERE f2.freund_id = '1337'
    26. AND f1.freund_id = '1'
    27. LIMIT 1
    Alles anzeigen


    Da sind die redundaten Datenmengen doch wahrscheinlich leichter zu verschmerzen.



    Noch lustiger wird's, wenn Du noch nicht nur den Freundesfreund wissen willst,
    sondern wie oben ursprünglich mal gefragt den "Freundesfreundesfreundesfreund".


    Hab zwischendurch mal mit einigen Dummy-Daten gespielt:
    10.000 eingetragene Freundschaften, d.h. 20.000 Tabellen-Einträge:

    Quellcode

    1. SELECT *
    2. FROM friends f1
    3. JOIN friends f2 ON f1.freund_von = f2.freund_id
    4. WHERE f1.freund_id != f2.freund_von

    >> (28,466 Treffer, die Abfrage dauerte 0.0021 sek.)

    ---------------------

    Quellcode

    1. SELECT *
    2. FROM friends f1
    3. JOIN friends f2 ON f1.freund_von = f2.freund_id
    4. JOIN friends f3 ON f2.freund_von = f3.freund_id
    5. WHERE f1.freund_id != f2.freund_von
    6. AND f1.freund_id != f3.freund_von

    >> (69,208 Treffer, die Abfrage dauerte 0.0022 sek.)

    ---------------------

    Quellcode

    1. SELECT *
    2. FROM friends f1
    3. JOIN friends f2 ON f1.freund_von = f2.freund_id
    4. JOIN friends f3 ON f2.freund_von = f3.freund_id
    5. JOIN friends f4 ON f3.freund_von = f4.freund_id
    6. WHERE f1.freund_id != f2.freund_von
    7. AND f1.freund_id != f3.freund_von
    8. AND f1.freund_id != f4.freund_von

    >> (152,406 Treffer, die Abfrage dauerte 0.0046 sek.)


    Aber auch diese Abfragen sind nicht 100%ig.
    Ich hab nicht alle möglichen "Pingpong-Verknüpfungen" ausgeschlossen,
    also sowas, wie
    1<->2<->1<->2<->1
    1<->2<->3<->2<->3
    ....
    ----------------------

    Das funktioniert natürlich nur, wenn man Indizes setzt, ansonsten tickt jeder Rechner aus.
    Nichts auf der Welt ist so gerecht verteilt wie der Verstand. Jeder glaubt, er hätte genug davon.
    --------------------------------------------------(Rene Descartes)

    Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von McSush ()

  • hm, also ok, spaßeshalber:

    Tabelle "friends", weiterhin beidseitig redundant ausgelegt, enthält wie gehabt, 20.000 Einträge, also 10.000 Freundschaften.
    Tabelle "friends2" ist nun einseitig ausgelegt, enthält also 10.000 Einträge = 10.000 Freundschaften.

    "friends" hat eine Größe von 594 KB, 180 davon reine Daten, der Rest Indizierung.
    "friends2" hat eine Größe von 299 KB, 90 davon reine Daten, Rest Indizierung.

    Da ich weiß, daß die UserIDs 2414 und 6282 Freundesfreunde sind,
    frage ich diese Freundesfreundschaft nun ab:

    __________________________

    Bei Tabelle "friends":

    Quellcode

    1. SELECT *
    2. FROM friends f1
    3. JOIN friends f2 ON f1.freund_von = f2.freund_id
    4. WHERE f1.freund_id='2414' AND f2.freund_von='6282'
    5. LIMIT 1


    Ergebnis:
    freund_id | freund_von | freund_id | freund_von
    2414 | 8450 | 8450 | 6282

    (Abfragegeschwindigkeit: 0.0013 sek. | 0.0024 sek. beim ersten Aufruf)
    __________________________

    Bei Tabelle "friends2":

    Quellcode

    1. (SELECT * FROM friends2 f1 JOIN friends2 f2
    2. ON f1.freund_id = f2.freund_id
    3. WHERE
    4. (f2.freund_von = '2414' AND f1.freund_von='6282')
    5. OR (f2.freund_von = '6282' AND f1.freund_von='2414')
    6. LIMIT 1)
    7. UNION
    8. (SELECT * FROM friends2 f1 JOIN friends2 f2
    9. ON f1.freund_von = f2.freund_id
    10. WHERE
    11. (f2.freund_von = '2414' AND f1.freund_id='6282')
    12. OR (f2.freund_von = '6282' AND f1.freund_id='2414')
    13. LIMIT 1)
    14. UNION
    15. (SELECT * FROM friends2 f1 JOIN friends2 f2
    16. ON f1.freund_id = f2.freund_von
    17. WHERE
    18. (f2.freund_id = '2414' AND f1.freund_von='6282')
    19. OR (f2.freund_id = '6282' AND f1.freund_von='2414')
    20. LIMIT 1)
    21. UNION
    22. (SELECT * FROM friends2 f1 JOIN friends2 f2
    23. ON f1.freund_von = f2.freund_von
    24. WHERE
    25. (f2.freund_id = '2414' AND f1.freund_id='6282')
    26. OR (f2.freund_id = '6282' AND f1.freund_id='2414')
    27. LIMIT 1)
    28. LIMIT 1
    Alles anzeigen


    Ergebnis:
    freund_id | freund_von | freund_id | freund_von
    8450 | 2414 | 8450 | 6282

    Hier muß man anschließend noch kombinieren, daß der Verknüpfungsfreund
    wohl derjenige ist, der nicht die ID 2414 oder 6282 hat.

    (Abfragegeschwindigkeit: 0.0022 sek. | 0.0083 sek beim ersten Aufruf)
    __________________________

    Nachteil von der ersten Methode sind halt die doppelten Datenmengen,
    wobei Festplattenspeicher heutzutage kein Problem darstellt.

    Nachteile der zweiten Methode:

    * Gruselige SQL-Abfrage,
    * fast doppelt so lange Abarbeitungszeit,
    * und anschließend muß man noch kombinieren, in welchem Feld der Verknüpfungsfreund steht.

    Außerdem kann man Methode 1 leicht auf mehrere Freundesfreundfreunde erweitern.
    Das würde ich bei der 2. Methode ganz bestimmt nicht versuchen.

    Oder wüßte jemand eine Optimierung bei der friends2-Abfrage?
    Nichts auf der Welt ist so gerecht verteilt wie der Verstand. Jeder glaubt, er hätte genug davon.
    --------------------------------------------------(Rene Descartes)

    Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von McSush ()

  • Das Teil sieht ja gruselig aus. Ich hab mir keine großartigen Gedanken gemacht und auch keine Testdatenbank, mir schwebte Folgendes vor um die ersten Beiden Queries zusammenzufassen.

    Quellcode

    1. SELECT * FROM friends f1
    2. JOIN friends f2
    3. ON ((f1.freund_id = f2.freund_id) or (f1.freund_von = f2.freund_id))
    4. WHERE ((f2.freund_von = '2') or (f1.freund_von = '3'))
    5. AND ((f1.freund_von = '2') or (f2.freund_von = '3'))
    6. LIMIT 1


    Die anderen beiden wären analog, somit wären es insgesamt 2 Queries - aber wie gesagt ist nicht getestet. Kann sein dass da auch an den Bedingungen geschraubt werden müsste.
    ~ mfg SeBa

    Ich beantworte keine PMs zu Computer-/Programmierproblemen. Bitte wendet euch an das entsprechende Forum.

    [Blockierte Grafik: http://i.creativecommons.org/l/by-sa/3.0/80x15.png]

  • SeBa schrieb:


    Quellcode

    1. SELECT * FROM friends f1
    2. JOIN friends f2
    3. ON ((f1.freund_id = f2.freund_id) or (f1.freund_von = f2.freund_id))
    4. WHERE ((f2.freund_von = '2') or (f1.freund_von = '3'))
    5. AND ((f1.freund_von = '2') or (f2.freund_von = '3'))
    6. LIMIT 1



    Mal überlegen...

    WHERE
    ((f2.freund_von = '2') OR (f1.freund_von = '3'))
    AND
    ((f1.freund_von = '2') OR (f2.freund_von = '3'))

    Theoretisch also 4 Kombinationen, aber
    f1.freund_von kann nicht gleichzeitig den Wert 2 und 3 haben
    und f2.freund_von kann auch nicht gleichzeitig 2 und 3 enthalten.

    Also bleiben von den Kombinationen noch 2 möglich:

    f1.freund_von=3 AND f2.freund_von=3
    OR
    f2.freund_von=2 AND f1.freund_von=2


    Hab die beiden Fälle hinter diesen "Skizzen" aufgeschrieben,
    welche Deine 2 JOIN-Verknüpfungen zeigen.

    also entweder f1.freund_von und f2.freund_von = 3 ,
    oder f1.freund_von und f2.freund_von = 2:


    f1.freund_von 3 | 2
    f1.freund_id
    \
    (join)     (oben 3, wenn unten 3 || oben 2, wenn unten 2)
    /
    f2.freund_id
    f2.freund_von 3 | 2

    Damit findest Du doch eigentlich nur die direkten Freunde
    von "3" und die von "2", nicht aber diejenigen, die mit beiden befreundet sind.

    Und Fall 2 der JOIN-Verknüpfung:


    f1.freund_id
    f1.freund_von 3 | 2
    \
    (join)
    /
    f2.freund_id
    f2.freund_von 3 | 2

    Die dürfte eigentlich garkeine Ergebnisse liefern,
    es sei denn "3" oder "2" haben sich selbst in ihre Freundesliste aufgenommen.


    - noch eben schnell in der Test-Tabelle ausprobieren...
    Jup, wie erwartet: einen direkten Freund gefunden.
    Nichts auf der Welt ist so gerecht verteilt wie der Verstand. Jeder glaubt, er hätte genug davon.
    --------------------------------------------------(Rene Descartes)