为什么这个程序在大小大于50的情况下需要指数级的更长时间？

Question

因此，我正在为类编写一个ARM程序集快速排序方法。我已经了解了大部分，除了复杂性是没有意义的。

我们正在将它与我们创建的另一种冒泡排序方法进行比较，它在具有1个参数和10个参数的示例中执行得更好。然而，我甚至不能比较100参数测试，因为它花费了太长的时间…我不能让它做75甚至，但50在几秒钟内完成。

这就是我的资料

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)

有没有人能告诉我为什么要花这么长时间并呈指数级增长？我能做些什么来修复它呢？

Answer 1

我没有研究过你的逻辑，但我已经在你的程序中添加了一些调试脚本，这可能会对你有所帮助。包装器是一个独立的程序。

/* qsort1.s */

@ ---- Added ----
.data

tstdat:
    .word 9, 9, 9, 9, 9

array:
    .word 3, 7, 8, 5, 2, 1, 9, 5, 4
len:
    .word ((len - array) /4)

.balign 4
format:
    .asciz " %2d  %2d  %2d  %2d  %2d  %2d  %2d  %2d  %2d  |  %2d  %2d  %2d\n"


.text

.global main

Print:
    push  {r0-v7, lr}
    mrs   v7,  cpsr
    push  {v7, v8}
    push  {r2, r6, r7}
    ldr   r7,  =array
    ldm   r7,  {r1-r9}
    push  {r4-r9}
    ldr   r0,  =format
    bl    printf
    add   sp,  #36
    pop   {v7, v8}
    msr   cpsr_f, v7
    pop   {r0-v7, pc}

main:

    ldr     r0,  =array
    ldr     r1,  =len
    ldr     r1,  [r1]

    push    {r3-r11, lr}
    bl      Print
    bl      qsort
    bl      Print
    pop     {r3-r11, pc}

@ ---------------------------

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),
@   bl      Print                @ <---- Added
    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]
    bl      Print                @ <---- Added
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)

下面是输出的开始部分。左边是要排序的数组，右边是r2、r6和r7。此数组来自https://en.wikipedia.org/wiki/Quicksort (https://upload.wikimedia.org/wikipedia/commons/a/af/Quicksort-diagram.svg)。

pi@RPi:~/pgm $ mym qsort1
as -o qsort1.o qsort1.s
gcc -o qsort1 qsort1.o

./qsort1; echo $?
  3   7   8   5   2   1   9   5   4  |  2126935836  66296   0 (before pgm)
  3   4   8   5   2   1   9   5   7  |   0   9   3
  3   5   8   5   2   1   9   4   7  |   0   9   3
  3   9   8   5   2   1   5   4   7  |   0   9   3
  3   1   8   5   2   9   5   4   7  |   0   9   3
  3   1   2   5   8   9   5   4   7  |   0   9   3    
 ...
 (  array to be sorted             )    r2   r4  r7

Answer 2

要解决变得过长的快速排序问题，可以使用“Linux qsort”对数字进行排序。

@ 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数字。

/* 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