Array is not a Vector
JavaScript does not have vectors, it uses Array and Object that can both behave like vectors (grows and shrinks).
As you have not defined what you mean by vector
one must make an assumption in regard to what the variable vector
will contain and the general rule for arrays is that they are dense with numeric 0 based indexes.
My assumption that it is an array is based on the following
Is vector
an Array?
The question's examples show arrays [5, 10, 20, 50, 100]
and Objects do not (may not) have a length property.
Is vector
a dense array?
The line = vector.length;
would return the last index of a sparse array. eg a = []; a[100] = 1; console.log(a.length);
outputs 101 but has only 1 item. Your code would fail if you passed a sparse array.
Once we have established that the input is a standard array we can begin to optimize the function
Too complex
The first part of the function is overly complex and mostly redundant.
Sort
Array.sort is required but can be simplified as follows
.sort((a,b) => vector[a] - vector[b])
Tracking sorted position
There is no need to track the sort position by creating an object for each item. The sort position is already available in the indices
array by index. Eg indices[0]
gives the sort position for the first item.
Thus the need to call Array.map and create {i,d}
for each item is not needed, however if it were required it could be better
Better the map
Properties names are very poor and the map function is also too complex. the line
.map((d, i) => { const k = indices[i]; const v = vector[k]; return { i: indices[i] , value: vector[indices[i]] }; });
could be be simplified to
.map(pos => ({pos , value: vector[pos]}));
Avoid duplicated processing
You create the array indices using Array.keys . const indices = [...Array(l).keys()]
to get an ordered list of indexes, then lower down you create the array const deltas = new Array(l);
Note that the both lines are based on identical arrays. If you create deltas
first and use it to get the keys you can remove one of the created arrays.
const deltas = new Array(l);
const indices = [...deltas.keys()];
Calculate deltas and return
There are a lot of changes before we get to the meat of the function so all the rest of your original code can be replaced while considering the following...
Changes
- The for loop can be replaced with the simpler while loop.
- There is no need to create yet another object for each value. Once you have used the sorted positions they can be ignored.
- The final sort and map operations are not required.
- The first entry in the resulting array deltas
may not be at position 0 so the array
deltas` must be pre-assigned space to avoid creating a sparse array.
BTW: Always delimit code blocks, eg for(i = 0; i < 10; i++) foo += i;
is better as for(i = 0; i < 10; i++) { foo+=i; }
Rewrite
Changing the overly long function name remapVectorToIndexSortedDiffs
with sortedDiffs
The functions complexity (time and storage) is the same,
however its memory use and performance have been improved significantly.
function sortedDiffs(vector) {
var i = 0;
const length = vector.length, deltas = Array(length);
const idxs = [...deltas.keys()].sort((a, b) => vector[a] - vector[b]);
deltas[idxs[i]] = vector[idxs[i]];
while (i++ < length - 1) {
deltas[idxs[i]] = vector[idxs[i]] - vector[idxs[i - 1]];
}
return deltas;
}
or a less verbose version.
function sortedDiffs(vecs) {
var i = 0;
const len = vecs.length - 1, res = Array(len + 1);
const idxs = [...res.keys()].sort((a, b) => vecs[a] - vecs[b]);
res[idxs[i]] = vecs[idxs[i]];
while (i++ < len) { res[idxs[i]] = vecs[idxs[i]] - vecs[idxs[i - 1]] }
return res;
}