精易论坛

标题: 使用缩小增量法改善 “数组_排序1” 的性能 [打印本页]

作者: zainex    时间: 2024-6-27 20:48
标题: 使用缩小增量法改善 “数组_排序1” 的性能
数组_排序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)

计次循环尾 ()


为了提高排序性能,可以用其它更高效的排序算法来代替其中的选择排序算法,这里的替代方案是希尔排序(又称缩小增量法):
  
子程序名返回值类型公开备 注
数组_排序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特殊功能支持库


与其它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特殊功能支持库


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

看到这里一般就算结束了,但它其实还有改进空间,上面的代码使用了 __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



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




作者: a3960382663    时间: 2024-6-28 02:04
        感谢分享,很给力!~
作者: emodiyu    时间: 2024-6-28 04:29
大佬太厉害了!!!
作者: 查过    时间: 2024-6-28 07:34
下个学习一下
作者: 豆豆灰常开心    时间: 2024-6-28 07:39
感谢您对论坛的支持!
作者: year1970    时间: 2024-6-28 08:27
感谢分享
作者: 一指温柔    时间: 2024-6-28 08:57
感谢分享,很给力!~
作者: kanhaiyouyue    时间: 2024-6-28 10:08
大佬,真牛逼
作者: mytiger    时间: 2024-6-28 11:38
感谢分享~!
作者: 396384183    时间: 2024-6-28 15:11
感谢分享,很给力!~
作者: ZHuanR    时间: 2024-6-28 17:47
新技能已get√
作者: 夏亿    时间: 2024-6-28 21:01
感谢分享,很给力!~
作者: qq977352880    时间: 2024-6-28 22:30
赞一个,这样的才是我们需要的。

作者: 算法艺术家    时间: 2024-6-29 00:04
这是真大神
作者: 查过    时间: 2024-6-29 07:46
已经顶贴,感谢您对论坛的支持!
作者: 豆豆灰常开心    时间: 2024-6-29 07:51
全都是大佬~
作者: please    时间: 2024-6-29 09:37
感谢分享,支持开源!!!
作者: ΒΜΧ    时间: 2024-6-29 11:09

作者: 天雷    时间: 2024-6-29 19:01
期待精易模块下次更新
作者: bianyuan456    时间: 2024-6-29 20:22
已经顶贴,感谢您对论坛的支持!
作者: qq73s5456    时间: 2024-6-29 21:27
#在这里快速回复#如果您要查看本帖隐藏内容请回复
作者: shuya1    时间: 2024-6-30 01:15
感谢分享,很给力!~
作者: please    时间: 2024-6-30 09:40
感谢分享,支持开源!!!
作者: 蒲强    时间: 2024-6-30 09:46
顶顶顶顶顶顶顶顶
作者: static101    时间: 2024-6-30 18:27
牛蛙
作者: 笨来无一悟    时间: 2024-6-30 19:45
功德无量
作者: 神祇    时间: 2024-7-1 09:06
这个可以有
作者: 网络注册络员    时间: 2024-7-1 09:13
学习了支持楼主
作者: shuya1    时间: 2024-7-1 14:35
支持开源~!感谢分享
作者: 光影魔术    时间: 2024-7-1 20:26
感谢分享源码
作者: 191039295    时间: 2024-7-4 09:40
支持开源~!感谢分享




欢迎光临 精易论坛 (https://125.confly.eu.org/) Powered by Discuz! X3.4