我该如何读懂这个15行的数组排序函数qsort!的代码?

我使用vscode左边栏的run and debug, 添加了一些断点,可以看到local变量每次运行的变化…

但函数qsort!里又出现了qsort!击溃了我。这来自于c吗?

把函数体当作一种循环之后这个套娃变得好接受了。
我想我现在的问题在于:

pivot = a[(lo+hi)>>>1]

这个函数来自于官方主页,那么我认为它就是最优算法,那么为什么这样做是最优的呢?

function qsort!(a,lo,hi)
    i, j = lo, hi
    while i < hi
        pivot = a[(lo+hi)>>>1]
        while i <= j
            while a[i] < pivot; i += 1; end
            while a[j] > pivot; j -= 1; end
            if i <= j
                a[i], a[j] = a[j], a[i]
                i, j = i+1, j-1
            end
        end
        if lo < j; qsort!(a,lo,j); end
        lo, j = i, hi
    end
    return a
end

sortperf(n) = qsort!(rand(n), 1, n)

sortperf(6)

代码引自:

Microbenchmarks/perf.jl at master · JuliaLang/Microbenchmarks · GitHub

我试图debug:
F5(继续):每一行添加断点,运行代码。

这里发现每一行添加断点和单步调试的区别:

F11(单步调试):跳到了另一个page里

@eval setindex!(A::Array{T}, x, i1::Int) where {T} = arrayset($(Expr(:boundscheck)), A, convert(T,x)::T, i1)

vscode这个debug还能快一些吗,读秒时间有点久了,助长self-humiliation…

看上去是利用了二分法,递归的快排算法。

julia> a = collect(1:10)
10-element Vector{Int64}:
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10

julia> a .>>> 1
10-element Vector{Int64}:
 0
 1
 1
 2
 2
 3
 3
 4
 4
 5

pivot 应当是取了 lo 与 hi 中间的元素。
你可以参考
https://www.runoob.com/w3cnote/quick-sort-2.html

题外话,qsort这个是不是暂且不说,但一般情况下并不能单靠是否出自官方主页就得出这种结论。

啊对对对!就是它!
昨晚我把问题梳理好拿两个手指头比划指针比划出来了,对上了,感谢回复!

这个>>>1,玩矩阵是真好用索引拼接啥的,现在也是我的了。

不好意思再发帖了,这里偷偷问一下:
想把vector{Vector{Any}}变成Matrix{any},有比reduce(hcat,target)更好的吗?

a = [collect(0:2) for i in (1:3)]
reduce(hcat,a)

aye aye.
确实不妥,我改下。
#update
我改不了了呢!

我一般这么用VScode来debug:
先用Alt+Enter(实际是Julia: Execute Code in REPL and Move的快捷键,可用F1,输入命令来找到)加载相关的函数,再用Alt+Enter运行@run foo(arg) 进入debug.

qsort,q的含义应该是quickly,就是快排。快排是不是最优排序我不太清楚,但是快排的分而治之(这就是你会遇到函数递归函数的原因)使得快排的时间复杂度变成了O(nlogn),比冒泡排序的双循环的O(n2)快很多。
。。。>>>1,表示二进制下右移1位,等价于整除2并向下取整,这个做法比//2快很多。

如何一行一行的执行并看中间变量的变化呢? 没能找到.
像我恨不得每个函数每一行都添加个断点(:older_man:就是这样做的).

感谢各位的回复!

明天下午年终大组会, 老板给我30min让我推销Julia.

回复不及时希望原谅.

ppt还在做做做做不完了呜呜

1 个赞



在源码点上断点,用上面的按钮/快捷键进行单步、进入函数等调试。

1 个赞

备案号:京ICP备17009874号-2