First N map values ​​<K, V> sorted by value

Question

I have a list of strings. I want to evaluate each row based on a function that returns double. Then I want the first 5 rows to be based on their calculated values. If there are less than 5 of them, I want them all (in order). Let them say that the strings are chemical compounds, and the function calculates the mass. The function is computationally expensive; I need to evaluate it once per line. (I'm just compiling the data here.)

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

The program should return the first five lines sorted by their respective values. For this sample data: H20, HCl, HeNe, H2SO4, 4FeO3 . In fact, I don't really care about the order; I just need the five smallest in any order.

I thought about how to do this in Perl. These are just a few lines:

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

But I need to do this in Java. And it drives me crazy.

First I tried to populate the HashMap<String, Double> , and then using Collections.sort using a special comparator, like the Perl version. But looking at the comparator prevented him from accessing the HashMap for values.

Then I tried TreeMap<String, Double> , but it only sorts by key, and no amount of coercion can force it to sort the records by value.

So, I tried TreeMap<Double, String> . It will discard entries with the same Double. However, the probability of having strings that map to the same Double is low, so I pushed forward. Adding entries to TreeMap is not a problem, but I ran into problems trying to extract values ​​from it.

TreeMap provides a method called subMap , but its parameters are keys that limit the subset. I do not know what it is; I just need the first five of them. So I tried using the values method to get all the values ​​from TreeMap, hoping that they would be fine. Then I can just get the top ten.

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

Nope. Runtime error: Unable to pass TreeMap $ values ​​to ArrayList.

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

Same. Runtime error trying to translate. Ok, just assign a collection ...

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

Sorry, subList not a collection method.

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

Finally, that works! But two additional data structures to get the first five elements? And I'm not too alone in using Double as a key for TreeMap.

Is there a better solution?

Answer 1

I do not think that you will get more compact than the three lines above, and not in Java.

In addition, I got the impression that Map as a data structure is the wrong choice in the first place, since you don't seem to need subscript searches (if you want to somehow deal with multiple occurrences of lines, but you don’t they said). An alternative approach would be to declare your own comparable data class:

 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; 

Now this is much more verbose than the three lines above (after all, this is Java), but it also includes code that would insert key / value pairs into the map.

Answer 2

Will there be something like the following work for you?

Note that I suggested that you do not need a double value other than sorting the data.

 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 } 

This example prints:

 a a d e h i i s s s 

Answer 3

Why don't you just create a class to combine String , Double and the function that performs the calculations - something like:

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

Then you need List<Thing> , Collections.sort and List.subList .