wie suche schneller von contactList für gegeben string

Question

Ich habe ContactList, die Kontakte mit firstName und lastName enthält. Ich möchte die Suche nach Vorname oder Nachname ausführen.

Ich habe bereits Code geschrieben, der gut funktioniert, aber ich möchte die Suche in Bezug auf Geschwindigkeit und Speicher verbessern.

public class Contact implements Comparable<Contact> { 

    private String firstName; 
    private String lastName; 
    private String name; 

    public Contact(String name) { 

     this.name = name; 
     if (name.contains(" ")) { 
      this.firstName = name.split("\\s+")[0]; 
      this.lastName = name.split("\\s+")[1]; 
     } else { 
      this.firstName = name; 
      this.lastName = ""; 
     } 
    } 

    public String getFirstName() { 
     return firstName; 
    } 

    public String getLastName() { 
     return lastName; 
    } 

    public String getName() { 
     return name; 
    } 

    @Override 
    public String toString() { 
     return "Contact{" + name + '}'; 
    } 

    @Override 
    public int compareTo(Contact contact) { 
     System.out.println("in compareto"); 
     return this.name.compareToIgnoreCase(contact.getName()); 
    } 
@Override 
public int hashCode() { 
    return (firstName.hashCode() * (lastName != null ? lastName.hashCode() : 0)); 
} 

@Override 
public boolean equals(Object obj) { 
    if(obj == null) 
     return false; 
    if(!(obj instanceof Contact)) 
     return false; 

    Contact other = (Contact) obj; 
    if(! this.name.equalsIgnoreCase(other.name)) return false; 

    return true; 
} 
    } 

public class ContactService { 

    private Set<Contact> contacts; 

    public ContactService() { 
     this.contacts = new TreeSet<>(); 
    } 

    public void addContact(String name) { 
     Contact contact = new Contact(name); 
     contacts.add(contact); 
    } 

    public void searchContact(String searchStr) { 
     System.out.println(contacts); 
     for (Contact contact : contacts) { 
      if (contact.getName().equalsIgnoreCase(searchStr)||(searchStr.contains(" ") && contact.getName().contains(searchStr))) { 
       System.out.println(contact.getName()); 
      } else if (contact.getFirstName().toLowerCase().startsWith(searchStr) || contact.getLastName().toLowerCase().startsWith(searchStr)) { 
       System.out.println(contact.getName()); 
      } 
     } 
    } 
} 

Bitte schlagen Sie vor, wie Sie die Leistung in obigem Code verbessern können.

Answer 1

Sie können eine java.util.HashMap verwenden, um eine Nachschlagetabelle für Kontakte für Suchbegriffe zu speichern.

Die Idee besteht darin, die Nachschlagetabelle mit wahrscheinlichen Suchbegriffen (z.B. dem Vornamen oder den ersten drei Buchstaben des Namens) zu füllen. Wenn Ihre Suche keine Treffer liefert, können Sie immer eine vollständige Suche durchführen. Wenn Sie eine leistungsfähigere Suche wünschen, können Sie sich etwas wie Apache Lucene ansehen.

z.

Map<String, Set<Contact>> contactLookup = new HashMap<>(); 

Dann würden Sie beginnen, indem Sie den Suchbegriff in der Karte nachschlagen. Dies würde die Möglichkeiten auf eine kleine Menge eingrenzen, die Sie mit der gleichen Methode, die Sie oben verwenden, durchlaufen können.

Sie könnten auch auf die Multimap von Guava, die die gleiche Funktionalität bietet eleganter.

---

Durch die Art und Weise (auf einer nicht verwandte Anmerkung), wenn Sie die compareTo() Methode überschreiben, ist es empfehlenswert, auch equals() außer Kraft setzen, so dass (x.compareTo(y)==0) == (x.equals(y)). Wenn Sie equals() außer Kraft setzen, müssen Sie auch hashCode() überschreiben!

Answer 2

Ich habe vordefinierte search nicht, ist meine Anforderung wie Benutzer eingegeben Kontakte wie „Manoj Pathak“, „Manoj“. Wenn Benutzertyp „Man“ und Treffer Such dann führt Manoj Pathak Manoj sein, wenn Benutzertyp „Manoj“ und auf Suche klicken dann wird zur Folge haben Manoj (genaue Übereinstimmung) Manoj Pathak“

In diesem Fall werde ich vorschlagen, implementieren Sie Längste Präfix-Matching - Eine Trie basierte Lösung in Java die intern HashMap verwenden wird