ncnn
ncnn copied to clipboard
Finish the heapsort of simplestl partial_sort
算法思路
堆排序partial_sort
算法思路如下:
一个大小为n的array,我们要获得top k
个最大(最小)的元素。
- 以array的前k个元素建立一个大小为k的小(大)根堆(使用自定义
heapify()
函数) - 遍历剩余
n-k
个元素与小(大)根堆的堆顶元素比较,如果比堆顶元素大(小)那么就会交换两者同时重新更新小(大)根堆,遍历结束后会获得top k
个最大(最小)的元素,但是并不是按照严格的顺序来排序。 - 利用堆顶是最大(最小)的元素对这k个元素使用常规意义下的堆排序来依次获得严格降序(升序)的
top k
array. 以上所有操作均为inplace操作
复杂度分析
- 时间复杂度
之前冒泡排序时间复杂度为
O(nk)
, 此处堆排序时间复杂度为O((n-k)logk)
。 - 空间复杂度
空间复杂度相同,均为
inplace
操作并没有使用额外空间。
Codecov Report
Merging #4124 (0477bef) into master (acbaaa6) will not change coverage. The diff coverage is
n/a
.
@@ Coverage Diff @@
## master #4124 +/- ##
=======================================
Coverage 94.43% 94.43%
=======================================
Files 748 748
Lines 179004 179004
=======================================
Hits 169046 169046
Misses 9958 9958
Help us with your feedback. Take ten seconds to tell us how you rate us. Have a feature suggestion? Share it here.
@nihui 这里想另外请教nihui姐姐一些其他问题:
- 关于argmax/argmin
计划任务书中介绍实现
argmax
,argmin
layer实现并实现相关的pnnx转化。 本人查看当前ncnn仓库已经有了argmax的实现(个人认为代码比较简单,不过有点缩进问题以及omp可以简单优化),同时pnnx似乎也实现了argmax
。个人疑问如下:
- 有必要再重写一遍
argmin
吗? - 有必要在
x86
端做avx等指令集优化吗? - 有必要加
test_argmax.cpp
做验证吗? - nihui姐姐布置这个任务的本意是什么?感觉
argmax/argmin
这个任务好多部分ncnn都已经基本实现了?
- 关于grid_sample
如果以上没有必要,我将会开始尝试grid_sample
的开发与编写。