jjzjj

c++ - 排序 : Is this performance difference for real or am I doing something wrong?

coder 2024-02-25 原文

我需要对很多由 8 个 float 组成的小数组进行排序。最初我使用的是 std::sort 但对其性能不满意，我尝试了由此生成的比较交换算法:http://pages.ripco.net/~jgamble/nw.html

测试代码如下:

template <typename T>
bool PredDefault(const T &a, const T &b) {return a > b;}

template <typename T>
bool PredDefaultReverse(const T &a, const T &b) {return a < b;}

template <typename T>
void Sort8(T* Data, bool(*pred)(const T &a, const T &b) = PredDefault) {
    #define Cmp_Swap(a, b) if (pred(Data[a], Data[b])) {T tmp = Data[a]; Data[a] = Data[b]; Data[b] = tmp;}

    Cmp_Swap(0, 1); Cmp_Swap(2, 3); Cmp_Swap(4, 5); Cmp_Swap(6, 7);
    Cmp_Swap(0, 2); Cmp_Swap(1, 3); Cmp_Swap(4, 6); Cmp_Swap(5, 7);
    Cmp_Swap(1, 2); Cmp_Swap(5, 6); Cmp_Swap(0, 4); Cmp_Swap(3, 7); 
    Cmp_Swap(1, 5); Cmp_Swap(2, 6);  
    Cmp_Swap(1, 4); Cmp_Swap(3, 6);
    Cmp_Swap(2, 4); Cmp_Swap(3, 5);
    Cmp_Swap(3, 4);

}

int lastTick;
int tick() {
    int hold = lastTick;
    lastTick = GetTickCount();
    return lastTick - hold;
}

int main()
{
    vector<vector<float>> rVec(1000, vector<float>(8)); 
    for (auto &v : rVec) {
        v[0] = ((float)rand()) * 0.001;
        v[1] = ((float)rand()) * 0.001;
        v[2] = ((float)rand()) * 0.001;
        v[3] = ((float)rand()) * 0.001;
        v[4] = ((float)rand()) * 0.001;
        v[5] = ((float)rand()) * 0.001;
        v[6] = ((float)rand()) * 0.001;
        v[7] = ((float)rand()) * 0.001;
    }

    system("PAUSE");
    tick();

    for (int n = 0; n < 50000; n++)
    for (int j = 0; j < rVec.size(); j++) {
        std::sort(rVec[j].begin(), rVec[j].end(), PredDefault<float>);
        std::sort(rVec[j].begin(), rVec[j].end(), PredDefaultReverse<float>);
        //Sort8(rVec[j].data(), PredDefault<float>);
        //Sort8(rVec[j].data(), PredDefaultReverse<float>);
    }

    cout << "\nTime: " << tick() << "\n";
    system("PAUSE");

    return 1;
}

在测试一个或另一个时添加/删除评论标记。

我并没有期待太多，但差异是支持交换排序的 10 倍(测试在 vs2012 的发布配置中完成，关闭了节能功能)。结果也查出来了。这是正确的吗？

最佳答案

我可以马上想到几个原因。

  1. 您有硬编码比较。这有助于流水线化多条指令，从而使其非常高效。但想象一下将其编码为 N=1000。你必须写 1000*1000 个比较。
  2. std::sort 进行O(nlogn) 比较。但是这个大 O 符号适用于大 N，因为符号常数可以很大。所以你不能通过在 8 个值的范围内运行来判断效率。

关于c++ - 排序 : Is this performance difference for real or am I doing something wrong?，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/28869451/

performancedifferenceCmp_SwapSwapfloatc++sorting

有关c++ - 排序 : Is this performance difference for real or am I doing something wrong?的更多相关文章

  1. ruby-on-rails - 如何优雅地重启 thin + nginx？ - 2

    我的瘦服务器配置了nginx，我的ROR应用程序正在它们上运行。在我发布代码更新时运行thinrestart会给我的应用程序带来一些停机时间。我试图弄清楚如何优雅地重启正在运行的Thin实例，但找不到好的解决方案。有没有人能做到这一点？ 最佳答案 #Restartjustthethinserverdescribedbythatconfigsudothin-C/etc/thin/mysite.ymlrestartNginx将继续运行并代理请求。如果您将Nginx设置为使用多个上游服务器，例如server{listen80;server

  2. ruby - 使用 `+=` 和 `send` 方法 - 2

    如何将send与+=一起使用？a=20;a.send"+=",10undefinedmethod`+='for20:Fixnuma=20;a+=10=>30 最佳答案 恐怕你不能。+=不是方法，而是语法糖。参见http://www.ruby-doc.org/docs/ProgrammingRuby/html/tut_expressions.html它说Incommonwithmanyotherlanguages,Rubyhasasyntacticshortcut:a=a+2maybewrittenasa+=2.你能做的最好的事情是:

  3. ruby - 如何计算 Liquid 中的变量 +1 - 2

    我对如何计算通过{%assignvar=0%}赋值的变量加一完全感到困惑。这应该是最简单的任务。到目前为止，这是我尝试过的:{%assignamount=0%}{%forvariantinproduct.variants%}{%assignamount=amount+1%}{%endfor%}Amount:{{amount}}结果总是0。也许我忽略了一些明显的东西。也许有更好的方法。我想要存档的只是获取运行的迭代次数。 最佳答案 因为{{incrementamount}}将输出您的变量值并且不会影响{%assign%}定义的变量，我

  4. ruby-on-rails - 需要帮助最大化多个相似对象中的 3 个因素并适当排序 - 2

    我需要用任何语言编写一个算法，根据3个因素对数组进行排序。我以度假村为例(如Hipmunk)。假设我想去度假。我想要最便宜的地方、最好的评论和最多的景点。但是，显然我找不到在所有3个中都排名第一的方法。Example(assumingthereare20importantattractions):ResortA:$150/night...98/100infavorablereviews...18of20attractionsResortB:$99/night...85/100infavorablereviews...12of20attractionsResortC:$120/night

  5. ruby-on-rails - 在具有 ActiveRecord 条件的相关模型中按字段排序 - 2

    我正在尝试按Rails相关模型中的字段进行排序。我研究的所有解决方案都没有解决如果相关模型被另一个参数过滤？元素模型classItem相关模型:classPriority我正在使用where子句检索项目:@items=Item.where('company_id=?andapproved=?',@company.id,true).all我需要按相关表格中的“位置”列进行排序。问题在于，在优先级模型中，一个项目可能会被多家公司列出。因此，这些职位取决于他们拥有的company_id。当我显示项目时，它是针对一个公司的，按公司内的职位排序。完成此任务的正确方法是什么？感谢您的帮助。PS-我

  6. arrays - Ruby 数组 += vs 推送 - 2

    我有一个数组数组，想将元素附加到子数组。+=做我想做的，但我想了解为什么push不做。我期望的行为(并与+=一起工作):b=Array.new(3,[])b[0]+=["apple"]b[1]+=["orange"]b[2]+=["frog"]b=>[["苹果"],["橙子"],["Frog"]]通过推送，我将推送的元素附加到每个子数组(为什么？):a=Array.new(3,[])a[0].push("apple")a[1].push("orange")a[2].push("frog")a=>[[“苹果”、“橙子”、“Frog”]、[“苹果”、“橙子”、“Frog”]、[“苹果”、“

  7. ruby - 按数字(从大到大)然后按字母(字母顺序)对对象集合进行排序 - 2

    我正在构建一个小部件来显示奥运会的奖牌数。我有一个“国家”对象的集合，其中每个对象都有一个“名称”属性，以及奖牌计数的“金”、“银”、“铜”。列表应该排序:1.首先是奖牌总数2.如果奖牌相同，按类型分割(金>银>铜，即2金>1金+1银)3.如果奖牌和类型相同，则按字母顺序子排序我正在用ruby​​做这件事，但我想语言并不重要。我确实找到了一个解决方案，但如果感觉必须有更优雅的方法来实现它。这是我做的:使用加权奖牌总数创建一个虚拟属性。因此，如果他们有2个金牌和1个银牌，加权总数将为“3.020100”。1金1银1铜为“3.010101”由于我们希望将奖牌数排序为最高的，因此列表按降序排

  8. += 的 Ruby 方法 - 2

    有没有办法让Ruby能够做这样的事情？classPlane@moved=0@x=0defx+=(v)#thisiserror@x+=v@moved+=1enddefto_s"moved#{@moved}times,currentxis#{@x}"endendplane=Plane.newplane.x+=5plane.x+=10putsplane.to_s#moved2times,currentxis15 最佳答案 您不能在Ruby中覆盖复合赋值运算符。任务在内部处理。您应该覆盖+，而不是+=。plane.a+=b与plane.a=

  9. ruby-on-rails - 在不重新查询数据库的情况下重新排序 Rails 中的事件记录？ - 2

    例如，假设我有一个名为Products的模型，并且在ProductsController中，我有以下代码用于product_listView以显示已排序的产品。@products=Product.order(params[:order_by])让我们想象一下，在product_listView中，用户可以使用下拉菜单按价格、评级、重量等进行排序。数据库中的产品不会经常更改。我很难理解的是，每次用户选择新的order_by过滤器时，rails是否必须查询，或者rails是否能够以某种方式缓存事件记录以在服务器端重新排序？有没有一种方法可以编写它，以便在用户排序时rails不会重新查询结果

  10. ruby - Sinatra + Heroku + Datamapper 使用 dm-sqlite-adapter 部署问题 - 2

    出于某种原因，heroku尝试要求dm-sqlite-adapter，即使它应该在这里使用Postgres。请注意，这发生在我打开任何URL时-而不是在gitpush本身期间。我构建了一个默认的Facebook应用程序。gem文件:source:gemcuttergem"foreman"gem"sinatra"gem"mogli"gem"json"gem"httparty"gem"thin"gem"data_mapper"gem"heroku"group:productiondogem"pg"gem"dm-postgres-adapter"endgroup:development,:t

随机推荐