6

我有一个字符串列表。我想根据返回双精度的函数来评估每个字符串。然后我想要前 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来做。它让我发疯。

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

然后我尝试了 a 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<String> strs = treemap.values();
ArrayList<String> a = new ArrayList<String>(strs);
return new ArrayList<String>(a.subList(0,  5));

最后，一些有效的东西！但是两个额外的数据结构只是为了获得前五个元素？而且我不太喜欢使用 Double 作为 TreeMap 的键。

有更好的解决方案吗？

4

3 回答 3

3

我认为你不会比上面的三行更紧凑，不是在 Java 中。

除此之外，我的印象是 aMap作为数据结构首先是错误的选择，因为您似乎不需要按字符串查找（除非您希望以某种方式处理多次出现的字符串，但是您没说）。另一种方法是声明您自己的可比较数据记录类：

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），但还包括将键/值对插入映射所需的代码。

于 2013-04-30T09:59:19.377 回答
1

以下内容对您有用吗？

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

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
于 2013-04-30T09:57:38.347 回答
0

你为什么不创建一个类来组合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。

于 2013-04-30T09:57:41.127 回答