网络广告投放网站,中山网,微官网和移动网站区别,品牌管理公司网站建设本代码全网首发#xff0c;使用Go plan9 windows arm64汇编#xff0c;实现基础版快速排序算法。
未引入随机因子的快速排序的普通Go代码长这样。
func QuickSort(arr []int) {if len(arr) 1 {return}base, l, r : arr[0], 0, len(arr)-1for i : 1; i r; {if arr…本代码全网首发使用Go plan9 windows arm64汇编实现基础版快速排序算法。
未引入随机因子的快速排序的普通Go代码长这样。
func QuickSort(arr []int) {if len(arr) 1 {return}base, l, r : arr[0], 0, len(arr)-1for i : 1; i r; {if arr[i] base {arr[i], arr[r] arr[r], arr[i]r--continue}arr[i], arr[l] arr[l], arr[i]l, i l1, i1}QuickSort(arr[:l])QuickSort(arr[l1:])
}如下使用windows arm64 Go plan9汇编实现的快速排序。
file: quickSort.s
#include textflag.h
// func QuickSortByASM(slice []int)
TEXT ·QuickSortByASM(SB), $104-24// NO_LOCAL_POINTERSMOVD R0 , tmp-8*3(SP); MOVD R1 , tmp-8*4(SP)MOVD R2 , tmp-8*5(SP); MOVD R3 , tmp-8*6(SP)MOVD R4 , tmp-8*7(SP); MOVD R5 , tmp-8*8(SP)MOVD R6 , tmp-8*9(SP); MOVD R7 , tmp-8*10(SP)MOVD R8 , tmp-8*11(SP); MOVD R9 , tmp-8*12(SP)MOVD R10, tmp-8*13(SP)MOVD slice0(FP), R0 // arrayPtrMOVD slice8(FP), R1 // arrayLengthMOVD $0, R2 // l_indexMOVD R1, R3 // r_index arrayLengthSUB $1, R3 // r_index - 1MOVD $0, R4 // pointer1MOVD $0, R5 // pointer2MOVD $8, R6 // dataSizeMOVD $1, R7 // indexMOVD (R0), R8 // base TODO random indexMOVD $0, R9CMP $1, R1; BLE LABEL_END // if arrayLength 1 return
LABEL_FOR_START:CMP R3, R7; BGT LABEL_FOR_END // if index r_index returnMOVD R7, R4 // offset indexMUL R6, R4 // offset * dataSizeADD R0, R4 // arr[i] R4MOVD (R4), R5 // arr[i]CMP R8, R5; BLE LABEL_SWAP // if arr[i] baseMOVD R3, R5 // offset r_indexMUL R6, R5 // offset * dataSizeADD R0, R5 // arr[r]MOVD (R5), R9 // tmp arr[r]MOVD (R4), R10 // tmp1 arr[i]MOVD R10, (R5) // arr[r] arr[i]MOVD R9, (R4) // arr[i] tmpSUB $1, R3 // r_index - 1JMP LABEL_FOR_START
LABEL_SWAP:MOVD R7, R4MUL R6, R4ADD R0, R4MOVD R2, R5MUL R6, R5ADD R0, R5MOVD (R4), R9 // tmp arr[i]MOVD (R5), R10 // tmp1 arr[l]MOVD R10, (R4) // arr[i] tmp1MOVD R9, (R5) // arr[l] tmpADD $1, R2 // l_index 1ADD $1, R7 // index 1JMP LABEL_FOR_START
LABEL_FOR_END:MOVD R0, R4MOVD R2, R5MOVD R4, tmp-104(SP)MOVD R5, tmp-96(SP)CALL ·QuickSortByASM(SB)MOVD R2, R4ADD $1, R4MUL R6, R4ADD R0, R4 // right addressMOVD R1, R5 // tmp arrayLengthSUB R2, R5 // tmp - l_indexSUB $1, R5MOVD R4, tmp-104(SP)MOVD R5, tmp-96(SP)CALL ·QuickSortByASM(SB)
LABEL_END:MOVD tmp-8*3(SP), R0; MOVD tmp-8*4(SP), R1MOVD tmp-8*5(SP), R2; MOVD tmp-8*6(SP), R3MOVD tmp-8*7(SP), R4; MOVD tmp-8*8(SP), R5MOVD tmp-8*9(SP), R6; MOVD tmp-8*10(SP), R7MOVD tmp-8*11(SP), R8;MOVD tmp-8*12(SP), R9MOVD tmp-8*13(SP), R10RET该汇编版本快排基于普通版快排手写而成 未加入stackmap信息大数据量样本可能会出现panic仅供参考。
对数器
package mainimport (fmtmath/randsort
)func QuickSortByASM(slice []int) // 汇编函数声明func main() {N : 50for index : 0; index 1000; index {slice : make([]int, N)for i : 0; i N; i {slice[i] rand.Int()}slice1 : make([]int, N)slice2 : make([]int, N)for i, v : range slice {slice1[i] vslice2[i] v}sort.Ints(slice1)QuickSortByASM(slice2)for i : 0; i N; i {if slice1[i] ! slice2[i] {fmt.Println(slice)fmt.Println(slice1)fmt.Println(slice2)panic(i)}}}fmt.Println(pass)
}pass
