Negative Indices in Array

Is it feasible an Array to fully support negative indices (in a mathematical and not python point of view) by means of an extra option which will set negative bounds and, hence, make Array.prototype.length to consider them.

Please have a look at this issue to understand what I talk about.

Tia

You can't do that with plain arrays. You could implement something like this with a Proxy:

function startAt(start, orig) {
  return new Proxy(orig || [], {
    get(target, prop, receiver) {
      if (typeof prop === 'symbol' || isNaN(prop)) return Reflect.get(target, prop, receiver)
      else return Reflect.get(target, prop - start, receiver)
    },
    set(target, prop, value, receiver) {
      if (typeof prop === 'symbol' || isNaN(prop)) return Reflect.set(target, prop, value, receiver)
      else return Reflect.set(target, prop - start, value, receiver)
    }
  })
}

const orig = [0,1,2,3,4]

const x = startAt(-3, orig)

x[-3] = 3

console.log(x[-3], orig) // 3, [3, 1, 2, 3, 4]

You'll have to also patch Symbol.iterator if you want spread syntax to work properly.

live demo

IMO, when discussing features that an arrays should have, we should look at them through the lens of a simple data structure who's only purpose is to hold an ordered list of elements, and that's it. Yes, each element in the array is assigned a unique and predictable index, but these indices should be treated as meaningless IDs. The moment we start trying to assign meaning to the indices, we're leaving array territory and are entering territory that's better handles by other data structures, like, perhaps a map, or an ordered map (which JavaScript doesn't have), etc. Certainly, there may be room for improvement in the kind of data structures available to handle these sorts of use cases, but I don't think the array is the best choice.

@pygy Could be feasible for this to be implemented behind the scene as Array.prototype.bound(x) where x is any negative or positive number from which Array.length starts counting?

In your example:

init index  0  1  2 3 4
orig        0  1  2 3 4 
new index  -3 -2 -1 0 1

x[-3] = 0 // not 3
x[0] = 3

@theScottyJam What kind of meaning we give to the indices when we set the beginning of them by using for example array.bound(-3) or array.bound(5)? We just have an auxiliary feature which gives us Freedom! What is the difference if index starts counting from -3 or 0 or 5? Why to use a more complicated ordered data structure (if exists) when we can use the simplest one, 1-dim array? Tia

And that's the problem. More freedom isn't necessarily better. It means every method that deals with arrays now needs to account for this additional degree of freedom.

As just one example, a head function is supposed to grab the first element of an array, and a tail function is supposed to grab everything after the first. I took a peak at Lodash's implementation for these, and it implements _.head() by using yourArray[0], which means it'll always grab whatever is at index 0 (might not be the first if we introduce this new feature), and it grabs the tail by doing const [, ...result] = yourArray, which means _.tail() actually grabs everything but the first, even if the input array had negative indices. These functions will become broken.

I've seen delegates really hate on the fact that JavaScript arrays support being sparse. This too is additional freedom that certainly can be occasionally useful. The problem is that everyone who wants to make a function that consumes arrays now needs to conscientiously consider what to do if the end-user passed in a sparse array. To me, having arrays start with negative indices isn't that different from the use case for spare arrays - The purpose of either of them is to assign additional meaning to indices, and in the process, they force anyone who consumes an array to have to be aware of these new dimensions of freedom.

3 Likes

I do still think there's a problem here that needs to be solved somehow, and perhaps this is an opportunity to discuss a new data structure to help solve this problem. I'm just not sure retrofitting Arrays is the best solution to the problem at hand.

Do you think you could expound on your use case? I saw from your link that you're wanting to represent a table using arrays, and that table could start at a negative position. Not sure if this was hypothetical or a real use case, but would you also need to do things like:

  • Add and remove stuff from the end of the table?
  • And and remove stuff from the beginning of the table? When this happens, do you need the value to the right to shift over so the starting, negative index is preserved, or do you also wish to shift the starting index?
  • Be able to add or remove something from the middle, and have everything after it shift over?
  • Iterate over the entries in order?
  • I would presume random access is needed, i.e. the ability to find what's at (-2, 3) without having to iterate over everything to get there.

That already exists - the .at() method.

.at(-1) will return the last element of the array. It sounds like @GHNewbiee is wanting to create arrays where, for example, the indices start counting at -5 instead of 0. So, array[-5] returns the first, array[-4] returns the second, and so forth.

For the time being, there is no need for dynamical adding, removing, shifting values from the beginning or the end of the 2D array. It is used as a static entity to calculate and keep values of a function or statistics (for example, the number of occurrences of two consecutive values x = - 3 and y = 2 in an array representing a time series). The only need is to correspond x, y values in a natural way to avoid tricks.

If it’s not a conceptual list, then it should probably just be an object or a Map.

1 Like

There are other languages (Fortran, Julia) where this is possible AFAIK without (much or any) perf downsides, and little ceremony, but JS's focus isn't math, and you'll probably face an upcliff battle with the TC if you want to have it included.

Beside the proxy (which will have poor perf because the proxy traps turn the indices into strings, even if you pass in numbers), or you can use array.at(), with a helper that rearranges the items when you construct the array.

As Jordan suggested, a plain JS object may be the lightest way to achieve what you're after with plain indexing syntax. Negative indices will be turned into strings by the engine, non-negative ones are optimized and stored in an array under the hood in major engines (and the way for in is spec'ed makes such an optimization the go-to representation anyway). So it will perform better than the proxy solution.

Here are benchmarks of the indexing speed of the various solutions.

IIRC the timings in the final results are in nanoseconds per individual op (but what really matters is relative perf). The x scale of the graphs is logarithmic.

In Chrome, you can see that the POJO is about twice as fast as the proxy. Both are slower that using array.at, and using a plain array is an order of magnitude faster.

Other browsers have different perf profiles In Firefox, array.at is almost as fast as a plain array index, and in SafariTechnologyPreview, it is faster (the Safari version installed here doesn't support array.at()).

Edit: tweaks in the benchmark code

1 Like

And that's the problem. More freedom isn't necessarily better....

Freedom is never the problem! And, yes, freedom is always better. But, its cost is high(er)!

What you, in general speaking, have to realise is that both arrays with negative index and sparse arrays, among other things, exist. Soon or late, both have to be faced and solved. You just have to decide what to do and how to do it.

One more actual example:

  • We have a time series represented as a single array value.
  • From that array we calculate a new array with the sums of the consecutive elements, sum.
  • After removing all empty elements, we get a new array comp.
  • From that array we count the occurrences of
    • each element,
    • two consecutive elements
    • three consecutive elements
    • ...
    • N consecutive elements

It's not heavy mathematics - only adding and counting is required - isn't it?

Please tell me what kind of data structure is more convenient for storing the following occurrences/values.

value: -1, 1, -1, -1, 0,  1, 1, -1, 1, 1,  1,  0, ...
sum:   -1, 1,   , -2, 0,   , 2, -1,  ,  ,  3,  0, ...
comp:  -1, 1, -2,  0, 2, -1, 3,  0, ...
index:  0, 1,  2,  3, 4,  5, 6,  7, 8, 9, 10, 11, ...

Single element:

element: -2, -1, 0, 1, 2, 3
occurrs:  1,  2, 2, 1, 1, 1

2 consecutive elements:

comp:  -1, 1, -2,  0, 2, -1, 3,  0, ...

 pairs   occurrences
-1,  1        1
 1, -2        1
-2,  0        1
 0,  2        1
 2, -1        1
-1,  3        1
 3,  0        1

3 consecutive elements:

comp:  -1, 1, -2,  0, 2, -1, 3,  0, ...

   pairs     occurrences
-1,  1, -2        1
 1, -2,  0        1
-2,  0,  2        1
 0,  2, -1        1
 2, -1,  3        1
-1,  3,  0        1

... you'll probably face an upcliff battle with the TC if you want to have it included.

I avoid bloodshed! Life is very beautiful!

Here are benchmarks of the indexing speed of the various solutions.

Thanks a lot for your time!

Conclusion

It is not practically feasible the Array to support negative indices.

1 Like

In regards to your hypothetical example, I think it would be most convenient to just skip the step of having a sparse array, and go directly from the value array to the comp array. Like this:

const value = [-1, 1, -1, -1, 0, 1, 1, -1, 1, 1, 1, 0];
const comp = [];

let lastSeen = null;
for (const x of value) {
  if (x === lastSeen) {
    comp[comp.length - 1] += x;
  } else {
    lastSeen = x;
    comp.push(x);
  }
}

console.log(comp);

However, I can see value with other problems needing an array like that. In this case, I would choose to use an ordered-map instead (if the language provided one). An ordered-map is a lot like an array, except you're allowed to give the indices whatever meaning you wish to give them. You can skip indices, start from wherever, count backwards, or even use letters if you so wish for your indices. I believe this data structure would be able to solve the problems you're presenting. In fact, I would argue that an ordered-map is the same as what you're proposing (and more), the only difference is we're moving the feature to a new data structure instead of trying to retrofit the same datastructure with more features that could potentially cause existing libraries to break when passed a odd-behaving array.

So, OrderedMap also means more freedom, but without the cost of creating issues with existing code (like the lodash example I presented earlier, which would become broken, though granted, it's not like they tried hard to support sparse arrays either).

For prior art, take a look a python's OrderedDict: collections β€” Container datatypes β€” Python 3.10.6 documentation

1 Like

@theScottyJam

In regards to your hypothetical example,...

It's an actual example.

... the only difference is we're moving the feature to a new data structure instead ...

It's sounds awesome to have a new data structure (OrderedMap)!

Many thanks!

1 Like

A related data structure is the double-ended list (AKA dual-unbounded array). It's one of the best data structures for Busy-Beavers and Turing Machines (to make it "the best", it must be constrained to a packed bool array)