并行计算期末复习

标签: 并行与分布式程序设计

文章目录

推动并行计算的因素

  • cpu晶体管集成密度一直在指数级增长(符合摩尔定律), 但是单个cpu的时钟频率2003之后急剧放缓, 说明单核的时钟频率已不是处理器发展的主角
  • 功耗/ 散热 的限制使得单个cpu的时钟频率无法在提升, 只能选择增加cpu数量
  • 多核, 众核称为之后cpu的发展趋势, 转变之前“更复杂的处理器设计, 更快的时钟频率”

硬件因素, 单核cpu的发展使得性能的提升受到限制, 导致不得不向多核, 众核发展.

并行计算的应用

  • 航空领域, 数据库, 能源, 环境, 游戏, 地理, 药物, 科研, 天气, 生物

  • 科学仿真

    • 全局气候建模
    • 海洋建模
    • 星系演化
    • 生物信息学
    • 天文学
    • 强子对撞机
  • 商用领域 : 运算能力更强, 速度更快, 价格更便宜

超算机

  • 神威·太湖之光 2016年, 无锡 12.5亿亿次/秒

    • 自研的“申威26010”众核处理器
  • Summit(顶点) 2018年 IBM研发 20亿亿次/秒 超过神威·太湖之光 约60%

  • 下一步规划 : E级超算 (百亿亿次)

并行计算软件技术面临的挑战

并行程序设计的复杂性

  • 足够的并发度
  • 并发粒度
    • 独立的计算任务的大小
  • 负载均衡
    • 处理器的工作量相近
  • 协调和同步
  • 局部性
    • 对临近的数据进行计算

数据移动(通信)代价很高

  • 因此在设计算法和软件时, 要尽可能地最小化数据移动; 每单位数据移动要做更多的计算.

能耗挑战

  • 每MW 需要1M美元

伸缩性挑战

  • 相同的程序在新一代硬件架构下仍能高效运行.
  • 在**更大规模(更多核心)**的硬件平台下仍然能够高效运行(甚至提升)

软件生态环境几乎停滞

  • 现有代码还未准备好硬件架构的改变
  • 新软件技术还不成熟.

Cache相关工作原理及概念

冯诺伊曼结构

  • 五部分: 控制器, 运算器, 存储器, 输入设备, 输出设备
  • 控制器和运算器继承在cpu中, 使用不同的寄存器实现对应功能, ALU(算数逻辑单元)和程序计数器
  • 缺点: CPU和存储单元分离设计, 导致一条指令的执行过程中, cpu从主存中存取数据的过程耗时较大

Cache 高速缓冲存储器(缓存)

  • cpu对缓存中的数据进行存取花费时间更短

  • 缓存可以集成在cpu上, 也可以在cpu外

  • 缓存存储依照的准则

    • 空间局部性, 时间局部性
    • 程序接下来可能会用到的指令和数据 与 刚刚访问过的指令和数据在物理上是临近存放的
  • 多级缓存(一般3级)

    • 离cpu越近的, 速度越快, 容量越少
  • 缓存命中, 缺失

    • 命中 : 在多级缓存中找到了相应的数据
    • 缺失 : 在多级缓存中未找到.
  • 往缓存中存放数据时, 并不是一次放一个, 而是放一个数据块(一个高速缓存行).

    • 第一次访问, 缓存中没有, 需要在主存中找到需要使用的数据, 然后把这个数据附近的一块数据都放入缓存中.
  • 缓存和主存中数据不一致(缓存一致性)

    • 写直达(write-through) : 一旦发生不一致, 立刻相应更改主存中数据
    • 写回(write-back) : 将缓存中不一致的数据标记为脏数据, 待整个高速缓存行里的数据都执行完毕后, 再一次性写入主存中.
  • 行主序, 列主序对访问数据效率的影响

虚拟内存

  • 在磁盘上开辟一块区域当作内存, 暂时访问不到的数据放在上面

低层次的并行 (硬件级别, 程序员不可控)

  • 一个核, 充分利用其中各种的寄存器
  • 指令集并行
    • 流水线(pipeline) : 7 * 1000 -> 7 + (1000 - 1)
    • 多发射(multiple issue) : 把任务平均分给不同的处理单元, 让它们同时处理 (有一些数据调度, 任务分配额外开销)
      • 静态 : 编译时起分配
      • 动态 : 运行时动态分配调整 (超标量)
        • 硬件级别, 程序员无法控制
        • 需要预测哪些指令可以同时执行, 如果判断失误, 会有额外的开销

并行 多线程相关概念

  • 进程 : 运行着的计算机程序的实体
    • 包含程序, 内存空间, 资源描述符, 安全信息,状态信息
  • 多任务 : 单个处理器同时运行多个任务(宏观上, 微观上分时间片)
  • 线程 : 一个进程被划分成一些相互独立的任务, 每个运行着的独立任务称作线程
    • fork 派生线程, join合并线程, master线程控制整个程序逻辑, 比如线程的派生和合并

硬件级别的单核多线程

  • 细粒度 : 分时间片平均轮换执行各个线程
    • 优点 : 一个线程遇到阻塞时, 别的线程仍然可以继续执行
    • 缺点 : 当一个线程阻塞时, 并不能立刻切 换另外一个线程, 而是要等待它所分配的时间片时间结束. 造成了一定的资源浪费
    • 细粒度是相对的, 比之前的指令集还是要粗的
  • 粗粒度 : 不再分时间片, 只有当某个线程遇到较长时间阻塞时才切换另一个线程.
    • 优点 : 线程之间切换少了, 切换浪费的时间少了
    • 缺点 : 但是线程切换仍然需要浪费时间, 对于阻塞时间的判断也需要浪费一定时间
  • 同步多线程(SMY, 超线程) : 模拟多核, 让一个核同时(真正意义上的同时)运行多个线程. 通过分配计算资源, 让不同的计算资源运行不同的线程
    • 一个核上不会同时运行太多线程

Flynn分类法及相关概念

  • 计算机体系结构的分类
    • SISM : 单指令流 单数据流 (冯诺伊曼系统)
    • SIMD : 单指令流 多数据流
      • 对多个数据同时执行相同的指令. 一个控制单元对应多个计算单元
    • MISD : 多指令流 单数据流
      • 多个控制单元对应单个计算单元
    • MIMD : 多指令流 多数据流

SIMD

  • 将数据分配给多个处理单元, 对多组数据执行相同的指令; 数据并行

    • n个数据进行计算, m个算数逻辑单元, 一个控制单元, 将n个数据分配给m个算数逻辑单元同时进行运算.
  • 所有的计算单元执行相同的指令, 有些计算单元甚至虚啊哟空转

  • 这些计算单元必须同步操作, 计算快的需要等待

  • 计算单元没有指令存储功能

  • 适用于数据量大, 计算简单的并行问题, 并不适合于其余比较复杂的并行问题

SIMD的应用–向量处理器 和 GPU

  • 运行速度快
  • 易于使用

MIMD(共享内存, 分布式内存, 网络连接)

  • 由一些完全独立的处理单元或者核构成, 每一个核或者处理单元都有自己的控制单元和逻辑计算单元
  • SIMD同步执行, MIMD每一个处理器上有自己的时钟, 可以独立执行, 并不同步

共享内存系统

  • 一组自治的处理器通过一个互联网络与内存系统进行连接,
  • 每一个处理器可以访问内存中的每一块空间
  • 处理器之间通过共享数据进行隐式通信.
  • 包括一个或多个多核处理器
    在这里插入图片描述

一致内存访问(UMA)

  • 一般意义的共享内存系统
    在这里插入图片描述

非一致内存访问(NUMA)

  • 将每一个多核处理器连接特定的一块内存空间
  • 通过处理器中一种特殊的硬件, 互相通信, 从而间接访问所有内存.
  • 访问别的内存块时速度较慢
    在这里插入图片描述

分布式内存系统

  • 集群
  • 每一个CPU单独对应一个内存空间, 构成一节点, 节点之间通过一个互联网络相互连接.
    在这里插入图片描述

互联网络

共享内存的互联网络

  • 总线

    • 一条总线, 连接各个设备, 同一时刻总线只能被一个设备使用
    • 当设备数量增多时, 会设计总线争夺, 效率变低
    • 设计简单, 比较灵活, 成本低
  • 交叉开关矩阵(crossbar)

    • 多个cpu可以同时访问内存
    • 设计复杂, 灵活性差, 成本高
      在这里插入图片描述

分布式内存的互联网络

直接互联

- 每一个交换器直接连接一个处理器和内存, 交换器之间再互相连接
- ring(环) 和 torodal mesh(二维环形网格)
	- 缺点 : 两个处理器之间通信时, 需要占用别的额外的开关和链路. 

在这里插入图片描述

等分宽度

- 用来衡量一个互联网络连通性的标准(同时通信的链路数目)
- 把节点平分成两组, 看这两组之间同多少个可以同时通信的链路数目. 分组不同, 数目不同, **等分宽度取最小的那个.**
- **去除最少的链路数目, 使得所有节点均分成两份, 最少的链路数目即为等分宽度**
  • 二维网格的等分宽度 : 2根号p
  • 环状 : 2

带宽, 等分带宽

  • 带宽 : 链路上传输数据的速度, MB/s, Mb/s
  • 等分带宽 : 带宽 * 等分宽度, 用来衡量一个网络的数据传输速度

全相连的互联网络

  • 等分宽度 : p^2/4 (p/2 * p/2)
  • 造价太高, 现实不可能

超立方体互联网络 (Hypercubes)

在这里插入图片描述

  • 等分宽度 : p/2
    • 当p>4, 时超立方体的互联网络优于环和二维环形网格结构

间接互联

  • 需要许多交换器用来维护任意两个节点之间的通信
  • Crossbar
    • 之前讲的是共享内存系统, 处理器和内存块之间的互联结构
    • 现在是分布式内存系统, 节点(一个处理器对应一个内存块称为一对)之间的互联方式.
  • Omega network

延迟和带宽

  • 信息传输时间 = l + n / b
  • l : 延迟
  • n : 数据长度(字节)
  • b : 带宽

共享内存系统缓存一致性

  • 基于监听的缓存一致性协议 : 当共有变量被修改时, 需要在互联网络上进行一个广播, 别的核将该数据标记为非法, 待重新读取更改后数据时,才能继续执行后续步骤
  • 基于目录的缓存一致性协议 : 用一个目录存放每一个内存行的状态, 每一个高速缓存行的变更都会在目录中进行记录, 别的核在读取数据之前都会先查看目录.

并行算法设计(竞争条件, 数据依赖, 同步)

  • SPMD : 单程序 多数据流.

    • 只包含一份可执行代码, 通过一些分支语句, 表现的像在不同处理器上执行不同的程序.
    • 微观上看不同处理器执行不同的语句, 宏观上看, 执行同一个程序
  • 先设计串行算法, 然后将其 改为并行算法

    • 并不一定是最好的策略----有些情况下, 最优并行算法与最有串行算法之间完全没有关系
    • 但是是一个切实可行的方法

设计要求

  • 进程/线程 的任务分配
    • 负载均衡 : 每个进程/线程获得大致相同的工作量
    • 通信量尽量少
  • 安排进程/线程之间的同步
  • 安排进程/线程之间的通信

如何设计

  • 任务并行 : 输出的内容, 每一个任务需要用到所有数据

  • 数据并行 : 输入的数据, 每一个数据需要完成所有任务.

  • 混合并行 : 任务 + 数据 并行结合使用

  • 数据分解 : 每个任务的计算工作的结果对最终结果都有用, 都要全部昨晚

  • 搜索分解 : 一旦一个任务找到解, 全部任务即可停止, 工作量可能大于, 也可能小于串行算法.

概念定义

  • 原子性 : 一组操作要么全部执行, 要么全部不执行
  • 互斥 : 任何时刻都只有一个线程在执行
  • 竞争条件 : 执行结果依赖于两个或更多事件的时许
    • 多个进程/线程尝试更新同一个共享资源时, 结果可能是无法预测的.
  • 数据依赖 : 两个内存操作的序, 为了保证结果的正确性, 必须保持这个序
  • 同步 : 在时间上, 强制使各个进程/线程在某一点相互等待, 确保各进程/线程的正常顺序和对共享可写数据的正确访问.
  • 障碍 : 阻塞线程继续执行, 在此程序点等待, 直到所有参与线程都到达障碍点才继续执行

额外开销

  • 分配计算任务的额外带啊嘛
  • 锁开销 : 加锁/ 解锁操作本身开销和线程间竞争导致的空闲等待
  • 负载不均

并行算法性能分析(加速比, 效率, 可扩展性, 阿姆达尔定律)

  • 串行算法的评价 : 算法时间复杂度标示为输入规模的函数
  • 并行算法的评价 : 除了输入规模, 还要考虑处理器数目, 处理器相对运算速度, 通信速度.
  • 评价标准
    • 运行时间
    • 加速比 : 与最优串行算法做比较

性能评价标准

  • 运行时间

    • 串行时间 : Ts, 算法开始到结束的时间
    • 并行时间 : Tp, 并行算法开始到最后一个进程结束所经历的时间
  • 并行算法总额外开销

    • T0 = pTp- Ts
  • 加速比:

    • S = Ts/Tp
  • p为并行核数

    • 一般S<=p
    • S=p : 线性加速比
    • S>p : 超线性加速比, 在实践中可能出现

阿姆达尔定律

  • 除非一个串行程序的执行几乎全部都并行化, 否则不论多少可利用的核, 通过并行化产生的加速比都是会受限的.

  • 加速比只和a, p有关, 与串行时间无关
    在这里插入图片描述
    在这里插入图片描述

效率

  • 把核数引入了评价指标
    在这里插入图片描述

可扩展性

  • 强可扩展性 : 问题规模不变时, 效率不随着线程数的增大而降低. 则称程序时强可扩展的.

    • 只有程序全部并行化, 才能达到.
  • 弱可扩展的 : 问题规模以一定速率增大(退而求其次), 效率不随着线程数的增大而降低, 则称程序是弱可扩展的.

  • 可扩展的 : 程序核数增加, 如果在输入规模也以相应的增长率增加的情况下, 该程序效率不降 , 则称是可扩展的.

在这里插入图片描述

  • 可扩展性是高性能并行算法追求的主要目标
    • 度量并行系统性能的方法之一
    • 度量并行体系结构在不同系统规模下的并行处理能力
    • 度量并行算法内在的并行性
    • 利用系统规模和问题规模已知的并行系统性能来预测规模增大后的性能

上述评价指标针对的是MIMD(SPMD属于MIMD)

SIMD编程

SIMD编程的额外开销

打包/ 解包数据的开销

  • 打包---- 将数据拷贝到连续的内存区域, 然后读进向量寄存器
  • 解包 ---- 将数据对象从向量寄存器拷贝回内存中

除非数据本来就在连续内存, 否则打包/解包开销难以避免

对齐开销

  • 对齐的内存访问

    • 读取的起始地址总是向量长度的倍数(例如16字节, 128b)
      • 因此如果存储的数据不再向量长度的倍数位置, 则会额外读取一段, 在进行合并. 造成额外开销
  • 未对齐的内存访问

    • 地址不是16字节的倍数
    • 静态对齐: 对未对齐的毒操作, 做两次相邻的对齐毒操作, 然后进行合并.
    • 有时硬件会帮你做, 但仍然会产生多次内存操作.

在这里插入图片描述

在这里插入图片描述

控制流导致额外开销

  • 如果程序中有控制流变化, 就需要所有路径都执行. , 因此造成额外开销

在这里插入图片描述

  • 假定所有控制流路径执行频率都不同
  • 应该针对频率最高的路径优化代码
  • 其他路径按默认方式执行
    在这里插入图片描述

但是一般不知道每条路径的执行频率, 一般认为控制流程序不适合向量化

SIMD编程

  • SSE指令集 : 8个128位向量寄存器

在这里插入图片描述

  • 转秩, 缓存优化
    在这里插入图片描述

    在这里插入图片描述

  • 分块 进入Cache的次数 2n/T, 不分块是n+

Pthread编程

  • 伪共享 : 读取数据时,是一个缓存行一个缓存行的读取

    • 当多个处理器访问同一个缓存行时, 即使访问的是不同的机器字, 看起来也会有竞争条件. 会产生不必要的协同开销.
  • Pthread是POSIX标准

    • 相对底层
      • 程序员控制线程管理和协调
      • 程序员分解并行任务并管理任务调度
    • 可移植但比较慢

基础API

pthread_t 是一种Pthread编程中的数据类型
pthread_create(pthread_t *, const pthread_attr_t*, void*(*)(void*), void*);
- 第一个参数是线程id
- 第二个参数是各种属性, NULL表示默认属性值
- 第三个参数是线程要运行的函数(参数和返回值类型都是void*)
- 第四个参数是传递给要运行的函数的参数

	1. 主线程借助操作系统创建一个新线程
	2. 线程执行一个特定函数thread_fun
	3. 所有创建的线程执行相同的函数, 表示线程的计算任务分解
	4. 对于程序中不同线程执行不同任务的情况, 可以用创建线程时传递的参数区分线程的id, 以及其他线程的独特特性

int main()
{
   pthread_t threads[16];
   int tn;
   for(tn=0; tn < 16; tn++)
   {
   	pthread_create(&threads[tn], NULL, ParFun, NULL);  //执行ParFun函数
   }
   for(tn=0; tn < 16; tn++)
   {
   	pthread_join(threads[tn], NULL);
   }
   return 0;
}

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

void pthread_exit(void* value_ptr)
通过value_ptr返回结果给调用者

int pthread_cancel(pthread_t thread);
取消线程thread的执行

主线程使用pthread_cancel(thread);  
子线程使用pthread_testcancel()接收信号

同步相关概念

  • 临界区 : 一个更新共享资源的代码段, 一次只能允许一个线程执行该代码段
  • 原子性 : 一组操作要么全部执行, 要么全部不执行
  • 竞争条件 : 多个进程/线程尝试更新同一共享资源时, 结果可能是无法预测的, 则存在竞争条件
  • 数据依赖 : 两个内存操作的序, 为了保证结果的正确性, 必须保持这个序
  • 同步 : 在时间上, 使所有进程/线程强制在某一点必须相互等待, 确保进程/线程的正常顺序和对共享可写数据的正确访问

在这里插入图片描述

在这里插入图片描述

忙等待

在这里插入图片描述

互斥量

在这里插入图片描述
在这里插入图片描述

  • 忙等待和互斥量的区别

    • 互斥量是阻塞等待, 没有占用cpu资源. 而忙等待是依然占用cpu资源的.
    • 忙等待必须指定顺序, 依次执行临界区. 互斥量, 则是操作系统自行决定顺序.
  • 死锁

在这里插入图片描述

信号量同步

在这里插入图片描述
在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

路障(Barrier)

  • 线程数3, 表示当有3个线程到达路障时, 就不用再等待
    在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

条件变量

读写锁

  • 结点级锁
  • 对整个链表加锁
    • 额外开销太大
  • 读写锁

负载均衡 / 任务分配

  • 数据分布不均等且未知, 如果按照大块划分, 会造成划分任务时不均衡.

    • 动态任务分配, 每个线程一开始只分配一部分, 之后哪个线程先完成, 哪个线程继续取任务.
    • 动态划分的块也有讲究
  • 块划分

  • 二维划分

  • 高维划分

  • 循环划分

  • 随机块划分 – 稀疏矩阵
    在这里插入图片描述

总结

  • 优点
    • 支持多种语言
    • 之称的语言被程序员所熟悉
    • 数据共享方便
  • 缺点
    • 数据竞难发现

OpenMP

  • 通过少量编译指示指出并行部分和数据共享, 即可实现很多串行程序的并行化

  • 可以

    • 程序员只需要将程序分为串行和并行区域, 而不是构建并发执行的多线程
    • 隐藏栈管理
    • 提供同步机制
  • 不可以

    • 自动化并行
    • 确保加速
    • 避免数据竞争

编译指示

#pragma omp 
  • 共享数据 : 所有程序可见, 通常是具名的
  • 私有数据 : 单线程可见, 通常在栈中分配
shared 变量是共享的
private 变量是私有的
默认是shared
循环变量是private

#pragma omp parallel shared(bigdata) private(p)

条件编译
#ifdef _OPENMP
#include <omp.h>
#endif

任何使用编译指示的地方都需要这两个条件编译

int omp_get_num_threads(void);
返回当前并行区域的线程组中的线程数

int omp_get_thread_num(void);
返回当前线程在线程组中的编号, 主线程是0, 编号在0-omp_get_num_threads()-1之间

在这里插入图片描述

在这里插入图片描述

积分法求和

在这里插入图片描述

# pragma omp critical

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述
在这里插入图片描述

OpenMP 归约

在这里插入图片描述

  • **对for循环自动进行并行化. 默认块状划分 **
    在这里插入图片描述
    在这里插入图片描述

在这里插入图片描述

  • 第二个错了, 不能编译通过
  • 第一个错了, 可以编译通过, 但是结果会错误.
    在这里插入图片描述

在这里插入图片描述

  • 除非最开始出现, 后面紧接for循环
#pragma omp parallel for
否则可以不要parallel

一些定义, 定理

  • 计算等价
    • 相同的输入, 产生相同的输出(顺序也同)
  • 重排转换
    • 改变语句的执行顺序, 不增加或删除任何语句的执行
  • 一个重排转换保持依赖关系
    • 重排转换过程中保持了依赖源和目的语句的相对执行顺序

依赖关系基本定理

  • 任何重排转换, 只要保持了程序中所有依赖关系, 它就保持了程序的含义

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

  • 将# pragma omp paralle 提到最外层循环
  • pragma omp for 指针对没有循环依赖的内部两个循环

在这里插入图片描述

循环调度

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

MPI编程

  • 一个库
  • SPMD
  • 隔离了独立的地址空间
    • 不会有数据竞争, 但可能有通信错误
    • 编程复杂, 代码膨胀
    • 暴露了执行模型, 迫使程序员思考局部性, 亮点对性能都有好处
  • 所有通信, 同步都需要调用函数完成
    • 无共享变量

基本原语

MPI_Init(&argc, &argv); 初始化MPI
MPI_Finalize(); 结束MPI
MPI_Comm_size(MPI_COMM_WORLD, &myid)
查看进程数
MPI_Comm_rank(MPI_COMM_WORLD, &numprocs)
查看进程号

第二个参数是赋值操作

通信

在这里插入图片描述

在这里插入图片描述

  • 消息中的数据用三元组描述 : 地址, 个数, 类型
    在这里插入图片描述
    在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

阻塞通信模式

  • MPI有一个默认缓冲区, 执行Send时, 先将数据放入缓冲区, 只要缓冲区中的数据被发送完毕, 就认为发送完毕, 可以继续执行其余代码.

  • 接收方一定是等到数据全部接受完毕才执行其余代码

  • 缺点

    • 死锁

在这里插入图片描述
在这里插入图片描述

在这里插入图片描述

两种编程模型

  • 对等式
  • 主从式

在这里插入图片描述

组通信

  • 一个进程组内所有进程同时参加通信
  • 所有参与进程的函数调用形式一致
  • 三个功能 : 通信, 同步, 计算
  • 在组通信中不需要消息标志参数
  • 操作是成对的 : 互为逆操作

广播和归约

n-1 1-n

在这里插入图片描述
在这里插入图片描述

在这里插入图片描述

在这里插入图片描述
在这里插入图片描述

  • 先传播一行, 在一起扩展到其余行
    在这里插入图片描述

在这里插入图片描述

n-n

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述
在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

  • all归约, 最后每个节点结果相同
  • all-to-all归约, 每个节点结果不同
    在这里插入图片描述
    在这里插入图片描述

在这里插入图片描述

Scatter 和 Gather

在这里插入图片描述

非阻塞通信

  • 发送和接受数据的过程中, CPU可以执行别的事情.
  • 查询命令MPI_Wait 查看是否完成

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

  • 只是一个查询, 不满足也不会变阻塞.
    在这里插入图片描述

在这里插入图片描述
在这里插入图片描述

混合编程

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

在这里插入图片描述

版权声明:本文为weixin_40996518原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_40996518/article/details/108316248

智能推荐

使用欧几里得算法解决问题——求字符串的最大公因子(力扣第1071题)(JavaScript解法)

1、欧几里得算法的思想 基于辗转相除法的原理,具体做法:用较大数除以较小数,再用出现的余数(第一个余数)去除除数,,再用出现的余数(第二个余数)去除第一个余数,如此仿佛,直到最后一个余数为0 2、算法流程 3、JavaScript实现欧几里得算法 4、使用欧几里得算法解决问题 力扣1071字符串的最大公因子 题目描述: 对于字符串 S 和 T,只有在 S = T + … + T(T ...

spring与redis整合和序列化问题

spring与redis整合 首先用docker下载redis 下载:docker pull redis 运行:docker run -d -p 6379:6379 --name myredis docker.io/redis 连接redis Desktop Manager 然后开始在springboot上开始配置 application.yml: 自动配置好StringRedisTemplate...

CentOS 7配置南大docker镜像

文章目录 CentOS 7配置南大docker镜像 0.帮助页面 1.系统要求 2.卸载旧版本(没有旧版本可跳过) 3.安装方式 4.准备工作 5.可选操作 Stable Test Nightly 6.安装docker引擎 7. (可选)修改配置文件防止与xshell连接冲突 8.启动docker CentOS 7配置南大docker镜像 0.帮助页面 南大docker源:https://mirr...

Qcon演讲纪实:详解如何在实时视频通话中实现AR功能

2018年4月20日-22日,由 infoQ 主办的 Qcon 2018全球软件开发大会在北京如期举行。声网首席 iOS 研发工程师,iOS 端移动应用产品设计和技术架构负责人龚宇华,受邀分享了《基于 ARkit 和 ARcore,在实时视频通话中实现 AR 功能》,在演讲中剖析了 AR 与 VR 差异,ARKit 的工作原理,以及逐步讲解如何基于 ARKit 与声网Agora SDK 创建 AR...

POJ2348 UVa10368 HDU1525 Euclid's Game【博弈】

Euclid's GameTime Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 4106    Accepted Submission(s): 1947 Probl...

猜你喜欢

使用Breeze.js编写更好的查询

这篇文章是由同行评审Agbonghama柯林斯 。 感谢所有SitePoint的审稿作出SitePoint内容也可以是最好的! 数据量正在迅速发展,他们正在变得越来越复杂,维护。 许多开发人员希望避免由数据问题他们的工作过程中造成的问题和头痛。 一个使我们的工作更轻松的图书馆是Breeze.js 。 在这篇文章中,我们将讨论我们如何能够写出更好的查询与Breeze.js。 但是首先,我们应该知道什...

Netty框架构建Nio编程

~~~ 随手点赞,养成习惯 ~~~ 为什么选择Netty框架 Netty是业界最流行的NIO框架之一,它的健壮性、功能、性能、可定制性和可扩展性在同类框架中都是首屈一指的。 优点: ① API使用简单,开发门槛低 ②功能强大,预置了多种编解码功能,支持多种主流协议 ③ 定制能力强,可以通过ChannelHandler对通信框架进行灵活地扩展; ④性能高,通过与其他业界主流的NIO框架对比,Nett...

【JZOJ5262】【GDOI2018模拟8.12】树(DP,性质题)

Description Solution 首先我们可以知道两个性质:1、路径u-v和路径v-w可以合并为路径u-w;2、路径u1-v1加路径u2-v2和路径u1-v2加路径u2-v1是等价的(就是起始点和终点可以互换) 那么知道这些性质之后就很好做了。我们只用知道每个点多少次做起点和多少次做终点。 我们设f[i]表示满足i子树的需求i上的值要是多少。 那么枚举i的所有儿子,判断a[i]-f[i],...

【String-easy】541. Reverse String II 反转的元素,有反转个数和间隔

1. 题目原址 https://leetcode.com/problems/reverse-string-ii/ 2. 题目描述 3. 题目大意 给定一个字符串,和字符串的间隔k, 这个k表示每k个数反转一次,然后再间隔k个元素再反转k个元素。 4. 解题思路 只要按照间隔去反转就可以了。然后间隔k个元素不反转是通过让i每次递增 2*k完成的。 5. AC代码 6. 相似题型 【1】344. Re...

【C语言笔记结构体】

我们都知道C语言中变量的类型决定了变量存储占用的空间。当我们要使用一个变量保存年龄时可以将其声明为int类型,当我们要使用一个变量保存某一科目的考试成绩时可以将其声明为float。 那么,当我们要做一个学生信息管理系统时,需要保存学生的姓名、学号、年龄等信息,该怎么做呢? 如当要保存三个学生的信息时, 方法一是: 方法二是: 显然,方法二跟更清晰,因为它把name、num、age都集成在一个模板,...