java - 高效的排序功能

Question

对于我正在开发的 Java 项目，我需要创建一个排序方法，该方法使用映射函数对列表进行排序。最明显的解决方案是使用内置的 Collections.sort() 方法:

static <D, R extends Comparable> void sortBy(List<D> list, Function<D, R> function) {
    Collections.sort(list, new Comparator<D>() {
        @Override
        public int compare(D d1, D d2) {
            return function.apply(d1).compareTo(function.apply(d2));
        }
    });
}

问题是这会多次调用每个元素上的函数(我认为是 2 log N)。此外，该函数可能很慢，每次调用至少需要几毫秒，甚至可能更长。我想要一种更有效的算法，它调用该函数的次数尽可能少。

我考虑过在开始时应用每个函数，然后对映射列表进行排序，但我不知道如何返回原始列表:

static <D, R extends Comparable> void sortBy(List<D> list, Function<D, R> function) {
    List<R> newList = new ArrayList<>();
    for (D d : list){
        newList.add(function.apply(d));
    }
    Collections.sort(newList);

    // now what?
}

(请注意，该函数是纯函数，即每个输入产生相同的输出，没有副作用。)

Answer 1

正如评论中所建议的，您可以对某种元组的列表进行排序，该元组将保存原始值和计算值。然后，通过按排序顺序提取原始值来构建一个新列表。该解决方案创建临时对象(元组)，但如果映射函数昂贵，则应该是高效的。当然，这需要衡量...

static <D, R extends Comparable> List<D> sortBy(List<D> list, Function<D, R> function) {
    // Build the list of pairs
    List<Pair<D,R>> newList = list.stream()
            .map(d -> new Pair<>(d, function.apply(d)))
            .collect(Collectors.toList());

    // Sort the list of pairs on second member, which is the computed one
    Collections.sort(newList, new Comparator<Pair<D,R>>() {
        @Override
        public int compare(Pair<D, R> p1, Pair<D, R> p2) {
            return p1.second.compareTo(p2.second);
        }
    });

    // extract the first member of pair, which is the original value 
    return newList.stream().map(p -> p.first).collect(Collectors.toList());
}

给定一个简单的类 Pair<U, V>像:

public final class Pair<U,V> {
   public final U first;
   public final V second;
   public Pair(U u, V v) {
      this.first = u;
      this.second = v;
   }
   public String toString() {
      return "["+first+","+second+"]";
   }
}

然后:

List<String> data = Arrays.asList("blah", "foo", "bar", "hello world", "bye bye", "fizz", "buzz");

List<String> sortedDataByLength = sortBy(data, new Function<String, Integer>() {
    @Override
    public Integer apply(String t) {
        return t.length();
    }});
System.out.println(sortedDataByLength);

产量:

[foo, bar, blah, fizz, buzz, bye bye, hello world]