Ändern Komplexität von O (n) bis O (log n)

Question

Wir haben eine LinkedList ratings genannt, die drei ganze Zahlen enthält userId, ItemId und Wert der aktuellen Bewertung (zB von 0 bis 10) diese Methode tatsächlich Bewertung von User-i und j Artikel, dass die Programme liest sie aus einer Datei und -1, wenn keine Bewertung

die Methode, die BigOh (n):

public int getRating(int i, int j){ 
    ratings.findFirst(); 
    while(!ratings.empty()){ 
     if(ratings.retrieve().getUserId() == i && ratings.retrieve().getItemId() == j) 
      return ratings.retrieve().getValue(); 
     else 
      ratings.findNext(); 
    } 
    return -1; 
} 

Wie kann ich dies tun in BigOh (logn)?
Oder ist es sowieso ich kann es mithilfe der binären Suche Baum lösen?

Answer 1

Sie können Hashing verwenden, um Ihre Aufgabe in O (1) zu erreichen. Bitte lesen Sie diese article, um ein tieferes Verständnis über Hashing zu erhalten.

Da Sie Java verwenden, können Sie HashMap verwenden, um Ihre Aufgabe zu erfüllen. Man beachte, dass die Zeitkomplexität im ungünstigsten Fall für die hashing Technik O (log n) ist, aber im Durchschnitt ist es O (1). Wenn Sie mehr über Hashtabellen und amortisierte Analysen erfahren möchten, gehen Sie bitte durch diese article.

Codebeispiel: Sie können einen Class mit den erforderlichen Attributen erstellen und equals und hashCode Verfahren wie folgt implementieren. [Lesen Java collections - hashCode() and equals()]

class Rating { 

    public int user_id; // id of the user who rated 
    public int item_id; // id of the item being rated 

    public Rating(int user_id, int item_id) { 
     this.user_id = user_id; 
     this.item_id = item_id; 
    } 

    @Override 
    public boolean equals(Object o) { 
     if (o == this) { 
      return true; 
     } 
     if (!(o instanceof Rating)) { 
      return false; 
     } 
     Rating ratingObj = (Rating) o; 
     return ratingObj.user_id == user_id 
       && ratingObj.item_id == item_id; 
    } 

    @Override 
    public int hashCode() { 
     int result = 17; 
     result = 31 * result + user_id; 
     result = 31 * result + item_id; 
     return result; 
    } 
} 

Dann speichern Werte in HashMap wie folgt:

public static void main(String[] args) { 
    HashMap<Rating, Integer> ratingMap = new HashMap<>(); 
    Rating rt = new Rating(1, 5); // user id = 1, item id = 5 
    ratingMap.put(rt, 3); 
    rt = new Rating(1, 2); // user id = 1, item id = 2 
    ratingMap.put(rt, 4); 
    rt = new Rating(1, 3); // user id = 1, item id = 3 
    ratingMap.put(rt, 5); 

    // now search in HashMap 
    System.out.println(ratingMap.get(new Rating(1, 3))); // prints 5 
} 

Answer 2

Wie dargestellt, das kaum in O (log n) durchgeführt werden konnte. Sie schauen durch die Elemente, bis Sie die gewünschte gefunden haben. Im schlimmsten Fall werden Sie das gewünschte Element bis zum Ende der Schleife nicht finden und somit O (n) machen.

Natürlich, wenn ratings ein Wörterbuch wäre, würden Sie den Wert in fast O (1) abrufen: Benutzer-IDs als Schlüssel und zum Beispiel eine Liste von Bewertungen als Wert. Die Einfügung wäre etwas langsamer, aber nicht viel.

Answer 3

Die kurze Antwort lautet: Verwenden Sie eine andere Datenstruktur. Verkettete Listen sind nicht in der Lage, Suchen in irgendetwas als lineare Zeit, da jedes Element ohne echten Schein oder Reihenfolge miteinander verbunden ist (und sogar wenn die Liste sortiert wäre, müssten Sie immer noch tun einige andere Art der zeitgesteuerten Traversierung). Eine Datenstruktur, die Sie verwenden könnten, wäre eine Table von Guava. Mit dieser Datenstruktur, würden Sie mehr Arbeit zu hinzufügen ein Element in zu tun haben ...

Table<Integer, Integer, Rating> ratings = HashBasedTable.create(); 
ratings.put(rating.getUserId(), rating.getItemId(), rating); 

... aber man kann sehr schnell abrufen - in etwa O (1) Zeit seit HashBasedTable wird von LinkedHashSet<Integer, LinkedHashSet<Integer, Rating>> unterstützt.

ratings.get(i, j);