2
\$\begingroup\$

I have two arrays, arr_of_frequencies and float_array, of the same length — around 500-800k values each. I have to get that down to somewhere between 200 and 300k values per array. Below is the code I've been using so far. It works but it will take around 15 seconds to run, which is about 14 seconds too long.

function get_freq_for_each_sweep_value() {
        if (frequency_span > 3000000000) {
            while (float_array.length > 300000) {
               for(var a = 0; a < float_array.length; a++){
                  float_array.splice(a, 3);
                  arr_of_frequencies.splice(a, 3);
               };
            }
        } else {
            while (float_array.length > 300000) {
               for(var a = 3-1; a < float_array.length; a += 3){
                  float_array.splice(a, 2);
                  arr_of_frequencies.splice(a, 2);
               };
            }
        }

        return arr_of_frequencies;
        return float_array;
    };

What I'm trying to do is take my original array and then cut out a certain amount of values. If there are 500k values, then I want to cut 3 out of every 4, so that array [1,2,3,4,5,6,7,8,9] is now only [1,5,9].

These arrays have to be passed along to a graphing API in Python that will plot the points, but will only plot up to 300k points at the most. Depending on the inputs (frequency_span) determines how many values there are. The higher the span, the more values there will be. The code I have above is working right now, but it is not working well. Any ways to improve the time, or a better approach to my problem, would be appreciated.

\$\endgroup\$
1
  • \$\begingroup\$ is this a pro-audio app? \$\endgroup\$
    – Nate T
    Jun 19 at 0:01
4
\$\begingroup\$

Avoid Array.splice

Your code is not clear because you have two returns. Only the first return will return a value the second return is ignored.

As you are using splice you are ignoring the returns and depending on the fact that the arrays are being reduced in place.

To get better performance you need to avoid using splice.

300,000 values should not take much more than 1/2 a second on even the most basic device. (assuming they are just floats).

Example

The example function does one array at a time and returns a new array if the size is reduced. The max complexity is the \$O(n)\$ where \$n\$ is the size of the result array.

If you must shorten the existing array in place, this function can also be used, just pass the input array twice as in the second example call.

function reduceArraySize(size, inArray, resultArray = []) {
    if (inArray.length < size) { return inArray }
    const spacing = inArray.length / size;
    var i = -1;
    while (++i < size) {
        resultArray[i] = inArray[Math.round(i * spacing)];
    }
    resultArray.length = size;  //if the result is same array shorten it
    return resultArray;
}
const testData = [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20];

console.log("Reduce to new array");
console.log(reduceArraySize(10, testData) + "")
console.log(" ");
console.log("Reduce in place");
console.log(reduceArraySize(15, testData, testData) + "");

Performance

The next example creates an array with 30million floats and compares the time to reduce that array to 300,000 items. First it create a new array, and then it does the same in play.

Reducing the array in place is about 4 times faster as there is no need to allocate new memory for the copy.

Run snippet (on low end devices it may take a moment or to to build the test array). When its ready Follow instructions (click page)

function reduceArraySize(size, inArray, resultArray = []) {
    if (inArray.length < size) { return inArray }
    const spacing = inArray.length / size;
    var i = -1;
    while (++i < size) {
        resultArray[i] = inArray[Math.round(i * spacing)];
    }
    resultArray.length = size;  //if the result is same array shorten it
    return resultArray;
}

const setOf = (size, cb, a = [], i = 0) => {while (i < size) { a[i] = cb(i++) } return a};
const testData = setOf(30_000_000, i => i);

info.textContent ="Ready click page to reduce " + testData.length + " item array to 300,000 items";
addEventListener("click", () => {
   var time1, time2,  now = performance.now();
   reduceArraySize(300000, testData);
   time1 = performance.now() - now;
   now = performance.now();
   reduceArraySize(300000, testData, testData);
   time2 = performance.now() - now;
   info.innerHTML = "Reduce 30,000,000 to 300,000 items.<br>" +
       "To new array in " + (time1 | 0) + "ms<br>"+
       "In place in " + (time2 | 0) + "ms<br>";
}, {once: true});
   
  
  
<div id="info">Creating data</div>

Even faster?

There are quicker ways of reducing the array however that will depend on the content (range and type of values in the array).

If all values can be Floats (32 bit floating point, JS Numbers are Doubles 64 bit floating point) then you could get the GPU to do the work for you (from fractions of a second to a few ms)

\$\endgroup\$
2
  • \$\begingroup\$ I like your solution a lot, I just implemented it, using the second version of shortening it in place. The only problem I'm having is that, let's say I ask for 250k values total in the array, and there are 900k in it, the 250k spots will be taken up by values in positions 0-600k, would shortening the size of the array each time move it along quicker? To reset size minus a few extra places each time \$\endgroup\$
    – Luke
    Jun 18 at 13:43
  • \$\begingroup\$ For example, my arrays run from 20 to 50. Spots 0-300k in the array are taken up by the values between 20 and 40, and the values in 50 are left off completely \$\endgroup\$
    – Luke
    Jun 18 at 15:00
1
\$\begingroup\$

I would avoid splicing an array. If I remember correctly, changing the size of an array has implications under the hood. It's probably better if you created a new array of new values, if you have memory to spare.

You can create a custom function that asynchronously iterates and operates through your array instead of a while loop. That way, while it's potentially slower, at least you won't block other operations in your code.

If you're mostly dealing with numbers, you might want to check out Typed Arrays. They're potentially faster since you're just working with numbers and don't have the extra overhead of regular arrays.

You might also consider using iterators. The general gist of this is that you don't necessarily to represent a sequence of things as something concrete (e.g. an array). You can represent it with an array-like object which can fetch the items lazily/on-the-fly/allows you to write the fetching behavior.

Or consider using streams if the platform you're running on supports it (e.g. node). Set up a pipeline of transformations, and then stream your data through it. There are modules that simplify streams usage, might want to check those out instead of the built-in API.

If you can, you could also split the work across threads. JavaScript runs on one thread by default. If you can split it out the work to separate workers, that would maximize the use of your processor.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.