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)

liminal18
  • 563
  • 7
  • 21

3 Answers3

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))
Mark
  • 90,562
  • 7
  • 108
  • 148
  • unfortunately when you get a million this simple does not return with in 7 minutes at least. tried this. – liminal18 Jan 02 '19 at 01: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 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 Jan 02 '19 at 01:29
  • 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 02 '19 at 01:38
  • 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 Jan 02 '19 at 01:45
  • @ibrahimmahrir weird I was finding the tail recursive method was faster than a while loop when the array has 50,001 elements. – liminal18 Jan 02 '19 at 02:19
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;
}
ibrahim mahrir
  • 31,174
  • 5
  • 48
  • 73
  • 2
    Yes, this is what I just tried. The sort is by far the biggest bottleneck. – Mark Jan 02 '19 at 01:46
  • 1
    @MarkMeyer Yeah, especially with OP's _"array with 1 million elements"_. Removing the `splice`s 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 02 '19 at 01: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 02 '19 at 02:15
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.

Timothy Lee
  • 768
  • 4
  • 15
  • 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 02 '19 at 02: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 02 '19 at 02:34