当前位置: 首页 > news >正文

windows C++-并行编程-并行算法(五) -选择排序算法

并行模式库 (PPL) 提供了对数据集合并行地执行工作的算法。这些算法类似于 C++ 标准库提供的算法。并行算法由并发运行时中的现有功能组成。

在许多情况下,parallel_sort 会提供速度和内存性能的最佳平衡。 但是,当您增加数据集的大小、可用处理器的数量或比较函数的复杂性时,parallel_buffered_sort 或 parallel_radixsort 性能更佳。 确定在任何给定方案中使用哪种排序算法的最佳方式是:体验并度量在有代表性计算机配置下对典型数据排序需要多长时间。 在选择排序策略时请遵循以下准则。

  • 数据集的大小。 在本文档中,小型数据集包含的元素少于 1,000 个,中型数据集包含的元素介于 10,000 和 100,000 个之间,而大型数据集包含的元素多于 100,000 个;
  • 您的比较函数或哈希函数所执行的工作量;
  • 可用计算资源的量;
  • 数据集的特征。 例如,一种算法对已完成近似排序的数据可能执行效果很好,但对完全未排序的数据执行效果就不那么好了;
  • 区块的大小。 可选的 _Chunk_size 参数将指定算法在将整体排序细分成较小工作单元时何时从并行排序实现切换为串行排序实现。 例如,如果提供的是 512,算法会在工作单元包含 512 个或更少元素时切换到串行实现。 串行实现可以提高整体性能,因为它消除了并行处理数据所需的开销;

以并行方式对小型数据集排序可能不值得,即使是在您拥有大量的可用计算资源或您的比较函数或哈希函数执行相对大量的工作时。 可以使用 std::sort 函数对小型数据集排序。 (当你指定的区块大小大于数据集时,parallel_sort 和 parallel_buffered_sort 会调用 sort;但是,parallel_buffered_sort 将必须分配 O(N) 空间,这样会因锁争用或内存分配而花费更多时间。)

如果您必须节省内存或您的内存分配器容易出现锁争用问题,请使用 parallel_sort 对中型数据集排序。 parallel_sort 不需要额外的空间;其他算法需要 O(N) 空间。

当你的应用程序能够满足额外的 O(N) 空间需求时,使用 parallel_buffered_sort 对中型数据集排序。 当您拥有大量的计算资源或高开销的比较函数或哈希函数时,parallel_buffered_sort 尤其有用。

当你的应用程序能够满足额外的 O(N) 空间需求时,使用 parallel_radixsort 对大型数据集排序。 当等效的比较操作开销较大或两种操作开销都很大时,parallel_radixsort 尤其有用。

好的哈希函数的实现要求你知道数据集范围以及数据集中的每个元素如何转换为对应的无符号值。 由于哈希操作会处理无符号值,如果无法生成无符号哈希值,请考虑使用另外的排序策略。

下面的示例针对相同大小的随机数据集对 sort、parallel_sort、parallel_buffered_sort 和 parallel_radixsort 的性能进行比较。

// choosing-parallel-sort.cpp
// compile with: /EHsc
#include <ppl.h>
#include <random>
#include <iostream>
#include <windows.h>using namespace concurrency;
using namespace std;// Calls the provided work function and returns the number of milliseconds 
// that it takes to call that function.
template <class Function>
__int64 time_call(Function&& f)
{__int64 begin = GetTickCount();f();return GetTickCount() - begin;
}const size_t DATASET_SIZE = 10000000;// Create
// Creates the dataset for this example. Each call
// produces the same predefined sequence of random data.
vector<size_t> GetData()
{vector<size_t> data(DATASET_SIZE);generate(begin(data), end(data), mt19937(42));return data;
}int wmain()
{// Use std::sort to sort the data.auto data = GetData();wcout << L"Testing std::sort...";auto elapsed = time_call([&data] { sort(begin(data), end(data)); });wcout << L" took " << elapsed << L" ms." <<endl;// Use concurrency::parallel_sort to sort the data.data = GetData();wcout << L"Testing concurrency::parallel_sort...";elapsed = time_call([&data] { parallel_sort(begin(data), end(data)); });wcout << L" took " << elapsed << L" ms." <<endl;// Use concurrency::parallel_buffered_sort to sort the data.data = GetData();wcout << L"Testing concurrency::parallel_buffered_sort...";elapsed = time_call([&data] { parallel_buffered_sort(begin(data), end(data)); });wcout << L" took " << elapsed << L" ms." <<endl;// Use concurrency::parallel_radixsort to sort the data.data = GetData();wcout << L"Testing concurrency::parallel_radixsort...";elapsed = time_call([&data] { parallel_radixsort(begin(data), end(data)); });wcout << L" took " << elapsed << L" ms." <<endl;
} 
/* Sample output (on a computer that has four cores):Testing std::sort... took 2906 ms.Testing concurrency::parallel_sort... took 2234 ms.Testing concurrency::parallel_buffered_sort... took 1782 ms.Testing concurrency::parallel_radixsort... took 907 ms.
*/

本示例中假设在排序期间分配 O(N) 空间是可以接受的,parallel_radixsort 在此计算机配置下对这个数据集表现得最好。 

相关文章:

windows C++-并行编程-并行算法(五) -选择排序算法

并行模式库 (PPL) 提供了对数据集合并行地执行工作的算法。这些算法类似于 C 标准库提供的算法。并行算法由并发运行时中的现有功能组成。 在许多情况下&#xff0c;parallel_sort 会提供速度和内存性能的最佳平衡。 但是&#xff0c;当您增加数据集的大小、可用处理器的数量或…...

【系统架构设计师-2014年真题】案例分析-答案及详解

更多内容请见: 备考系统架构设计师-核心总结索引 文章目录 【材料1】问题1问题2【材料2】问题1问题2问题3【材料3】问题1问题2问题3【材料4】问题1问题2【材料5】问题1问题2问题3【材料1】 请详细阅读以下关于网络设备管理系统架构设计的说明,在答题纸上回答问题1和问题2。 …...

windows C++-并行编程-并行算法(三)-分区工作

并行模式库 (PPL) 提供了对数据集合并行地执行工作的算法。这些算法类似于 C 标准库提供的算法。并行算法由并发运行时中的现有功能组成。 若要对数据源操作进行并行化&#xff0c;一个必要步骤是将源分区为可由多个线程同时访问的多个部分。 分区程序将指定并行算法应如何在线…...

下载 llama2-7b-hf 全流程【小白踩坑记录】

1、文件转换 在官网 https://ai.meta.com/llama/ 申请一个账号&#xff0c;选择要下载的模型&#xff0c;会收到一个邮件&#xff0c;邮件中介绍了下载方法 执行命令 git clone https://github.com/meta-llama/llama.git​ &#xff0c;然后执行 llama/download.sh&#xff0c…...

Codeforces practice C++ 2024/9/11 - 2024/9/13

D. Mathematical Problem Codeforces Round 954 (Div. 3) 原题链接&#xff1a;https://codeforces.com/contest/1986/problem/D 题目标签分类&#xff1a;brute force&#xff0c;dp&#xff0c;greedy&#xff0c;implementation&#xff0c;math&#xff0c;two pointers…...

RabbitMQ创建交换机和队列——配置类 注解

交换机的类型 Fanout&#xff1a;广播&#xff0c;将消息交给所有绑定到交换机的队列。 Direct&#xff1a;订阅&#xff0c;基于RoutingKey&#xff08;路由key&#xff09;发送给订阅了消息的队列。 Topic&#xff1a;通配符订阅&#xff0c;与Direct类似&#xff0c;只不…...

proteus+51单片机+AD/DA学习5

目录 1.DA转换原理 1.1基本概念 1.1.1DA的简介 1.1.2DA0832芯片 1.1.3PCF8591芯片 1.2代码 1.2.1DAC8053的代码 1.2.2PCF8951的代码 1.3仿真 1.3.1DAC0832的仿真 1.3.2PFC8951的仿真 2.AD转换原理 2.1AD的基本概念 2.1.1AD的简介 2.1.2ADC0809的介绍 2.1.3XPT2…...

【Python机器学习】长短期记忆网络(LSTM)

目录 随时间反向传播 实践 模型的使用 脏数据 “未知”词条的处理 字符级建模&#xff08;英文&#xff09; 生成聊天文章 进一步生成文本 文本生成的问题&#xff1a;内容不受控 其他记忆机制 更深的网络 尽管在序列数据中&#xff0c;循环神经网络为对各种语言关系…...

【Go】使用Goland创建第一个Go项目

✨✨ 欢迎大家来到景天科技苑✨✨ &#x1f388;&#x1f388; 养成好习惯&#xff0c;先赞后看哦~&#x1f388;&#x1f388; &#x1f3c6; 作者简介&#xff1a;景天科技苑 &#x1f3c6;《头衔》&#xff1a;大厂架构师&#xff0c;华为云开发者社区专家博主&#xff0c;…...

STM32学习笔记(一、使用DAP仿真器下载程序)

我们想要使用32单片机&#xff0c;总共包含四个步骤&#xff1a; 1、硬件连接 2、仿真器配置 3、编写程序 4、下载程序 一、第一个问题&#xff08;硬件连接&#xff09;&#xff1a;如何进行硬件连接&#xff0c;才能够启动32板子并能够下载程序呢&#xff1f; 答&#…...

储能运维管理云平台解决方案EMS能量管理系统

在储能行业蓬勃发展的今天&#xff0c;储能运维管理的重要性日益凸显。而储能运维管理云平台的出现&#xff0c;正为储能系统的稳定运行和高效管理注入了新的活力。 一、储能运维管理面临的挑战 传统的储能运维管理方式往往依赖人工巡检和现场操作&#xff0c;存在诸多问题。比…...

网络药理学:16、速通流程版

一、筛选疾病靶点 GeneCards 下载数据得到GeneCards-SearchResult.csv通过Relevance score≥1.0得到GeneCards.csv步骤2只保留Gene Symbol&#xff0c;即基因名这一列得到GeneCards_gene_names.csv OMIM 下载数据得到OMIM-Gene-Map-Retrieval.xlsx只保留Gene/Locus&#xf…...

P2515 [HAOI2010] 软件安装

~~~~~ P2515 [HAOI2010] 软件安装 ~~~~~ 总题单链接 思路 ~~~~~ 发现构成的图是一个森林和一些环。 ~~~~~ 对于森林&#xff0c;建一个虚点然后树形 D P DP DP 即可。 ~~~~~ 对于环&#xff0c;发现要么把这个环上的每一个点都选了&#xff0c;要么每一个都不选。所以可以先缩…...

51单片机快速入门之定时器和计数器

51单片机快速入门之定时器 断开外部输入 晶振振荡 假设为 12MHz 12分频之后,为1MHz 当其从0-65536 时,需要65536μs 微秒 也就是65.536ms 毫秒 溢出(值>65536 时)>中断>执行中断操作 假设需要1ms后产生溢出,则需要设置初始值为64536 此时定时器会从 64536 开始计…...

【计算机网络 - 基础问题】每日 3 题(一)

✍个人博客&#xff1a;Pandaconda-CSDN博客 &#x1f4e3;专栏地址&#xff1a;http://t.csdnimg.cn/fYaBd &#x1f4da;专栏简介&#xff1a;在这个专栏中&#xff0c;我将会分享 C 面试中常见的面试题给大家~ ❤️如果有收获的话&#xff0c;欢迎点赞&#x1f44d;收藏&…...

Unity全面取消Runtime费用 安装游戏不再收版费

Unity宣布他们已经废除了争议性的Runtime费用&#xff0c;该费用于2023年9月引入&#xff0c;定于1月1日开始收取。Runtime费用起初是打算根据使用Unity引擎安装游戏的次数收取版权费。2023年9月晚些时候&#xff0c;该公司部分收回了计划&#xff0c;称Runtime费用只适用于订阅…...

IDEA测试类启动报 “java: 常量字符串过长” 解决办法

目录标题 问题描述问题分析解决办法其他办法 问题描述 问题分析 字符串长度过长&#xff0c;导致 idea 默认使用的 javac 编译器编译不了。 查询资料发现&#xff0c;原因是javac在编译期间&#xff0c;常量字符串最大长度为65534。 解决办法 Javac 编译器改为 Eclipse 编译…...

计算机科学基础 -- 访存单元

访存单元&#xff08;Memory Access Unit&#xff09;的概念 访存单元&#xff08;Memory Access Unit&#xff09; 是处理器中的一个关键模块&#xff0c;负责处理指令中的内存访问操作&#xff0c;包括从内存中读取数据和将数据写入内存。由于内存访问速度通常比处理器执行速…...

Linux压缩、解压缩、查看压缩内容详解使用(tar、gzip、bzip2、xz、jar、war、aar)

在Linux环境中&#xff0c;你可以使用各种命令来压缩、解压缩和查看不同类型的压缩包。以下是常用的命令和操作说明&#xff0c;包括tar、gzip、bzip2、xz、jar、war、aar等类型的包文件。 1. tar命令&#xff1a;压缩、解压、查看tar包 压缩&#xff1a; tar -cvf archive.…...

StreamReader 和 StreamWriter提供自动处理字符编码的功能

FileStream、StreamReader 和 StreamWriter 都用于文件操作&#xff0c;但它们的设计目标和使用方式有所不同。下面是它们之间的主要差异以及如何结合使用的说明&#xff1a; 1. FileStream 用途&#xff1a;提供对文件的字节流访问&#xff0c;用于读写二进制数据。特点&…...

Opencv中的addweighted函数

一.addweighted函数作用 addweighted&#xff08;&#xff09;是OpenCV库中用于图像处理的函数&#xff0c;主要功能是将两个输入图像&#xff08;尺寸和类型相同&#xff09;按照指定的权重进行加权叠加&#xff08;图像融合&#xff09;&#xff0c;并添加一个标量值&#x…...

汽车生产虚拟实训中的技能提升与生产优化​

在制造业蓬勃发展的大背景下&#xff0c;虚拟教学实训宛如一颗璀璨的新星&#xff0c;正发挥着不可或缺且日益凸显的关键作用&#xff0c;源源不断地为企业的稳健前行与创新发展注入磅礴强大的动力。就以汽车制造企业这一极具代表性的行业主体为例&#xff0c;汽车生产线上各类…...

大语言模型如何处理长文本?常用文本分割技术详解

为什么需要文本分割? 引言:为什么需要文本分割?一、基础文本分割方法1. 按段落分割(Paragraph Splitting)2. 按句子分割(Sentence Splitting)二、高级文本分割策略3. 重叠分割(Sliding Window)4. 递归分割(Recursive Splitting)三、生产级工具推荐5. 使用LangChain的…...

【快手拥抱开源】通过快手团队开源的 KwaiCoder-AutoThink-preview 解锁大语言模型的潜力

引言&#xff1a; 在人工智能快速发展的浪潮中&#xff0c;快手Kwaipilot团队推出的 KwaiCoder-AutoThink-preview 具有里程碑意义——这是首个公开的AutoThink大语言模型&#xff08;LLM&#xff09;。该模型代表着该领域的重大突破&#xff0c;通过独特方式融合思考与非思考…...

VTK如何让部分单位不可见

最近遇到一个需求&#xff0c;需要让一个vtkDataSet中的部分单元不可见&#xff0c;查阅了一些资料大概有以下几种方式 1.通过颜色映射表来进行&#xff0c;是最正规的做法 vtkNew<vtkLookupTable> lut; //值为0不显示&#xff0c;主要是最后一个参数&#xff0c;透明度…...

现代密码学 | 椭圆曲线密码学—附py代码

Elliptic Curve Cryptography 椭圆曲线密码学&#xff08;ECC&#xff09;是一种基于有限域上椭圆曲线数学特性的公钥加密技术。其核心原理涉及椭圆曲线的代数性质、离散对数问题以及有限域上的运算。 椭圆曲线密码学是多种数字签名算法的基础&#xff0c;例如椭圆曲线数字签…...

多种风格导航菜单 HTML 实现(附源码)

下面我将为您展示 6 种不同风格的导航菜单实现&#xff0c;每种都包含完整 HTML、CSS 和 JavaScript 代码。 1. 简约水平导航栏 <!DOCTYPE html> <html lang"zh-CN"> <head><meta charset"UTF-8"><meta name"viewport&qu…...

华为云Flexus+DeepSeek征文|DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建

华为云FlexusDeepSeek征文&#xff5c;DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建 前言 如今大模型其性能出色&#xff0c;华为云 ModelArts Studio_MaaS大模型即服务平台华为云内置了大模型&#xff0c;能助力我们轻松驾驭 DeepSeek-V3/R1&#xff0c;本文中将分享如何…...

select、poll、epoll 与 Reactor 模式

在高并发网络编程领域&#xff0c;高效处理大量连接和 I/O 事件是系统性能的关键。select、poll、epoll 作为 I/O 多路复用技术的代表&#xff0c;以及基于它们实现的 Reactor 模式&#xff0c;为开发者提供了强大的工具。本文将深入探讨这些技术的底层原理、优缺点。​ 一、I…...

AI,如何重构理解、匹配与决策?

AI 时代&#xff0c;我们如何理解消费&#xff1f; 作者&#xff5c;王彬 封面&#xff5c;Unplash 人们通过信息理解世界。 曾几何时&#xff0c;PC 与移动互联网重塑了人们的购物路径&#xff1a;信息变得唾手可得&#xff0c;商品决策变得高度依赖内容。 但 AI 时代的来…...