0
\$\begingroup\$

I feel like I am doing a lot of unnecessary operations and some places I feel like I am being redundant in some places. I am focused on performance and optimization. I am trying to find the five largest numbers at set intervals, while also removing those values from the array. My current implementation is horrendous, because of splice as well as other things I am probably unaware of. I need to grab the top candidates in their respective range. That range can change and the number that I need to query can also change.

var arr = [101, 88, 267, 175, 154, 39, 74, 217, 31, 105, 235, 31, 14, 49, 226, 195, 134, 207, 222, 281,
  262, 112, 133, 115, 0, 53, 128, 103, 88, 145, 238, 13, 204, 199, 100, 247, 292, 157, 141, 286,
  72, 160, 85, 61, 57, 54, 263, 50, 125, 179, 243, 281, 39, 76, 151, 79, 1, 238, 200, 249, 35, 82,
  204, 174, 293, 216, 84, 209, 170, 236, 3, 247, 25, 162, 25, 57, 49, 215, 8, 167, 180, 268,
  204, 257, 134, 151, 191, 81, 77, 106, 85, 128, 52, 136, 46, 185, 229, 116, 145, 253, 258, 222,
  269, 225, 101, 175, 265, 77, 32, 8, 72, 54, 111, 264, 292, 161, 91, 215, 139, 245, 73, 127, 297,
  73, 258, 183, 232, 55, 199, 175, 31, 24, 21, 155, 231, 95, 40, 223, 222, 86, 115, 210, 134, 229,
  211, 54, 294, 153, 52, 165, 168, 125,186, 185, 289, 188, 248, 61, 136, 15, 19, 92, 200, 80, 208,
  195, 241, 85, 288, 279, 119, 247, 208, 11, 80, 111, 29, 292, 222, 289, 70, 11, 209, 25, 267, 233,
  16, 289, 154, 141, 174, 30, 156, 40, 266, 139, 116, 241, 1, 101, 109, 61, 220, 265, 45, 178, 166,
  102, 181, 193, 202, 133, 200, 266, 114, 222, 231, 89, 190, 29, 20, 64, 233, 261,213, 40, 161, 167,
  100, 121, 288, 268, 50, 264, 78, 105, 21, 33, 79, 114, 5, 134, 56, 259, 124, 44, 134, 133, 74, 176,
  65, 68, 34, 56, 2, 287, 63, 167, 299, 59, 290, 241, 104, 75, 76, 116, 225, 297, 208, 136, 265, 290,
  170, 267, 10, 176, 141, 217, 195, 4, 173, 32, 150, 271, 238, 171, 195, 16, 282, 77, 62, 39, 44, 248,
  270, 222, 295, 122, 190, 230];
function maxAtIntervals (arr, segment, select) {
  let apexValues = [], copy = [], count = 0;
  for (var i = 0; i < arr.length;i += segment) {
    copy[count] = arr.slice(i, i + segment)
    if (segment > 200) {
      let apex = wideSort(copy[count], select)
      apexValues.push(apex)
    }else {
      var box = [],dec = select
      while(dec--){
        let apex = narrowSearch(copy[count], dec),hash = apex.hash
        box[dec] = hash[dec]
        if (dec === 0) {
          apexValues.push(box)
        }
        copy[count].splice(copy[count].indexOf(apex.search, 0), 1)
      }
    }
    count++
  }
  return ['matching pairs at intervals of 20 grabing top 5:  ',apexValues,'what is left over:  ',copy.reduce((a,b)=> a.concat(b))]
}

function wideSort (arri,  select) {
  var bounce = arri.sort((a, b ) => a - b)
  bounce = bounce.slice(-select)
  return bounce
}

function narrowSearch (arri, dec) {
  let hash = new Map(),
      half = Math.floor(arri.length / 2) + 1,
      search = arri[0];
  hash[dec] = arri[0];
  for (var i = 0; i < half;i++) {
    let l = arri.length - 1 - i
    if (arri[i] > search) {
      hash[dec] = arri[i]
      search = arri[i]
    }
    if (arri[l] > search) {
      hash[dec] = arri[l]
      search = arri[l]
    }
  }
  return {search,hash}
}


console.time('startEnd')
console.log(
    maxAtIntervals(arr, 20, 5)
)
console.timeEnd('startEnd')
.as-console-wrapper { max-height: 100% !important; top: 0; }

\$\endgroup\$
4
  • \$\begingroup\$ Do you want to split the array in n chunks, and get the largest m numbers from every chunk? \$\endgroup\$
    – Gabriel
    May 22, 2017 at 0:35
  • \$\begingroup\$ A) The formatting is quite broken. B) The problem definition is not obvious -- and it will take too much time to infer it from the code. Could you explain the problem in a few statements and provide a few sample inputs+outputs? \$\endgroup\$ May 22, 2017 at 0:36
  • \$\begingroup\$ @Arrow is what I said correct? \$\endgroup\$
    – Gabriel
    May 22, 2017 at 0:56
  • \$\begingroup\$ @Gabriel sorry I meant to say you are correct Gabriel. hard to read text on a cell phone screen under the sun my apologies \$\endgroup\$
    – Rick
    May 22, 2017 at 0:59

1 Answer 1

1
\$\begingroup\$

Instead of writing two cases depending on the length of the chunk, you could certainly make one general way for each task. Doing so you simplify the code inside maxAtIntervals and get rid of findmax (as you can use .sort().slice(-n) to get the max n numbers).

The return of maxAtIntervals is [values]. If values is already an array, why would you create an array of 1 array?

There are so many comments I could not even focus on the code. Be succinct!

After applying this changes and removing unnecessary variables, the function looks like this:

function maxAtIntervals (intervalLength, grab, xs) {
    const comparator = (a, b, _) => a - b;
    const temp = [];

    for (var i = 0; i < xs.length; i += intervalLength) {
        const interval = xs.slice(i, i + intervalLength);
        temp.push(interval.sort(comparator).slice(-grab));
    }

    return temp;
}

Your original code makes 111ms on my machine. After my changes it goes to 51ms.

\$\endgroup\$
2
  • \$\begingroup\$ That indicates that the question is still of a low quality. Please provide several examples of inputs-outputs \$\endgroup\$ May 22, 2017 at 17:02
  • \$\begingroup\$ @igor Soloydenko I included inputs and outputs. The one thing I worry about are large intervals and small inputs, browser sort does poorly on those. Someone mentioned Median of Means quicksort \$\endgroup\$
    – Rick
    May 23, 2017 at 3:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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