首页 > 其他分享 >为什么处理已排序数组比处理未排序数组更快?

为什么处理已排序数组比处理未排序数组更快?

时间:2023-10-06 12:33:05浏览次数:37  
标签:... 处理 int arraySize 数组 排序 data 分支

在这个C++代码中,在计时区域之前对数据进行排序(*)使得主循环快6倍:

#include <algorithm>
#include <ctime>
#include <iostream>

int main()
{
    // 生成数据
    const unsigned arraySize = 32768;
    int data[arraySize];

    for (unsigned c = 0; c < arraySize; ++c)
        data[c] = std::rand() % 256;

    // !!! With this, the next loop runs faster.
    std::sort(data, data + arraySize);

    // 测试
    clock_t start = clock();
    long long sum = 0;
    for (unsigned i = 0; i < 100000; ++i)
    {
        for (unsigned c = 0; c < arraySize; ++c)
        {   // 主循环。
            if (data[c] >= 128)
                sum += data[c];
        }
    }

    double elapsedTime = static_cast<double>(clock()-start) / CLOCKS_PER_SEC;

    std::cout << elapsedTime << '\n';
    std::cout << "sum = " << sum << '\n';
}
  • 如果不使用std::sort(data, data + arraySize);,代码运行时间为11.54秒。
  • 使用排序后的数据,代码运行时间为1.93秒。

(排序本身比遍历数组所需的时间要多,所以如果我们需要为未知数组计算这个,它实际上并不值得做。)


最初,我以为这可能是一个语言或编译器的异常,所以我尝试了Java:

import java.util.Arrays;
import java.util.Random;

public class Main
{
    public static void main(String[] args)
    {
        // 生成数据
        int arraySize = 32768;
        int data[] = new int[arraySize];

        Random rnd = new Random(0);
        for (int c = 0; c < arraySize; ++c)
            data[c] = rnd.nextInt() % 256;

        // !!! With this, the next loop runs faster
        Arrays.sort(data);

        // 测试
        long start = System.nanoTime();
        long sum = 0;
        for (int i = 0; i < 100000; ++i)
        {
            for (int c = 0; c < arraySize; ++c)
            {   // 主循环。
                if (data[c] >= 128)
                    sum += data[c];
            }
        }

        System.out.println((System.nanoTime() - start) / 1000000000.0);
        System.out.println("sum = " + sum);
    }
}

结果类似但程度略低。


我的第一反应是排序将数据带入缓存(https://en.wikipedia.org/wiki/CPU_cache ),但这很愚蠢,因为数组刚刚生成。

  • 这是怎么回事?
  • 为什么处理已排序数组比处理未排序数组更快?

代码正在对一些独立的项求和,因此顺序不应该很重要。


你成为了分支预测失败的受害者。

什么是分支预测?

想象一个铁路交叉口:

显示铁路交叉口的图片
图片 by Mecanismo,通过Wikimedia Commons获得。根据CC-By-SA 3.0许可证使用。

现在为了论证,假设这是回到19世纪的事情 - 在远距离或无线电通信之前。

你是交叉口的一个盲目操作员,你听到一列火车驶来。你不知道它应该往哪个方向去。你停下来让司机告诉你他们想要的方向。然后你适当地设置开关。

火车很重且具有很大的惯性,所以它们需要很长时间才能启动和减速。

有更好的方法吗?你可以猜测火车将往哪个方向行驶!

*如果你猜对了,它将继续前进。
*如果你猜错了,船长将停下来,后退,并大声责骂你要翻转开关。然后它可以重新启动沿着另一条路径。

如果你每次都猜对,火车将永远不会停下来。

如果你猜错的次数太多,火车将花费很多时间停下来,后退,然后重新启动。


考虑一个if语句:在处理器级别,它是一个分支指令:

包含if语句的编译代码的屏幕截图

你是处理器,你看到一个分支。你不知道它会走哪条路。你会怎么做?你停止执行,等待前面的指令完成。然后你继续沿着正确的路径前进。

现代处理器复杂且具有长流水线。这意味着它们需要很长时间才能“预热”和“减速”。

有更好的方法吗?你可以猜测分支将往哪个方向行驶!

*如果你猜对了,你将继续执行。
*如果你猜错了,你需要冲洗流水线并回滚到分支。然后你可以重新启动沿着另一条路径。

如果你每次都猜对,执行将永远不会停止。

如果你猜错的次数太多,你会花费很多时间停止、回滚和重新启动。


这就是分支预测。我承认这个比喻并不完美,因为火车可以使用标志来指示方向。但在计算机中,处理器在分支的最后一刻才知道分支将走向何方。

你会如何战略性地猜测以最小化火车必须后退并沿着另一条路径重新启动的次数?你看过去的历史!如果火车99%的时间都向左,那么你猜测左边。如果它交替,那么你交替你的猜测。如果它每三次向一个方向前进一次,你猜测相同的...

换句话说,你尝试识别一个模式并遵循它。这大致是分支预测器的工作方式。

大多数应用程序都有行为良好的分支。因此,现代分支预测器通常可以实现>90%的命中率。但是当面对无法预测的分支且没有可识别的模式时,分支预测器几乎无用。

进一步阅读:【分支预测器】维基百科文章。
这是非常友好的分支预测器,因为分支连续地走相同的方向很多次。即使是一个简单的饱和计数器也可以正确预测分支,除了在它切换方向后的几次迭代之外。

快速可视化:

T = 分支被采取
N = 分支未被采取

data[] = 0, 1, 2, 3, 4, ... 126, 127, 128, 129, 130, ... 250, 251, 252, ...
分支 = N  N  N  N  N  ...   N    N    T    T    T  ...   T    T    T  ...

       = NNNNNNNNNNNN ... NNNNNNNTTTTTTTTT ... TTTTTTTTTT  (容易预测)

然而,当数据完全随机时,分支预测器将被证明是无用的,因为它无法预测随机数据。因此,可能会有大约50%的误预测(不比随机猜测好)。

data[] = 226, 185, 125, 158, 198, 144, 217, 79, 202, 118,  14, 150, 177, 182, ...
分支 =   T,   T,   N,   T,   T,   T,   T,  N,   T,   N,   N,   T,   T,   T  ...

       = TTNTTTTNTNNTTT ...   (完全随机 - 无法预测)


可以做什么?

如果编译器无法将分支优化为条件移动,如果您愿意牺牲性能以换取可读性,可以尝试一些技巧。

将以下代码:

if (data[c] >= 128)
    sum += data[c];

替换为:

int t = (data[c] - 128) >> 31;
sum += ~t & data[c];

这将消除分支并用一些位操作替换它。

(注意,此技巧并不严格等同于原始的if语句。但是在这种情况下,对于data[]的所有输入值,它是有效的。)

基准测试:

  • Core i7 920 @ 3.5 GHz

  • C++ - Visual Studio 2010 - x64 Release
    | 场景 | 时间(秒) |
    | --- | --- |
    | 分支 - 随机数据 | 11.777 |
    | 分支 - 排序数据 | 2.352 |
    | 无分支 - 随机数据 | 2.564 |
    | 无分支 - 排序数据 | 2.587 |

  • Java - NetBeans 7.1.1 JDK 7 - x64
    | 场景 | 时间(秒) |
    | --- | --- |
    | 分支 - 随机数据 | 10.93293813 |
    | 分支 - 排序数据 | 5.643797077 |
    | 无分支 - 随机数据 | 3.113581453 |
    | 无分支 - 排序数据 | 3.186068823 |

观察结果:

  • 有分支的情况:排序和未排序数据之间存在巨大差异。
  • 使用技巧的情况:排序和未排序数据之间没有区别。
  • 在C++情况下,当数据已排序时,技巧实际上比有分支的情况稍慢。

一般规则是,在关键循环中避免数据相关的分支(例如本例)。

标签:...,处理,int,arraySize,数组,排序,data,分支
From: https://www.cnblogs.com/xiaomandujia/p/17744433.html

相关文章

  • 力扣-1646-获取生成数组中的最大值
    给你一个整数n。按下述规则生成一个长度为n+1的数组nums:nums[0]=0nums[1]=1当2<=2*i<=n时,nums[2*i]=nums[i]当2<=2*i+1<=n时,nums[2*i+1]=nums[i]+nums[i+1]返回生成数组nums中的最大值。 示例1:输入:n=7输出:3解释:根据规则:......
  • VMware workstation pro12 突然蓝屏的处理方法
      电脑是win10操作系统,以前安装VMwareWorkstationpro12x,一直用得不错,昨天突然出现状况:进入虚拟机后前面看着正常,出现CentOS灰色图案后,静默——蓝屏!提示:你的设备遇到问题,需要重启......分别尝试以下方法:(1)重启——无效,查看log(引用一部分,仅作参考):2023-10-05T16:48:14.2......
  • 深入探讨Java Stream流:数据处理的新思维
    文章目录1.流式思想1.1输入流与输出流1.2Stream流2.使用Stream流的步骤3.获取Stream流3.1容器3.2数组4.Stream流中间操作方法4.1`filter(Predicate<?superT>predicate)`4.2`limit(longmaxSize)`4.3`skip(longn)`4.4`distinct()`4.5`sorted()`和`sorted(Compar......
  • Leetcode刷题83. 删除排序链表中的重复元素
    给定一个已排序的链表的头 head , 删除所有重复的元素,使每个元素只出现一次 。返回 已排序的链表 。示例1:输入:head=[1,1,2]输出:[1,2]示例2:输入:head=[1,1,2,3,3]输出:[1,2,3] 提示:链表中节点数目在范围 [0,300] 内-100<=Node.val<=100题目数......
  • 快速排序
    快速排序使用java实现快速排序publicstaticvoidquickSort(int[]arr,intl,intr){if(l>=r){return;}intlift=l;intright=r;//选取比较的值,取需要排序的序列的第一个数作为基值intp=ar......
  • 12_指针数组
    指针数组数值指针数组本质的数组,只是每个元素都是指针32位平台:char*arr1[4];short*arr2[4];int*arr3[4];sizeof(arr1);//16Bsizeof(arr2);//16Bsizeof(arr3);//16B字符指针数组char*arr[4]={"hehehehe","xixixixix","lalalala","wuwuwuwu"......
  • 第8章 排序
    一、插入排序基本思想:每次将一个待排序的记录按其关键字大小插入到前面已排好序的子序列,直到全部记录插入完成直接插入排序时间复杂度:最好O(n):表中元素有序,最坏O(n2):表中元素逆序空间复杂度:O(1)稳定性:稳定,总是插入到相同元素的后面适用性:顺序、链式(从前往后查找指定元素......
  • 快速排序
    一、算法描述快速排序算法是对冒泡排序算法的一种改进算法,在当前所有内部排序算法中,快速排序算法被认为是最好的排序算法之一。快速排序的基本思想:通过一趟排序将待排序的序列分割为左右两个子序列,左边的子序列中所有数据都比右边子序列中的数据小,然后对左右两个子序列继续进行......
  • Webserver报错处理
    启动web-server不成功,会报错误:java.net.ConnectException:Connectionrefused:nofurtherinformationatjava.base/sun.nio.ch.Net.pollConnect(NativeMethod)~[na:na]atjava.base/sun.nio.ch.Net.pollConnectNow(Net.java:672)~[na:na]atjava.base/sun.nio.ch.Sock......
  • uniapp微信小程序如何处理input输入空格问题?
    第一种方法用input组件自带的@input事件使用@input事件绑定变量用trim修剪掉前端和末尾的空格后用replace替换空格为空把处理过的值赋给自己<inputtype="text"class=""v-model="certNo"placeholder="请输入您的证书编号"@blur="certNo=certNo.trim().replace(/\s+/g,''......