比较器工作的效率

Question

比较器工作的效率

6

我正在尝试使用比较器来帮助排序对象列表。我对比较器的工作原理和以下示例中它将要做什么有疑问：

private static Comparator<Student> comparator()
{
        return (Student a, Student b) ->
        {  
                return Integer.compare(complexOperation(a), complexOperation(b));
        }
}

如您所见，需要根据 complexOperation() 方法返回的整数排名来比较和排序学生。正如其名称所示，这是一个繁重的操作。上述方法是否最有效？或者最好基本上通过遍历要排序的列表中的每个学生，对每个学生执行 complexOperation() 并将结果存储在 Student 对象的字段中。然后比较器会执行：

Integer.compare(a.getRank(), b.getRank())

这两种方法是否可以相互比较，或者由于比较器的工作方式（可能会多次将同一对象与其他对象进行比较，因此在比较期间每个学生都会运行complexOperation()多次），在学生字段中进行complexOperation()结果的预计算是否更快？

以上代码可以按如下方式调用：

Collections.sort(students, comparator());

希望这很清楚！编辑：假设为了简便，无法向学生对象添加字段（这是一个玩具问题，真正的情况更加复杂，我没有权利修改学生对象）。是否仍然最好创建一个自定义对象，其中包含一个带有另一个字段的学生，而不是在比较器中直接执行复杂操作（complexOperation()）？或者还有其他方法来解决这个问题吗？我可以想到创建一个Hashmap，以学生ID作为键，以复杂操作（complexOperation()）的结果作为值，并在比较器中创建/访问该记录。

- John Baum

@HovercraftFullOfEels 我特别使用比较器作为排序机制，并希望它尽可能地高效。 - John Baum

（可能将同一对象与其他对象多次比较，因此在比较期间每个学生都会运行complexOperation()多次） - 添加一个System.out.println(...)语句到比较器中，以查看它被调用的频率。或者添加一种计数器，在比较器完成后进行显示。如果调用次数大于要排序的元素，则知道复杂操作被调用了超过一次。这是一种基本的问题解决技巧，可以显示一些输出。 - camickr

你现在正在询问JVM的优化工作方式，如果它确定这样做可以使事情更有效地运行，它通常会为您执行此类操作。 - Hovercraft Full Of Eels

2个回答

5

平均而言，对于一个包含N个学生的数组，您的排序算法将大约调用 log2N 次 complexOperation() 方法。如果该操作非常缓慢，您最好为每个学生单独运行它。这可以使 1,000 名学生的数组的性能提高一个数量级。

然而，您不必显式地执行此操作：您可以使 complexOperation(...) 存储每个学生的结果，然后在后续请求中返回缓存值。

private Map<Student,Integer> cache = new HashMap<Student,Integer>();

private int complexOperation(Student s) {
    // See if we computed the rank of the student before
    Integer res = cache.get(s);
    if (res != null) {
        // We did! Just return the stored result:
        return res.intValue();
    }
    ... // do the real computation here
    // Save the result for future invocations
    cache.put(s, result);
    return result;
}

请注意，为了使这种方法起作用，Student类需要实现hashCode和equals方法。

- Sergey Kalinichenko

@bayou.io 清除缓存必须通过明确的方式或者通过丢弃拥有缓存的对象来完成。 - Sergey Kalinichenko

comparator() 方法的用户可能不想被那个细节所困扰 :) - ZhongYu

@JohnBaum 是的，最好制作一个带有额外int字段的“持有者”，特别是对于大量学生的情况，其中调用次数增加了十倍或更多。与潜在的CPU节省相比，对象开销代表了微不足道的成本。 - Sergey Kalinichenko

@JohnBaum，这与我上面提出的建议非常类似，只不过您使用学生ID作为键，而我直接使用Student，而不提取其ID（在底层，equal和hashCode可能完全依赖于ID）。除此之外，这两种方法是相同的。 - Sergey Kalinichenko

FYI，这都是理论上的，缓存确实可以提高性能，但会增加代码的复杂性，所以除非你真正有性能问题，否则不要费心。这就是关于不要在没有问题之前调整代码的老话，因为你可能会把时间浪费在错误的问题上，这样你就没有时间去找到和解决真正的问题了，如果你真的有问题的话。请参见过早优化。 - Andreas

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- ZhongYu · Accepted Answer

基本上，您想通过比较每个学生映射到的一些值来比较学生。通常是通过以下方式实现的：

    static Comparator<Student> comparator()
    {
        return Comparator.comparing( Foo::complexOperation );
    }

然而，由于 complexOperation 函数过于耗时，我们希望缓存其结果。我们可以使用一个通用的实用方法 Function cache(Function)。

    static Comparator<Student> comparator()
    {
        return Comparator.comparing( cache(Foo::complexOperation) );
    }

通常情况下，最好由调用者提供Map作为缓存。

public static <K,V> Function<K,V> cache(Function<K,V> f, Map<K,V> cache)
{
    return k->cache.computeIfAbsent(k, f);
}

我们可以将 IdentityHashMap 用作默认缓存。

public static <K,V> Function<K,V> cache(Function<K,V> f)
{
    return cache(f, new IdentityHashMap<>());
}