In the context of Immutable.JS, what does "dense" mean?

Question

From the docs:

Lists are ordered indexed dense collections, much like a JavaScript Array.

What does "dense" mean?

score 3 · Answer 1 · answered May 24 '17 at 00:10

3

An object with indices from 0 to N, where every index in the range is defined, is dense.

On the other hand, an object with (e.g.) only indices 1, 100, 200, 400, 450, 500 populated is sparse, since not every index is used.

answered May 24 '17 at 00:10

PMV

1

Then the part *much like a JavaScript Array* is a bit misleading as javascript arrays are not inherently dense. :-/ – RobG May 24 '17 at 00:12

score 3 · Accepted Answer · answered May 24 '17 at 00:11

3

It refers to the opposite of sparse arrays. In a dense array, there exists a property with a value for every index between 0 and arr.length.

answered May 24 '17 at 00:11

Bergi

arr.length exclusive. Those are informal definitions, correct? Can arrays with limited number of holes still be dense? – le_m May 24 '17 at 00:19
@le_m I'm not sure whether "between" carries any notion of in/exclusiveness, but yes `[0, arr.length[`. No, a dense array cannot have *any* holes. – Bergi May 24 '17 at 00:38
@le_m Yes, informal, I don't know of any standards body that would define them. And of course, when an engine use a dense C array to represent a sparse JS array with few holes, terminology gets weird. – Bergi May 24 '17 at 00:42
I was referring to the later case, but you are probably right that - due to different and constantly evolving heuristics used by engines to determine the underlying datastructure of an array - we should stick to the simple implementation agnostic definition of "dense" as having no holes. Thanks for your comments! – le_m May 24 '17 at 00:49

2 Answers2