javascript - 内置排序比手工排序慢？-6ren

javascript - 内置排序比手工排序慢？

转载作者：行者123 更新时间：2023-12-02 15:27:19

我手工制作的堆排序似乎比 JavaScript 的内置排序例程更快，无论是在 Chromium 45.02454.101 中还是在 Firefox 41.0.2 中，在 Intel i5 上的 Ubuntu 14.04 LTS 上运行。

由于我怀疑我是否实现了世界一流的排序例程，因此我完全不清楚原因可能是什么。

为了允许重现该现象，这里是所有代码:

<!doctype html>
<html>
<head>
  <title>Sorting Runtime</title>
  <meta charset="utf-8">
  <style>
  #output {
      background-color: #EEEEEE;
      padding: 1ex;
  }
  #output p {
      font-family: monospace;
      margin: 0;
  }
  </style>
  <script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.4/jquery.min.js"></script>
  <script>
  "use strict";


  var actualCode = function () {
     var ary;

     var dataSizes = [1000, 2000, 4000, 8000, 16000, 32000, 64000, 128000, 256000];
     var sortingFunctions = [
        { name: "built-in sort", fn: function (ary) { ary.sort (); } },
        { name: "heapsort", fn: function (ary) { heapsort (ary); } }
     ];
     var runsPerDataSize = 10;

     sortingFunctions.forEach (function (f) {
        print (f.name);
        var s = f.fn;
        dataSizes.forEach (function (dataSize) {
           var nRun, ary;
           var masterAry = buildAry (dataSize);
           var profilingStart = new Date().getTime();
           for (nRun = 0; nRun < runsPerDataSize; ++nRun) {
              ary = masterAry.slice (); // copy
              s (ary); // sort
              if (!checkSorted(ary)) { print ("Not sorted!"); }
           }
           var profilingElapsed = new Date().getTime() - profilingStart;
           print ("Number of items: " + dataSize + " -- Time needed (in milliseconds): " + profilingElapsed / runsPerDataSize);
        })
     });


     function heapify (ary) {
        var i;
        var arylen = ary.length;
        for (i = 1; i < arylen; ++i) {
           repairUpwards (ary, i);
        }
     }

     function fillVacancy (ary, arylen) {
        var first, second;
        var i = 0;
        while (true) {
           first = (i << 1) + 1;
           second = first + 1;
           if (first >= arylen) { return i; }
           if (second >= arylen) {
              ary [i] = ary [first];
              return first;
           }
           if (ary [first] > ary [second]) {
              ary [i] = ary [first];
              i = first;
           } else {
              ary [i] = ary [second];
              i = second;
           }
        }
     }

     function repairUpwards (ary, fromIndex) {
        var parent, tmp;
        var i = fromIndex;
        while (i > 0) {
           parent = (i-1) >> 1;
           if (ary [parent] < ary [i]) {
              tmp = ary [parent]; ary [parent] = ary [i]; ary [i] = tmp;
           } else {
              return;
           }
           i = parent;
        }
     }

     function heapsort (ary) {
        var tmplast, newVacancy;

        heapify (ary);
        var arylen = ary.length;
        var nRemaining = arylen;

        while (nRemaining > 1) {
           tmplast = ary [nRemaining - 1];
           ary [nRemaining - 1] = ary [0];
           newVacancy = fillVacancy (ary, nRemaining - 1);
           ary [newVacancy] = tmplast;
           repairUpwards (ary, newVacancy);
           --nRemaining;
        } 
     }

     function checkSorted (ary) {
        var i;
        for (i = ary.length - 1; i > 0; --i) {
           if (ary [i] < ary [i-1]) { return false; }
        }
        return true;
     }

     function buildAry (dataSize) {
        var ary = [];
        var i;
        for (i = dataSize - 1; i >= 0; --i) ary.push (Math.random ());
        return ary;
     }
  };

  // user interface
  var outputDivLogger = {
    reset : function () { $('#output').empty (); },

    log : function (msg) {
        var p = $('<p />').text (msg);
        $('#output').append (p);
    }   
  };

  var print = function (msg) {
     outputDivLogger.log (msg);
  };

  var run = function () {
     outputDivLogger.reset ();
     try {
        actualCode ();
     } catch (e) {
        outputDivLogger.log (String(e));
     }
  };


  $(document).ready (function () {
      $("#btnStart").click (function () {
          run ();
      });

      outputDivLogger.log ("[No output yet.]")
  });
  </script>
</head>
<body>
    <h2>Measuring Sorting Speed</h2>
    <div class="content">
        <form>
            <p><input type="button" id="btnStart" value="Run"></p>
        </form>
    </div>
    <h3>Output</h3>
    <div class="content">
        <div id="output"></div>
    </div>
</body>
</html>

示例输出(Firefox):

built-in sort

Number of items: 1000 -- Time needed (in milliseconds): 0.8
Number of items: 2000 -- Time needed (in milliseconds): 1.5
Number of items: 4000 -- Time needed (in milliseconds): 2.8
Number of items: 8000 -- Time needed (in milliseconds): 4.9
Number of items: 16000 -- Time needed (in milliseconds): 8.5
Number of items: 32000 -- Time needed (in milliseconds): 14.9
Number of items: 64000 -- Time needed (in milliseconds): 31.3
Number of items: 128000 -- Time needed (in milliseconds): 68.9
Number of items: 256000 -- Time needed (in milliseconds): 168.7

heapsort

Number of items: 1000 -- Time needed (in milliseconds): 0.2
Number of items: 2000 -- Time needed (in milliseconds): 0.2
Number of items: 4000 -- Time needed (in milliseconds): 0.4
Number of items: 8000 -- Time needed (in milliseconds): 0.8
Number of items: 16000 -- Time needed (in milliseconds): 1.6
Number of items: 32000 -- Time needed (in milliseconds): 3.5
Number of items: 64000 -- Time needed (in milliseconds): 7.6
Number of items: 128000 -- Time needed (in milliseconds): 16.5
Number of items: 256000 -- Time needed (in milliseconds): 34.9

编辑:在下面的一条评论中，有人指出

ary.sort ();

应替换为

ary.sort (function (a, b) { return a - b; });

这确实改善了内置排序的结果，但仍然较慢:

火狐浏览器

built-in sort

Number of items: 1000 -- Time needed (in milliseconds): 0.3
Number of items: 2000 -- Time needed (in milliseconds): 0.4
Number of items: 4000 -- Time needed (in milliseconds): 0.8
Number of items: 8000 -- Time needed (in milliseconds): 1.8
Number of items: 16000 -- Time needed (in milliseconds): 3.5
Number of items: 32000 -- Time needed (in milliseconds): 6.5
Number of items: 64000 -- Time needed (in milliseconds): 10.9
Number of items: 128000 -- Time needed (in milliseconds): 21.8
Number of items: 256000 -- Time needed (in milliseconds): 49.9

heapsort

Number of items: 1000 -- Time needed (in milliseconds): 0.3
Number of items: 2000 -- Time needed (in milliseconds): 0.2
Number of items: 4000 -- Time needed (in milliseconds): 0.3
Number of items: 8000 -- Time needed (in milliseconds): 0.7
Number of items: 16000 -- Time needed (in milliseconds): 1.6
Number of items: 32000 -- Time needed (in milliseconds): 3.4
Number of items: 64000 -- Time needed (in milliseconds): 7.3
Number of items: 128000 -- Time needed (in milliseconds): 15.7
Number of items: 256000 -- Time needed (in milliseconds): 34.4

Chrome :

built-in sort
Number of items: 1000 -- Time needed (in milliseconds): 2.7
Number of items: 2000 -- Time needed (in milliseconds): 1.6
Number of items: 4000 -- Time needed (in milliseconds): 1.6
Number of items: 8000 -- Time needed (in milliseconds): 3.3
Number of items: 16000 -- Time needed (in milliseconds): 6.1
Number of items: 32000 -- Time needed (in milliseconds): 10.7
Number of items: 64000 -- Time needed (in milliseconds): 24.6
Number of items: 128000 -- Time needed (in milliseconds): 53.8
Number of items: 256000 -- Time needed (in milliseconds): 158

heapsort
Number of items: 1000 -- Time needed (in milliseconds): 0.3
Number of items: 2000 -- Time needed (in milliseconds): 0.1
Number of items: 4000 -- Time needed (in milliseconds): 0.4
Number of items: 8000 -- Time needed (in milliseconds): 0.8
Number of items: 16000 -- Time needed (in milliseconds): 2
Number of items: 32000 -- Time needed (in milliseconds): 4.1
Number of items: 64000 -- Time needed (in milliseconds): 8.9
Number of items: 128000 -- Time needed (in milliseconds): 19.6
Number of items: 256000 -- Time needed (in milliseconds): 62.4

最佳答案

免责声明:这不是完整的答案，但我认为值得发布。

<小时/>

我发现的一个问题是您认为复制这些元素的成本很低。如果我用 String(Math.random()) 替换随机调用，我会在 Firefox 中得到以下结果:

built-in sort
Number of items: 1000 -- Time needed (in milliseconds): 0.6
Number of items: 2000 -- Time needed (in milliseconds): 1.2
Number of items: 4000 -- Time needed (in milliseconds): 2.5
Number of items: 8000 -- Time needed (in milliseconds): 5.6
Number of items: 16000 -- Time needed (in milliseconds): 12.5
Number of items: 32000 -- Time needed (in milliseconds): 31.4
Number of items: 64000 -- Time needed (in milliseconds): 77.8
Number of items: 128000 -- Time needed (in milliseconds): 171.9
Number of items: 256000 -- Time needed (in milliseconds): 384.9
heapsort
Number of items: 1000 -- Time needed (in milliseconds): 1
Number of items: 2000 -- Time needed (in milliseconds): 1.6
Number of items: 4000 -- Time needed (in milliseconds): 3.4
Number of items: 8000 -- Time needed (in milliseconds): 7.3
Number of items: 16000 -- Time needed (in milliseconds): 16.2
Number of items: 32000 -- Time needed (in milliseconds): 42
Number of items: 64000 -- Time needed (in milliseconds): 116.4
Number of items: 128000 -- Time needed (in milliseconds): 465.7
Number of items: 256000 -- Time needed (in milliseconds): 757.6

您的堆排序在 Chrome 中仍然更快。我想它在字符串方面做得更好(引用计数？..必须检查)。

值得注意的是，即使是这种情况，对数组进行线性扫描以确定要使用哪种算法也是有意义的。

关于javascript - 内置排序比手工排序慢？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/33582014/

文章推荐： visual-studio-2010 - 在 Visual Studio 2010 中搁置

文章推荐： grails - 如何在项目根目录下测试GrailsPlugin类

文章推荐： node.js - hummus 模块导致 npm 安装失败

文章推荐： hdfs - KAFKA生产者可以读取日志文件吗？

内置 "in"算子的Python源码
我试图在 (C) Python 源代码中找到内置 in 运算符的实现。我在内置函数源代码中搜索过，bltinmodule.c ，但找不到此运算符的实现。我在哪里可以找到这个实现？我的目标是通过扩展此
带重定向的 shell 内置
我们正在开发一个 shell(学校项目)。我们不理解一种行为。为什么内置函数在重定向时不起作用？喜欢 cd - | command 不改变目录。或 export NAME=VALUE | comm
.net - 内置.NET集合分类器的性能
有人问有关如何对列表进行排序的问题。从基本List.Sort()到List.OrderBy()有几种方法。最可笑的是自己动手的SelectionSort。我迅速将其否决，但这使我思考。应用于列表的
内置 qsort 函数中的比较函数
我正在尝试使用 C 中内置的 qsort 函数对结构进行排序 typedef struct abc{ long long int fir; long long int sec; }abc; 在
c# - 内置 CastOrDefault？
我觉得有一些内置的东西。如果对象为空，我想要默认值(或者特别是 0，我只使用十进制/整数)。是否有编写此函数的内置方法？ static int GetDecimalFromObject(object
Java 内置 XML
Java 是否有用于生成和解析文档的内置 XML 库？如果不是，我应该使用哪个第三方？最佳答案 Sun Java 运行时附带 Xerces 和 Xalan 实现，它们提供解析 XML(通过 DOM
带有生成器的 Python 内置 "all"
我对 python 的“all”和生成器有以下问题: G = (a for a in [0,1]) all(list(G)) # returns False - as I expected 但是:
c - 内置/内在测试
我有一些使用 gcc 内部函数的代码。我想包含代码以防缺少内在函数。我该怎么做？ #ifdef __builtin_ctzll 不起作用。最佳答案使用最新版本的 clang，现在可以使用 __ha
performance - (内置)Lua 函数的本地声明以减少开销
人们常说应该在本地重新声明(某些)Lua 函数，因为这样可以减少开销。但这背后的确切规则/原则是什么？我怎么知道哪些功能应该完成，哪些是多余的？还是应该为每个功能完成，甚至是您自己的功能？不幸的是，
python - 如何覆盖 "set"内置？
我想实现以下功能: TestClass values 接受任意数量的 NewClass 对象只有 NewClass 对象没有完全相同的属性值被添加到TestClass.values 我想出了这个:
sql - 内置 MAX 函数只返回一个整数
我正在尝试编写一个存储过程(使用 SQL Server Management Studio 2008 R2)以从表中检索最大测量值。这似乎是一件容易的事，所以我写了一个简短的存储过程来获取 MAX。但
electron - 内置 Electron 应用程序仅将json打印到屏幕上
我刚写了我的第一个Electron应用程序。现在，我正在尝试通过electron-packager构建它。我的package.json看起来像这样: { "name": "pixelcast",
wpf - 内置 WPF 字体列表
我正在寻找在 WPF 应用程序中使用的“安全”字体系列列表 - 应该安装在所有能够运行 WPF 的客户端机器上的字体系列。 Silverlight 有一个明确定义的列表( listed on MSDN
wpf - 内置 WPF IValueConverter
好吧，(在写了几次之后)发现System.Windows.Controls命名空间中已经有一个BooleanToVisibilityConverter，这真是一个惊喜。可能还有更多这样隐藏的节省时间
java - 内置 gradle 插件的版本号是多少？
在我的 gradle 构建文件中，我有以下插件 block plugins { `java-library` jacoco checkstyle } 这些都没有指定版本，但一切
json - 内置 Azure 策略定义
关闭。这个问题需要多问focused 。目前不接受答案。想要改进此问题吗？更新问题，使其仅关注一个问题 editing this post . 已关闭 3 年前。 Improve this ques
javascript - 字符串反转内置 ES6
10 implementations String#reverse 已根据每个浏览器进行分析。自 2011 年以来已对这些实现进行了解释。当 ES6 出现时，有很多代码变得更加优雅和性能。关于
time - 内置@time 宏与基准模块中的宏之间的区别
在 Julia 包 BenchmarkTools 中，有一些像 @btime、@belapse 这样的宏对我来说似乎是多余的，因为 Julia 内置了@time、@elapse 宏。在我看来，这些宏服
c++ - LLVM如何检测和忽略库(内置)函数？
我正在尝试编写一个简单的 LLVM 通行证，其目标如下: 查找所有 call指示。在被调用函数中插入我编写的外部函数。例如，考虑我有以下示例程序: #include #include int
f# - 内置 f# 运算符来组合具有相同输入但不同输出的函数？
我理解 'a) -> (rhs:'a -> 'a) -> 'a 在我感兴趣的情况下，我经常发现自己想要类似 (lhs:'a -> 'b) -> (rhs:'c -> 'b) -> 'b 的东西在侧面

行者123

个人简介

我是一名优秀的程序员,十分优秀！

作者热门文章

滴滴打车优惠券免费领取

全站热门文章

首页

博学

6Ren·AI

商城

javascript - 内置排序比手工排序慢？