草庐IT

javascript - native JavaScript 排序的执行速度比实现的合并排序和快速排序慢

coder 2023-05-29 原文

我已经实现了一个合并排序和一个快速排序来将它们与原生 JavaScript 排序进行比较。对于快速排序，我尝试使用此算法:view algorithm on youtube .两种算法都使用尽可能少的内存，对于合并排序，为每个递归调用传递一个辅助数组(以避免开销)，对于快速排序，开始和结束位置的位置。我正在使用排序来管理 NodeJs 应用程序中的大量数据。

下面你有合并排序、快速排序和原生 JavaScript 排序，你可以测试性能

问题是:为什么原生 JavaScript 执行速度较慢？

就我而言:

Chrome - 合并排序:测量:1997.920ms；快速排序:测量:1755.740ms； native :测量:4988.105ms
Node :归并排序:测量:2233.413ms；快速排序:测量:1876.055ms； native :测量:6317.118ms

合并排序 

var length = 10000000; //  ten millions;
var arr = [];
for (let i = length; i > 0; i--) {
  // random array
  arr.push(parseInt(Math.random() * 1000000000));
}
var mergeSort = function(array) {
  function merge(arr, aux, lo, mid, hi) {
    for (var k = lo; k <= hi; k++) {
      aux[k] = arr[k];
    }

    var i = lo;
    var j = mid + 1;
    for (var k = lo; k <= hi; k++) {
      if (i > mid) {
        arr[k] = aux[j++];
      } else if (j > hi) {
        arr[k] = aux[i++];
      } else if (aux[i] < aux[j]) {
        arr[k] = aux[i++];
      } else {
        arr[k] = aux[j++];
      }
    }
  }

  function sort(array, aux, lo, hi) {
    if (hi <= lo) return;
    var mid = Math.floor(lo + (hi - lo) / 2);
    sort(array, aux, lo, mid);
    sort(array, aux, mid + 1, hi);

    merge(array, aux, lo, mid, hi);
  }

  function merge_sort(array) {
    var aux = array.slice(0);
    sort(array, aux, 0, array.length - 1);
    return array;
  }

  return merge_sort(array);
}


console.time('measure');
mergeSort(arr);
console.timeEnd('measure');
console.log(arr[0], arr[1]);

快速排序 

var length = 10000000; //  ten millions;
var arr = [];
for (let i = length; i > 0; i--) {
  // random array
  arr.push(parseInt(Math.random() * 1000000000));
}

function quickSort(arr, leftPos, rightPos, arrLength) {
  let initialLeftPos = leftPos;
  let initialRightPos = rightPos;
  let direction = true;
  let pivot = rightPos;
  while ((leftPos - rightPos) < 0) {
    if (direction) {
      if (arr[pivot] < arr[leftPos]) {
        quickSort.swap(arr, pivot, leftPos);
        pivot = leftPos;
        rightPos--;
        direction = !direction;
      } else
        leftPos++;
    } else {
      if (arr[pivot] <= arr[rightPos]) {
        rightPos--;
      } else {
        quickSort.swap(arr, pivot, rightPos);
        leftPos++;
        pivot = rightPos;
        direction = !direction;
      }
    }
  }
  if (pivot - 1 > initialLeftPos) {
    quickSort(arr, initialLeftPos, pivot - 1, arrLength);
  }
  if (pivot + 1 < initialRightPos) {
    quickSort(arr, pivot + 1, initialRightPos, arrLength);
  }
}
quickSort.swap = (arr, el1, el2) => {
  let swapedElem = arr[el1];
  arr[el1] = arr[el2];
  arr[el2] = swapedElem;
}
arrLength = arr.length;
console.time('measure');
quickSort(arr, 0, arrLength - 1, arrLength);
console.log(arr[0], arr[1]);
console.timeEnd('measure');

原生 Javascript 排序 

var length = 10000000; //  ten millions;
var arr = [];
for (let i = length; i > 0; i--) {
  // random array
  arr.push(parseInt(Math.random() * 100000000));
}

console.time('measure');
arr.sort(function compareNumbers(a, b) {
  return a - b;
});
console.timeEnd('measure');

console.log(arr[0], arr[1]);

最佳答案

那么为什么原生排序更慢呢？查看中的代码

https://github.com/v8/v8/blob/0c76b0ae850027006d5ec0d92449e449d996d3bb/src/js/array.js#L744

问题似乎是 GetThirdIndex()。当分区大小> 1000时调用它，我假设它用于防止快速排序最坏情况的性能，但开销很大，因为它创建内部对数组并对它们进行排序，并且这些对的排序可能导致进一步递归调用 GetThirdIndex()。这与与分割原始数组和分割内部对数组相关的递归调用相结合。

由于这些示例的测试数据是随机数据，因此 Relu 的快速排序不需要 GetThirdIndex() 之类的东西。还检查了数组中的“孔”，但我认为这并不重要。

GetThirdIndex() 的替代方法是中位数的就地中位数:

http://en.wikipedia.org/wiki/Median_of_medians

合并排序比快速排序更快，这些方法用于防止最坏的情况，但它需要一个与原始数组大小相同或一半大小的辅助数组。

Introsort 是快速排序和堆排序的混合体，如果递归级别太深，可以切换到堆排序:

http://en.wikipedia.org/wiki/Introsort

下面的第二个合并排序示例使用比较函数进行公平比较。它比 native 版本快得多。对于 Chrome，比较功能对整体时间影响不大。在 Firefox 的情况下，比较功能更有效。在火狐的情况下，原生版本因内存不足而失败，所以我无法比较。

这些是自顶向下合并排序的更快版本，原始发布者对此感到“好奇”，使用相互递归函数来避免复制和稍微优化的 merge()(每次比较两个条件)。

Firefox 的结果(时间略有不同)

native sort - failed for out of memory.
Relu's merge sort - 1.8 seconds
Relu's quick sort - 1.3 seconds
optimized merge sort - 1.4 seconds
optimized merge sort with compare - 1.8 seconds

Chrome 的结果(时间有所不同)

native sort - 5.3 seconds
Relu's merge sort - 2.1 seconds
Relu's quick sort - 1.8 seconds
optimized merge sort - 1.6 seconds
optimized merge sort with compare - 1.7 seconds

合并排序

var length = 10000000; //  ten millions;
var arr = [];
for (let i = length; i > 0; i--) {
  // random array
  arr.push(parseInt(Math.random() * 1000000000));
}
var mergeSort = function(array) {
  function merge(arr, aux, lo, mid, hi) {
    var i = lo;
    var j = mid + 1;
    var k = lo;
    while(true){
      if(arr[i] <= arr[j]){
        aux[k++] = arr[i++];
        if(i > mid){
          do
            aux[k++] = arr[j++];
          while(j <= hi);
          break;
        }
      } else {
        aux[k++] = arr[j++];
        if(j > hi){
          do
            aux[k++] = arr[i++];
          while(i <= mid);
          break;
        }
      }
    }
  }

  function sortarrtoaux(arr, aux, lo, hi) {
    if (hi < lo) return;
    if (hi == lo){
        aux[lo] = arr[lo];
        return;
    }
    var mid = Math.floor(lo + (hi - lo) / 2);
    sortarrtoarr(arr, aux, lo, mid);
    sortarrtoarr(arr, aux, mid + 1, hi);
    merge(arr, aux, lo, mid, hi);
  }

  function sortarrtoarr(arr, aux, lo, hi) {
    if (hi <= lo) return;
    var mid = Math.floor(lo + (hi - lo) / 2);
    sortarrtoaux(arr, aux, lo, mid);
    sortarrtoaux(arr, aux, mid + 1, hi);
    merge(aux, arr, lo, mid, hi);
  }

  function merge_sort(arr) {
    var aux = arr.slice(0);
    sortarrtoarr(arr, aux, 0, arr.length - 1);
    return arr;
  }

  return merge_sort(array);
}

console.time('measure');
mergeSort(arr);
console.timeEnd('measure');
console.log(arr[0], arr[1]);

使用比较功能合并排序

var length = 10000000; //  ten millions;
var arr = [];
for (let i = length; i > 0; i--) {
  // random array
  arr.push(parseInt(Math.random() * 1000000000));
}
var mergeSort = function(array, comparefn) {
  function merge(arr, aux, lo, mid, hi, comparefn) {
    var i = lo;
    var j = mid + 1;
    var k = lo;
    while(true){
      var cmp = comparefn(arr[i], arr[j]);
      if(cmp <= 0){
        aux[k++] = arr[i++];
        if(i > mid){
          do
            aux[k++] = arr[j++];
          while(j <= hi);
          break;
        }
      } else {
        aux[k++] = arr[j++];
        if(j > hi){
          do
            aux[k++] = arr[i++];
          while(i <= mid);
          break;
        }
      }
    }
  }

  function sortarrtoaux(arr, aux, lo, hi, comparefn) {
    if (hi < lo) return;
    if (hi == lo){
        aux[lo] = arr[lo];
        return;
    }
    var mid = Math.floor(lo + (hi - lo) / 2);
    sortarrtoarr(arr, aux, lo, mid, comparefn);
    sortarrtoarr(arr, aux, mid + 1, hi, comparefn);
    merge(arr, aux, lo, mid, hi, comparefn);
  }

  function sortarrtoarr(arr, aux, lo, hi, comparefn) {
    if (hi <= lo) return;
    var mid = Math.floor(lo + (hi - lo) / 2);
    sortarrtoaux(arr, aux, lo, mid, comparefn);
    sortarrtoaux(arr, aux, mid + 1, hi, comparefn);
    merge(aux, arr, lo, mid, hi, comparefn);
  }

  function merge_sort(arr, comparefn) {
    var aux = arr.slice(0);
    sortarrtoarr(arr, aux, 0, arr.length - 1, comparefn);
    return arr;
  }

  return merge_sort(array, comparefn);
}

console.time('measure');
mergeSort(arr, function compareNumbers(a, b) {
  return a - b;
});
console.timeEnd('measure');
// check result
for (let i = 1; i < length; i++) {
    if(arr[i] < arr[i-1]){
        console.log('error');
        break;
    }
}
console.log(arr[0], arr[1]);

旁注:原生排序不稳定:

原生 Javascript 排序 - 测试稳定性 

var length = 100000;
var arr = [];
var j;
for (let i = 0; i < length; i++) {
  j = parseInt(Math.random() * 100);
  arr[i] = [j, i];
}

console.time('measure');
arr.sort(function compareNumbers(a, b) {
  return a[0] - b[0];
});
console.timeEnd('measure');

for (let i = 1; i < length; i++) {
    if( (arr[i][0] == arr[i-1][0]) &&
        (arr[i][1] <  arr[i-1][1]) ){
        console.log('not stable');
        console.log(arr[i-1][0], arr[i-1][1]);
        console.log(arr[i  ][0], arr[i  ][1]);
        break;
    }
}

原生 Javascript 排序 - 更改比较以使其稳定 

var length = 100000;
var arr = [];
var j;
for (let i = 0; i < length; i++) {
  j = parseInt(Math.random() * 100);
  arr[i] = [j, i];
}

console.time('measure');
arr.sort(function compareNumbers(a, b) {
  if(a[0] == b[0])
    return a[1] - b[1];
  return a[0] - b[0];
});
console.timeEnd('measure');

for (let i = 1; i < length; i++) {
    if( (arr[i][0] == arr[i-1][0]) &&
        (arr[i][1] <  arr[i-1][1]) ){
        console.log('not stable');
        console.log(arr[i-1][0], arr[i-1][1]);
        console.log(arr[i  ][0], arr[i  ][1]);
        break;
    }
}

关于javascript - native JavaScript 排序的执行速度比实现的合并排序和快速排序慢，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/38732480/

javascriptarrsectionconsolenode.jsalgorithmperformancesorting

有关javascript - native JavaScript 排序的执行速度比实现的合并排序和快速排序慢的更多相关文章

  1. ruby-openid:执行发现时未设置@socket - 2

    我在使用omniauth/openid时遇到了一些麻烦。在尝试进行身份验证时，我在日志中发现了这一点:OpenID::FetchingError:Errorfetchinghttps://www.google.com/accounts/o8/.well-known/host-meta?hd=profiles.google.com%2Fmy_username:undefinedmethod`io'fornil:NilClass重要的是undefinedmethodio'fornil:NilClass来自openid/fetchers.rb，在下面的代码片段中:moduleNetclass

  2. ruby - Chef 执行非顺序配方 - 2

    我遵循了教程http://gettingstartedwithchef.com/,第1章。我的运行list是"run_list":["recipe[apt]","recipe[phpap]"]我的phpapRecipe默认Recipeinclude_recipe"apache2"include_recipe"build-essential"include_recipe"openssl"include_recipe"mysql::client"include_recipe"mysql::server"include_recipe"php"include_recipe"php::modul

  3. ruby - 如果指定键的值在数组中相同，如何合并哈希 - 2

    我有一个这样的哈希数组:[{:foo=>2,:date=>Sat,01Sep2014},{:foo2=>2,:date=>Sat,02Sep2014},{:foo3=>3,:date=>Sat,01Sep2014},{:foo4=>4,:date=>Sat,03Sep2014},{:foo5=>5,:date=>Sat,02Sep2014}]如果:date相同，我想合并哈希值。我对上面数组的期望是:[{:foo=>2,:foo3=>3,:date=>Sat,01Sep2014},{:foo2=>2,:foo5=>5:date=>Sat,02Sep2014},{:foo4=>4,:dat

  4. ruby - 如何根据特征实现 FactoryGirl 的条件行为 - 2

    我有一个用户工厂。我希望默认情况下确认用户。但是鉴于unconfirmed特征，我不希望它们被确认。虽然我有一个基于实现细节而不是抽象的工作实现，但我想知道如何正确地做到这一点。factory:userdoafter(:create)do|user,evaluator|#unwantedimplementationdetailshereunlessFactoryGirl.factories[:user].defined_traits.map(&:name).include?(:unconfirmed)user.confirm!endendtrait:unconfirmeddoenden

  5. ruby - 为什么 Ruby 的 each 迭代器先执行？ - 2

    我在用Ruby执行简单任务时遇到了一件奇怪的事情。我只想用每个方法迭代字母表，但迭代在执行中先进行:alfawit=("a".."z")puts"That'sanalphabet:\n\n#{alfawit.each{|litera|putslitera}}"这段代码的结果是:(缩写)abc⋮xyzThat'sanalphabet:a..z知道为什么它会这样工作或者我做错了什么吗？提前致谢。 最佳答案 因为您的each调用被插入到在固定字符串之前执行的字符串文字中。此外，each返回一个Enumerable，实际上您甚至打印它。试试

  6. ruby - 检查是否通过 require 执行或导入了 Ruby 程序 - 2

    如何检查Ruby文件是否是通过“require”或“load”导入的，而不是简单地从命令行执行的？例如:foo.rb的内容:puts"Hello"bar.rb的内容require'foo'输出:$./foo.rbHello$./bar.rbHello基本上，我想调用bar.rb以不执行puts调用。 最佳答案 将foo.rb改为:if__FILE__==$0puts"Hello"end检查__FILE__-当前ruby​​文件的名称-与$0-正在运行的脚本的名称。 关于ruby-检查是否

  7. 华为OD机试用Python实现 -【明明的随机数】 2023Q1A - 2

    华为OD机试题本篇题目：明明的随机数题目输入描述输出描述：示例1输入输出说明代码编写思路最近更新的博客华为od2023|什么是华为od，od薪资待遇，od机试题清单华为OD机试真题大全，用Python解华为机试题|机试宝典【华为OD机试】全流程解析+经验分享,题型分享,防作弊指南华为o

  8. 基于C#实现简易绘图工具【100010177】 - 2

    C#实现简易绘图工具一.引言实验目的:通过制作窗体应用程序(C#画图软件),熟悉基本的窗体设计过程以及控件设计,事件处理等,熟悉使用C#的winform窗体进行绘图的基本步骤,对于面向对象编程有更加深刻的体会.Tutorial任务设计一个具有基本功能的画图软件**·包括简单的新建文件,保存,重新绘图等功能**·实现一些基本图形的绘制,包括铅笔和基本形状等,学习橡皮工具的创建**·设计一个合理舒适的UI界面**注明:你可能需要先了解一些关于winform窗体应用程序绘图的基本知识,以及关于GDI+类和结构的知识二.实验环境Windows系统下的visualstudio2017C#窗体应用程序三.

  9. postman——集合——执行集合——测试脚本——pm对象简单示例02 - 2

    //1.验证返回状态码是否是200pm.test("Statuscodeis200",function(){pm.response.to.have.status(200);});//2.验证返回body内是否含有某个值pm.test("Bodymatchesstring",function(){pm.expect(pm.response.text()).to.include("string_you_want_to_search");});//3.验证某个返回值是否是100pm.test("Yourtestname",function(){varjsonData=pm.response.json

  10. ruby-on-rails - rbenv:从 RVM 移动到 rbenv 后，在 Jenkins 执行 shell 中找不到命令 - 2

    我从Ubuntu服务器上的RVM转移到rbenv。当我使用RVM时，使用bundle没有问题。转移到rbenv后，我在Jenkins的执行shell中收到“找不到命令”错误。我内爆并删除了RVM，并从~/.bashrc'中删除了所有与RVM相关的行。使用后我仍然收到此错误:rvmimploderm~/.rvm-rfrm~/.rvmrcgeminstallbundlerecho'exportPATH="$HOME/.rbenv/bin:$PATH"'>>~/.bashrcecho'eval"$(rbenvinit-)"'>>~/.bashrc.~/.bashrcrbenvversions

随机推荐