相关疑难解决方法(0)

注意:请不要将此解释为"作业问题".这只是我很想知道的事情:)

中值为5有时用作算法设计中的练习,并且已知仅使用6次比较可计算.

在C#中实现"使用6次比较的五个中位数"的最佳方法是什么？我的所有尝试似乎都导致了尴尬的代码:(我需要漂亮可读的代码,同时仍然只使用6次比较.

public double medianOfFive(double a, double b, double c, double d, double e){
    //
    // return median
    //
    return c;
}

注意:我想我也应该提供"算法":

我发现自己无法像Azereal在论坛帖子中那样清楚地解释算法.所以我会在这里引用他的帖子.来自http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_cs;action=display;num=1061827085

好吧,我在我的一个任务中提出了这个问题,我转向这个论坛寻求帮助,但没有帮助.我终于找到了如何做到这一点.

1. 使用前4个元素启动mergesort并订购每对(2个比较)

2. 比较每对中的两个较低的一个并从可能性中消除最低的一个(3个比较)

3. 在没有配对的情况下添加第5个号码并比较两个(4个比较)

4. 比较两个新对中的两个最低对并消除较低对(5个比较)

5. 比较一个单独和最后一对中的较低者,较低的数字是中位数

   可能的中位数在肠胃外

(54321)

5:4 3:2 2比较

(4 <5 2 <3 1)

4:2 3比较

2(4 <5 3 1)

1:3 4比较

2(4 <5 1 <3)

4:1 5比较

1,2(4 <5 3)

4:3 6比较

1,2(3)4,5-

三是中位数

编辑:作为您的请求,并防止自己得到更多的downvotes,这是我写的C++代码,找到五个中位数.不要介意它的尴尬:

double StageGenerator::MedianOfFive(double n1, double n2, …

我有一些性能关键代码,涉及在C++中对大约3到10个元素之间的非常短的固定长度数组进行排序(参数在编译时更改).

在我看来,专门针对每个可能的输入大小的静态排序网络可能是一种非常有效的方法:我们进行必要的比较以确定我们所处的情况,然后进行最佳的交换数量以进行排序数组.

要应用此功能,我们使用一些模板魔法来推断数组长度并应用正确的网络:

#include <iostream>
using namespace std;

template< int K >
void static_sort(const double(&array)[K])
{
    cout << "General static sort\n" << endl;
}

template<>
void static_sort<3>(const double(&array)[3])
{
    cout << "Static sort for K=3" << endl;
}


int main()
{

    double  array[3];

    // performance critical code.
    // ...
    static_sort(array);
    // ...

}

显然,编写所有这些代码非常麻烦,所以:

• 有没有人对是否值得努力有任何意见？
• 有谁知道这种优化是否存在于任何标准实现中,例如std :: sort？
• 是否有一个容易实现这种排序网络的代码？
• 也许有可能使用模板魔法静态生成这样的排序网络.

现在我只使用带有静态模板参数的插入排序(如上所述),希望它会鼓励展开和其他编译时优化.

欢迎你的想法.

更新: 我写了一些测试代码来比较'static'插入short和std :: sort.(当我说静态时,我的意思是数组大小是固定的并在编译时推断出来(可能是允许循环展开等).我至少得到20%的NET改进(请注意,生成包含在时间中).平台: clang,OS X 10.9.

代码在这里https://github.com/rosshemsley/static_sorting如果你想将它与你的stdlib实现进行比较.

我还没有为比较器网络分拣机找到一套很好的实现.

我正在研究一种基于Select算法的快速变量实现,用于选择一个好的枢轴元素.传统智慧似乎是将数组划分为5个元素块,取每个元素的中位数,然后递归地将相同的阻塞方法应用于得到的中位数以获得"中位数中位数".

令我困惑的是选择5元素块而不是3元素块.对于5元素块,在我看来,你执行n/4 = n/5 + n/25 + n/125 + n/625 + ...5个中值运算,而对于3个元素块,你执行n/2 = n/3 + n/9 + n/27 + n/81 + ...3个中值运算.由于每个5的中位数是6个比较,并且每个中位数3是2个比较,这导致3*n/2使用5的n中位数和使用3的中位数进行比较.

任何人都可以解释这种差异,使用5元素块的动机是什么？我不熟悉应用这些算法的常规做法,所以也许你可以通过某种方式减少一些步骤,并且仍然能够"足够接近"中位数以确保良好的转向,并且这种方法可以更好地使用5元素块？