jjzjj

c++ - 三向快速排序需要更高的性能

coder 2024-02-20 原文

我目前正在尝试实现三分区快速排序。下面的代码工作正常，但运行时间不够。我对数据结构、算法和一般的“深入”编程都不熟悉，所以我尝试摆弄它以使其在更短的时间内工作的尝试基本上没有成功。 (内存性能很好。)

我的直觉是改变主元，但我担心这不是三路快速排序。 

#include <iostream>
#include <vector>
#include <cstdlib>

using std::vector;
using std::swap;


int partition3(vector<int> &a, int l, int r) {

    int x = a[l]; 
    int j = l;
    int k = r;
    int i = l+1; 

    while (i <= k) {
        if (a[i] < x) {
          swap(a[i],a[j]);
          j++; 
          i++;
        }
        else if(a[i] > x) {
            swap(a[i],a[k]);
            k--;
        }
        else {
            i++;
        }
    }

    return j;
}

void randomized_quick_sort(vector<int> &a, int l, int r) {

    if (l >= r) {
        return;
    }

    int k = l + rand() % (r - l + 1);
    swap(a[l], a[k]);

    while (l < r) {
        int m = partition3(a, l, r);
        if ((m-l) < (r-m)) {
            randomized_quick_sort(a, l, m - 1);
            l = m + 1; 
        }
        else {
            randomized_quick_sort(a, m + 1, r);
            r = m - 1;
        }
    }
}

int main() {
    int n; 
    std::cin >> n;
    vector<int> a(n);
    for (size_t i = 0; i < a.size(); ++i) {
        std::cin >> a[i];
    }
    randomized_quick_sort(a, 0, a.size() - 1);
    for (size_t i = 0; i < a.size(); ++i) {
        std::cout << a[i] << ' ';
    }
}

最佳答案

排序在现实世界中是一个相当复杂的问题。尝试查看一些有效的实现，例如，由 C++ 标准库的实现提供的那些。探索网络、阅读文章、查看讨论……

一些注意事项:

  1. 随机数生成(相对)代价高昂，它会显着降低快速排序的速度。 (但是，它也可以对某些类型的数据执行相反的操作。)
  2. 整数除法(相对)非常昂贵，可能比随机数生成还贵。
  3. 在实践中很少单独使用纯快速排序。通常，它与插入排序相结合，因为递归调用对于非常小的分区效率低下(阈值通常设置在 8 到 16 个元素之间)。
  4. 为了防止快速排序出现最坏情况的复杂性，通常会检查递归级别，如果它超过某个阈值 (2 x log_2(n))，则使用另一种算法(通常是堆排序)对其余数据进行排序。

等等...

更新

另外两个想法:

  1. 在多核/众核环境中，并行算法可能会为您提供最佳加速。但是设计并行快速排序绝非易事。大部分复杂性落在高效的并行分区和负载平衡上。 Libstdc++ Parallel Mode 有一个很好的 OpenMP 实现。或者，你也可以查看我的AQsort:https://github.com/DanielLangr/AQsort .
  2. 要使快速排序更高效，请使用尾调用消除/优化。它大大减少了所需的调用堆栈空间。

关于c++ - 三向快速排序需要更高的性能，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/36331213/

三向ampintsectionrandomized_quick_sortc++algorithmperformancetimequicksort

有关c++ - 三向快速排序需要更高的性能的更多相关文章

  1. ruby - 我需要将 Bundler 本身添加到 Gemfile 中吗？ - 2

    当我使用Bundler时，是否需要在我的Gemfile中将其列为依赖项？毕竟，我的代码中有些地方需要它。例如，当我进行Bundler设置时:require"bundler/setup" 最佳答案 没有。您可以尝试，但首先您必须用鞋带将自己抬离地面。 关于ruby-我需要将Bundler本身添加到Gemfile中吗？，我们在StackOverflow上找到一个类似的问题： https://stackoverflow.com/questions/4758609/

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

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

  3. ruby - rspec 需要 .rspec 文件中的 spec_helper - 2

    我注意到像bundler这样的项目在每个specfile中执行requirespec_helper我还注意到rspec使用选项--require，它允许您在引导rspec时要求一个文件。您还可以将其添加到.rspec文件中，因此只要您运行不带参数的rspec就会添加它。使用上述方法有什么缺点可以解释为什么像bundler这样的项目选择在每个规范文件中都需要spec_helper吗？ 最佳答案 我不在Bundler上工作，所以我不能直接谈论他们的做法。并非所有项目都checkin.rspec文件。原因是这个文件，通常按照当前的惯例，只

  4. ruby - 如何在 Lion 上安装 Xcode 4.6，需要用 RVM 升级 ruby - 2

    我实际上是在尝试使用RVM在我的OSX10.7.5上更新ruby，并在输入以下命令后:rvminstallruby我得到了以下回复:Searchingforbinaryrubies,thismighttakesometime.Checkingrequirementsforosx.Installingrequirementsforosx.Updatingsystem.......Errorrunning'requirements_osx_brew_update_systemruby-2.0.0-p247',pleaseread/Users/username/.rvm/log/138121

  5. ruby - 当使用::指定模块时，为什么 Ruby 不在更高范围内查找类？ - 2

    我刚刚被困在这个问题上一段时间了。以这个基地为例:moduleTopclassTestendmoduleFooendend稍后，我可以通过这样做在Foo中定义扩展Test的类:moduleTopmoduleFooclassSomeTest但是，如果我尝试通过使用::指定模块来最小化缩进:moduleTop::FooclassFailure这失败了:NameError:uninitializedconstantTop::Foo::Test这是一个错误，还是仅仅是Ruby解析变量名的方式的逻辑结果？ 最佳答案 Isthisabug,or

  6. ruby - 为什么在 ruby​​ 中创建 Rational 不需要新方法 - 2

    这个问题在这里已经有了答案:关闭10年前。PossibleDuplicate:Rubysyntaxquestion:Rational(a,b)andRational.new!(a,b)我正在阅读ruby镐书，我对创建有理数的语法感到困惑。Rational(3,4)*Rational(1,2)产生=>3/8为什么Rational不需要new方法(我还注意到例如我可以在没有new方法的情况下创建字符串)？

  7. 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.你能做的最好的事情是:

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

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

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

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

  10. ruby - 我需要从 facebook 游戏中抓取数据——使用 ruby - 2

    修改(澄清问题)我已经花了几天时间试图弄清楚如何从Facebook游戏中抓取特定信息；但是，我遇到了一堵又一堵砖墙。据我所知，主要问题如下。我可以使用Chrome的检查元素工具手动查找我需要的html-它似乎位于iframe中。但是，当我尝试抓取该iframe时，它​​是空的(属性除外):如果我使用浏览器的“查看页面源代码”工具，这与我看到的输出相同。我不明白为什么我看不到iframe中的数据。答案不是它是由AJAX之后添加的。(我知道这既是因为“查看页面源代码”可以读取Ajax添加的数据，也是因为我有b/c我一直等到我可以看到数据页面之后才抓取它，但它仍然不存在)。发生这种情况是因为

随机推荐