Pierwsze wartości N mapy <K, V> posortowane według wartości

Question

Mam listę ciągów znaków. Chcę ocenić każdy ciąg na podstawie funkcji zwracającej podwójne. Następnie chcę pierwszych 5 ciągów, na podstawie ich obliczonych wartości. Jeśli jest ich mniej niż 5, chcę je wszystkie (w kolejności). Powiedzmy, że łańcuchy są związkami chemicznymi, a funkcja oblicza masę. Funkcja jest kosztowna pod względem obliczeniowym; Muszę to ocenić raz na ciąg. (Ja tylko tworzących dane tutaj, choć.)

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

Program powinien powrócić pierwsze pięć strun ułożone w kolejności według ich wartości. Dla tych przykładowych danych: H20, HCl, HeNe, H2SO4, 4FeO3. Właściwie to nie zależy mi na zamówieniu; Potrzebuję tylko pięciu najniższych w dowolnej kolejności.

Zastanowiłem się, jak to zrobić w Perlu. To tylko kilka linii:

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

Ale muszę to zrobić w Javie. I doprowadza mnie to do szału.

Najpierw próbowałem zapełnić HashMap<String, Double>, a następnie użyć Collections.sort z niestandardowym komparatorem, tak jak wersja Perla. Jednak ustalenie zakresu na Komparatorze uniemożliwiło mu odwołanie się do HashMap w celu sprawdzenia wartości.

Potem próbowałem TreeMap<String, Double>, ale sortuje się tylko według klucza i żadna ilość wymuszenia nie może go zmusić do uporządkowania wpisów według wartości.

Próbowałem więc TreeMap<Double, String>. Odrzuci wpisy z tym samym Double. Jednak prawdopodobieństwo posiadania Strings, które mapują do tego samego Double jest niska, więc naciskałem do przodu. Dodanie wpisów do TreeMap nie stanowi problemu, ale napotkałem problemy próbujące wyodrębnić z niego wartości.

TreeMap dostarcza metodę o nazwie subMap, ale jej parametry są kluczami ograniczającymi podzbiór. Nie wiem, czym one są; Chcę tylko pierwszych pięciu z nich. Próbowałem więc użyć metody values, aby uzyskać wszystkie wartości z TreeMap, mając nadzieję, że będą w porządku. Wtedy mogę dostać pierwszą dziesiątkę.

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

Nie. Runtime error: nie można przesłać TreeMap $ Values ​​do ArrayList.

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

To samo. Wystąpił błąd podczas wykonywania rzutowania. OK, niech po prostu przypisać do kolekcji ...

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

Niestety, subList nie jest metodą Collection.

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

Wreszcie coś, co działa! Ale dwie dodatkowe struktury danych tylko po to, by zdobyć pierwsze pięć elementów? I nie jestem za bardzo szalony, że używam Double jako klucza do TreeMap.

Czy istnieje lepsze rozwiązanie?

Answer 1

Nie sądzę, że uzyskasz bardziej kompaktowy niż trzy powyższe linie, a nie Java.

Poza tym mam wrażenie, że Map jako struktura danych jest złym wyborem, ponieważ wydaje się, że nie potrzebujesz wyszukiwań ciągłych (BEZ WZGLĘDÓW, że chcesz w jakiś sposób radzić sobie z wieloma wystąpieniami strun, ale tego nie powiedziałeś). Alternatywnym rozwiązaniem byłoby zadeklarować własną porównywalnej klasy rekord danych:

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; 

To jest teraz dużo bardziej gadatliwy niż trzech liniach powyżej (to jest Java, po wszystkim), ale również zawiera kod, który byłby wymagany aby wstawić pary klucz/wartość do mapy.

Answer 2

Czy jest coś takiego dla Ciebie?

Zauważ, że założyłem, że nie potrzebujesz podwójnej wartości poza sortowaniem danych.

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 
} 

Ten przykład druki:

a 
a 
d 
e 
h 
i 
i 
s 
s 
s 

Answer 3

Dlaczego nie można po prostu utworzyć klasę połączyć String, Double i funkcji, które wykonuje obliczenia - coś jak:

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) 
    { 
    ... 
    } 
} 

Wszystko czego potrzebujesz to: List<Thing>, Collections.sort i List.subList.