Map<K, V>按值排序的前N个值

Question

我有一个字符串列表。我想基于一个返回双精度浮点数的函数来评估每个字符串。然后，我想根据它们计算出的值，获取前5个字符串。如果少于5个，则按顺序获取所有字符串。假设这些字符串是化合物，函数计算它们的质量。该函数的计算成本很高；我需要对每个字符串仅评估一次。（这里只是举例子，数据是虚构的。）

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

该程序应该按其各自值的顺序返回前五个字符串。对于这个示例数据：H20，HCl，HeNe，H2SO4，4FeO3。 实际上，我并不关心顺序； 我只需要任意顺序的最低的五个。

我思考了如何在Perl中完成这项任务。它只需要几行代码：

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

但我需要用Java来实现，这真的让我感到疯狂。

首先我尝试通过填充一个 HashMap<String, Double> ，然后使用具有自定义比较器的 Collections.sort 来排序，就像Perl版本一样。但是，比较器上的作用域阻止它引用 HashMap 来查找值。

然后我尝试了一个 TreeMap<String, Double>，但它只按键排序，无论如何强制都不能按值对条目进行排序。

所以我尝试了一个 TreeMap<Double, String>。它会丢弃相同Double的条目。然而，映射到相同Double的字符串的可能性很低，所以我继续前进。将条目添加到 TreeMap 中没有问题，但是我在从中提取值时遇到了问题。

TreeMap 提供了一个名为 subMap 的方法，但其参数是限定子集的键。我不知道它们是什么；我只想要前五个。所以我尝试使用 values 方法将所有值从 TreeMap 中取出，希望它们按顺序排列。然后我可以只获取前十个。

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

不行。运行时错误：无法将TreeMap$Values转换为ArrayList。

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

一样。在尝试强制转换时发生运行时错误。好的，让我们将其分配给一个集合...

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

抱歉，subList 不是 Collection 的一个方法。

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

终于有东西能用了！但是为了获取前五个元素需要两个额外的数据结构吗？我也不太喜欢使用Double作为TreeMap的键。

有更好的解决方案吗？

- Barry Brown

---

请您提供一些样例以更好地理解问题。 - asifsid88

示例数据？还是我尝试过的代码示例？ - Barry Brown

通过样本数据，我指的是给定一组输入，预期输出是什么。 - asifsid88

现在包含示例数据。 - Barry Brown

Answer 1

我认为在Java中不可能有比上面三行代码更紧凑的了。

除此之外，我觉得作为数据结构的Map可能是个错误的选择，因为你似乎不需要通过字符串查找（除非你想以某种方式处理多个字符串出现的情况，但是你没有说明）。另一种方法是声明自己的可比较数据记录类：

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;

现在这段代码比前面三行更冗长了（毕竟这是Java），但也包括将键/值对插入到映射中所需的代码。

- misberner

Answer 2

你是否希望以下内容对你有效？

请注意，我假设您除了对数据进行排序之外，并不需要双倍值。

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
}

这个例子输出：

a
a
d
e
h
i
i
s
s
s

- Duncan Jones

---

请注意，这种方法执行的evaluate()调用比必要的多得多（如果调用此函数很便宜或性能根本不重要，则可能完全没有问题）。还要注意，subList()返回的列表由原始列表支持，因此在维护对result的引用时，data的内容不能被垃圾回收。 - misberner

@polkageist 是的，说得好。后者很容易解决。前者是一个设计选择 - 如果 evaluate() 很昂贵，那么添加一个单独的类（就像您的示例中一样）的努力可能是值得的。 - Duncan Jones

Answer 3

为什么不创建一个类来组合 String、Double 和执行计算的函数，就像这样：

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

然后你所需要的就是一个 List<Thing>，Collections.sort 和 List.subList。

- Nick Holt