java - 为什么 Point 的 Set.contains() 比大小为 2 的 List 快得多？

Question

我最近需要对一组整数对进行多次查找，以解决编程竞赛中的问题。我用 Java 编程。通常我会使用数组来表示整数对，但是因为 Java 中的集合不适用于数组，所以这次我决定使用列表。后来我发现我的解决方案很慢，但另一个参赛者的解决方案使用 Point 相反要快得多。

我实现了一个小型基准来比较两者。我发现 Set.contains()在 Set<List<Integer>> 上(其中每个 List<Integer> 的大小为 2)平均比 Set<Point> 慢 4.5 倍。 ，无论该对是否实际包含在集合中。我认为原因可能源于 hashCode() 的不同实现。并另外实现了自定义 Point使用 List.hashCode() 的类.这似乎是部分原因，但与实际的不同 List<Integer>还是很可观的。

这是我的基准代码:

import java.awt.Point;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Random;
import java.util.Set;

public class IntPairTiming {

    public static final int SIZE = 1_000_000;
    public static final int TRIES = 100_000_000;

    public static void main(String[] args) {

        Random random = new Random();

        // Pairs to store
        Set<Point> pointSet = new HashSet<>();
        Set<List<Integer>> listSet = new HashSet<>();
        Set<MyPoint> myPointSet = new HashSet<>();
        for (int i = 0; i < SIZE; i++) {
            Point point = new Point(random.nextInt(), random.nextInt());
            pointSet.add(point);
            List<Integer> list = Arrays.asList(point.x, point.y);
            listSet.add(list);
            myPointSet.add(new MyPoint(point.x, point.y, list));
        }

        // Pair to lookup
        Point point = new Point(random.nextInt(), random.nextInt());
        List<Integer> list = Arrays.asList(point.x, point.y);
        MyPoint myPoint = new MyPoint(point.x, point.y, list);
        pointSet.add(point);
        listSet.add(list);
        myPointSet.add(myPoint);

        // Time set of points
        timeLookup(pointSet, point, "Set of Points");

        // Time set of lists
        timeLookup(listSet, list, "Set of Lists");

        // Time set of mypoints
        timeLookup(myPointSet, myPoint, "Set of MyPoints");
    }

    private static <T> void timeLookup(Set<T> set, T obj, String what) {
        System.out.println("-----------");
        System.out.printf("%s:%n", what);
        System.out.printf("Contains = %s%n", set.contains(obj));
        long s = System.nanoTime();
        for (int i = 0; i < TRIES; i++) set.contains(obj);
        long e = System.nanoTime();
        System.out.printf("Average lookup = %sns%n", (e - s) / TRIES);
    }

    private static class MyPoint extends Point {

        private final List<Integer> list;

        public MyPoint(int x, int y, List<Integer> list) {
            super(x, y);
            this.list = list;
        }

        @Override
        public int hashCode() {
            return this.list.hashCode();
        }
    }
}

输出:

-----------
Set of Points:
Contains = true
Average lookup = 12ns
-----------
Set of Lists:
Contains = true
Average lookup = 55ns
-----------
Set of MyPoints:
Contains = true
Average lookup = 25ns

为什么会有如此明显的差异？据我了解，hashCode()和 equals()应该或多或少地在 Point 上执行相同的操作和一个 List<Integer>大小为 2 的。如果我们需要查找两个以上元素的元组，将类似于 Point 的自定义类怎么办？总是比列表更有效？

Answer 1

这是基于 expense for equals() on any sort of AbstractList 的事实比人们想象的要大。

实现需要构造一个迭代器，迭代它，并比较所有元素(hashCode 也需要)，而专用的 Point 类有两个比较JIT 非常容易对其进行优化(由于字段偏移量变化不大)，而列表需要更多的间接访问。

当您的字段数达到十位时(没有双关语意)，创建一个单独的元组类成为过早的优化，除非该元组类本身有一些用作 POJO 的作用。