首页 文章

为什么处理排序数组*比未排序数组慢? (Java的ArrayList.indexOf)

提问于
浏览
78

Headers 是参考Why is it faster to process a sorted array than an unsorted array?

这也是分支预测效果吗?注意:这里对排序数组的处理速度较慢!!

请考虑以下代码:

private static final int LIST_LENGTH = 1000 * 1000;
private static final long SLOW_ITERATION_MILLIS = 1000L * 10L;

@Test
public void testBinarySearch() {
    Random r = new Random(0);
    List<Double> list = new ArrayList<>(LIST_LENGTH);
    for (int i = 0; i < LIST_LENGTH; i++) {
        list.add(r.nextDouble());
    }
    //Collections.sort(list);
    // remove possible artifacts due to the sorting call
    // and rebuild the list from scratch:
    list = new ArrayList<>(list);

    int nIterations = 0;
    long startTime = System.currentTimeMillis();
    do {
        int index = r.nextInt(LIST_LENGTH);
        assertEquals(index, list.indexOf(list.get(index)));
        nIterations++;
    } while (System.currentTimeMillis() < startTime + SLOW_ITERATION_MILLIS);
    long duration = System.currentTimeMillis() - startTime;
    double slowFindsPerSec = (double) nIterations / duration * 1000;
    System.out.println(slowFindsPerSec);

    ...
}

这会在我的机器上打印出大约720的值 .

现在,如果我激活集合排序调用,该值将下降到142.为什么?!?

结果是结论性的,如果我增加迭代次数/时间,它们不会改变 .

Java版本是1.8.0_71(Oracle VM,64位),在Windows 10下运行,在Eclipse Mars中运行JUnit .

UPDATE

似乎与连续的内存访问有关(按顺序访问的Double对象与随机顺序访问) . 对于我来说,对于大约10k或更小的阵列长度,效果开始消失 .

感谢assylias提供the results

/**
 * Benchmark                     Mode  Cnt  Score   Error  Units
 * SO35018999.shuffled           avgt   10  8.895 ± 1.534  ms/op
 * SO35018999.sorted             avgt   10  8.093 ± 3.093  ms/op
 * SO35018999.sorted_contiguous  avgt   10  1.665 ± 0.397  ms/op
 * SO35018999.unsorted           avgt   10  2.700 ± 0.302  ms/op
 */

3 回答

  • 8

    它看起来像缓存/预取效果 .

    线索是你比较双打(对象),而不是双打(基元) . 在一个线程中分配对象时,它们通常按顺序分配在内存中 . 因此,当 indexOf 扫描列表时,它会通过顺序存储器地址 . 这有利于CPU缓存预取启发式 .

    但是在对列表进行排序之后,您仍然必须进行相同数量的内存查找,但这次内存访问将按随机顺序进行 .

    UPDATE

    Here is the benchmark证明分配对象的顺序很重要 .

    Benchmark            (generator)  (length)  (postprocess)  Mode  Cnt  Score   Error  Units
    ListIndexOf.indexOf       random   1000000           none  avgt   10  1,243 ± 0,031  ms/op
    ListIndexOf.indexOf       random   1000000           sort  avgt   10  6,496 ± 0,456  ms/op
    ListIndexOf.indexOf       random   1000000        shuffle  avgt   10  6,485 ± 0,412  ms/op
    ListIndexOf.indexOf   sequential   1000000           none  avgt   10  1,249 ± 0,053  ms/op
    ListIndexOf.indexOf   sequential   1000000           sort  avgt   10  1,247 ± 0,037  ms/op
    ListIndexOf.indexOf   sequential   1000000        shuffle  avgt   10  6,579 ± 0,448  ms/op
    
  • 25

    我想我们正在看到内存缓存未命中的影响:

    创建未排序列表时

    for (int i = 0; i < LIST_LENGTH; i++) {
        list.add(r.nextDouble());
    }
    

    所有double都很可能在连续的内存区域中分配 . 迭代这将产生很少的缓存未命中 .

    另一方面,在排序列表中,引用以混乱的方式指向内存 .

    现在,如果您创建一个具有连续内存的排序列表:

    Collection.sort(list);
    List<Double> list2 = new ArrayList<>();
    for (int i = 0; i < LIST_LENGTH; i++) {
        list2.add(new Double(list.get(i).doubleValue()));
    }
    

    这个排序列表具有与原始列表相同的性能(我的时间) .

  • 85

    作为确认answer by weroanswer by apangin(1!)的简单示例:以下是两个选项的简单比较:

    • 创建随机数,并可选择对其进行排序

    • 创建序列号,并可选择改组它们

    它也没有作为JMH基准实现,但与原始代码类似,只需稍加修改即可观察效果:

    import java.util.ArrayList;
    import java.util.Collections;
    import java.util.List;
    import java.util.Random;
    
    public class SortedListTest
    {
        private static final long SLOW_ITERATION_MILLIS = 1000L * 3L;
    
        public static void main(String[] args)
        {
            int size = 100000;
            testBinarySearchOriginal(size, true);
            testBinarySearchOriginal(size, false);
            testBinarySearchShuffled(size, true);
            testBinarySearchShuffled(size, false);
        }
    
        public static void testBinarySearchOriginal(int size, boolean sort)
        {
            Random r = new Random(0);
            List<Double> list = new ArrayList<>(size);
            for (int i = 0; i < size; i++)
            {
                list.add(r.nextDouble());
            }
            if (sort)
            {
                Collections.sort(list);
            }
            list = new ArrayList<>(list);
    
            int count = 0;
            int nIterations = 0;
            long startTime = System.currentTimeMillis();
            do
            {
                int index = r.nextInt(size);
                if (index == list.indexOf(list.get(index)))
                {
                    count++;
                }
                nIterations++;
            }
            while (System.currentTimeMillis() < startTime + SLOW_ITERATION_MILLIS);
            long duration = System.currentTimeMillis() - startTime;
            double slowFindsPerSec = (double) nIterations / duration * 1000;
    
            System.out.printf("Size %8d sort %5s iterations %10.3f count %10d\n",
                size, sort, slowFindsPerSec, count);
        }
    
        public static void testBinarySearchShuffled(int size, boolean sort)
        {
            Random r = new Random(0);
            List<Double> list = new ArrayList<>(size);
            for (int i = 0; i < size; i++)
            {
                list.add((double) i / size);
            }
            if (!sort)
            {
                Collections.shuffle(list);
            }
            list = new ArrayList<>(list);
    
            int count = 0;
            int nIterations = 0;
            long startTime = System.currentTimeMillis();
            do
            {
                int index = r.nextInt(size);
                if (index == list.indexOf(list.get(index)))
                {
                    count++;
                }
                nIterations++;
            }
            while (System.currentTimeMillis() < startTime + SLOW_ITERATION_MILLIS);
            long duration = System.currentTimeMillis() - startTime;
            double slowFindsPerSec = (double) nIterations / duration * 1000;
    
            System.out.printf("Size %8d sort %5s iterations %10.3f count %10d\n",
                size, sort, slowFindsPerSec, count);
        }
    
    }
    

    我机器上的输出是

    Size   100000 sort  true iterations   8560,333 count      25681
    Size   100000 sort false iterations  19358,667 count      58076
    Size   100000 sort  true iterations  18554,000 count      55662
    Size   100000 sort false iterations   8845,333 count      26536
    

    很好地显示时间恰好与另一个时间相反:如果对随机数进行排序,则排序后的版本会更慢 . 如果随机数被洗牌,那么洗牌版本会变慢 .

相关问题