回答另一个Stack Overflow问题(这个)我偶然发现了一个有趣的子问题.排序6个整数数组的最快方法是什么？
由于问题是非常低的水平:
&&或||).真的这个问题是一种高尔夫,其目标不是最小化源长度而是执行时间.我把它叫做"Zening"代码在本书的标题中的代码优化禅由迈克尔·亚伯拉什及其续集.
至于为什么它很有趣,有几个层次:
这是我的参考(天真的,未优化的)实现和我的测试集.
#include <stdio.h>
static __inline__ int sort6(int * d){
char j, i, imin;
int tmp;
for (j = 0 ; j < 5 ; j++){
imin = j;
for (i = j + 1; i < 6 ; i++){
if (d[i] < d[imin]){
imin = i;
}
}
tmp = d[j];
d[j] = d[imin];
d[imin] = …是否有比x >= start && x <= endC或C++ 更快的方法来测试整数是否在两个整数之间？
更新:我的特定平台是iOS.这是盒子模糊功能的一部分,它将像素限制为给定方块中的圆圈.
更新:在尝试接受的答案后,我在一行代码上以正常x >= start && x <= end方式执行了一个数量级的加速.
更新:这是来自XCode的汇编程序的after和before代码:
新方法
// diff = (end - start) + 1
#define POINT_IN_RANGE_AND_INCREMENT(p, range) ((p++ - range.start) < range.diff)
Ltmp1313:
ldr r0, [sp, #176] @ 4-byte Reload
ldr r1, [sp, #164] @ 4-byte Reload
ldr r0, [r0]
ldr r1, [r1]
sub.w r0, r9, r0
cmp r0, r1
blo LBB44_30
老路
#define POINT_IN_RANGE_AND_INCREMENT(p, range) (p <= range.end …我想在下面的例子中理解"中位数中位数"算法:
我们有45个不同的数字,分为9组,每组5个元素.
48 43 38 33 28 23 18 13 8
49 44 39 34 29 24 19 14 9
50 45 40 35 30 25 20 15 10
51 46 41 36 31 26 21 16 53
52 47 42 37 32 27 22 17 54
第二步递归,找到中位数的"真实"中位数(50 45 40 35 30 25 20 15 10)即该集合将分为两组:
50 25
45 20
40 15
35 10
30
对这两组进行排序
30 10
35 15
40 20
45 25
50
中位数是40和15(如果数字是偶数我们左中位数)所以返回值是15但是中位数的"真实"中位数(50 …
这是众所周知的选择算法.见http://en.wikipedia.org/wiki/Selection_algorithm.
我需要它来找到一组3x3x3体素值的中值.由于体积由十亿个体素组成,算法是递归的,因此最好快一点.通常可以预期值相对接近.
到目前为止,我尝试过的最快的已知算法使用了快速排序分区功能.我想知道是否有更快的.
我已经"发明"了使用两个堆的速度提高了20%,但预计使用散列会更快.在实现这个之前,我想知道是否已经存在闪电战快速解决方案.
我使用浮点数的事实应该无关紧要,因为它们在反转符号位后可以被认为是无符号整数.订单将被保留.
编辑:基准和源代码按照Davy Landman的建议转移到单独的答案中.请参阅下面的chmike答案.
编辑:迄今为止最有效的算法被Boojum引用作为Fast Median和双边过滤论文的链接,现在这个问题的答案就是答案.这种方法的第一个聪明的想法是使用基数排序,第二个是组合共享大量像素的相邻像素的中值搜索.
我正在寻找优化这种线性搜索:
static int
linear (const int *arr, int n, int key)
{
int i = 0;
while (i < n) {
if (arr [i] >= key)
break;
++i;
}
return i;
}
数组已排序,函数应返回大于或等于键的第一个元素的索引.它们的数组不大(低于200个元素),并且会为大量搜索准备一次.如果需要,可以在第n个之后将数组元素初始化为适当的数组,如果这样可以加快搜索速度.
不,不允许二进制搜索,只能进行线性搜索.
有人能给我一个现实的例子,其中O(N*N)算法比O(N)某些算法更快N>10.
编辑:我认为这个问题因过于笼统而被搁置.但我确实只有一般性问题.没有其他方式可以以不同的方式提出这个问题.
我正在研究一个kd-tree实现,我现在正在使用std :: nth_element来按照中位数对元素的向量进行分区.但是std :: nth_element占用树构造的90%的时间.有谁能建议更有效的替代方案？
提前致谢
我正在尝试将以下代码从Matlab转换为C ++
function data = process(data)
data = medfilt2(data, [7 7], 'symmetric');
mask = fspecial('gaussian', [35 35], 12);
data = imfilter(data, mask, 'replicate', 'same');
maximum = max(data(:));
data = 1 ./ ( data/maximum );
data(data > 10) = 16;
end
我在medfilt2中遇到的问题-这是一个2D中值滤波器，我需要它支持每像素10位和更多图像。
1.我研究过openCV，它有一个5x5的中值过滤器，它支持16位，但是7x7仅支持字节。
http://docs.opencv.org/2.4/modules/imgproc/doc/filtering.html?highlight=medianblur#medianblur
2.我也正在研究英特尔IPP，但我只能看到一维中值过滤器 https://software.intel.com/zh-cn/node/502283
二维滤波器有快速实现吗？
寻找类似的东西：
C / C ++ / C＃/ VB.NET / Delphi中的带实现的快速中位数过滤有更多代码示例。
我还发现了“恒定时间中值过滤”。