使用缩小增量法改善 “数组_排序1” 的性能

zainex

数组_排序1 是精易模块中提供的文本排序功能，与 数组_排序 不同的是，它采用了 StrCmpLogicalW 进行文本比较，因此排序效果会更优。

不过由于其内部采用了选择排序，因此除了小规模数组（10~100个元素），运行起来是相当的慢：

  

子程序名	返回值类型	公开	备 注
数组_排序1			通过对字符串逻辑比较后的排序
参数名	类 型	参考	可空	数组	备 注
排序数组	文本型
从大到小	逻辑型

变量名	类 型	静态	数组	备 注
dwCount	整数型
szBuf1	字节集
szBuf2	字节集
pBuffer	整数型
psz1	整数型
psz2	整数型
i	整数型
n	整数型
j	整数型

dwCount ＝ 取数组成员数 (排序数组)
pBuffer ＝ 取数据_通用型_数组 (排序数组)
计次循环首 (dwCount, i)
n ＝ i
计次循环首 (dwCount － i, j)
szBuf1 ＝ 编码_Ansi到Unicode (排序数组 [n], )
szBuf2 ＝ 编码_Ansi到Unicode (排序数组 [i ＋ j], )
如果 (从大到小)
如果真 (StrCmpLogicalW (szBuf1, szBuf2) ＜ 0)
n ＝ i ＋ j

如果真 (StrCmpLogicalW (szBuf1, szBuf2) ＞ 0)
n ＝ i ＋ j


计次循环尾 ()
如果真 (n ≠ i)
psz1 ＝ __get (pBuffer, (n － 1) × 4)
psz2 ＝ __get (pBuffer, (i － 1) × 4)
__set (pBuffer, (n － 1) × 4, psz2)
__set (pBuffer, (i － 1) × 4, psz1)

计次循环尾 ()

.版本 2<br /> <br /> .子程序 数组_排序1, , 公开, 通过对字符串逻辑比较后的排序<br /> .参数 排序数组, 文本型, 数组<br /> .参数 从大到小, 逻辑型, 可空<br /> .局部变量 dwCount, 整数型<br /> .局部变量 szBuf1, 字节集<br /> .局部变量 szBuf2, 字节集<br /> .局部变量 pBuffer, 整数型<br /> .局部变量 psz1, 整数型<br /> .局部变量 psz2, 整数型<br /> .局部变量 i, 整数型<br /> .局部变量 n, 整数型<br /> .局部变量 j, 整数型<br /> <br /> dwCount ＝ 取数组成员数 (排序数组)<br /> pBuffer ＝ 取数据_通用型_数组 (排序数组)<br /> .计次循环首 (dwCount, i)<br />     n ＝ i<br />     .计次循环首 (dwCount － i, j)<br />         szBuf1 ＝ 编码_Ansi到Unicode (排序数组 [n], )<br />         szBuf2 ＝ 编码_Ansi到Unicode (排序数组 [i ＋ j], )<br />         .如果 (从大到小)<br />             .如果真 (StrCmpLogicalW (szBuf1, szBuf2) ＜ 0)<br />                 n ＝ i ＋ j<br />             .如果真结束<br /> <br />         .否则<br />             .如果真 (StrCmpLogicalW (szBuf1, szBuf2) ＞ 0)<br />                 n ＝ i ＋ j<br />             .如果真结束<br /> <br />         .如果结束<br /> <br />     .计次循环尾 ()<br />     .如果真 (n ≠ i)<br />         psz1 ＝ __get (pBuffer, (n － 1) × 4)<br />         psz2 ＝ __get (pBuffer, (i － 1) × 4)<br />         __set (pBuffer, (n － 1) × 4, psz2)<br />         __set (pBuffer, (i － 1) × 4, psz1)<br />     .如果真结束<br /> <br /> .计次循环尾 ()

为了提高排序性能，可以用其它更高效的排序算法来代替其中的选择排序算法，这里的替代方案是希尔排序（又称缩小增量法）：

  

子程序名	返回值类型	公开	备 注
数组_排序1_改
参数名	类 型	参考	可空	数组	备 注
数组	文本型
从大到小	逻辑型

变量名	类 型	静态	数组	备 注
平行数组	字节集		0
长度	整数型
数	整数型
增量	整数型
元素	字节集
项目	文本型
起点	整数型
值	整数型
顺序	整数型

顺序 ＝ -1
如果真 (从大到小)
顺序 ＝ 1
重定义数组 (平行数组, 假, 取数组成员数 (数组))
计次循环首 (取数组成员数 (平行数组), 数)
长度 ＝ MultiByteToWideChar (936, 0, 取变量数据地址 (数组 [数]), -1, 0, 0)
平行数组 [数] ＝ 取空白字节集 ( (长度 ＋ 1) × 2)
MultiByteToWideChar (936, 0, 取变量数据地址 (数组 [数]), -1, 取变量数据地址 (平行数组 [数]), 长度)
计次循环尾 ()
增量 ＝ 0
判断循环首 (增量 ＜ 取数组成员数 (数组))
增量 ＝ 增量 × 3 ＋ 1
判断循环尾 ()
判断循环首 (增量 ≠ 0)
增量 ＝ 增量 ÷ 3
变量循环首 (增量 ＋ 1, 取数组成员数 (数组), 1, 数)
元素 ＝ 平行数组 [数]
项目 ＝ 数组 [数]
起点 ＝ 数 － 增量
值 ＝ 起点
判断循环首 (值 ≥ 1)
如果 (StrCmpLogicalW (元素, 平行数组 [值]) ＝ 顺序)
数组 [值 ＋ 增量] ＝ 数组 [值]
平行数组 [值 ＋ 增量] ＝ 平行数组 [值]
跳出循环 ()
值 ＝ 值 － 增量
判断循环尾 ()
如果真 (值 ≠ 起点)
数组 [值 ＋ 增量] ＝ 项目
平行数组 [值 ＋ 增量] ＝ 元素

变量循环尾 ()
判断循环尾 ()

i支持库列表	支持库注释
spec	特殊功能支持库

.版本 2<br /> .支持库 spec<br /> <br /> .子程序 数组_排序1_改<br /> .参数 数组, 文本型, 数组<br /> .参数 从大到小, 逻辑型, 可空<br /> .局部变量 平行数组, 字节集, , "0"<br /> .局部变量 长度, 整数型<br /> .局部变量 数, 整数型<br /> .局部变量 增量, 整数型<br /> .局部变量 元素, 字节集<br /> .局部变量 项目, 文本型<br /> .局部变量 起点, 整数型<br /> .局部变量 值, 整数型<br /> .局部变量 顺序, 整数型<br /> <br /> 顺序 ＝ -1<br /> .如果真 (从大到小)<br />     顺序 ＝ 1<br /> .如果真结束<br /> 重定义数组 (平行数组, 假, 取数组成员数 (数组))<br /> .计次循环首 (取数组成员数 (平行数组), 数)<br />     长度 ＝ MultiByteToWideChar (936, 0, 取变量数据地址 (数组 [数]), -1, 0, 0)<br />     平行数组 [数] ＝ 取空白字节集 ((长度 ＋ 1) × 2)<br />     MultiByteToWideChar (936, 0, 取变量数据地址 (数组 [数]), -1, 取变量数据地址 (平行数组 [数]), 长度)<br /> .计次循环尾 ()<br /> 增量 ＝ 0<br /> .判断循环首 (增量 ＜ 取数组成员数 (数组))<br />     增量 ＝ 增量 × 3 ＋ 1<br /> .判断循环尾 ()<br /> .判断循环首 (增量 ≠ 0)<br />     增量 ＝ 增量 ÷ 3<br />     .变量循环首 (增量 ＋ 1, 取数组成员数 (数组), 1, 数)<br />         元素 ＝ 平行数组 [数]<br />         项目 ＝ 数组 [数]<br />         起点 ＝ 数 － 增量<br />         值 ＝ 起点<br />         .判断循环首 (值 ≥ 1)<br />             .如果 (StrCmpLogicalW (元素, 平行数组 [值]) ＝ 顺序)<br />                 数组 [值 ＋ 增量] ＝ 数组 [值]<br />                 平行数组 [值 ＋ 增量] ＝ 平行数组 [值]<br />             .否则<br />                 跳出循环 ()<br />             .如果结束<br />             值 ＝ 值 － 增量<br />         .判断循环尾 ()<br />         .如果真 (值 ≠ 起点)<br />             数组 [值 ＋ 增量] ＝ 项目<br />             平行数组 [值 ＋ 增量] ＝ 元素<br />         .如果真结束<br /> <br />     .变量循环尾 ()<br /> .判断循环尾 ()

与其它O(nlogn)排序算法相比，希尔排序通常只慢一半，也就是说你用快速排序只需1秒完成的排序，那用希尔排序也就2秒左右，考虑到O(nlogn)算法通常需要O(n)左右的辅助空间，希尔排序则只有O(1)，相当于用时间换了空间。
另外希尔排序还有易于实现优点，通过观察上面提供的代码，很容易发现，基本上在插入排序外面套个缩小增量的循环就算完成了。
当然 增量序列 的选择也很重要（会直接影响其性能），上面采用的序列由高德纳（Knuth）在1969年提出，因此可以被称为高德纳序列。

采用上面的替代方案后，性能已经明显优于原始的 数组_排序1 以及 数组_排序，但它存在一个潜在问题会拖累排序的性能，你发现了吗？

这个问题是非基本类型变量（如字节集、文本型）的释放问题，在子程序调用结束前，程序内部会对会对所有需要释放的非基本类型变量进行释放，它的表现是需要释放的非基本类型变量越多，释放的整个过程就会越长，也就是越耗时。这个问题会随着用来排序的数组元素增多，而越发明显。

为了解决这个问题，我们可以通过避免使用非基本类型来做到：

  

子程序名	返回值类型	公开	备 注
数组_排序1_甲
参数名	类 型	参考	可空	数组	备 注
数组	文本型
从大到小	逻辑型

变量名	类 型	静态	数组	备 注
长度	整数型
数	整数型
增量	整数型
元素	整数型
项目	整数型
起点	整数型
值	整数型
地址	整数型
索引	整数型
缓存	整数型
偏移	整数型
顺序	整数型

顺序 ＝ -1
如果真 (从大到小)
顺序 ＝ 1
索引 ＝ 申请内存 (取数组成员数 (数组) × 4, )
长度 ＝ 0
计次循环首 (取数组成员数 (数组), 数)
长度 ＝ 长度 ＋ MultiByteToWideChar (936, 0, 取变量数据地址 (数组 [数]), -1, 0, 0) ＋ 1
计次循环尾 ()
缓存 ＝ 申请内存 (长度 × 2, )
偏移 ＝ 缓存
计次循环首 (取数组成员数 (数组), 数)
长度 ＝ MultiByteToWideChar (936, 0, 取变量数据地址 (数组 [数]), -1, 0, 0) × 2
MultiByteToWideChar (936, 0, 取变量数据地址 (数组 [数]), -1, 偏移, 长度)
__set (索引, (数 － 1) × 4, 偏移)
偏移 ＝ 偏移 ＋ 长度
计次循环尾 ()
地址 ＝ 取变量数据地址 (数组)
增量 ＝ 0
判断循环首 (增量 ＜ 取数组成员数 (数组))
增量 ＝ 增量 × 3 ＋ 1
判断循环尾 ()
判断循环首 (增量 ≠ 0)
增量 ＝ 增量 ÷ 3
变量循环首 (增量, 取数组成员数 (数组) － 1, 1, 数)
元素 ＝ __get (索引, 数 × 4)
项目 ＝ __get (地址, 数 × 4)
起点 ＝ 数 － 增量
值 ＝ 起点
判断循环首 (值 ≥ 0)
如果 (_StrCmpLogicalW (元素, __get (索引, 值 × 4)) ＝ 顺序)
__set (地址, (值 ＋ 增量) × 4, __get (地址, 值 × 4))
__set (索引, (值 ＋ 增量) × 4, __get (索引, 值 × 4))
跳出循环 ()
值 ＝ 值 － 增量
判断循环尾 ()
如果真 (值 ≠ 起点)
__set (地址, (值 ＋ 增量) × 4, 项目)
__set (索引, (值 ＋ 增量) × 4, 元素)

变量循环尾 ()
判断循环尾 ()
释放内存 (索引)
释放内存 (缓存)

i支持库列表	支持库注释
spec	特殊功能支持库

.版本 2<br /> .支持库 spec<br /> <br /> .子程序 数组_排序1_甲<br /> .参数 数组, 文本型, 数组<br /> .参数 从大到小, 逻辑型, 可空<br /> .局部变量 长度, 整数型<br /> .局部变量 数, 整数型<br /> .局部变量 增量, 整数型<br /> .局部变量 元素, 整数型<br /> .局部变量 项目, 整数型<br /> .局部变量 起点, 整数型<br /> .局部变量 值, 整数型<br /> .局部变量 地址, 整数型<br /> .局部变量 索引, 整数型<br /> .局部变量 缓存, 整数型<br /> .局部变量 偏移, 整数型<br /> .局部变量 顺序, 整数型<br /> <br /> 顺序 ＝ -1<br /> .如果真 (从大到小)<br />     顺序 ＝ 1<br /> .如果真结束<br /> 索引 ＝ 申请内存 (取数组成员数 (数组) × 4, )<br /> 长度 ＝ 0<br /> .计次循环首 (取数组成员数 (数组), 数)<br />     长度 ＝ 长度 ＋ MultiByteToWideChar (936, 0, 取变量数据地址 (数组 [数]), -1, 0, 0) ＋ 1<br /> .计次循环尾 ()<br /> 缓存 ＝ 申请内存 (长度 × 2, )<br /> 偏移 ＝ 缓存<br /> .计次循环首 (取数组成员数 (数组), 数)<br />     长度 ＝ MultiByteToWideChar (936, 0, 取变量数据地址 (数组 [数]), -1, 0, 0) × 2<br />     MultiByteToWideChar (936, 0, 取变量数据地址 (数组 [数]), -1, 偏移, 长度)<br />     __set (索引, (数 － 1) × 4, 偏移)<br />     偏移 ＝ 偏移 ＋ 长度<br /> .计次循环尾 ()<br /> 地址 ＝ 取变量数据地址 (数组)<br /> 增量 ＝ 0<br /> .判断循环首 (增量 ＜ 取数组成员数 (数组))<br />     增量 ＝ 增量 × 3 ＋ 1<br /> .判断循环尾 ()<br /> .判断循环首 (增量 ≠ 0)<br />     增量 ＝ 增量 ÷ 3<br />     .变量循环首 (增量, 取数组成员数 (数组) － 1, 1, 数)<br />         元素 ＝ __get (索引, 数 × 4)<br />         项目 ＝ __get (地址, 数 × 4)<br />         起点 ＝ 数 － 增量<br />         值 ＝ 起点<br />         .判断循环首 (值 ≥ 0)<br />             .如果 (_StrCmpLogicalW (元素, __get (索引, 值 × 4)) ＝ 顺序)<br />                 __set (地址, (值 ＋ 增量) × 4, __get (地址, 值 × 4))<br />                 __set (索引, (值 ＋ 增量) × 4, __get (索引, 值 × 4))<br />             .否则<br />                 跳出循环 ()<br />             .如果结束<br />             值 ＝ 值 － 增量<br />         .判断循环尾 ()<br />         .如果真 (值 ≠ 起点)<br />             __set (地址, (值 ＋ 增量) × 4, 项目)<br />             __set (索引, (值 ＋ 增量) × 4, 元素)<br />         .如果真结束<br /> <br />     .变量循环尾 ()<br /> .判断循环尾 ()<br /> 释放内存 (索引)<br /> 释放内存 (缓存)

上面的代码直接取消了平行数组，取而代之的是 缓存 + 索引 的方案，对于必须分配的内存，全部采用手工申请与释放。

看到这里一般就算结束了，但它其实还有改进空间，上面的代码使用了 __set __get 来直接操作元素的指针，这虽然有效的避免了潜在的非基本类型变量的产生，但这也会使整个排序过程中产生大量的子程序调用，如果我们能消除这些调用，显然可以带来性能的提升。

在别的一些编程语言当中，通常会提供一种叫做内联函数的功能，以消除函数的调用开销，但易语言并不都支持此项功能，因此我们需要另辟蹊径，比如用 置入代码 来做的这点。


置入代码 置入的是机器码，也就是可以运行的机器代码，它由CPU指令集中的二进制指令组成。
这些指令可以通过官方公开的手册查询，比如我们可以通过英特尔架构手册第二卷的附录B（指令格式与编码）查看各种指令的二进制表示：


当你按照这些手册中指令描述，只用数字零和一，一点点的打到二进制编辑器里，实际上进行的正是机器语言编程。

当然通常我们不会这样做，而是使用汇编代码，让汇编器转换出机器代码，然后加到 置入代码 中。

汇编代码可以是手写的，也可以生成的，从未使用过其它编程语言的朋友可能会以为编译器只能生成exe，而事实上有一些编译器也能输出汇编代码。
比如在使用 GCC 编译器时，加上 -S 参数，它就会输出汇编代码。

因为像 GCC 这样的编译器可以产生质量高于易语言的机器代码，所以有时会采用 其它编译器（如GCC） -> 汇编代码 -> 汇编器 -> 置入代码 的方式将高质量代码加入易语言当中，来改善其性能。

那什么时候会选择手写汇编呢？在即使是手写汇编，工作量也不大的时候（一般不超过100行汇编代码），会考虑使用手工编写。
比如我们之前提到的，希尔排序易于实现，因此即使是手写汇编也不会超过100行：

  

子程序名	返回值类型	公开	备 注
希尔排序_汇编
参数名	类 型	参考	可空	数组	备 注
数组地址	整数型
数组长度	整数型
索引地址	整数型
比较函数地址	子程序指针
从大到小	整数型

置入代码 ({ 131, 236, 16, 139, 116, 36, 32, 139, 124, 36, 24, 49, 237, 235, 4, 107, 237, 3, 69, 59, 108, 36, 28, 124, 246, 235, 92, 139, 12, 134, 139, 20, 135, 137, 12, 36, 137, 84, 36, 8, 137, 68, 36, 12, 137, 195, 41, 235, 235, 17, 141, 4, 43, 139, 12, 158, 139, 20, 159, 137, 12, 134, 137, 20, 135, 41, 235, 131, 251, 0, 124, 20, 139, 4, 158, 137, 68, 36, 4, 255, 84, 36, 36, 131, 236, 8, 59, 68, 36, 40, 116, 214, 141, 4, 43, 139, 12, 36, 139, 84, 36, 8, 137, 12, 134, 137, 20, 135, 139, 68, 36, 12, 64, 59, 68, 36, 28, 124, 164, 49, 210, 137, 232, 185, 3, 0, 0, 0, 247, 249, 137, 197, 133, 237, 117, 233, 131, 196, 16, 93, 194, 20, 0 })
' sub esp, 16
' mov esi, [esp+16+16]
' mov edi, [esp+16+8]
' xor ebp, ebp
' jmp L7
' L8:
' imul ebp, 3
' inc ebp
' L7:
' cmp ebp, [esp+16+12]
' jl L8
' jmp L6
' L4:
' mov ecx, [esi+eax*4]
' mov edx, [edi+eax*4]
' mov [esp], ecx
' mov [esp+8], edx
' mov [esp+12], eax
' mov ebx, eax
' sub ebx, ebp
' jmp L1
' L3:
' lea eax, [ebx+ebp]
' mov ecx, [esi+ebx*4]
' mov edx, [edi+ebx*4]
' mov [esi+eax*4], ecx
' mov [edi+eax*4], edx
' sub ebx, ebp
' L1:
' cmp ebx, 0
' jl L2
' mov eax, [esi+ebx*4]
' mov [esp+4], eax
' call [esp+16+20]
' sub esp, 8
' cmp eax, [esp+16+24]
' je L3
' L2:
' lea eax, [ebx+ebp]
' mov ecx, [esp]
' mov edx, [esp+8]
' mov [esi+eax*4], ecx
' mov [edi+eax*4], edx
' mov eax, [esp+12]
' inc eax
' L5:
' cmp eax, [esp+16+12]
' jl L4
' L6:
' xor edx, edx
' mov eax, ebp
' mov ecx, 3
' idiv ecx
' mov ebp, eax
' test ebp, ebp
' jne L5
' add esp, 16
' pop ebp
' ret 20

.版本 2<br /> <br /> .子程序 希尔排序_汇编<br /> .参数 数组地址, 整数型<br /> .参数 数组长度, 整数型<br /> .参数 索引地址, 整数型<br /> .参数 比较函数地址, 子程序指针<br /> .参数 从大到小, 整数型<br /> <br /> 置入代码 ({ 131, 236, 16, 139, 116, 36, 32, 139, 124, 36, 24, 49, 237, 235, 4, 107, 237, 3, 69, 59, 108, 36, 28, 124, 246, 235, 92, 139, 12, 134, 139, 20, 135, 137, 12, 36, 137, 84, 36, 8, 137, 68, 36, 12, 137, 195, 41, 235, 235, 17, 141, 4, 43, 139, 12, 158, 139, 20, 159, 137, 12, 134, 137, 20, 135, 41, 235, 131, 251, 0, 124, 20, 139, 4, 158, 137, 68, 36, 4, 255, 84, 36, 36, 131, 236, 8, 59, 68, 36, 40, 116, 214, 141, 4, 43, 139, 12, 36, 139, 84, 36, 8, 137, 12, 134, 137, 20, 135, 139, 68, 36, 12, 64, 59, 68, 36, 28, 124, 164, 49, 210, 137, 232, 185, 3, 0, 0, 0, 247, 249, 137, 197, 133, 237, 117, 233, 131, 196, 16, 93, 194, 20, 0 })<br /> ' sub esp, 16<br /> ' mov esi, [esp+16+16]<br /> ' mov edi, [esp+16+8]<br /> ' xor ebp, ebp<br /> ' jmp L7<br /> ' L8:<br /> ' imul ebp, 3<br /> ' inc ebp<br /> ' L7:<br /> ' cmp ebp, [esp+16+12]<br /> ' jl L8<br /> ' jmp L6<br /> ' L4:<br /> ' mov ecx, [esi+eax*4]<br /> ' mov edx, [edi+eax*4]<br /> ' mov [esp], ecx<br /> ' mov [esp+8], edx<br /> ' mov [esp+12], eax<br /> ' mov ebx, eax<br /> ' sub ebx, ebp<br /> ' jmp L1<br /> ' L3:<br /> ' lea eax, [ebx+ebp]<br /> ' mov ecx, [esi+ebx*4]<br /> ' mov edx, [edi+ebx*4]<br /> ' mov [esi+eax*4], ecx<br /> ' mov [edi+eax*4], edx<br /> ' sub ebx, ebp<br /> ' L1:<br /> ' cmp ebx, 0<br /> ' jl L2<br /> ' mov eax, [esi+ebx*4]<br /> ' mov [esp+4], eax<br /> ' call [esp+16+20]<br /> ' sub esp, 8<br /> ' cmp eax, [esp+16+24]<br /> ' je L3<br /> ' L2:<br /> ' lea eax, [ebx+ebp]<br /> ' mov ecx, [esp]<br /> ' mov edx, [esp+8]<br /> ' mov [esi+eax*4], ecx<br /> ' mov [edi+eax*4], edx<br /> ' mov eax, [esp+12]<br /> ' inc eax<br /> ' L5:<br /> ' cmp eax, [esp+16+12]<br /> ' jl L4<br /> ' L6:<br /> ' xor edx, edx<br /> ' mov eax, ebp<br /> ' mov ecx, 3<br /> ' idiv ecx<br /> ' mov ebp, eax<br /> ' test ebp, ebp<br /> ' jne L5<br /> ' add esp, 16<br /> ' pop ebp<br /> ' ret 20

有时候手工编写与编译器生成的汇编代码，区别是很明显的，比如上面的代码，在寄存器分配方面显然更加灵活，在提交参数方面也不一定需要 push，我们完全可以在固定位置直接写入。

数组_排序1_改进.zip (6.81 KB, 下载次数: 11)

2024-6-27 20:47 上传

点击文件名下载附件

191039295

支持开源~！感谢分享

光影魔术

感谢分享源码

shuya1

支持开源~！感谢分享

网络注册络员

学习了支持楼主

神祇

这个可以有

笨来无一悟

功德无量

static101

牛蛙

蒲强

顶顶顶顶顶顶顶顶

please

感谢分享，支持开源！！！