Effizienteste Datenstruktur zur Darstellung von Kommentaren von Thread in Java?

Question

Ich möchte vertreten Thread -Kommentare in Java. Dies würde ähnlich aussehen, wie Kommentare eingetrieben werden Reddit.com

hello
   hello
      hello
      hello
   hello
   hello
      hello

Wie im obigen Beispiel sind die Antworten in der HTML mit geeigneter Eindrücke verschachtelt, um ihre Beziehung zu früheren Kommentaren widerzuspiegeln.

Was wäre eine effiziente Möglichkeit, dies in Java darzustellen?

Ich denke an eine Art Baumdatenstruktur wäre angemessen.

Aber gibt es einen insbesondere, der wäre höchsteffizient Um Baumquellen zu minimieren?

Dies wäre wichtig, wenn ich über jeden Kommentar abstimmen würde. Denn dann müsste der Baum nach jeder Abstimmung neu angeordnet werden - ein potenziell teurer Betrieb.

Wenn jemand von einer Open -Source -vorhandenen Implementierung in Java kennt, würde dies übrigens helfen, dies auch zu helfen.

Answer 1

Ich würde Ebenen von verknüpften Listen verwenden.

message1
    message2
        message3
        message4
    message5
    message6
        message7

Jeder Knoten hätte einen Zeiger auf seinen:

- forward sibling  (2->5, 3->4, 5->6,                   1/4/6/7->NULL).
- backward sibling (4->3, 5->2, 6->5,                   1/2/3/7->NULL).
- first child      (1->2, 2->3, 6->7,                   3/4/5/7->NULL).
- parent           (2->1, 3->2, 4->2, 5->1, 6->1, 7->6,       1->NULL).

Innerhalb jeder Ebene werden Nachrichten in der Liste nach Stimmenzahl sortiert (oder welche andere Punktzahl, die Sie verwenden wollten).

Das würde Ihnen eine maximale Flexibilität geben, um die Dinge umzusetzen, und Sie könnten ganze Unterbäume (z. message2) Nur durch Ändern der Links auf dem übergeordneten und dieser Ebene.

Zum Beispiel sagen message6 bekommt einen Zustrom von Stimmen, der es populärer macht als message5. Die Änderungen sind (Anpassung sowohl der nächsten als auch der vorherigen Geschwisterzeiger):

• message2 -> message6
• message6 -> message5
• message5 -> NULL.

bekommen:

message1
    message2
        message3
        message4
    message6
        message7
    message5

Wenn es weitergeht, bis es mehr Stimmen sammelt als message2, Das Folgende tritt auf:

• message6 -> message2
• message2 -> message5

UND der erste Kinderzeiger von message1 ist eingestellt auf message6 (es war message2), immer noch relativ einfach, um zu bekommen:

message1
    message6
        message7
    message2
        message3
        message4
    message5

Das Neubestehen muss nur auftreten, wenn eine Score-Änderung dazu führt, dass eine Botschaft mehr als ihr oberes Geschwister oder weniger als ihr niedrigeres Geschwister wird. Sie müssen nach jeder Punktzahl nicht nachbestellen.

Answer 2

Der Baum ist recht (mit GetLastsibling und GetNextsibling), aber wenn Sie die Daten speichern/abfragen, möchten Sie wahrscheinlich eine Linie für jeden Eintrag oder eine Nummer durch eine Vorbestellungspflege speichern:

http://www.sitepoint.com/article/hierarchical-data-database/2/

Für den Verlust der genauen Anzahl von Subnodes können Sie Lücken lassen, um die Nutzung zu minimieren. Trotzdem bin ich mir nicht sicher, ob dies merklich schneller sein wird, als jedes Mal den Baum zu durchqueren. Ich denke, es hängt davon ab, wie tief dein Baum wächst.

Siehe auch:

SQL - Wie kann man Hierarchien speichern und navigieren? http://www.ibase.ru/devinfo/dbmstrees/sqlrees.html (Dieses Schema wird auch als Celko -Baum bezeichnet)

Answer 3

Dies wäre wichtig, wenn ich über jeden Kommentar abstimmen würde. Denn dann müsste der Baum nach jeder Abstimmung neu angeordnet werden - ein potenziell teurer Betrieb.

Klingt für mich nach einer vorzeitigen Optimierung, möglicherweise sogar einer fehlerhaften Optimierung.

Ihre Baumdatenstruktur klingt logisch für die Darstellung Ihrer Daten. Ich sage, bleib dabei. Optimieren Sie es später nur, wenn ein Leistungsproblem erkannt und gemessen wird und mit Alternativen verglichen werden kann.