1

I have a sparse array; that is, an array in which some elements have been deleted. Elements are constantly being added and deleted from the middle, so it is very large and very sparse.

At some point, every element will be undefined, but the length won't be 0 — so it is empty, but it doesn't express that. How can I check if this has happened?

The best that I can think of is to loop through the whole monster and check if they're all undefined. But that would be too inefficient for my application.

rvighne
  • 20,755
  • 11
  • 51
  • 73
  • 1
    If possible, you could keep a separate counter that keep tracks of the number of elements in the array. – Felix Kling Apr 07 '14 at 19:30
  • There is a way to check each element's value without actually looking at each element. But with some more bookkeeping, you could check if the # of elements in the array is 0. – Chris Dargis Apr 07 '14 at 19:30
  • Are you able to pop values out of the list instead of making them `undefined`? – Farmer Joe Apr 07 '14 at 19:31
  • 1
    You may want to consider using an object (with numeric keys) instead of an array. The only drawback is that you cannot iterate the items in key order. – cybersam Apr 07 '14 at 19:34
  • @farmerjoe: I use `delete` on a certain index, I don't explicitly set them `undefined`. Since I usually delete from the middle of the array, `pop` is out of the question. – rvighne Apr 07 '14 at 19:35
  • See my answer for a workaround for this. – Farmer Joe Apr 07 '14 at 19:37
  • @cybersam: But how would I test for emptiness on that? – rvighne Apr 07 '14 at 19:40
  • 1
    You could also use a `for...in` loop to iterate over the array/array. The run time grow linearly with the number of elements in the array. If you `delete` the elements, there won't be any so the loop won't be executed. Like this `var count = 0; for (var _ in obj) { count++: }` – Felix Kling Apr 07 '14 at 19:40
  • 1
    See http://stackoverflow.com/questions/4994201/is-object-empty – cybersam Apr 07 '14 at 19:42
  • Why not add a simple if/else before actually utilizing the input? If it is empty, simply do nothing, or call the function again to recheck (basically a loop) but if you just check before using it you rid yourself of any undefined errors. – WASasquatch Apr 07 '14 at 19:51
  • Depending on the use-case, the better choice might be avoiding a sparse structure in the first place. They are generally something you want to avoid, except for certain cases. – Ingo Bürk Apr 07 '14 at 20:01

5 Answers5

2

Two solutions I can think of. Both require some modification to your interactions with the array.

First solution

Keep a counter.

If you simply keep a counter that represents how many elements in the array are actually there, then the emptiness check is a mere comparison.

var n = 0;

// Adding something to the array:
myArr[2] = somethingDefined;
n ++;

// Removing from the array:
delete myArr[2];
n --;

// Check if empty
if(n == 0) {
   console.log("myArr is empty.");
}

Second solution

Use splice instead of delete

splice will actually modify the array instead of setting the values to undefined. Example:

myArr.splice(2, 1); // Get rid of myArr[2]

And this mutates the array and will change .length so you can easily check the actual length of the array. Note that splice is less efficient (and given you seem to care about the efficiency, the first solution is probably more applicable).

Chris
  • 26,544
  • 5
  • 58
  • 71
  • 1
    If you're gonna keep a counter, I would strongly suggest encapsulating this functionality to *enforce* the counter to be in sync. It's too easy to forget it and that can be a real pain in the *** bug. – Ingo Bürk Apr 07 '14 at 20:03
  • Keeping a counter is not technically a solution, but OK. Better than the alternative. – rvighne Apr 10 '14 at 21:18
2

You can use the array method some that quits when it hits any non falsy value:

a.some(Boolean); // returns false if the array has no truthy values

or, if false is a possible value, check for not === undefined:

a.some(function(itm){
   return itm !==undefined;
});
kennebec
  • 102,654
  • 32
  • 106
  • 127
1

Though this may not be the most efficient, it does the trick quite succinctly:

Object.keys(myArr).length === 0

It might be appropriate for less performance-intensive applications.

rvighne
  • 20,755
  • 11
  • 51
  • 73
  • That's certainly easier-to-read (and probably write) code, but it is even less efficient than simply iterating over the array. – Chris Apr 07 '14 at 19:53
  • 1
    @Chris: Yeah, I was afraid of that. I put it there so it'd be useful to one-liner-hunters in the future. – rvighne Apr 07 '14 at 19:55
  • @Chris: I just ran [this test](http://jsperf.com/check-if-sparse-array-is-empty) on Chrome and nearly had a heart attack. Object.keys is *faster*! Sadly, this doesn't hold true on Firefox. – rvighne Apr 07 '14 at 20:07
  • Huh, very interesting! I'm surprised. Thanks for sharing. – Chris Apr 07 '14 at 20:13
  • @Chris: Well, your brute force method is much faster and makes sense. If you only want to know whether the array/object is empty or not, then you can exit the loop once you found the first none empty element. – Felix Kling Apr 07 '14 at 22:10
0

You can simulate the removal of your list by using a call to splice:

myArr.splice(indexToRemoveAt,nubmerOfElementsToRemove);

So for your use case:

myArr.splice(indexToRemoveAt,1)
Farmer Joe
  • 6,020
  • 1
  • 30
  • 40
0

Worked for me sparseArray.size()==0

Arthur Melo
  • 454
  • 5
  • 13