Question 272740 in Jquery Question posted in
The official Jquery Api Documentation can be found here.

Jquery – How to efficiently extract rows from large 2d array containing the lowest N values at a specific index?

I have a multidimensional array of x columns and y rows:

[
[11.7, 18.8, 10.5],
[4.8,   6.3,  3.6],
[6.6,   8.4,  5.2],
[37.8, 80.8, 41.8],
[12.3, 29.2, 10.6],
[16.9, 42.9, 14.8],
[12.8, 30.9, 11.6],
[30.9, 69.5, 32.4],
[5.3,   7.9,  4.7],
[25.4,   57, 25.7],
[11.9, 17.6, 10.4],
[8.8,  13.6,  7.7],
[4.2,   6.2,  3.4],
[7.6,  12.3,  9.6]
]

My goal is to return the rows that contain the N lowest values in index position 0, sorted from smallest to largest. I need the rows kept intact.

I naively achieved this using .sort and .slice in jQuery:

.sort((a, b) => a[0] - b[0]) // sorts the 2d array by column value
.slice(0, n);  // retrieves the lowest n values

Using 3 for n yields the following result:

[
[4.2,  6.2,  3.4],
[4.8,  6.3,  3.6],
[5.3,  7.9,  4.7]
]

But this is REALLY inefficient since sorting the entire list first is expensive for longer lists. I need to get the min values first, then sort the result. I’m struggling on how to do that.

What I really need is to build a new array with only the min values at index 0:

[
[4.8,  6.3,  3.6],
[5.3,  7.9,  4.7],
[4.2,  6.2,  3.4]
]

…and then sort that array by the 0th index:

[
[4.2,  6.2,  3.4],
[4.8,  6.3,  3.6],
[5.3,  7.9,  4.7]
]
Tags:

2

Answers


  1. 0

    You can create a custom algorithm for this solution.

    Full working example:

    function findNLowestValues(arr, n) {
  var result = arr.slice(); // Create a shallow copy of the original array
  var nLowest = [];

  for (let i = 0; i < n; i++) {
    let minIndex = i;

    for (let j = i + 1; j < result.length; j++) {
      if (result[j][0] < result[minIndex][0]) {
        minIndex = j;
      }
    }

    // Swap the rows to move the minimum value to the beginning
    [result[i], result[minIndex]] = [result[minIndex], result[i]];
    nLowest.push(result[i]);
  }

  return nLowest;
}

var yourArray = [
    [11.7, 18.8, 10.5],
    [4.8,   6.3,  3.6],
    [6.6,   8.4,  5.2],
    [37.8, 80.8, 41.8],
    [12.3, 29.2, 10.6],
    [16.9, 42.9, 14.8],
    [12.8, 30.9, 11.6],
    [30.9, 69.5, 32.4],
    [5.3,   7.9,  4.7],
    [25.4,   57, 25.7],
    [11.9, 17.6, 10.4],
    [8.8,  13.6,  7.7],
    [4.2,   6.2,  3.4],
    [7.6,  12.3,  9.6]
];

var n = yourArray.length; // Number of lowest values you want to find
var nLowestValues = findNLowestValues(yourArray, n);

// Sort the n lowest values by the 0th index
nLowestValues.sort((a, b) => a[0] - b[0]);

console.log(nLowestValues);
    Login or Signup to reply.
  2. 0

    sorting the entire list first is expensive for longer lists

    not true. JS can sort thousands of rows in a fraction of second.

    a = [
    [11.7, 18.8, 10.5],
    [4.8,   6.3,  3.6],
    [6.6,   8.4,  5.2],
    [37.8, 80.8, 41.8],
    [12.3, 29.2, 10.6],
    [16.9, 42.9, 14.8],
    [12.8, 30.9, 11.6],
    [30.9, 69.5, 32.4],
    [5.3,   7.9,  4.7],
    [25.4,   57, 25.7],
]

b = []
for (i = 0; i < 1e6; i++)
    b.push(...a)

console.log(b.length) // ten million

console.time('sort')
b.sort((x, y) => x[0] - y[0])
console.timeEnd('sort')  // about 1 second for me
    Login or Signup to reply.
Please signup or login to give your own answer.

Back To Top
Search