ncnn icon indicating copy to clipboard operation
ncnn copied to clipboard

Finish the heapsort of simplestl partial_sort

Open LRY89757 opened this issue 2 years ago • 2 comments

算法思路

堆排序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操作并没有使用额外空间。

LRY89757 avatar Aug 09 '22 10:08 LRY89757

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.

codecov-commenter avatar Aug 09 '22 10:08 codecov-commenter

@nihui 这里想另外请教nihui姐姐一些其他问题:

  • 关于argmax/argmin

计划任务书中介绍实现argmax, argminlayer实现并实现相关的pnnx转化。 本人查看当前ncnn仓库已经有了argmax的实现(个人认为代码比较简单,不过有点缩进问题以及omp可以简单优化),同时pnnx似乎也实现了argmax。个人疑问如下:

  1. 有必要再重写一遍argmin吗?
  2. 有必要在x86端做avx等指令集优化吗?
  3. 有必要加test_argmax.cpp做验证吗?
  4. nihui姐姐布置这个任务的本意是什么?感觉argmax/argmin这个任务好多部分ncnn都已经基本实现了?
  • 关于grid_sample

如果以上没有必要,我将会开始尝试grid_sample的开发与编写。

LRY89757 avatar Aug 09 '22 11:08 LRY89757