JavaScript - more efficient way to truncate an array

Question

I have an int array sorted ascending and I would like to remove array items from the tail according to the specific boundary. What is a better way to truncate an array in my case? Consider next code snippets:

var a = [1, 2, 3, 4];
var length = a.length;
var boundary = 2;
var count = 0;
for (var i = length - 1; i >= 0; i--) {
    if (a[i] > boundary) {
        a[i] = null; // or delete a[i] ???
        count++;
    }
}
a.length -= count;

Or the same but using splice:

for (var i = length - 1; i >= 0; i--) {
    if (a[i] > boundary) {
        a.splice(i, 1);
    }
}

Those two snippets of code do very different things, and neither of them remove elements that are only on the tail. To see what I mean, use [4, 3, 2, 1] as your array. — castletheperson
– castletheperson, Commented Dec 22, 2017 at 22:21
Ah, I didn't notice that detail. You should be using a binary search then. — castletheperson
– castletheperson, Commented Dec 22, 2017 at 22:27
Good point! Didn't think about that but need to give it a try! — Alex
– Alex, Commented Dec 22, 2017 at 22:29

Jonas Wilms · Accepted Answer · 2017-12-22 22:20:36Z

8

 a.length -= count;

Thats sufficient ;) (as length is not a simple property, but rather a getter/setter which truncates/adds elements (ref))

Alternatively use splice:

 a.splice(-count, count);

edited Dec 22, 2017 at 22:20

answered Dec 22, 2017 at 22:17

Jonas Wilms

139k20 gold badges164 silver badges164 bronze badges

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

7 Comments

Alex Over a year ago

Can you explain why? What is happening under the hood?

Barmar Over a year ago

@Alex It's probably similar to splice(), but it doesn't need to create an array of the removed elements, or worry about shifting the elements after the splice down.

Paul Over a year ago

If I interpreted the OPs question correctly, he wants to delete the x tail elements which are > boundary, not specifically #count elements. count is just a variable he used to track how many elements were > boundary in the first snippet. a.length -= count; is already exactly what he does in that sample, once he has determined the number of elements to remove, but that is not already known.

Alex Over a year ago

@Paulpro You are right, count is a way to track the number of elements that I want to cut off from the tail.

Jonas Wilms Over a year ago

@paulpro imo the real question is a[i] = null; // or delete a[i] ??? which ive answered above

|

Paul · Accepted Answer · 2017-12-22 22:21:21Z

2

In modern engines, or with a shim, you can use Array.prototype.findIndex:

var a = [1, 2, 3, 4];
var boundary = 2;
a.length = a.findIndex( x => x > boundary );
console.log( a );

Since you're array is sorted you can also just use Array.prototype.filter:

var a = [1, 2, 3, 4];
var boundary = 2;
a = a.filter( x => x <= boundary );
console.log( a );

which may be slightly (negligibly) slower if the array is huge, but has more support in older engines.

answered Dec 22, 2017 at 22:21

Paul

142k28 gold badges285 silver badges272 bronze badges

Comments

traktor · Accepted Answer · 2017-12-23 13:00:52Z

Don't delete array entries at the end of an array to truncate it. Deleting array entries removes them from the array by creating a sparse array: the length property of the array remains unchanged:

var a = [1,2,3,4];
console.log( "a.length %s", a.length);
delete a[3];
console.log( "a[3] after deletion: %s", a[3]);
console.log( "a.length after deletion %s", a.length);
console.log( "a[3] still exists: %s", a.hasOwnProperty("3"));

Similar considerations apply to setting array entries to null. They will no longer test as truthy in a conditional expression, but have not been removed. As before the length of the array will remain unchanged.

Setting the length of the an array to something shorter than its existing value will truncate it in place. There are many ways of finding the boundary position at which to truncate the array. I suggest choosing one that appears natural to you and works in target browsers. E.G. using forSome on a sorted array may not meet your requirements :)

var a = [1,2,3,4];
var boundary = 2;
a.some(
   (c,i) => {
      if( c > boundary)
      {  a.length = i;
         return true;
      }
   }
);

console.log( a)

If using splice, note that all entries from the boundary position to the end of array can be deleted in one call rather than deleting them one at a time:

var a = [1,2,3,4];
var boundary = 2;
for( var i = a.length-1; a[i]>boundary; --i) {} // linear search
a.splice(i+1);
console.log(a);

Collectives™ on Stack Overflow

JavaScript - more efficient way to truncate an array

3 Answers 3

7 Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

7 Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related