为什么这个(部分)归并排序实现会破坏堆栈?
Why is this (partial) MergeSort Implementation blowing the stack?
我正在经历制作我自己的MergeSort实现的步骤。它是递归的,有一个基本情况。我唯一没有做的是对长度% 2 != 0的数组进行不完美的对半分割。所以你必须代入长度为2^n的数组。我可以稍后再修。然而,当我插入一个长度为4的数组时,我得到一个堆栈溢出。为什么?
代码如下:
function mergeSort(arr){
// step 0 - establish the variables
let
newArr = [],
len = arr.length;
// step 1 - divide the problem into smaller parts until no longer possible
if(len <= 1){
return arr;
}
if (len === 2){
newArr = (arr[0] < arr[1]) ? arr : arr.reverse();
} else {
let
arr1 = arr.slice(0, len/2),
arr2 = arr.slice(len/2, len);
// step 2 - conquer each small problem
arr1 = mergeSort(arr1);
arr2 = mergeSort(arr2);
// step 3 - bring them back together
while(arr1.length > 0 || arr2.length > 0){
if (!arr1[0]){
newArr = [...newArr, ...arr2];
break;
}
if (!arr2[0]) {
newArr = [...newArr, ...arr1];
break;
}
arr1[0] < arr2[0] ? newArr.push(arr1.shift) : newArr.push(arr2.shift);
}
}
// step 4 - return the new array
return newArr;
}
这是我在Node中运行mergeSort([4,3,2,1])
时的堆栈跟踪:
> mergeSort([1,2,3,4])
<--- Last few GCs --->
14198 ms: Mark-sweep 1074.0 (1080.2) -> 862.8 (872.4) MB, 8.8 / 0.0 ms (+ 515.6 ms in 2 steps since start of marking, biggest step 400.2 ms) [GC interrupt] [GC in old space requested].
14859 ms: Mark-sweep 862.8 (872.4) -> 361.0 (370.6) MB, 185.2 / 0.0 ms [allocation failure] [GC in old space requested].
15922 ms: Mark-sweep 895.8 (905.4) -> 539.3 (548.8) MB, 201.6 / 0.0 ms [allocation failure] [GC in old space requested].
<--- JS stacktrace --->
==== JS stack trace =========================================
Security context: 0x186ecb3cfb51 <JS Object>
2: mergeSort [/Users/waleo/Projects/algorithms/mergesort.js:~1] [pc=0x8c4e2bbcf4f] (this=0x186ecb3e6ee9 <JS Global Object>,arr=0x3b3bf2463f21 <JS Array[4]>)
3: /* anonymous */ [repl:1] [pc=0x8c4e2bba890] (this=0x186ecb3e6ee9 <JS Global Object>)
7: /* anonymous */(aka /* anonymous */) [vm.js:22] [pc=0x8c4e2b9eb48] (this=0x186ecb304381 <undefined>)
8: sigintHandlersWrap(aka sigint...
FATAL ERROR: invalid array length Allocation failed - JavaScript heap out of memory
1: node::Abort() [/usr/local/bin/node]
2: node::FatalException(v8::Isolate*, v8::Local<v8::Value>, v8::Local<v8::Message>) [/usr/local/bin/node]
3: v8::internal::V8::FatalProcessOutOfMemory(char const*, bool) [/usr/local/bin/node]
4: v8::internal::Heap::AllocateUninitializedFixedArray(int) [/usr/local/bin/node]
5: v8::internal::Factory::NewUninitializedFixedArray(int) [/usr/local/bin/node]
6: v8::internal::(anonymous namespace)::FastElementsAccessor<v8::internal::(anonymous namespace)::FastPackedObjectElementsAccessor, v8::internal::(anonymous namespace)::ElementsKindTraits<(v8::internal::ElementsKind)2> >::AddArguments(v8::internal::Handle<v8::internal::JSArray>, v8::internal::Handle<v8::internal::FixedArrayBase>, v8::internal::Arguments*, unsigned int, v8::internal::(anonymous namespace)::Where) [/usr/local/bin/node]
7: v8::internal::(anonymous namespace)::DoArrayPush(v8::internal::Isolate*, v8::internal::(anonymous namespace)::BuiltinArguments<(v8::internal::BuiltinExtraArguments)0>) [/usr/local/bin/node]
8: v8::internal::Runtime_ArrayPush(int, v8::internal::Object**, v8::internal::Isolate*) [/usr/local/bin/node]
9: 0x8c4e2a079a7
[1] 65429 abort node
怎么了?我怎样才能解决这个问题,使递归归并排序不会破坏我的堆栈?
您不能用()
调用.shift
-将其改为.shift()
相关文章:
- 如何使用动画实现纸张推车
- 客户端服务器REST API captcha实现
- 如何实现此布局
- Rails File_field最大堆栈大小
- d3中堆栈函数和嵌套函数之间的差异
- 是什么让一个“;Uncaught RangeError:超过了最大调用堆栈大小“;错误(Chrome,在其他浏览器中显示
- Meteor忘记了密码的实现
- 使用Native Sockets在Android中实现WebSockets
- 在样板文件中实现Ajax
- instanceof是如何在JavaScript中实现的
- 如何正确实现Jquery多选小部件
- 实现一个建立在google.com之上的自定义搜索引擎
- 多个组件是如何实现的
- window.location使用jquery mobile实现chrome跳转
- 如何在OpenERP中实现网络摄像头
- Node.js使用Series函数(模式?)实现流控制时出现意外结果
- CakePHP3:如何使用视图单元格实现Facebook风格或堆栈式用户通知
- "超过了最大调用堆栈大小“;在处理JS时实现Fractal工厂时出错
- 用javascript实现if-then-else-if-else堆栈的更简单方法是什么
- 为什么这个(部分)归并排序实现会破坏堆栈?