建立企业网站的形式有,河南省建设厅网站门户,in word in the wordpress,买个人家的网站绑定自己的域名前言
我们往往都希望优化我们的程序#xff0c;使之达到一个更好的效果#xff0c;程序优化的一个重点就是速度#xff0c;加快速度的一个好办法就是使用并行技术#xff0c;但是#xff0c;并行时我们要考虑必须串行执行的任务#xff0c;也就是有依赖关系的任务#…前言
我们往往都希望优化我们的程序使之达到一个更好的效果程序优化的一个重点就是速度加快速度的一个好办法就是使用并行技术但是并行时我们要考虑必须串行执行的任务也就是有依赖关系的任务任务中的重点往往是具体的数据这些任务中的数据通常具有局部性和关联性。
而数据中数组具有代表性现在让笔者从数组开始谈谈程序数据的优化。
从数据的存储内存开始
我们都知道计算机的基本内存结构如下 #mermaid-svg-EMPvLuYQyarcCgR4 {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-EMPvLuYQyarcCgR4 .error-icon{fill:#552222;}#mermaid-svg-EMPvLuYQyarcCgR4 .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-EMPvLuYQyarcCgR4 .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-EMPvLuYQyarcCgR4 .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-EMPvLuYQyarcCgR4 .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-EMPvLuYQyarcCgR4 .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-EMPvLuYQyarcCgR4 .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-EMPvLuYQyarcCgR4 .marker{fill:#333333;stroke:#333333;}#mermaid-svg-EMPvLuYQyarcCgR4 .marker.cross{stroke:#333333;}#mermaid-svg-EMPvLuYQyarcCgR4 svg{font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-EMPvLuYQyarcCgR4 .label{font-family:"trebuchet ms",verdana,arial,sans-serif;color:#333;}#mermaid-svg-EMPvLuYQyarcCgR4 .cluster-label text{fill:#333;}#mermaid-svg-EMPvLuYQyarcCgR4 .cluster-label span{color:#333;}#mermaid-svg-EMPvLuYQyarcCgR4 .label text,#mermaid-svg-EMPvLuYQyarcCgR4 span{fill:#333;color:#333;}#mermaid-svg-EMPvLuYQyarcCgR4 .node rect,#mermaid-svg-EMPvLuYQyarcCgR4 .node circle,#mermaid-svg-EMPvLuYQyarcCgR4 .node ellipse,#mermaid-svg-EMPvLuYQyarcCgR4 .node polygon,#mermaid-svg-EMPvLuYQyarcCgR4 .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-EMPvLuYQyarcCgR4 .node .label{text-align:center;}#mermaid-svg-EMPvLuYQyarcCgR4 .node.clickable{cursor:pointer;}#mermaid-svg-EMPvLuYQyarcCgR4 .arrowheadPath{fill:#333333;}#mermaid-svg-EMPvLuYQyarcCgR4 .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-EMPvLuYQyarcCgR4 .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-EMPvLuYQyarcCgR4 .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-EMPvLuYQyarcCgR4 .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-EMPvLuYQyarcCgR4 .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-EMPvLuYQyarcCgR4 .cluster text{fill:#333;}#mermaid-svg-EMPvLuYQyarcCgR4 .cluster span{color:#333;}#mermaid-svg-EMPvLuYQyarcCgR4 div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-EMPvLuYQyarcCgR4 :root{--mermaid-font-family:"trebuchet ms",verdana,arial,sans-serif;} 处理器 cache高速缓存 多层cache 总线 内存 而内存的结构又可以继续划分 #mermaid-svg-RJXE9Vbu9Vay5WGi {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-RJXE9Vbu9Vay5WGi .error-icon{fill:#552222;}#mermaid-svg-RJXE9Vbu9Vay5WGi .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-RJXE9Vbu9Vay5WGi .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-RJXE9Vbu9Vay5WGi .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-RJXE9Vbu9Vay5WGi .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-RJXE9Vbu9Vay5WGi .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-RJXE9Vbu9Vay5WGi .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-RJXE9Vbu9Vay5WGi .marker{fill:#333333;stroke:#333333;}#mermaid-svg-RJXE9Vbu9Vay5WGi .marker.cross{stroke:#333333;}#mermaid-svg-RJXE9Vbu9Vay5WGi svg{font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-RJXE9Vbu9Vay5WGi .label{font-family:"trebuchet ms",verdana,arial,sans-serif;color:#333;}#mermaid-svg-RJXE9Vbu9Vay5WGi .cluster-label text{fill:#333;}#mermaid-svg-RJXE9Vbu9Vay5WGi .cluster-label span{color:#333;}#mermaid-svg-RJXE9Vbu9Vay5WGi .label text,#mermaid-svg-RJXE9Vbu9Vay5WGi span{fill:#333;color:#333;}#mermaid-svg-RJXE9Vbu9Vay5WGi .node rect,#mermaid-svg-RJXE9Vbu9Vay5WGi .node circle,#mermaid-svg-RJXE9Vbu9Vay5WGi .node ellipse,#mermaid-svg-RJXE9Vbu9Vay5WGi .node polygon,#mermaid-svg-RJXE9Vbu9Vay5WGi .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-RJXE9Vbu9Vay5WGi .node .label{text-align:center;}#mermaid-svg-RJXE9Vbu9Vay5WGi .node.clickable{cursor:pointer;}#mermaid-svg-RJXE9Vbu9Vay5WGi .arrowheadPath{fill:#333333;}#mermaid-svg-RJXE9Vbu9Vay5WGi .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-RJXE9Vbu9Vay5WGi .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-RJXE9Vbu9Vay5WGi .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-RJXE9Vbu9Vay5WGi .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-RJXE9Vbu9Vay5WGi .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-RJXE9Vbu9Vay5WGi .cluster text{fill:#333;}#mermaid-svg-RJXE9Vbu9Vay5WGi .cluster span{color:#333;}#mermaid-svg-RJXE9Vbu9Vay5WGi div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-RJXE9Vbu9Vay5WGi :root{--mermaid-font-family:"trebuchet ms",verdana,arial,sans-serif;} 速度从慢到快 虚拟内存-磁盘 物理内存 二级cache 一级cache 寄存器 虚拟内存是一个很伟大的发明它借助内存管理单元MMU并利用分页机制将磁盘的一部分模拟为内存使用。它允许计算机使用硬盘空间来扩展实际的物理内存。这使得操作系统能够运行超过实际物理内存容量的程序。
而我们重点关注的地方在cache这里。
cache命中率
cache会从更低一级的内存结构中搬数据如果数据访问是局部性很强如访问同一数据块多次则缓存命中率会较高如果不命中那么计算机会跑到下一级内存中寻找数据这样程序运行效率就会非常低。
优化
得知了这一点后我们可以考虑改善我们的程序写法了以数组操作为例
for(int i 0; i 2; i){for(int j i; j 2; j)Z[j][i] 0;
}在C语言中二维数组的内存分布通常是按行优先Row-major order存储的这意味着数组的行是连续存储在内存中的。具体来说对于一个二维数组 Z其内存布局是按以下方式排列的
二维数组的内存分布
假设我们有一个二维数组 Z其大小为 m 行 n 列。数组元素在内存中的排列顺序如下
Z[0][0], Z[0][1], ..., Z[0][n-1], Z[1][0], Z[1][1], ..., Z[1][n-1], ..., Z[m-1][0], ..., Z[m-1][n-1]每一行的元素是连续存储的然后依次存储下一行的元素。
那么优化后的遍历方法如下
for (int j 0; j 2; j) {for (int i 0; i j; i) {Z[j][i] 0;}
}上面的优化方法相信大家都能琢磨出来但是如果稍微改一下呢
for(int i 0; i 5; i){for(int j i; j 7; j)Z[j][i] 0;
}按照原程序的遍历
┌─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┐
│ 0,0 │ 1,0 │ 2,0 │ 3,0 │ 4,0 │ 5,0 │ 6,0 │ 7,0 │
│ │ 1,1 │ 2,1 │ 3,1 │ 4,1 │ 5,1 │ 6,1 │ 7,1 │
│ │ │ 2,2 │ 3,2 │ 4,2 │ 5,2 │ 6,2 │ 7,2 │
│ │ │ │ 3,3 │ 4,3 │ 5,3 │ 6,3 │ 7,3 │
│ │ │ │ │ 4,4 │ 5,4 │ 6,4 │ 7,4 │
│ │ │ │ │ │ 5,5 │ 6,5 │ 7,5 │
│ │ │ │ │ │ │ 6,6 │ 7,6 │
│ │ │ │ │ │ │ │ 7,7 │
└─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┘
更好的遍历方法
┌─────┬─────┬─────┬─────┬─────┬─────
│ 0,0 │
│ 1,0 │ 1,1 │
│ 2,0 │ 2,1 │ 2,2 │
│ 3,0 │ 3,1 │ 3,2 │ 3,3 │
│ 4,0 │ 4,1 │ 4,2 │ 4,3 │ 4,4 │
│ 5,0 │ 5,1 │ 5,2 │ 5,3 │ 5,4 │ 5,5
| 6,0 | 6,1 | 6,2 | 6,3 | 6,4 | 6,5
| 7,0 | 7,1 | 7,2 | 7,3 | 7,4 | 7,5
└─────┴─────┴─────┴─────┴─────┴─────
局部性更好的程序如下此时想要一眼看出来这样写就有点困难了那我们要怎么推导数组的遍历式呢
for (int j 0; j 7; j) {for (int i 0; i (j 5 ? j : 5); i) {Z[j][i] 0;}
}
引入线性代数
我们先看看各种值的范围
i的范围: i0, i5
j的范围: ji, j7尝试把它们写成线性方程
1*i 0*j 0 0
-1*i 0*j 5 0-1*i j 0 0
0*i -1*j 7 0
矩阵如下
| 1 0 | | i | | 0 |
| -1 0 | * | j | | -5 |
| -1 1 | | 0 |
| 0 -1 | | -7 |
现在我们得到了矩阵我们可以进一步得到多面体先回顾一下矩阵与多面体的关系
线性约束表示多面体
多面体可以通过一组线性不等式来定义这些不等式可以表示为矩阵和向量的形式。例如对于一个包含 n个变量的多面体可以用一个 m×n 的矩阵A和一个m维的向量 b来表示
Ax b
其中x是变量向量约束条件定义了多面体的边界。
顶点表示
多面体的顶点可以通过求解线性方程组通常涉及矩阵的逆或者伪逆来获得。这些顶点是满足约束条件的解。
矩阵操作多面体
线性变换
通过矩阵乘法可以对多面体进行线性变换如旋转、缩放、平移等。例如如果矩阵M描述了一个线性变换那么多面体中的每一个点 x在变换后的新位置可以表示为Mx。
仿射变换
仿射变换是线性变换的推广包括线性变换和平移。可以用如下形式表示
yMxt
其中MM 是线性变换矩阵t是平移向量。
好吧其实矩阵和多面体与接下来要讲的算法也没多大关系笔者只是想说明如何从不等式推导到线性代数并扩展到多面体和高维空间体的。
使用Fourier-Motzkin算法
Fourier-Motzkin算法是一种经常在多面体中用于求解线性不等式系统的消去算法概括如下
选择消去变量 选择一个变量 xi作为消去变量。
分类不等式 将所有不等式分为三类
包含 Xi的不等式且 Xi的系数为正。包含 Xi的不等式且 Xi的系数为负。不包含 Xi的不等式。
生成新不等式 通过将第一类不等式和第二类不等式配对消去 Xi
组合不等式 将生成的新不等式与不包含 xi的不等式组合得到一个新的线性不等式系统。
重复步骤 对新的线性不等式系统重复上述步骤直到所有变量都被消去。
应用该算法我们重新得到范围
0j, 0 5
j7那么i和j的范围如下
L(i):0
U(i):5,jL(i):0
U(J):7有了这个范围我们可以得到
for (int j 0; j 7; j) {for (int i 0; i min(5,j); i) {Z[j][i] 0;}
}也就是
for (int j 0; j 7; j) {for (int i 0; i (j 5 ? j : 5); i) {Z[j][i] 0;}
}总结
从程序中的优化出发由程序存储引出cache再由cache命中率引出数据局部性的重要性为了提高数据局部性必须改变循环遍历方法。为了改变循环遍历方法由不等式引出线性代数再由线性代数引出多面体最后使用算法计算约束得到具有良好局部性的程序。 其实没啥好总结的只写了一小段还没写完开头呢不过先更到这该上床睡觉了。
