Refactor Javascript to Optimize for Speed

Question

I was able to figure out a working solution to the problem but I would like to know how I could go about refactoring this code to make it faster. Thank you.

/*
    Given a sequence of integers as an array, determine whether it is     
    possible to obtain a strictly increasing sequence by removing no more 
    than one element from the array.
    */

//var array2 = [0, -2, 5, 6]; // expect true
//var array2 = [1, 1, 1, 2, 3]; // expect false
var array2 = [1, 2, 5, 5, 5] // expect false

function almostIncreasingSequence(sequence) {
  let passing = false;
  sequence.forEach((number, idx, array) => {
    let sequence2 = sequence.filter((num, id) => id !== idx);

    let answer = sequence2.every((num, idx, array) => {
      return idx === sequence2.length - 1 || num < sequence2[idx + 1];
    });

    if (answer) {
      passing = true;
    }

  });
  return passing;
}

console.log(almostIncreasingSequence(array2));

@dustytrash: refactoring == restructuring to achieve another purpose. Readability and speed are both purposes. — Ira Baxter
– Ira Baxter, Commented Sep 23, 2018 at 3:35

Without Haste · Accepted Answer · 2018-09-23 12:57:45Z

1

If I'm understanding the problem right, you only need to make 1 pass through the sequence. You're looking for arrays where the difference between index (i-1) and (i) decreases only one time in the whole array.

(this code has gone through several edits to handle edge cases)

function almostIncreasingSequence(sequence) {
    if(sequence.length == 1)
        return true;

    var countDecreases = 0;
    var i = -1;
    for(var index=1; index<sequence.length; index++)
    {
        if(sequence[index-1] > sequence[index])
        {
            countDecreases++;
            i = index;
            if(countDecreases > 1)
                return false;
        }
    }
    var canRemovePreviousElement = (i == 1 || sequence[i-2] <= sequence[i]);
    var cannotRemoveSelectedElement = (i+1 < sequence.length && sequence[i-1] > sequence[i+1]);

    if(canRemovePreviousElement)
        return cannotRemoveSelectedElement;

    return (countDecreases == 1 && !cannotRemoveSelectedElement);
}

// Testing /////////////////////////////////

var passTestCases = {
    "remove index 0": [2, 0, 1, 2],
    "remove index 1": [0, 1, 0, 0, 1],
    "remove index (last-1)": [0, 1, -1, 2],
    "remove index (last)": [0, 1, 2, -1],
    "remove only element": [1]
};
var failTestCases = {
    "remove index 0 or 1": [0, -1, 1, 2],
    "remove any index, all increasing": [1, 2, 5, 5, 5],
    "remove any index, with decrease": [1, 0],
    "one decrease": [0, 1, 2, 0, 1],
    "two decreases": [1, 0, 2, 1],
    "no elements to remove": []
};

runTests(passTestCases, true, almostIncreasingSequence);
runTests(failTestCases, false, almostIncreasingSequence);

function runTests(testCases, expectedResult, method) {
    console.log("\nShould Return " + expectedResult);
    for(var key in testCases)
    {
        var testCase = testCases[key];
        var result = method(testCase);
        console.log(key + ": " + testCase + ": result " + result); 
    }
}

On optimizing for speed:

This method will only make one pass through the array, while the original post uses nested loops. In general, a linear algorithm will be faster than a non-linear algorithm for large data sets.

Comparing the speeds of the two algorithms with these tiny test cases gives inconclusive results.

edited Sep 23, 2018 at 12:57

answered Sep 22, 2018 at 22:45

Without Haste

6623 silver badges7 bronze badges

Sign up to request clarification or add additional context in comments.

15 Comments

Piero Over a year ago

the requirements is "removing no more than one element" so: return (countDecreases <= 1)

Without Haste Over a year ago

@Piero but the example says [1,2,5,5,5] should return false.

Without Haste Over a year ago

@Macrunning "sequence.forEach", "sequence.filter", and "sequence.every" are all loops. There is no particular difference between those and a "for" loop.

Piero Over a year ago

the loops in your example are NESTED loops. This result in slow performance versus a single loop.

Macrunning Over a year ago

I guess I'm trying to understand where in the for loop it it removing element if needed to check for an almost increasing sequence. Is this not checking agains all of the elements in the array?

|

juvian · Accepted Answer · 2018-09-25 15:03:56Z

1

Note that we have a conflict when a[i] <= a[i - 1] as we want a strictly increasing sequence. There are two ways to solve the conflict. One is to remove a[i] from the array, hoping that a[i + 1] won't conflict with a[i - 1]. Another is to remove a[i - 1], hoping that a[i - 2] won't conflict with a[i].

As we have the case that a[i] <= a[i - 1], it should be better to remove a[i - 1] so that our new max element in the sequence is less or equal than before, thus giving more chances to have no conflict on next element. So if we can choose between removing a[i] and a[i - 1], removing a[i - 1] would be better.

We can remove a[i - 1] when a[i - 2] does not conflict with a[i]. In the code, sequence[prev - 1] is this a[i - 2], so in the case where there is a conflict, our only choice left is removing a[i].

To avoid actually removing elements on the array, I used the little trick of just doing a continue, which makes i increase but prev stays the same, thus making the new a[i] compare against a[i - 2] as they should be now next to each other in the strictly increasing sequence.

When we don't fall into the continue, we do prev = i instead of prev += 1 because we would actually need to add 2 to prev after we got into the continue and there was no conflict between a[i] and a[i - 2]. If we added just 1 to prev, we would have prev pointing to a[i - 1], but we can't have that as its the element we "removed" from the sequence.

function isAlmostIncreasingSequence(sequence) {
  var prev = 0;
  var removed = false;
  
  for (var i = 1; i < sequence.length; i++) {
    if (sequence[i] <= sequence[prev]) {
      if (removed == false) {
        removed = true;
        if (prev > 0 && sequence[i] <= sequence[prev - 1]) { // need to remove sequence[i] instead of sequence[prev]
          continue;           
        }
      } else {
        return false;
      }
    }
    prev = i;
  }
  
  return true;
}

var tests = [[0, -2, 5, 6], [1, 1, 1, 2, 3], [1, 2, 5, 5, 5], [1, 3, 2], [0, -2, 5, 6], [1, 2, 3, 4, 5, 3, 5, 6], [1, 1], [1, 2, 5, 3, 5], [1, 2, 3, 4, 3, 6]];

tests.forEach(function(arr){
  console.log(arr.join(","), isAlmostIncreasingSequence(arr));
});

edited Sep 25, 2018 at 15:03

answered Sep 24, 2018 at 19:07

juvian

16.1k2 gold badges42 silver badges40 bronze badges

3 Comments

Macrunning Over a year ago

thanks that passed all the tests. Now trying to process. :)

Macrunning Over a year ago

can you explain this part

if (prev > 0 && sequence[i] <= sequence[prev - 1]) { // need to remove sequence[i] instead of sequence[prev]           continue;                    }

I'm having trouble understanding how we don't get a return false when using the following array [10, 1, 2, 3, 4, 5] (which should return true). I'm going through the code and wouldn't we run in to false on the initial pass because prev = 0. I think I'm not understanding something.

juvian Over a year ago

@Macrunning added a bit of explanation. As for [10, 1, 2, 3, 4, 5], when prev = 0 we do not use continue but we don't do return false, return false is the else for the removed == false condition ^^

Collectives™ on Stack Overflow

Refactor Javascript to Optimize for Speed

2 Answers 2

15 Comments

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

15 Comments

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related