Why does this tail recursive loop cause stack overflow in javascript / node?
1
exports.tailLoop = function(A) {
const asc = A.sort((a,b) => a - b)
function tailRecur (rest) {
if (!rest.length) return 0
const pair = rest.splice(0,2)
if (pair[0] != pair[1]){
return pair[0]
} else {
return tailRecur(rest)
}
}
return tailRecur(asc)
}
I have also tried this with:
first = rest.shift()
next = rest.shift()
instead of the splice method.
When I input an array with 1 million elements it fails.
Am I not understanding tail recursion correctly or does tail recursion not work on sizes of 1 million (note sort works fine on a 1 million sized array)
javascript node.js
asked Jan 2 at 1:02
liminal18liminal18
353215
add a comment |
1
exports.tailLoop = function(A) {
const asc = A.sort((a,b) => a - b)
function tailRecur (rest) {
if (!rest.length) return 0
const pair = rest.splice(0,2)
if (pair[0] != pair[1]){
return pair[0]
} else {
return tailRecur(rest)
}
}
return tailRecur(asc)
}
I have also tried this with:
first = rest.shift()
next = rest.shift()
instead of the splice method.
When I input an array with 1 million elements it fails.
Am I not understanding tail recursion correctly or does tail recursion not work on sizes of 1 million (note sort works fine on a 1 million sized array)
javascript node.js
asked Jan 2 at 1:02
liminal18liminal18
353215
2
Only a few environments have implemented proper tail calls. Node.js is not one of them yet.
– CertainPerformance
Jan 2 at 1:03
ok that is an answer any advice on how to deal with large inputs in node? I am running node 10 BTW.
– liminal18
Jan 2 at 1:04
2
I think the only real way is to find a non-recursive way, if the recursive way requires tons of calls.
– CertainPerformance
Jan 2 at 1:06
@CertainPerformance or any type of recursive calls
– juanpa.arrivillaga
Jan 2 at 1:15
add a comment |
1
1
1
exports.tailLoop = function(A) {
const asc = A.sort((a,b) => a - b)
function tailRecur (rest) {
if (!rest.length) return 0
const pair = rest.splice(0,2)
if (pair[0] != pair[1]){
return pair[0]
} else {
return tailRecur(rest)
}
}
return tailRecur(asc)
}
I have also tried this with:
first = rest.shift()
next = rest.shift()
instead of the splice method.
When I input an array with 1 million elements it fails.
Am I not understanding tail recursion correctly or does tail recursion not work on sizes of 1 million (note sort works fine on a 1 million sized array)
javascript node.js
asked Jan 2 at 1:02
liminal18liminal18
353215
exports.tailLoop = function(A) {
const asc = A.sort((a,b) => a - b)
function tailRecur (rest) {
if (!rest.length) return 0
const pair = rest.splice(0,2)
if (pair[0] != pair[1]){
return pair[0]
} else {
return tailRecur(rest)
}
}
return tailRecur(asc)
}
I have also tried this with:
first = rest.shift()
next = rest.shift()
instead of the splice method.
When I input an array with 1 million elements it fails.
Am I not understanding tail recursion correctly or does tail recursion not work on sizes of 1 million (note sort works fine on a 1 million sized array)
javascript node.js
javascript node.js
asked Jan 2 at 1:02
liminal18liminal18
353215
asked Jan 2 at 1:02
liminal18liminal18
353215
asked Jan 2 at 1:02
liminal18liminal18
353215
asked Jan 2 at 1:02
liminal18liminal18
353215
asked Jan 2 at 1:02
liminal18liminal18
353215
353215
2
Only a few environments have implemented proper tail calls. Node.js is not one of them yet.
– CertainPerformance
Jan 2 at 1:03
ok that is an answer any advice on how to deal with large inputs in node? I am running node 10 BTW.
– liminal18
Jan 2 at 1:04
2
I think the only real way is to find a non-recursive way, if the recursive way requires tons of calls.
– CertainPerformance
Jan 2 at 1:06
@CertainPerformance or any type of recursive calls
– juanpa.arrivillaga
Jan 2 at 1:15
add a comment |
2
Only a few environments have implemented proper tail calls. Node.js is not one of them yet.
– CertainPerformance
Jan 2 at 1:03
ok that is an answer any advice on how to deal with large inputs in node? I am running node 10 BTW.
– liminal18
Jan 2 at 1:04
2
I think the only real way is to find a non-recursive way, if the recursive way requires tons of calls.
– CertainPerformance
Jan 2 at 1:06
@CertainPerformance or any type of recursive calls
– juanpa.arrivillaga
Jan 2 at 1:15
2
2
Only a few environments have implemented proper tail calls. Node.js is not one of them yet.
– CertainPerformance
Jan 2 at 1:03
Only a few environments have implemented proper tail calls. Node.js is not one of them yet.
– CertainPerformance
Jan 2 at 1:03
ok that is an answer any advice on how to deal with large inputs in node? I am running node 10 BTW.
– liminal18
Jan 2 at 1:04
ok that is an answer any advice on how to deal with large inputs in node? I am running node 10 BTW.
– liminal18
Jan 2 at 1:04
2
2
I think the only real way is to find a non-recursive way, if the recursive way requires tons of calls.
– CertainPerformance
Jan 2 at 1:06
I think the only real way is to find a non-recursive way, if the recursive way requires tons of calls.
– CertainPerformance
Jan 2 at 1:06
@CertainPerformance or any type of recursive calls
– juanpa.arrivillaga
Jan 2 at 1:15
@CertainPerformance or any type of recursive calls
– juanpa.arrivillaga
Jan 2 at 1:15
add a comment |
3 Answers
3
active
oldest
votes
2
To answer the comment question: how to deal with large inputs in node — You can always find ways to turn a recursive function into a non-recursive function. Sometimes it's not as elegant, but in this case, you are basically using recursion for a loop, which would be faster and easier to understand as a simple loop.
Something like:
function nonRec(A){
const asc = A.sort((a,b) => a - b)
while (asc.length){
const pair = asc.splice(0,2)
if (pair[0] != pair[1])
return pair[0]
}
return 0
}
a = [1, 2, 3, 2, 4, 2, 2, 1, 3]
console.log(nonRec(a))answered Jan 2 at 1:24
Mark MeyerMark Meyer
38.8k33160
unfortunately when you get a million this simple does not return with in 7 minutes at least. tried this.
– liminal18
Jan 2 at 1:28
1
Yes @liminal18 , I was trying to keep the code the same as yours for the most part to illustrate the point. The most obvious optimization is to avoid thesplice()and keep track of where you are in the array with an index variable. It will be much faster because you won't be recreating the giant array on every loop.
– Mark Meyer
Jan 2 at 1:29
yeah keeping track of the index worked
– liminal18
Jan 2 at 1:37
1
@liminal18 "unfortunately when you get a million this simple does not return with in 7 minutes". Well, thewhileloop will certainly be faster than any recursive function (tail recursion or not).
– ibrahim mahrir
Jan 2 at 1:38
1
@liminal18 Also, I just ran aforloop version of this with 50 milion random integers. The sort is by far the biggest bottleneck. The actual iteration took around 300ms. Not sure what you can do about that.
– Mark Meyer
Jan 2 at 1:45
|
show 1 more comment
2
@Mark has already answered the question, so this is merely a refactor of OP's code.
Your code is basically just checking for the two successive items that are equal by looping the array two items a time, this can be drastically optimized by using a for loop to get rid of the expensive calls to splice:
exports.tailLoop = function(A) {
const asc = A.sort((a,b) => a - b);
for(let i = 0; i < asc.length; i += 2) {
if(asc[i] != asc[i + 1]) {
return asc[i];
}
}
return 0;
}
answered Jan 2 at 1:44
ibrahim mahriribrahim mahrir
22.2k41950
2
Yes, this is what I just tried. The sort is by far the biggest bottleneck.
– Mark Meyer
Jan 2 at 1:46
1
@MarkMeyer Yeah, especially with OP's "array with 1 million elements". Removing thesplices might not be a big optimization againstsortbut at least it will help speed things up a little bit, especially with the worst cases where the results are near the end of the array. I'm also begining to think that thesortmight be avoided as I'm getting a vibe that OP is trying to look for duplicates, but I'm not quiet sure
– ibrahim mahrir
Jan 2 at 1:55
ok this is cool because it increments by 2 so thanks. kind of weird for me to come from a functionalist background and find out tail call optimization is not in the language yet.
– liminal18
Jan 2 at 2:15
add a comment |
1
You could try increasing NodeJS maximum call stack, not sure whether this will help in this case.
Another way to skip from the maximum call stack is to change your code from synchronous to asynchronous.
tailLoop = function(A) {
let resolver;
const promise = new Promise((res,_rej)=>{
resolver = res
})
const asc = A.sort((a,b) => a - b)
function tailRecur (rest) {
if (!rest.length) return 0
const pair = rest.splice(0,2)
if (pair[0] != pair[1]){
resolver(pair[0])
} else {
setImmediate(()=>{
tailRecur(rest)
})
}
}
tailRecur(asc)
return promise
}
now it won't exceed maximum call stack.
const a =
for(let i=0;i<10000;i++){
for(let j=0;j<100;j++){
a.push(0)
}
}
a.push(1)
tailLoop(a).then(result=>{
console.log(result) //1
})
By the way, the code above takes minutes to get the result...
I think you could find a better method/algorithm to solve this problem.
answered Jan 2 at 1:44
Timothy LeeTimothy Lee
459211
the while loop is pretty fast less than 20 seconds for a million yeah all those abstractions have a cost I tried using destructuring instead of shift or splice and man that leads to pretty fast stackoverflow. I do like this idea though.
– liminal18
Jan 2 at 2:17
In my case, using the worst-case input, both took about 4 minutes, but the while loop solution was faster 20 seconds.
– Timothy Lee
Jan 2 at 2:34
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "1"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
draft saved
draft discarded
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f54000171%2fwhy-does-this-tail-recursive-loop-cause-stack-overflow-in-javascript-node%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
2
To answer the comment question: how to deal with large inputs in node — You can always find ways to turn a recursive function into a non-recursive function. Sometimes it's not as elegant, but in this case, you are basically using recursion for a loop, which would be faster and easier to understand as a simple loop.
Something like:
function nonRec(A){
const asc = A.sort((a,b) => a - b)
while (asc.length){
const pair = asc.splice(0,2)
if (pair[0] != pair[1])
return pair[0]
}
return 0
}
a = [1, 2, 3, 2, 4, 2, 2, 1, 3]
console.log(nonRec(a))answered Jan 2 at 1:24
Mark MeyerMark Meyer
38.8k33160
unfortunately when you get a million this simple does not return with in 7 minutes at least. tried this.
– liminal18
Jan 2 at 1:28
1
Yes @liminal18 , I was trying to keep the code the same as yours for the most part to illustrate the point. The most obvious optimization is to avoid thesplice()and keep track of where you are in the array with an index variable. It will be much faster because you won't be recreating the giant array on every loop.
– Mark Meyer
Jan 2 at 1:29
yeah keeping track of the index worked
– liminal18
Jan 2 at 1:37
1
@liminal18 "unfortunately when you get a million this simple does not return with in 7 minutes". Well, thewhileloop will certainly be faster than any recursive function (tail recursion or not).
– ibrahim mahrir
Jan 2 at 1:38
1
@liminal18 Also, I just ran aforloop version of this with 50 milion random integers. The sort is by far the biggest bottleneck. The actual iteration took around 300ms. Not sure what you can do about that.
– Mark Meyer
Jan 2 at 1:45
|
show 1 more comment
2
To answer the comment question: how to deal with large inputs in node — You can always find ways to turn a recursive function into a non-recursive function. Sometimes it's not as elegant, but in this case, you are basically using recursion for a loop, which would be faster and easier to understand as a simple loop.
Something like:
function nonRec(A){
const asc = A.sort((a,b) => a - b)
while (asc.length){
const pair = asc.splice(0,2)
if (pair[0] != pair[1])
return pair[0]
}
return 0
}
a = [1, 2, 3, 2, 4, 2, 2, 1, 3]
console.log(nonRec(a))answered Jan 2 at 1:24
Mark MeyerMark Meyer
38.8k33160
unfortunately when you get a million this simple does not return with in 7 minutes at least. tried this.
– liminal18
Jan 2 at 1:28
1
Yes @liminal18 , I was trying to keep the code the same as yours for the most part to illustrate the point. The most obvious optimization is to avoid thesplice()and keep track of where you are in the array with an index variable. It will be much faster because you won't be recreating the giant array on every loop.
– Mark Meyer
Jan 2 at 1:29
yeah keeping track of the index worked
– liminal18
Jan 2 at 1:37
1
@liminal18 "unfortunately when you get a million this simple does not return with in 7 minutes". Well, thewhileloop will certainly be faster than any recursive function (tail recursion or not).
– ibrahim mahrir
Jan 2 at 1:38
1
@liminal18 Also, I just ran aforloop version of this with 50 milion random integers. The sort is by far the biggest bottleneck. The actual iteration took around 300ms. Not sure what you can do about that.
– Mark Meyer
Jan 2 at 1:45
|
show 1 more comment
2
2
2
To answer the comment question: how to deal with large inputs in node — You can always find ways to turn a recursive function into a non-recursive function. Sometimes it's not as elegant, but in this case, you are basically using recursion for a loop, which would be faster and easier to understand as a simple loop.
Something like:
function nonRec(A){
const asc = A.sort((a,b) => a - b)
while (asc.length){
const pair = asc.splice(0,2)
if (pair[0] != pair[1])
return pair[0]
}
return 0
}
a = [1, 2, 3, 2, 4, 2, 2, 1, 3]
console.log(nonRec(a))answered Jan 2 at 1:24
Mark MeyerMark Meyer
38.8k33160
To answer the comment question: how to deal with large inputs in node — You can always find ways to turn a recursive function into a non-recursive function. Sometimes it's not as elegant, but in this case, you are basically using recursion for a loop, which would be faster and easier to understand as a simple loop.
Something like:
function nonRec(A){
const asc = A.sort((a,b) => a - b)
while (asc.length){
const pair = asc.splice(0,2)
if (pair[0] != pair[1])
return pair[0]
}
return 0
}
a = [1, 2, 3, 2, 4, 2, 2, 1, 3]
console.log(nonRec(a))function nonRec(A){
const asc = A.sort((a,b) => a - b)
while (asc.length){
const pair = asc.splice(0,2)
if (pair[0] != pair[1])
return pair[0]
}
return 0
}
a = [1, 2, 3, 2, 4, 2, 2, 1, 3]
console.log(nonRec(a))function nonRec(A){
const asc = A.sort((a,b) => a - b)
while (asc.length){
const pair = asc.splice(0,2)
if (pair[0] != pair[1])
return pair[0]
}
return 0
}
a = [1, 2, 3, 2, 4, 2, 2, 1, 3]
console.log(nonRec(a))answered Jan 2 at 1:24
Mark MeyerMark Meyer
38.8k33160
answered Jan 2 at 1:24
Mark MeyerMark Meyer
38.8k33160
answered Jan 2 at 1:24
Mark MeyerMark Meyer
38.8k33160
answered Jan 2 at 1:24
Mark MeyerMark Meyer
38.8k33160
38.8k33160
unfortunately when you get a million this simple does not return with in 7 minutes at least. tried this.
– liminal18
Jan 2 at 1:28
1
Yes @liminal18 , I was trying to keep the code the same as yours for the most part to illustrate the point. The most obvious optimization is to avoid thesplice()and keep track of where you are in the array with an index variable. It will be much faster because you won't be recreating the giant array on every loop.
– Mark Meyer
Jan 2 at 1:29
yeah keeping track of the index worked
– liminal18
Jan 2 at 1:37
1
@liminal18 "unfortunately when you get a million this simple does not return with in 7 minutes". Well, thewhileloop will certainly be faster than any recursive function (tail recursion or not).
– ibrahim mahrir
Jan 2 at 1:38
1
@liminal18 Also, I just ran aforloop version of this with 50 milion random integers. The sort is by far the biggest bottleneck. The actual iteration took around 300ms. Not sure what you can do about that.
– Mark Meyer
Jan 2 at 1:45
|
show 1 more comment
unfortunately when you get a million this simple does not return with in 7 minutes at least. tried this.
– liminal18
Jan 2 at 1:28
1
Yes @liminal18 , I was trying to keep the code the same as yours for the most part to illustrate the point. The most obvious optimization is to avoid thesplice()and keep track of where you are in the array with an index variable. It will be much faster because you won't be recreating the giant array on every loop.
– Mark Meyer
Jan 2 at 1:29
yeah keeping track of the index worked
– liminal18
Jan 2 at 1:37
1
@liminal18 "unfortunately when you get a million this simple does not return with in 7 minutes". Well, thewhileloop will certainly be faster than any recursive function (tail recursion or not).
– ibrahim mahrir
Jan 2 at 1:38
1
@liminal18 Also, I just ran aforloop version of this with 50 milion random integers. The sort is by far the biggest bottleneck. The actual iteration took around 300ms. Not sure what you can do about that.
– Mark Meyer
Jan 2 at 1:45
unfortunately when you get a million this simple does not return with in 7 minutes at least. tried this.
– liminal18
Jan 2 at 1:28
unfortunately when you get a million this simple does not return with in 7 minutes at least. tried this.
– liminal18
Jan 2 at 1:28
1
1
Yes @liminal18 , I was trying to keep the code the same as yours for the most part to illustrate the point. The most obvious optimization is to avoid the
splice() and keep track of where you are in the array with an index variable. It will be much faster because you won't be recreating the giant array on every loop.– Mark Meyer
Jan 2 at 1:29
Yes @liminal18 , I was trying to keep the code the same as yours for the most part to illustrate the point. The most obvious optimization is to avoid the
splice() and keep track of where you are in the array with an index variable. It will be much faster because you won't be recreating the giant array on every loop.– Mark Meyer
Jan 2 at 1:29
yeah keeping track of the index worked
– liminal18
Jan 2 at 1:37
yeah keeping track of the index worked
– liminal18
Jan 2 at 1:37
1
1
@liminal18 "unfortunately when you get a million this simple does not return with in 7 minutes". Well, the
while loop will certainly be faster than any recursive function (tail recursion or not).– ibrahim mahrir
Jan 2 at 1:38
@liminal18 "unfortunately when you get a million this simple does not return with in 7 minutes". Well, the
while loop will certainly be faster than any recursive function (tail recursion or not).– ibrahim mahrir
Jan 2 at 1:38
1
1
@liminal18 Also, I just ran a
for loop version of this with 50 milion random integers. The sort is by far the biggest bottleneck. The actual iteration took around 300ms. Not sure what you can do about that.– Mark Meyer
Jan 2 at 1:45
@liminal18 Also, I just ran a
for loop version of this with 50 milion random integers. The sort is by far the biggest bottleneck. The actual iteration took around 300ms. Not sure what you can do about that.– Mark Meyer
Jan 2 at 1:45
|
show 1 more comment
2
@Mark has already answered the question, so this is merely a refactor of OP's code.
Your code is basically just checking for the two successive items that are equal by looping the array two items a time, this can be drastically optimized by using a for loop to get rid of the expensive calls to splice:
exports.tailLoop = function(A) {
const asc = A.sort((a,b) => a - b);
for(let i = 0; i < asc.length; i += 2) {
if(asc[i] != asc[i + 1]) {
return asc[i];
}
}
return 0;
}
answered Jan 2 at 1:44
ibrahim mahriribrahim mahrir
22.2k41950
2
Yes, this is what I just tried. The sort is by far the biggest bottleneck.
– Mark Meyer
Jan 2 at 1:46
1
@MarkMeyer Yeah, especially with OP's "array with 1 million elements". Removing thesplices might not be a big optimization againstsortbut at least it will help speed things up a little bit, especially with the worst cases where the results are near the end of the array. I'm also begining to think that thesortmight be avoided as I'm getting a vibe that OP is trying to look for duplicates, but I'm not quiet sure
– ibrahim mahrir
Jan 2 at 1:55
ok this is cool because it increments by 2 so thanks. kind of weird for me to come from a functionalist background and find out tail call optimization is not in the language yet.
– liminal18
Jan 2 at 2:15
add a comment |
2
@Mark has already answered the question, so this is merely a refactor of OP's code.
Your code is basically just checking for the two successive items that are equal by looping the array two items a time, this can be drastically optimized by using a for loop to get rid of the expensive calls to splice:
exports.tailLoop = function(A) {
const asc = A.sort((a,b) => a - b);
for(let i = 0; i < asc.length; i += 2) {
if(asc[i] != asc[i + 1]) {
return asc[i];
}
}
return 0;
}
answered Jan 2 at 1:44
ibrahim mahriribrahim mahrir
22.2k41950
2
Yes, this is what I just tried. The sort is by far the biggest bottleneck.
– Mark Meyer
Jan 2 at 1:46
1
@MarkMeyer Yeah, especially with OP's "array with 1 million elements". Removing thesplices might not be a big optimization againstsortbut at least it will help speed things up a little bit, especially with the worst cases where the results are near the end of the array. I'm also begining to think that thesortmight be avoided as I'm getting a vibe that OP is trying to look for duplicates, but I'm not quiet sure
– ibrahim mahrir
Jan 2 at 1:55
ok this is cool because it increments by 2 so thanks. kind of weird for me to come from a functionalist background and find out tail call optimization is not in the language yet.
– liminal18
Jan 2 at 2:15
add a comment |
2
2
2
@Mark has already answered the question, so this is merely a refactor of OP's code.
Your code is basically just checking for the two successive items that are equal by looping the array two items a time, this can be drastically optimized by using a for loop to get rid of the expensive calls to splice:
exports.tailLoop = function(A) {
const asc = A.sort((a,b) => a - b);
for(let i = 0; i < asc.length; i += 2) {
if(asc[i] != asc[i + 1]) {
return asc[i];
}
}
return 0;
}
answered Jan 2 at 1:44
ibrahim mahriribrahim mahrir
22.2k41950
@Mark has already answered the question, so this is merely a refactor of OP's code.
Your code is basically just checking for the two successive items that are equal by looping the array two items a time, this can be drastically optimized by using a for loop to get rid of the expensive calls to splice:
exports.tailLoop = function(A) {
const asc = A.sort((a,b) => a - b);
for(let i = 0; i < asc.length; i += 2) {
if(asc[i] != asc[i + 1]) {
return asc[i];
}
}
return 0;
}
answered Jan 2 at 1:44
ibrahim mahriribrahim mahrir
22.2k41950
answered Jan 2 at 1:44
ibrahim mahriribrahim mahrir
22.2k41950
answered Jan 2 at 1:44
ibrahim mahriribrahim mahrir
22.2k41950
answered Jan 2 at 1:44
ibrahim mahriribrahim mahrir
22.2k41950
22.2k41950
2
Yes, this is what I just tried. The sort is by far the biggest bottleneck.
– Mark Meyer
Jan 2 at 1:46
1
@MarkMeyer Yeah, especially with OP's "array with 1 million elements". Removing thesplices might not be a big optimization againstsortbut at least it will help speed things up a little bit, especially with the worst cases where the results are near the end of the array. I'm also begining to think that thesortmight be avoided as I'm getting a vibe that OP is trying to look for duplicates, but I'm not quiet sure
– ibrahim mahrir
Jan 2 at 1:55
ok this is cool because it increments by 2 so thanks. kind of weird for me to come from a functionalist background and find out tail call optimization is not in the language yet.
– liminal18
Jan 2 at 2:15
add a comment |
2
Yes, this is what I just tried. The sort is by far the biggest bottleneck.
– Mark Meyer
Jan 2 at 1:46
1
@MarkMeyer Yeah, especially with OP's "array with 1 million elements". Removing thesplices might not be a big optimization againstsortbut at least it will help speed things up a little bit, especially with the worst cases where the results are near the end of the array. I'm also begining to think that thesortmight be avoided as I'm getting a vibe that OP is trying to look for duplicates, but I'm not quiet sure
– ibrahim mahrir
Jan 2 at 1:55
ok this is cool because it increments by 2 so thanks. kind of weird for me to come from a functionalist background and find out tail call optimization is not in the language yet.
– liminal18
Jan 2 at 2:15
2
2
Yes, this is what I just tried. The sort is by far the biggest bottleneck.
– Mark Meyer
Jan 2 at 1:46
Yes, this is what I just tried. The sort is by far the biggest bottleneck.
– Mark Meyer
Jan 2 at 1:46
1
1
@MarkMeyer Yeah, especially with OP's "array with 1 million elements". Removing the
splices might not be a big optimization against sort but at least it will help speed things up a little bit, especially with the worst cases where the results are near the end of the array. I'm also begining to think that the sort might be avoided as I'm getting a vibe that OP is trying to look for duplicates, but I'm not quiet sure– ibrahim mahrir
Jan 2 at 1:55
@MarkMeyer Yeah, especially with OP's "array with 1 million elements". Removing the
splices might not be a big optimization against sort but at least it will help speed things up a little bit, especially with the worst cases where the results are near the end of the array. I'm also begining to think that the sort might be avoided as I'm getting a vibe that OP is trying to look for duplicates, but I'm not quiet sure– ibrahim mahrir
Jan 2 at 1:55
ok this is cool because it increments by 2 so thanks. kind of weird for me to come from a functionalist background and find out tail call optimization is not in the language yet.
– liminal18
Jan 2 at 2:15
ok this is cool because it increments by 2 so thanks. kind of weird for me to come from a functionalist background and find out tail call optimization is not in the language yet.
– liminal18
Jan 2 at 2:15
add a comment |
1
You could try increasing NodeJS maximum call stack, not sure whether this will help in this case.
Another way to skip from the maximum call stack is to change your code from synchronous to asynchronous.
tailLoop = function(A) {
let resolver;
const promise = new Promise((res,_rej)=>{
resolver = res
})
const asc = A.sort((a,b) => a - b)
function tailRecur (rest) {
if (!rest.length) return 0
const pair = rest.splice(0,2)
if (pair[0] != pair[1]){
resolver(pair[0])
} else {
setImmediate(()=>{
tailRecur(rest)
})
}
}
tailRecur(asc)
return promise
}
now it won't exceed maximum call stack.
const a =
for(let i=0;i<10000;i++){
for(let j=0;j<100;j++){
a.push(0)
}
}
a.push(1)
tailLoop(a).then(result=>{
console.log(result) //1
})
By the way, the code above takes minutes to get the result...
I think you could find a better method/algorithm to solve this problem.
answered Jan 2 at 1:44
Timothy LeeTimothy Lee
459211
the while loop is pretty fast less than 20 seconds for a million yeah all those abstractions have a cost I tried using destructuring instead of shift or splice and man that leads to pretty fast stackoverflow. I do like this idea though.
– liminal18
Jan 2 at 2:17
In my case, using the worst-case input, both took about 4 minutes, but the while loop solution was faster 20 seconds.
– Timothy Lee
Jan 2 at 2:34
add a comment |
1
You could try increasing NodeJS maximum call stack, not sure whether this will help in this case.
Another way to skip from the maximum call stack is to change your code from synchronous to asynchronous.
tailLoop = function(A) {
let resolver;
const promise = new Promise((res,_rej)=>{
resolver = res
})
const asc = A.sort((a,b) => a - b)
function tailRecur (rest) {
if (!rest.length) return 0
const pair = rest.splice(0,2)
if (pair[0] != pair[1]){
resolver(pair[0])
} else {
setImmediate(()=>{
tailRecur(rest)
})
}
}
tailRecur(asc)
return promise
}
now it won't exceed maximum call stack.
const a =
for(let i=0;i<10000;i++){
for(let j=0;j<100;j++){
a.push(0)
}
}
a.push(1)
tailLoop(a).then(result=>{
console.log(result) //1
})
By the way, the code above takes minutes to get the result...
I think you could find a better method/algorithm to solve this problem.
answered Jan 2 at 1:44
Timothy LeeTimothy Lee
459211
the while loop is pretty fast less than 20 seconds for a million yeah all those abstractions have a cost I tried using destructuring instead of shift or splice and man that leads to pretty fast stackoverflow. I do like this idea though.
– liminal18
Jan 2 at 2:17
In my case, using the worst-case input, both took about 4 minutes, but the while loop solution was faster 20 seconds.
– Timothy Lee
Jan 2 at 2:34
add a comment |
1
1
1
You could try increasing NodeJS maximum call stack, not sure whether this will help in this case.
Another way to skip from the maximum call stack is to change your code from synchronous to asynchronous.
tailLoop = function(A) {
let resolver;
const promise = new Promise((res,_rej)=>{
resolver = res
})
const asc = A.sort((a,b) => a - b)
function tailRecur (rest) {
if (!rest.length) return 0
const pair = rest.splice(0,2)
if (pair[0] != pair[1]){
resolver(pair[0])
} else {
setImmediate(()=>{
tailRecur(rest)
})
}
}
tailRecur(asc)
return promise
}
now it won't exceed maximum call stack.
const a =
for(let i=0;i<10000;i++){
for(let j=0;j<100;j++){
a.push(0)
}
}
a.push(1)
tailLoop(a).then(result=>{
console.log(result) //1
})
By the way, the code above takes minutes to get the result...
I think you could find a better method/algorithm to solve this problem.
answered Jan 2 at 1:44
Timothy LeeTimothy Lee
459211
You could try increasing NodeJS maximum call stack, not sure whether this will help in this case.
Another way to skip from the maximum call stack is to change your code from synchronous to asynchronous.
tailLoop = function(A) {
let resolver;
const promise = new Promise((res,_rej)=>{
resolver = res
})
const asc = A.sort((a,b) => a - b)
function tailRecur (rest) {
if (!rest.length) return 0
const pair = rest.splice(0,2)
if (pair[0] != pair[1]){
resolver(pair[0])
} else {
setImmediate(()=>{
tailRecur(rest)
})
}
}
tailRecur(asc)
return promise
}
now it won't exceed maximum call stack.
const a =
for(let i=0;i<10000;i++){
for(let j=0;j<100;j++){
a.push(0)
}
}
a.push(1)
tailLoop(a).then(result=>{
console.log(result) //1
})
By the way, the code above takes minutes to get the result...
I think you could find a better method/algorithm to solve this problem.
answered Jan 2 at 1:44
Timothy LeeTimothy Lee
459211
answered Jan 2 at 1:44
Timothy LeeTimothy Lee
459211
answered Jan 2 at 1:44
Timothy LeeTimothy Lee
459211
answered Jan 2 at 1:44
Timothy LeeTimothy Lee
459211
459211
the while loop is pretty fast less than 20 seconds for a million yeah all those abstractions have a cost I tried using destructuring instead of shift or splice and man that leads to pretty fast stackoverflow. I do like this idea though.
– liminal18
Jan 2 at 2:17
In my case, using the worst-case input, both took about 4 minutes, but the while loop solution was faster 20 seconds.
– Timothy Lee
Jan 2 at 2:34
add a comment |
the while loop is pretty fast less than 20 seconds for a million yeah all those abstractions have a cost I tried using destructuring instead of shift or splice and man that leads to pretty fast stackoverflow. I do like this idea though.
– liminal18
Jan 2 at 2:17
In my case, using the worst-case input, both took about 4 minutes, but the while loop solution was faster 20 seconds.
– Timothy Lee
Jan 2 at 2:34
the while loop is pretty fast less than 20 seconds for a million yeah all those abstractions have a cost I tried using destructuring instead of shift or splice and man that leads to pretty fast stackoverflow. I do like this idea though.
– liminal18
Jan 2 at 2:17
the while loop is pretty fast less than 20 seconds for a million yeah all those abstractions have a cost I tried using destructuring instead of shift or splice and man that leads to pretty fast stackoverflow. I do like this idea though.
– liminal18
Jan 2 at 2:17
In my case, using the worst-case input, both took about 4 minutes, but the while loop solution was faster 20 seconds.
– Timothy Lee
Jan 2 at 2:34
In my case, using the worst-case input, both took about 4 minutes, but the while loop solution was faster 20 seconds.
– Timothy Lee
Jan 2 at 2:34
add a comment |
draft saved
draft discarded
Thanks for contributing an answer to Stack Overflow!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
draft saved
draft discarded
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f54000171%2fwhy-does-this-tail-recursive-loop-cause-stack-overflow-in-javascript-node%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
2
Only a few environments have implemented proper tail calls. Node.js is not one of them yet.
– CertainPerformance
Jan 2 at 1:03
ok that is an answer any advice on how to deal with large inputs in node? I am running node 10 BTW.
– liminal18
Jan 2 at 1:04
2
I think the only real way is to find a non-recursive way, if the recursive way requires tons of calls.
– CertainPerformance
Jan 2 at 1:06
@CertainPerformance or any type of recursive calls
– juanpa.arrivillaga
Jan 2 at 1:15