问题：

为什么过滤未排序列表比过滤已排序列表快

墨翔宇

2023-03-14

我一直在玩Java 8 ，我决定对和流进行微基准测试。正如预期的那样，的速度是原来的两倍，但还是出现了其他一些问题--如果我在将数据传递给之前先对其进行排序，则与传递未排序列表相比， Map->Collect/code>得到结果所需的时间要多出5-8倍。

(Stream) Elapsed time [ns] : 53733996 (53 ms)
(ParallelStream) Elapsed time [ns] : 25901907 (25 ms)

(Stream) Elapsed time [ns] : 336976149 (336 ms)
(ParallelStream) Elapsed time [ns] : 204781387 (204 ms)

package com.github.svetlinzarev.playground.javalang.lambda;

import static java.lang.Long.valueOf;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;
import java.util.stream.Collectors;

import com.github.svetlinzarev.playground.util.time.Stopwatch;

public class MyFirstLambda {
    private static final int ELEMENTS = 1024 * 1024 * 16;

    private static List<Integer> getRandom(int nElements) {
        final Random random = new Random();
        final List<Integer> data = new ArrayList<Integer>(nElements);
        for (int i = 0; i < MyFirstLambda.ELEMENTS; i++) {
            data.add(random.nextInt(MyFirstLambda.ELEMENTS));
        }
        return data;
    }

    private static void benchStream(List<Integer> data) {
        final Stopwatch stopwatch = new Stopwatch();
        final List<Long> smallLongs = data.stream()
                .filter(i -> i.intValue() < 16)
                .map(Long::valueOf)
                .collect(Collectors.toList());
        stopwatch.log("Stream");
        System.out.println(smallLongs);
    }

    private static void benchParallelStream(List<Integer> data) {
        final Stopwatch stopwatch = new Stopwatch();
        final List<Long> smallLongs = data.parallelStream()
                .filter(i -> i.intValue() < 16)
                .map(Long::valueOf)
                .collect(Collectors.toList());
        stopwatch.log("ParallelStream");
        System.out.println(smallLongs);
    }

    public static void main(String[] args) {
        final List<Integer> data = MyFirstLambda.getRandom(MyFirstLambda.ELEMENTS);
        // Collections.sort(data, (first, second) -> first.compareTo(second)); //<- Sort the data

        MyFirstLambda.benchStream(data);
        MyFirstLambda.benchParallelStream(data);

        MyFirstLambda.benchStream(data);
        MyFirstLambda.benchParallelStream(data);

        MyFirstLambda.benchStream(data);
        MyFirstLambda.benchParallelStream(data);

        MyFirstLambda.benchStream(data);
        MyFirstLambda.benchParallelStream(data);

        MyFirstLambda.benchStream(data);
        MyFirstLambda.benchParallelStream(data);
    }
}

下面是一个更好的基准测试代码

package com.github.svetlinzarev.playground.javalang.lambda;

import static java.lang.Long.valueOf;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Random;
import java.util.stream.Collectors;

import com.github.svetlinzarev.playground.util.time.Stopwatch;

public class MyFirstLambda {
    private static final int ELEMENTS = 1024 * 1024 * 10;
    private static final int SMALLER_THAN = 16;
    private static final int WARM_UP_ITERRATIONS = 1000;

    private static List<Integer> getRandom(int nElements) {
        final Random random = new Random();
        final List<Integer> data = new ArrayList<Integer>(nElements);
        for (int i = 0; i < MyFirstLambda.ELEMENTS; i++) {
            data.add(random.nextInt(MyFirstLambda.ELEMENTS));
        }
        return data;
    }

    private static List<Long> filterStream(List<Integer> data) {
        final List<Long> smallLongs = data.stream()
                .filter(i -> i.intValue() < MyFirstLambda.SMALLER_THAN)
                .map(Long::valueOf)
                .collect(Collectors.toList());
        return smallLongs;
    }

    private static List<Long> filterParallelStream(List<Integer> data) {
        final List<Long> smallLongs = data.parallelStream()
                .filter(i -> i.intValue() < MyFirstLambda.SMALLER_THAN)
                .map(Long::valueOf)
                .collect(Collectors.toList());
        return smallLongs;
    }

    private static long filterAndCount(List<Integer> data) {
        return data.stream()
                .filter(i -> i.intValue() < MyFirstLambda.SMALLER_THAN)
                .count();
    }

    private static long filterAndCountinParallel(List<Integer> data) {
        return data.parallelStream()
                .filter(i -> i.intValue() < MyFirstLambda.SMALLER_THAN)
                .count();
    }

    private static void warmUp(List<Integer> data) {
        for (int i = 0; i < MyFirstLambda.WARM_UP_ITERRATIONS; i++) {
            MyFirstLambda.filterStream(data);
            MyFirstLambda.filterParallelStream(data);
            MyFirstLambda.filterAndCount(data);
            MyFirstLambda.filterAndCountinParallel(data);
        }
    }

    private static void benchmark(List<Integer> data, String message) throws InterruptedException {
        System.gc();
        Thread.sleep(1000); // Give it enough time to complete the GC cycle

        final Stopwatch stopwatch = new Stopwatch();
        MyFirstLambda.filterStream(data);
        stopwatch.log("Stream: " + message);

        System.gc();
        Thread.sleep(1000); // Give it enough time to complete the GC cycle

        stopwatch.reset();
        MyFirstLambda.filterParallelStream(data);
        stopwatch.log("ParallelStream: " + message);

        System.gc();
        Thread.sleep(1000); // Give it enough time to complete the GC cycle

        stopwatch.reset();
        MyFirstLambda.filterAndCount(data);
        stopwatch.log("Count: " + message);

        System.gc();
        Thread.sleep(1000); // Give it enough time to complete the GC cycle

        stopwatch.reset();
        MyFirstLambda.filterAndCount(data);
        stopwatch.log("Count in parallel: " + message);
    }

    public static void main(String[] args) throws InterruptedException {
        final List<Integer> data = MyFirstLambda.getRandom(MyFirstLambda.ELEMENTS);

        MyFirstLambda.warmUp(data);
        MyFirstLambda.benchmark(data, "UNSORTED");

        Collections.sort(data, (first, second) -> first.compareTo(second));
        MyFirstLambda.benchmark(data, "SORTED");

        Collections.sort(data, (first, second) -> second.compareTo(first));
        MyFirstLambda.benchmark(data, "IN REVERSE ORDER");

    }
}

结果也是相似的:

   16:09:20.470 [main] INFO  c.g.s.playground.util.time.Stopwatch - (Stream: UNSORTED) Elapsed time [ns] : 66812263 (66 ms)
16:09:22.149 [main] INFO  c.g.s.playground.util.time.Stopwatch - (ParallelStream: UNSORTED) Elapsed time [ns] : 39580682 (39 ms)
16:09:23.875 [main] INFO  c.g.s.playground.util.time.Stopwatch - (Count: UNSORTED) Elapsed time [ns] : 97852866 (97 ms)
16:09:25.537 [main] INFO  c.g.s.playground.util.time.Stopwatch - (Count in parallel: UNSORTED) Elapsed time [ns] : 94884189 (94 ms)
16:09:35.608 [main] INFO  c.g.s.playground.util.time.Stopwatch - (Stream: SORTED) Elapsed time [ns] : 361717676 (361 ms)
16:09:38.439 [main] INFO  c.g.s.playground.util.time.Stopwatch - (ParallelStream: SORTED) Elapsed time [ns] : 150115808 (150 ms)
16:09:41.308 [main] INFO  c.g.s.playground.util.time.Stopwatch - (Count: SORTED) Elapsed time [ns] : 338335743 (338 ms)
16:09:44.209 [main] INFO  c.g.s.playground.util.time.Stopwatch - (Count in parallel: SORTED) Elapsed time [ns] : 370968432 (370 ms)
16:09:50.693 [main] INFO  c.g.s.playground.util.time.Stopwatch - (Stream: IN REVERSE ORDER) Elapsed time [ns] : 352036140 (352 ms)
16:09:53.323 [main] INFO  c.g.s.playground.util.time.Stopwatch - (ParallelStream: IN REVERSE ORDER) Elapsed time [ns] : 151044664 (151 ms)
16:09:56.159 [main] INFO  c.g.s.playground.util.time.Stopwatch - (Count: IN REVERSE ORDER) Elapsed time [ns] : 359281197 (359 ms)
16:09:58.991 [main] INFO  c.g.s.playground.util.time.Stopwatch - (Count in parallel: IN REVERSE ORDER) Elapsed time [ns] : 353177542 (353 ms)

那么，我的问题是为什么过滤一个未排序的列表比过滤一个已排序的列表更快呢？

共有1个答案

高才

2023-03-14

当您使用未排序列表时，所有元组都是按内存顺序访问的。它们已在RAM中连续分配。CPU喜欢按顺序访问内存，因为它们可以推测性地请求下一个缓存行，这样在需要时它将始终存在。

当您对列表进行排序时，您将其按随机顺序排列，因为您的排序键是随机生成的。这意味着对元组成员的内存访问是不可预测的。CPU不能预取内存，几乎每一次对元组的访问都是一次缓存未命中。

这是一个很好的例子，说明了GC内存管理的一个特殊优点:一起分配和一起使用的数据结构性能非常好。它们有很大的参照点。

在这种情况下，缓存未命中带来的损失大于保存的分支预测损失。

这个问题是公认的答案，也回答了我的问题:为什么处理排序数组比处理未排序数组慢？

当我创建原始的 list ode=""> sorted-即它的元素顺序地存在于内存中时，执行时间没有差别，并且当被随机数填充时，它与版本相等。

类似资料：

使用Google集合对列表进行过滤和排序

问题内容：假设我有一个列表（或集合）：我想返回一个ImmutableList（Set），它以自然顺序对术语进行排序/分组，其中以“ src”开头的术语排在第一位，“ assoc”第二位，而“ dest”排在最后。如果一个术语不包含这些术语，则应将其从结果列表中删除。因此，这里的结果是“ srcB”，“ srcT”，“ assocX”，“ destA”。我想我可以通过Iterables.fi
16.3. 过滤已访问列表

16.3. 过滤已访问列表你已经熟识了应用列表遍历来过滤列表。这里介绍的是达到相同效果的另一种令很多人感觉清晰的实现方法。 Python 有一个内建 filter 函数，它接受两个参数：一个函数和一个列表，返回一个列表。[7] 作为第一个参数传递给 filter 的函数本身应接受一个参数，filter 返回的列表将会包含被传入列表参数传递给 filter 所有可以另函数返回真（true）的元
Django表-列过滤

问题内容：我开始使用django-tables2（从第一印象中就可以强烈推荐），我问自己如何实现列过滤。我找不到合适的文档，但是我确定它在那里。问题答案：答案有点晚了，但是无论如何…我也找不到任何合适的文档来进行列过滤。有很多方法可以做到这一点：答：手动：我添加了一个包含要过滤的字段的表单，然后在我的视图中执行以下操作：这很好用，但是不是那么干，因为它在视图中是硬编码的。 B.使用Sin
4.5. 过滤列表

4.5. 过滤列表如你所知，Python 具有通过列表解析（第 3.6 节 “映射 list”）将列表映射到其它列表的强大能力。这种能力同过滤机制结合使用，使列表中的有些元素被映射的同时跳过另外一些元素。过滤列表语法： [mapping-expression for element in source-list if filter-expression] 这是你所知所爱的列表解析的扩展。
1.5.1 过滤序列

RxJava让我们使用filter()方法来过滤我们观测序列中不想要的值，在上一章中，我们在几个例子中使用了已安装的应用列表，但是我们只想展示以字母C开头的已安装的应用该怎么办呢？在这个新的例子中，我们将使用同样的列表，但是我们会过滤它，通过把合适的谓词传给filter()函数来得到我们想要的值。上一章中loadList()函数可以改成这样： private void loadList(List
FilterableList(过滤器列表)

过滤字段的列表，每一个成员应该是数组或对象 $data = [ ['id'=>1, 'name'=>'a'], ['id'=>2, 'name'=>'b'], ]; // 两个毫无意义的实例化写法 $list = new FilterableList; $list = new FilterableList($data); // 只保留 name 字段 $list = new Fi

为什么过滤未排序列表比过滤已排序列表快

共有1个答案

相关问答

相关文章

相关阅读

相关工具

相关文档