为什么这个程序在大小大于 50 的情况下花费的时间呈指数级增长? [英] Why does this program take exponentially longer with sizes of greater than 50?
本文介绍了为什么这个程序在大小大于 50 的情况下花费的时间呈指数级增长?的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！
问题描述
所以我正在为类编写一个 ARM 程序集快速排序方法.除了复杂性没有意义之外，我的大部分理解都没有.
So I'm writing an ARM assembly quicksort method for class. I have the understanding down for the most part, other than the complexity is not making sense.
我们正在将它与我们制作的另一种冒泡排序方法进行比较，它在具有 1 个参数和 10 个参数的示例中表现更好.但是我什至无法比较 100 个参数的测试，因为它花费的时间太长……我什至无法让它做 75 个，但在几秒钟内完成了 50 个.
We're comparing it to another bubble sort method we made and it performs better for examples with 1 argument and 10 arguments. However I can't even compare the 100 argument test because it takes too long...I cant get it to do 75 even, but 50 is done in a few seconds.
这就是我所拥有的，
qsort: @ Takes three parameters:
@ a: Pointer to base of array a to be sorted (arrives in r0)
@ n: number of elements in the array (arrives in r1)
stmfd sp!, {r4, r6, lr} @ Save r4 and r6 for caller
mov r6, r1 @ r6 <- right
mov r2, #0 @ r2 <- left
qsort_tailcall_entry:
sub r7, r6, r2 @ If right - left <= 1 (already sorted),
cmp r7, #1
ldmlefd sp!, {r4, r6, pc} @ Return, restoring r4 and r6
ldr r7, [r0, r2, asl #2] @ r7 <- a[left], gets pivot element
add r1, r2, #1 @ l <- left + 1
mov r4, r6 @ r <- right
partition_loop:
ldr r3, [r0, r1, asl #2] @ r3 <- a[l]
cmp r3, r7 @ If a[l] <= pivot_element,
addle r1, r1, #1 @ ... increment l, and
ble partition_test @ ... continue to next iteration.
sub r4, r4, #1 @ Otherwise, decrement r,
ldr r8, [r0, r4, asl #2] @ ... and swap a[l] and a[r].
str r8, [r0, r1, asl #2]
str r3, [r0, r4, asl #2]
partition_test:
cmp r1, r4 @ If l < r,
blt partition_loop @ ... continue iterating.
partition_finish:
sub r1, r1, #1 @ Decrement l
ldr r3, [r0, r1, asl #2] @ Swap a[l] and pivot
str r3, [r0, r2, asl #2]
str r7, [r0, r1, asl #2]
bl qsort @ Call self recursively on left part,
@ with args a (r0), left (r2), r (r2),
@ also preserves r4 and r6
mov r2, r4
b qsort_tailcall_entry @ Tail-call self on right part,
@ with args a (r0), l (r2), right (r6)
谁能帮助我理解为什么世界上它需要这么长时间并且呈指数级增长?我能做些什么来修复它?
Can anyone help me understand why in the world it's taking THIS long and growing exponentially? What could I do to fix it?
推荐答案
为了解决快速排序的问题，解决方法是使用Linux qsort"对数字进行排序.
To fix quicksort for getting extra long, a fix would be to use 'Linux qsort' to sort numbers.
@ http://www.tutorialspoint.com/c_standard_library/c_function_qsort.htm
@
@ http://man7.org/linux/man-pages/man3/qsort.3.html
@
@ void qsort(void *base, size_t nmemb, size_t size,
@ int (*compar)(const void *, const void *));
@
@ qsort(r0 =array, r1 =numelements, r2 = 4 bytes,
@ r0=(r3 =cmpfunc){ r0=[r0] - r1=[r1] })
cmpfunc:
ldr r0, [r0]
ldr r1, [r1]
sub r0, r0, r1
mov pc, lr
qsort_setup:
ldr r0, =array
ldr r1, =numbytes
lsr r1, #2
mov r2, #4
ldr r3, =cmpfunc
bl qsort
使用 urandom 数的完整演示程序.
A complete demo program using urandom numbers.
/* qsort14.s */
.data
@ See /usr/include/arm-linux-gnueabihf/asm/unistd.h
@ See /usr/include/arm-linux-gnueabihf/bits/fcntl-linux.h
.equ create, 8
.equ Mode, 0644 @ -rw-r--r--
.equ open, 5
.equ Rd, 00
.equ Wr, 01
.equ RdWr, 02
.equ Apnd, 02000
.equ read, 3
.equ write, 4
.equ close, 6
.equ sync, 36
.equ exit, 1
.equ sfile, 187
.equ numbytes, (64 * 4) @ Has to be multiples
@ .equ numbytes, (128 * 4) @ of 8 times 4.
@ .equ numbytes, (512 * 4)
.balign 4
array: .skip numbytes
.balign 4
dir_file:
.asciz "/dev/urandom"
.balign 4
Open:
.word dir_file, RdWr | Apnd, open
.balign 4
Read:
.word array, numbytes, read
.balign 4
hex3ff:
.word 0x3ff
.balign 4
format:
.asciz " %4u %4u %4u %4u %4u %4u %4u %4u\n"
.balign 4
fmt:
.asciz "\n"
@ ---------------------------
.text
.global main
Prt_arr:
push {r0-r12, lr}
mrs r12, cpsr
push {r11, r12}
mov r0, #0xa
bl putchar
ldr r12, =numbytes
lsr r12, #5
mov r11, #0
endprt:
ldr r0, =array
add r0, r11
ldm r0, {r1-r8}
push {r4-r12}
ldr r0, =format
bl printf
pop {r4-r12}
add r11, #32
subs r12, #1
bne endprt
pop {r11, r12}
msr cpsr_f, r12
pop {r0-r12, lr}
mov pc, lr
@ ---- Program starts here ----
@ ---- Read random numbers ----
main:
push {r4-r12, lr}
ldr r3, =Open @ load address
ldm r3, {r0, r1, r7} @ load registers
svc #0 @ OS opens urandom file
mov r4, r0 @ save fd in r4
ldr r3, =Read @ load address
ldm r3, {r1, r2, r7} @ load registers
svc #0 @ OS reads urandom file
mov r0, r4 @ move fd in r0
mov r7, #close @ num for close
svc #0 @ OS closes urandom file
@ ---- Fix array so numbers are 999 or less ----
ldr r10, =array
ldr r1, =numbytes
sub r1, #4
ldr r2, =hex3ff
ldr r2, [r2]
fix:
ldr r0, [r10, r1]
and r0, r2
cmp r0, #1000
subge r0, #1000
lslge r0, r0, #5
str r0, [r10, r1]
subs r1, #4
bpl fix
@ ---- Print unsorted array ----
bl Prt_arr
b qsort_setup
@ http://www.tutorialspoint.com/c_standard_library/c_function_qsort.htm
@
@ http://man7.org/linux/man-pages/man3/qsort.3.html
@
@ void qsort(void *base, size_t nmemb, size_t size,
@ int (*compar)(const void *, const void *));
@
@ qsort(r0 =array, r1 =numelements, r2 = 4 bytes,
@ r0=(r3 =cmpfunc){ r0=[r0] - r1=[r1] })
cmpfunc:
ldr r0, [r0]
ldr r1, [r1]
sub r0, r0, r1
mov pc, lr
qsort_setup:
ldr r0, =array
ldr r1, =numbytes
lsr r1, #2
mov r2, #4
ldr r3, =cmpfunc
bl qsort
End:
bl Prt_arr
mov r0, #0xa
bl putchar
pop {r4-r12, lr}
bx lr
.end
这篇关于为什么这个程序在大小大于 50 的情况下花费的时间呈指数级增长?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
查看全文
