6

I was wondering what the use-cases for code like var foo = new Array(20), var foo = [1,2,3]; foo.length = 10 or var foo = [,,,] were (also, why would you want to use the delete operator instead of just removing the item from the array). As you may know already, all these will result in sparse arrays.

But why are we allowed to do the above thnigs ? Why would anyone want to create an array whose length is 20 by default (as in the first example) ? Why would anyone want to modify and corrupt the length property of an array (as in the second example) ? Why would anyone want to do something like [, , ,] ? Why would you use delete instead of just removing the element from the array ? Could anyone provide some use-cases for these statements ?


I have been searching for some answers for ~3 hours. Nothing. The only thing most sources (2ality blog, JavaScript: The Definitive Guide 6th edition, and a whole bunch of other articles that pop up in the Google search results when you search for anything like "JavaScript sparse arrays") say is that sparse arrays are weird behavior and that you should stay away from them. No sources I read explained, or at least tried to explain, why we were allowed to create sparse arrays in the first place. Except for You Don't Know JS: Types & Grammar, here is what the book says about why JavaScript allows the creation of sparse arrays:

An array that has no explicit values in its slots, but has a length property that implies the slots exist, is a weird exotic type of data structure in JS with some very strange and confusing behavior. The capability to create such a value comes purely from old, deprecated, historical functionalities ("array-like objects" like the arguments object).

So, the book implies that the arguments object somehow, somewhere, uses one of the examples I listed above to create a sparse array. So, where and how does arguments use sparse arrays ?


Something else that is confusing me is this part in the book "JavaScript: The Definitive Guide 6th Edition":

Arrays that are sufficiently sparse are typically implemented in a slower, more memory-efficient way than dense arrays are`.

"more memory-efficient" appears like a contradiction to "slower" to me, so what is the difference between the two, in the context of sparse arrays especially ? Here is a link to that specific part of the book.

Improve this question
11
  • 1
    I think "comes purely from old, deprecated, historical functionalities" covers it. ;) Commented Oct 2, 2017 at 13:35
  • 1
    The answer is simple, backcompatability or memory control Commented Oct 2, 2017 at 13:37
  • 1
    @Shard That's what other articles said. So, backcompatability for what ? How does it help memory control ? Javascript: The Definitive Guide said that it "sparse arrays are slow, but more memory efficient", what does that mean ? Commented Oct 2, 2017 at 13:41
  • 1
    The only time I've used it is to populate templates. Consider a table-like structure where you do want to render empty cells if a value is missing. By using a fixed array length (eg 20), you guarantee you'll create 20 cells with a simple loop 'for each value in array'. Otherwise you'd have to include a value check as well. 'if value, render value else render empty cell'. Just an example, could've fixed it differently as well. Commented Oct 2, 2017 at 14:01
  • 1
    @Taurus backcompatability for older websites which use that functionality still. For memory control, well if you know you'll only need 20 values in your array then you should specify that. Dynamic arrays on the backend otherwise will guess what size your array will be and set it to hundreds or thousands larger than it should be. Commented Oct 2, 2017 at 14:36

2 Answers 2

Reset to default
1

I was wondering what the use-cases for code like var foo = new Array(20), var foo = [1,2,3]; foo.length = 10 or var foo = [,,,] were

in theory, for the same reason people usually use sparse data structure ( not necessarily in order of importance ): memory usage ( var x = []; x[0]=123;x[100000]=456; won't consume 100000 'slots' ), performance ( say, take the avarage of the aforementioned x, via for-in or reduce() ) and convenience ( no 'hard' out of bound errors, no need to grow/shrink explicitly );

that said, semantically, a js array is just a special associative collection with index keys and a special property 'length' satisfying the invariant of being greater than all its index properties. While being a pretty elegant definition, it has the drawback of rendering sparsely defined arrays somewhat confusing and error prone as you noticed.

But why are we allowed to do the above thnigs ?

even if we were not allowed to define sparse arrays, we could still put undefined elements into arrays, resulting in basically the same usability problems you see with sparse arrays. So, say, having [0,undefined,...,undefined,1,undefined] the same as [0,...,1,] would buy you nothing but more memory consuming arrays and slower iterations.

Arrays that are sufficiently sparse are typically implemented in a slower, more memory-efficient way than dense arrays are. more memory-efficient and slower appear like a contradiction to me

"dense arrays" used for general purpose data are typically implemented as a contiguous block of memory filled with elements of the same size; if you add more elements, you continue filling the memory block allocating a new block if exhausted. Given that reallocation implies moving all elements to the new memory block, said memory is typically allocated in abundance to minimize chances of reallocation ( something like the golden ratio times the last capacity ). Hence, such data structures are typically the fastest for ordered/local traversal ( being more CPU/cache friendly ), the slowest for unpredicatble insertions/deletions ( for sufficiently big N ) and have high memory overhead ~ sizeof(elem) * N + extra space for future elems.

Conversely, "sparse arrays/matrices/..." are implemented by 'linking' together smaller memory blocks spreaded in memory or by using some 'logically compressed' form of a dense data structure or both; in either case, memory consumption is reduced for obvious reasons, but traversing them comparatively requires more work and less local memory access patterns.

So, if compared relative to the same effectively traversed elements sparse arrays consume much less memory but are much slower than dense arrays. However, given that you use sparse arrays with sparse data and algorithms acting trivially on 'zeros', sparse arrays can turn out much faster in some scenarios ( eg. multiply very big matrices with few non zero elements ... ).

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

5 Comments

memory usage ( var x = []; x[0]=123;x[100000]=456; won't consume 100000 'slots' ) But why do it that way ? Why not just say var x = []; x.push(456); ? Why would you want an element inserted at a specific index (that is much larger than the current size of the array) ?
So let's say I have an array [1,2,3,4,5,6,7], and for some reason, I want to mark the odd numbers, should I mark it by using delete on each odd index (1,3,5,7) instead of something like "odd_number_was_here" or false, since this will both help me mark my indices and help with memory consumption ?
Something else that is confusing me is this part in the book "JavaScript: The Definitive Guide 6th Edition": Arrays that are sufficiently sparse are typically implemented in a slower, more memory-efficient way than dense arrays are. more memory-efficient and slower appear like a contradiction to me. Here is a link to that specific part of the book.
@Taurus, why do it that way ? because some interface may require so ( consider a function asking some 1d data to be rendered in a graph ) or because it's more convenient to do so ( because you really want a 100000 length vector, or a big almost zero matrix ). I agree that this is pretty uncommon in js code though ... as others said, we all agree this is a rather exotic and error prone functionality; my reasoning is that disallowing it would buy you nothing, so ...
@Taurus, So let's say I have an array[...] in that case I see no reason to use delete; even if you needed to delete all odd-index numbers, I'd find more efficient/elegant to move them to the end of the array and delete 'em all by setting length accordingly
0

Because a JS Array is a very curious kind of data type that do not obey the time complexity rules as you would probably expect when the right tool is used. I mean the for in loop or the Object.keys() method. Despite being a very functional man i would swing towards the for in loop here since it is breakable.

There are some very beneficial use cases of sparse arrays in JS such as inserting and deleting items into a sorted array in O(1) without disturbing the sorted structure if your values are numerals like a Limit Order Book. Or in another words, if you could establish a direct numerical correlation among your keys and values.

Improve this answer

Comments

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.