Calculating ordered differences between elements in vector

Question

Input

I start with a vector of integers or floats, e.g.:

[10, 100, 20, 5, 50]

Output

I want to return a list of differences or "deltas" between elements of the sorted version of this vector. Differences are then presented in the same order as the items from the original, unsorted vector.

The above example vector would return, for instance:

[5, 50, 10, 5, 30]

Procedure

The procedure I have is to:

1. Order the input vector, e.g.,:

[5, 10, 20, 50, 100]

2. Calculate the differences between each pair of elements in the sorted vector (using the first element as-is; i.e., the difference between that value and zero):

[5, 5, 10, 30, 50]

3. Reorder differences by the original index of elements from the input vector:

[5, 50, 10, 5, 30]

Function

I am working in Javascript. This is the code I have written so far:

/**
 * Remap input vector into a vector of state-sorted delta scores
 * 
 * @param {Array} 1d array of numbers
 * @returns {Array} 1d array of per-element differences sorted by input index indices
 */
remapVectorToIndexSortedDiffs(vector) {
  const l = vector.length;
  const indices = [...Array(l).keys()];
  const vals = indices
    .sort((a, b) => vector[a] < vector[b] ? -1 : vector[a] > vector[b] ? 1 : 0 )
    .map((d, i) => { const k = indices[i]; const v = vector[k]; return { i:k , d:v }; });
  const deltas = new Array(l);
  deltas[0] = vals[0];
  for (let idx = 1; idx < l; idx++) deltas[idx] = { i : vals[idx].i, d : vals[idx].d - vals[idx - 1].d };
  return deltas
    .sort((a, b) => (a.i > b.i) ? 1 : -1)
    .map((d) => d.d);
}

I'm working with a large 2D matrix of such vectors and would like to optimize this function as much as possible, for both memory and speed (though speed is higher priority).

Are there ways I can improve this function in Javascript?

Answer 1

Array is not a Vector

JavaScript does not have vectors, it uses Array and Object that can both behave like vectors (grows and shrinks).

• Arrays can also be sparse [hash map] or dense [flat sequential array].

• Objects are sparse.

• Objects do not have a length property

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 deltasmay not be at position 0 so the arraydeltas` 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;
}