对“平滑”的条目进行排序的最快方法二维阵列
对平滑二维数组中的值进行排序的最快方法是什么？
输入是一个小的过滤图像：
- 大约 60 x 80 像素
- 单通道
- 单精度或双精度浮点
- 行主要存储，内存中的顺序
- 值具有混合符号
- 分段“平滑”，区域宽度约为 10 像素宽
输出是一个平面（大约 4800 个值）排序值的数组，以及对原始数组进行排序的索引。
What is the fastest way to sort the values in a smooth 2D array?
The input is a small filtered image:
- about 60 by 80 pixels
- single channel
- single or double precision float
- row major storage, sequential in memory
- values have mixed sign
- piecewise "smooth", with regions on the order of 10 pixels wide
Output is a flat (about 4800 value) array of the sorted values, along with the indices that sort the original array.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（5）
我预计 Timsort 会获胜，因为它利用了数据中的“运行”。
快速排序通常会很快，但存在遇到最坏情况的风险。例如，当给定已排序的输入时，某些版本的 Quickshort 的复杂度为 O(n^2)。如果有人给你错误类型的渐变填充图像，那就不太友好了……
这是一个有点疯狂的想法 - 你也可以尝试 Z 排序通道 (维基百科链接），这可以让您在两个维度上利用相邻的相似颜色。
I'd expect Timsort to win this since it takes advantage of "runs" in data.
Quicksort will normally be be fast but there is a risk that you hit a worst-case scenario. e.g. some versions of quickshort are O(n^2) when given already sorted input. Which would not be very friendly if someone gave you the wrong type of gradient-filled image......
Here's a slightly crazy idea - you might also try a Z-ordering pass (Wikipedia link) which could enable you to take advantage of adjacent similar colours in both dimensions.
我将从就地快速排序开始。浮点比较在大多数处理器上都很快（当然比合并排序所需的分配快得多）。
I'd start with in-place quicksort. Floating point comparisons are fast on most processors (certainly a lot faster than the allocation needed for a mergesort).
我使用 numpy 在平面数组上的排序例程对一些图像进行了快速而肮脏的基准测试。这是数百张随机图像和数百张人脸图像的平均值。两者都是单精度。
所有算法似乎都受益于现有的部分排序，尤其是快速排序。 Numpy 似乎没有排序列表合并功能，所以我无法尝试对行进行预排序，唉。
I hammered out a quick and dirty benchmark on some images using numpy's sort routines on the flat array. This is averaged over a few hundred random images and a few hundred images of human faces. Both are single precision.
All of the algorithms seem to benefit from the existing partial ordering, especially quicksort. Numpy doesn't seem to have a sorted list merge function, so I can't try pre-sorting the rows, alas.
有 timsort，但我在几个地方看到它适用于比较速度慢的应用程序； numpy 开发人员显然决定不去实现它：
http: //mail.scipy.org/pipermail/scipy-dev/2009-May/011929.html
There is timsort, but I have seen in several places that it is meant for applications with slow compares; the numpy devs apparently decided not to even bother implementing it:
http://mail.scipy.org/pipermail/scipy-dev/2009-May/011929.html
人们可以单独对行进行合并排序，然后合并排序后的行。
这至少会利用二维数组的一些特殊结构，即单调运行通常在数组边缘开始和停止的事实。它还暴露了另外几个级别的并行性。
One could mergesort the rows individually, and then merge the sorted rows.
That would at least leverage some of the special structure of the 2D array, i.e. the fact that monotonic runs will typically start and stop at the edge of the array. It also exposes another couple levels of parallelism.