Effizienter Weg/Struktur, um nur verschiedene Strings zu speichern

Question

Ich arbeite derzeit in einer Java-Anwendung mit vielen Strings (+2000). Ich möchte diese Strings in einer geeigneten Struktur speichern. Wenn ich also einen neuen String speichern möchte, kann ich schnell nachsehen, ob bereits ein String vorhanden ist. Wenn keine gleiche Zeichenfolge in der Struktur war, fahre ich fort, die neue zu speichern (im Grunde speichern, ohne Strings zu wiederholen.).

//PSEUDOCODE 
private ?????? myCollectionOfStrings; 

public void store_If_Not_Exist(String aNewString){ 
    if (!exist_in_Collection(aNewString)){ //this must be fast. 
     store_in_Collection(aNewString); 
    } 
} 

---

Ich bin derzeit eine naive Implementierung verwendet wird, aber ich weiß, dass ist wirklich ineffizient:

private List<String> myCollectionOfStrings; 

public void store_If_Not_Exist(String aNewString){ 
    boolean existInCollection = false; 

    for (String s: myCollectionOfStrings){ 
     if (s.equals(aNewString)){ 
      existInCollection = true; 
      break; 
     } 
    } 

    if(!existInCollection) 
     store_in_Collection(aNewString); 
} 

---

Die Frage ist: Welche Art von Verfahren/Struktur/Algorithmus kann i verwenden, um die Zeichenfolgen zu speichern, so dass die Überprüfung auf Existenz schnell implementiert werden kann? Vielleicht ein Trie Tree oder eine HashMap ???. Vielen Dank!

Answer 1

Wenn die Wörter in alphabetischer Reihenfolge nicht wichtig sind, verwenden Sie einfach ein HashSet. Es ermöglicht Ihnen, jedes Element in O (1) abzurufen, und Sie können das Wort einfach zum Satz hinzufügen, ohne sich Gedanken über das Erstellen von Duplikaten machen zu müssen.

Das einzige Problem mit Hash-Sammlungen ist, dass die nicht eine natürliche Reihenfolge beibehalten, wenn Sie über sie iterieren. Mit anderen Worten, ein HashSet wird Ihre Wörter nicht in alphabetischer Reihenfolge drucken.

Wenn Reihenfolge für Ihre Anwendung kritisch ist, ist mein Vorschlag, dass Sie entweder eine TreeMap oder eine Trie verwenden. Sie teilen beide einige Eigenschaften und die Grundstruktur, aber ein Trie ist für Saiten optimiert.

Wenn Sie die Dinge nicht zu kompliziert machen wollen, verwenden Sie die TreeMap, die Teil des Collections-Frameworks ist.

Aber wenn Sie die Extrameile auf Ihrem Weg zur Effizienz gehen wollen, dann ist die Datenstruktur, nach der Sie suchen, eine Trie.

https://en.wikipedia.org/wiki/Trie

Zusammengefasst ein Trie ist eine Datenstruktur, die Sie Zeichenfolgen in alphabetischer Reihenfolge zu speichern. Es ist sehr leistungsfähig, weil Sie so schnell erkennen können, dass ein Wort fehlt.

Stellen Sie sich vor, Sie möchten nach dem Wort "foo" suchen, und wenn es nicht in Ihrem Baum ist, möchten Sie es hinzufügen.

Wie Sie im wikipedia-Artikel sehen können, enthält der Wurzelknoten des Trie einen leeren String. Ihre erste Aktion, um zu bestimmen, ob das Wort foo in der Trie ist, wäre, zu überprüfen, ob der Wurzelknoten einen Kindknoten mit der Zeichenkette "f" hat. Wenn dies nicht der Fall ist, wissen Sie bereits, dass das Wort nicht in Ihrem Konto ist und Sie nur eine Operation durchgeführt haben.

Wenn der Wurzelknoten dagegen ein Kind mit der Zeichenfolge "f" hat, müssen Sie überprüfen, ob dieser Knoten ein Kind mit der Zeichenfolge "fo" hat, wenn nicht, Ihr Wort ist nicht im Trie. Wenn dies der Fall ist, überprüfen Sie schließlich, ob der Knoten "fo" ein Kind namens "foo" hat.

Zusammenfassend ist ein Trie genau das, was Sie suchen, und es wird Ihnen ermöglichen, effizient die Existenz von Wörtern einzufügen und zu überprüfen, während Sie die natürliche Reihenfolge beibehalten.

In diesem Forumsbeitrag können Sie eine Implementierung eines Trie sehen, damit Sie das Rad nicht neu erfinden müssen.

https://community.oracle.com/thread/2070706

Fazit:

• I kümmern sich nicht um eine bestimmte Reihenfolge beibehalten: Verwenden Sie ein HashSet
• meinetwegen ein, die Worte in alphabetischer Reihenfolge über die Erhaltung und ich möchte ein einfache Lösung, auch wenn es nicht die effizienteste ist: Verwenden Sie eine TreeMap
• Ich muss alphabetisch Reihenfolge und Leistung ist entscheidend wichtig: Verwenden Sie eine Trie.