草庐IT

c++ - inplace_merge : What causes a complexity of N*log(N) vs. N-1？

coder 2024-02-24 原文

根据关于 inplace_merge 的 C++ 文档，该算法的复杂度是“如果使用内部缓冲区，则比较线性 (N-1)，否则为 NlogN(其中 N 是范围 [first,last) 中的数字元素)” .它们所说的内部缓冲区是什么意思，是什么导致了 O(N-1) 与 O(NlogN) 的复杂性？

最佳答案

扩展其他答案:

  • 至少在 libstdc++ 和 libc++ 中，“内部缓冲区”是通过调用 std::get_temporary_buffer 提供的，STL 中一个晦涩但标准的例程。此例程已在 C++17 中弃用，主要是因为它令人困惑且有点愚蠢。参见 this question有关详细信息，或阅读 Stephan T. Lavavej's original deprecation proposal .

  • 在 libstdc++ 中，get_temporary_buffer 是作为对 operator new 的调用实现的。 (Source)

  • 在 libc++ 中，get_temporary_buffer 是作为对 operator new 的调用实现的。 (Source)

  • 我不知道 inplace_merge 是否在 MSVC 的标准库中使用了 get_temporary_buffer，但我敢打赌它确实如此。

  • 在 MSVC 中，it has been reported get_temporary_buffer 是作为对 operator new 的调用实现的。

你可以写一个程序到observe this call to operator new firsthand通过覆盖全局命名空间中的 operator new:

#include <algorithm>
#include <cstdio>
#include <cstdlib>

void *operator new(size_t nbytes, const std::nothrow_t&) noexcept
{
    puts("hello from operator new!");
    return malloc(nbytes);
}

int main()
{
    int a[32] = {
        1,1,1,2,3,4,4,5,5,5,5,6,6,8,9,9,
        1,1,2,3,3,3,4,4,5,5,7,8,9,9,9,9,
    };
    std::inplace_merge(&a[0], &a[16], &a[32]);  // "hello from operator new!"
    (void)a;
}

TL;DR:“内部缓冲区”是通过调用 operator new 在堆上分配的。调用 operator new 并不需要实现，但实际上它们都需要。如果您重视堆，请远离 inplace_merge。

关于c++ - inplace_merge : What causes a complexity of N*log(N) vs. N-1？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/11367674/

inplace_mergecomplexitycodeoperatornoreferrerc++mergecomplexity-theory

有关c++ - inplace_merge : What causes a complexity of N*log(N) vs. N-1？的更多相关文章

  1. ruby-on-rails - Railstutorial : db:populate vs. 工厂女孩 - 2

    在railstutorial中，作者为什么选择使用这个(代码list10.25):http://ruby.railstutorial.org/chapters/updating-showing-and-deleting-usersnamespace:dbdodesc"Filldatabasewithsampledata"task:populate=>:environmentdoRake::Task['db:reset'].invokeUser.create!(:name=>"ExampleUser",:email=>"example@railstutorial.org",:passwo

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

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

  3. ruby-on-rails - 在默认方法参数中使用 .reverse_merge 或 .merge - 2

    两者都可以defsetup(options={})options.reverse_merge:size=>25,:velocity=>10end和defsetup(options={}){:size=>25,:velocity=>10}.merge(options)end在方法的参数中分配默认值。问题是:哪个更好？您更愿意使用哪一个？在性能、代码可读性或其他方面有什么不同吗？编辑:我无意中添加了bang(!)...并不是要询问nobang方法与bang方法之间的区别 最佳答案 我倾向于使用reverse_merge方法:option

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

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

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

  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 - Heroku production.log 文件位置 - 2

    我想在heroku.com上查看我的应用程序日志的内容，所以我关注了thisexcellentadvice并拥有我所有的日志内容。但是我现在很想知道我的日志文件实际在哪里，因为“log/production.log”似乎是空的:C:\>herokuconsoleRubyconsoleforajpbrevx.heroku.com>>files=Dir.glob("*")=>["public","tmp","spec","Rakefile","doc","config.ru","app","config","lib","README","Gemfile.lock","vendor","sc

  8. Ruby#index 方法 VS 二进制搜索 - 2

    给定一个元素和一个数组，Ruby#index方法返回元素在数组中的位置。我使用二进制搜索实现了我自己的索引方法，期望我的方法会优于内置方法。令我惊讶的是，内置的在实验中的运行速度大约是我的三倍。有Rubyist知道原因吗？ 最佳答案 内置#indexisnotabinarysearch，这只是一个简单的迭代搜索。但是，它是用C而不是Ruby实现的，因此自然可以快几个数量级。 关于Ruby#index方法VS二进制搜索，我们在StackOverflow上找到一个类似的问题：

  9. += 的 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=

  10. ruby-on-rails - 在 Ruby 或 Rails 中，hash.merge({ :order => 'asc' }) can return a new hash with a new key. 什么可以返回带有已删除键的新散列？ - 2

    在Ruby(或Rails)中，我们可以做到new_params=params.merge({:order=>'asc'})现在new_params是一个带有添加键:order的散列。但是是否有一行可以返回带有已删除key的散列？线路new_params=params.delete(:order)不会工作，因为delete方法返回值，仅此而已。我们必须分3步完成吗？tmp_params=paramstmp_params.delete(:order)returntmp_params有没有更好的方法？因为我想做一个new_params=(params[:order].blank?||para

随机推荐