5

I'm aware that arrays in JavaScript differ from your traditional arrays in the sense that they are just objects under the hood. Because of this, JavaScript allows for sparse arrays to behave in a similar manner to dense arrays when it comes to memory management. When working with a sparse array, is there a way to reach the next element in that array efficiently?

For example, given this array:

var foo = [];
foo[0] = '0';
foo[1] = '1';
foo[2] = '2';
foo[100] = '100';

console.log(foo.length); // => 101

I'm know that there's a way to get all of the elements by using for ... in like so:

for (var n in foo){
    console.log(n);
}
// Output: 
// 0
// 1
// 2
// 100

However, is there an explicit way to simply get from one of these elements to the next?

For example, does there exist some way to achieve similar behavior to this? 

var curElement = foo[2]; // => 2 (the contents of foo[2])
var nextElement = curElement.next(); // => 100 (the contents of foo[100])
//                           ^^^^^^
// Not an actual function, but does there exist some way to potentially
// mimic this type of behavior efficiently?
Improve this question
10
  • No, you'd have to write your own code to do that. Commented Jan 3, 2016 at 2:53
  • @Pointy Does there exist an efficient way to do this? The only way I can think of is to iterate through the entire array, ignoring undefined values. Surely there must be some more efficient way? Commented Jan 3, 2016 at 2:55
  • 1
    Linked Lists ? Commented Jan 3, 2016 at 3:02
  • 1
    Ok I see. My point still stands though, using a linked list instead of arrays is probably the cleanest and fastest solution. Commented Jan 3, 2016 at 3:19
  • 1
    @LJᛃ: You should post an answer. I agree that a linked list would make more sense unless there's some need to also share the data as an actual Array elsewhere in code. If that's not the case, I'd push for your answer to be the accepted one. Commented Jan 3, 2016 at 14:05

3 Answers 3

Reset to default
3

You could create your own SparseArray types that has all the Array methods, but maintains a separate list of indices to iterate so that you can skip over holes efficiently.

Here's the start of such a type. It lets you iterate, push, add at specific indices, get/check specific indices.

There's also a .toString() that I added for display.

Not fully tested so there may be bugs. You'd need to add functionality as needed.

function SparseArray(arr) {
  this.data = arr || [];
  this.indices = [];

  for (var i = 0; i < this.data.length; i++) {
    if (this.data.hasOwnProperty(i)) {
      this.indices.push(i);        
    }
  }
}

SparseArray.prototype.forEach = function(cb, thisArg) {
  for (var i = 0; i < this.indices.length; i++) {
    cb.call(thisArg, this.data[this.indices[i]], i, this);
  }
};

SparseArray.prototype.push = function(item) {
  this.indices.push(this.data.push(item) - 1);
};

SparseArray.prototype.addAt = function(idx, item) {
  if (idx >= this.data.length) {
    this.indices.push(idx);
    
  } else if (!(idx in this.data)) {
    for (var i = 0; i < this.indices.length; i++) {
      if (this.indices[i] >= idx) {
        this.indices.splice(i, 0, idx);
        break;
      }
    }
  }
  this.data[idx] = item;
};

SparseArray.prototype.hasIndex = function(idx) {
  return idx in this.data;
};

SparseArray.prototype.getIndex = function(idx) {
  return this.data[idx];
};

SparseArray.prototype.nextFrom = function(idx) {
  for (var i = 0; i < this.indices.length; i++) {
    if (this.indices[i] >= idx) {
      return this.data[this.indices[i]];
    }
  }
};

SparseArray.prototype.toString = function() {
  var res = [];
  this.forEach(function(item) {
    res.push(item);
  });
  return res.join(", ");
};

var foo = [];
foo[0] = '0';
foo[1] = '1';
foo[2] = '2';
foo[100] = '100';

var pre = document.querySelector("pre");

var sa = new SparseArray(foo);

pre.textContent += "Start\n" + sa + "\n\n";

sa.addAt(1000, "1000");

pre.textContent += "Adding 1000\n" + sa + "\n\n";

sa.push("1001");

pre.textContent += "Pushing 1001\n" + sa + "\n\n";

pre.textContent += "Next from 300 is: " + sa.nextFrom(300) + "\n\n";
<pre></pre>

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

1 Comment

For arrays with large gaps between defined indices, rather than traversing the entire length, it might be better to define the indices property in one line: this.indices = Object.keys(arr).map(Number) (assuming the array doesn't have non-numeric properties defined, in which case it would need to be further filtered to numeric keys)
1

As squint mentioned in a comment above, one way I would do it involves another array. You could keep track of the indexes that actually mean something to you, that way you could jump straight to those indexes. I do however, have another idea.

If you want to eliminate large overhead, you could keep one array of values you care about, and one array of the indexes they correspond to. (Note that this is more like a Map - a datastructure in Java). That way, you can iterate over the numbers you need, and get the index you want in the other array.

Array 1: 1, 3, 6, 8
Array 2: 234, 298, 400, 500

So the value 1 occurs at index 234 in the data, the value 3 at 298...

I think this would greatly improve performance for large data sets and small data sets. However, I'm not totally sure how lookup works in javascript.

Improve this answer

Comments

-2

Try using .slice() , .filter()

// slice index of `curElement` + 1 through `foo` `.length`
var curr = foo.slice(foo.indexOf(curElement) + 1, foo.length);
// if `val` defined , return `val`
// alternatively , `return val !== undefined || val !== null`
var next = curr.filter(function(val) { return val })[0];


var foo = [];
foo[0] = '0';
foo[1] = '1';
foo[2] = '2';
foo[100] = '100';
var curElement = foo[2]; // => 2 (the contents of foo[2])
var curr = foo.slice(foo.indexOf(curElement) + 1, foo.length);
var next = curr.filter(function(val) { return val})[0];
console.log(next)

Alternatively, could use while loop

var foo = [];
foo[0] = '0';
foo[1] = '1';
foo[2] = '2';
foo[100] = '100';
var n = 2, next;
var curElement = foo[n]; // => 2 (the contents of foo[2])
while (n < foo.length) {
  if (foo[++n] !== undefined) {next = foo[n]; break;}
}
console.log(next)

Improve this answer

10 Comments

As OP seems to be concerned with performance, this is not a good idea.
@LJᛃ This seems like a relatively in place solution, how is this poor in performance?
slice constructs a new array and reindexes the source array, using filter is way slower than manually iterating the values and also constructs a new array. In addition to that the proposed solution will also skip values that are 0...
yeah I downvoted, because of the reasons stated in my comments above.
correction: slice does not reindex the source array. Other points still remain valid though.
|

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.