Erste N-Werte einer Karte <K, V> sortiert nach Wert

Question

Ich habe eine Liste von Strings. Ich möchte jede Zeichenfolge basierend auf einer Funktion, die ein Double zurückgibt, auswerten. Dann möchte ich die ersten 5 Strings, basierend auf ihren berechneten Werten. Wenn es weniger als 5 gibt, möchte ich alle (in der Reihenfolge). Nehmen wir an, die Strings sind chemische Verbindungen und die Funktion berechnet die Masse. Die Funktion ist rechenintensiv; Ich muss es einmal pro String auswerten. (Ich bin hier nur Daten bilden, though.)

H2O => 18.5 
C12H11O22 => 109.1 
HeNe => 32.0 
H2SO4 => 54.37 
HCl => 19.11 
4FeO3 => 82.39 
Xe6 => 281.9 

Das Programm sollte die ersten fünf Saiten, um durch ihre jeweiligen Werte angeordnet zurückzukehren. Für diese Beispieldaten: H20, HCl, HeNe, H2SO4, 4FeO3. Eigentlich interessiert mich die Bestellung nicht wirklich; Ich brauche nur die fünf niedrigsten in beliebiger Reihenfolge.

Ich dachte darüber nach, wie ich das in Perl machen würde. Es sind nur ein paar Zeilen:

foreach $s (@str) { 
    $strmap{$s} = f($s); 
} 
@sorted = sort { $strmap{$a} <=> $strmap{$b} } keys %strmap; 
return @sorted[0, 4] 

Aber ich muss es in Java tun. Und es macht mich verrückt.

Zuerst habe ich versucht, eine HashMap<String, Double> zu füllen, dann mit einem benutzerdefinierten Komparator, genau wie die Perl-Version. Durch die Festlegung des Komparators wurde jedoch verhindert, dass die HashMap verwendet wurde, um die Werte abzurufen.

Dann versuchte ich eine TreeMap<String, Double>, aber es sortiert nur nach Schlüssel und kein Betrag der Zwangsführung könnte es bekommen, um die Einträge nach Wert zu ordnen.

Also versuchte ich eine TreeMap<Double, String>. Es wird Einträge mit demselben Double verwerfen. Allerdings ist die Wahrscheinlichkeit, dass Strings die gleiche Double-Map haben, gering, also habe ich weitergedrückt. Das Hinzufügen der Einträge zur TreeMap ist kein Problem, aber ich stieß auf Probleme, die versuchen, die Werte daraus zu extrahieren.

TreeMap stellt eine Methode namens subMap bereit, die Parameter sind jedoch die Schlüssel, die die Teilmenge begrenzen. Ich weiß nicht, was sie sind; Ich will nur die ersten fünf von ihnen. Also habe ich versucht, die values Methode zu verwenden, um alle Werte aus der TreeMap zu bekommen, in der Hoffnung, dass sie in Ordnung sind. Dann kann ich nur die ersten zehn bekommen.

ArrayList<String> strs = (ArrayList<String>)(treemap.values()); 
return new ArrayList<String>(strs.subList(0, 5)); 

Nein. Laufzeitfehler: TreeMap $ Values ​​kann nicht in ArrayList umgewandelt werden.

List<String> strs = (List<String>)(treemap.values()); 
return new ArrayList<String>(strs.subList(0, 5)); 

Gleich. Laufzeitfehler, der versucht, die Besetzung zu tun. OK, lassen Sie uns einfach auf eine Sammlung zuweisen ...

Collection<String> strs = treemap.values(); 
return new ArrayList<String>(strs.subList(0, 5)); 

Sorry, subList keine Methode Collection enthalten ist.

Collection<String> strs = treemap.values(); 
ArrayList<String> a = new ArrayList<String>(strs); 
return new ArrayList<String>(a.subList(0, 5)); 

Endlich etwas, das funktioniert! Aber zwei zusätzliche Datenstrukturen, nur um die ersten fünf Elemente zu bekommen? Und ich bin nicht zu wild, Double als Schlüssel für TreeMap zu verwenden.

Gibt es eine bessere Lösung?

Answer 1

Ich glaube nicht, dass Sie kompakter werden als die drei Zeilen oben, nicht in Java.

Abgesehen davon, habe ich den Eindruck, dass eine Map als Datenstruktur in erster Linie die falsche Wahl ist, da Sie keine By-String-Lookups zu brauchen (wenn Sie in irgendeiner Weise mit mehreren Vorkommen von Streichern, aber du hast es nicht gesagt). Ein alternativer Ansatz wäre eine eigene vergleichbaren Datensatz Klasse zu deklarieren:

private static class Record implements Comparable<Record> { 
    // public final fields ok for this small example 
    public final String string; 
    public final double value; 

    public Record(String string, double value) { 
     this.string = string; 
     this.value = value; 
    } 

    @Override 
    public int compareTo(Record other) { 
     // define sorting according to double fields 
     return Double.compare(value, other.value); 
    } 
} 

// provide size to avoid reallocations 
List<Record> records = new ArrayList<Record>(stringList.size()); 
for(String s : stringList) 
    records.add(new Record(s, calculateFitness(s)); 
Collections.sort(records); // sort according to compareTo method 
int max = Math.min(10, records.size()); // maximum index 
List<String> result = new ArrayList<String>(max); 
for(int i = 0; i < max; i++) 
    result.add(records.get(i).string); 
return result; 

Dies als jetzt viel ausführlicher ist die drei Zeilen weiter oben (dies ist Java, nachdem alle), sondern auch den Code, der erforderlich wäre, Einfügen der Schlüssel/Wert-Paare in die Karte.

Answer 2

Würde so etwas wie das Folgende für Sie arbeiten?

Beachten Sie, dass ich angenommen habe, dass Sie nicht den doppelten Wert benötigen, außer die Daten zu sortieren.

public static void main(String[] args) throws Exception { 
    List<String> data = new ArrayList<>(Arrays.asList("t", "h", "i", "s", "i", "s", "t", "e", "s", "t", "d", "a", "t", "a")); 

    Collections.sort(data, new Comparator<String>() { 
    @Override 
    public int compare(String o1, String o2) { 
     double o1Value = evaluate(o1); 
     double o2Value = evaluate(o2); 
     return Double.compare(o1Value, o2Value); 
    } 
    }); 

    List<String> result = data.subList(0, 10); // Note the end point is exclusive 

    for (String s : result) { 
    System.out.println(s); 
    } 
} 

private static double evaluate(String s) { 
    return s.codePointAt(0); // Nonsense, I know 
} 

Dieses Beispiel druckt:

a 
a 
d 
e 
h 
i 
i 
s 
s 
s 

Answer 3

Warum gehst du nicht einfach eine Klasse erstellen, die String, Double und Funktion zu kombinieren, die die Berechnung tut - so etwas wie:

public Thing implements Comparable<Thing> 
{ 
    private String s; 
    private Double d; 

    public Thing(String s) 
    { 
    this.s = s; 
    this.d = calculateDouble(s); 
    } 

    public String getString() 
    { 
    return this.s; 
    } 

    public Double getDouble() 
    { 
    return this.d; 
    } 

    public int compareTo(Thing other) 
    { 
    return getDouble().compareTo(other.getDouble()); 
    } 

    public Double calculateDouble(String s) 
    { 
    ... 
    } 
} 

Dann brauchen Sie nur noch List<Thing>, Collections.sort und List.subList.