How to sort and search in JavaScript large set

Question

The array "scores" tells the total points for each person involved in a contest. So for example:

User A: 100 points
User B: 90 points
User C: 90 points
User D: 80 points
User E: 75 points
User F: 60 points

According to above scores we will have this ranking:

User A: #1
User B: #2  
User C: #2
User D: #3
User E: #4
User F: #5

This ranking method follows the Dense Ranking method.

Then we have a user named alice. If she gets 55 points, she will rank at position #6 (according to ranking above). If she scores 90 points, she will rank at position #2. And so on.

I actually have an array containing different "sessions" for alice. So having for example:
[55, 90]

This means that first time will alice be ranked at position #6. While second time she will be ranked at position #2.

I coded this, and it works. However, this does not seem to be very efficient. For large datasets, with half million entries in the scores-array, it times out. This is the code:

const getPosition = (element, scores) => {
    scores.push(element);
    scores.sort(function (a,b) { return b-a; });
    return scores.indexOf(element)+1;
}

function climbingLeaderboard(scores, alice) {
    var uniqueSet = new Set(scores);
    scores = [...uniqueSet];
    var positions = [];
    let aliceIndex = 0;
    while(aliceIndex < alice.length){
        positions.push(getPosition(alice[aliceIndex], scores));
        aliceIndex++;
    }
    return positions;
}

function main() {
    const scores = [100, 90, 90, 80, 75, 60];
    const alice = [50, 65, 77, 90, 102];
    let result = climbingLeaderboard(scores, alice);
    console.log(result.join("\n") + "\n");
}

I guess the "sort"-function and/or searching for the element in the array with indexOf is the problem. But I could not find a way to make these two operations more efficient.

Answer 1

Merged your function into one. returning rank as an object in the format { mark : rank}

{
  102: 1,
  50: 50,
  65: 35,
  77: 23,
  90: 10
}

function climbingLeaderboard(scores, alice) {
  scores = [...new Set(scores)];
  let length = scores.length;
  const rank = alice.reduce((obj, key) => {
    obj[key] = 1;
    return obj;
  }, {});
  for (let i = 0; i < length; i++) {
    alice.forEach((item) => {
      if (scores[i] > item) {
        rank[item]++;
      }
    });
  }
  return rank;
}


const scores = [];
for (i = 0; i < 500000; i++) {
  scores[i] = Math.floor(Math.random() * 100);
}
const alice = [50, 65, 77, 90, 102];
let result = climbingLeaderboard(scores, alice);
console.log(result);

Answer 2

this approach assumes that in case of equal scores Alice should be place first in the score bracket meaning if she scores 90 then she will be ranked 2nd, behind 100 but above the rest of the 90s

function calculatePositions(scores, aliceScores) {
  let positions = [];
  const uniqueScoresSet = new Set([...scores]);
  const uniqueScoresArray = Array.from(uniqueScoresSet);

aliceScores.forEach((aliceScore) => {
    let position = uniqueScoresArray.findIndex((score) => aliceScore >= score);
    position = position === -1 ? scores.length : position + 1;
    positions.push(position);
  });

  return positions;
}

function main() {
  const scores = [100, 90, 90, 80, 75, 60];
  const alice = [50, 65, 77, 90, 102];
  let result = calculatePositions(scores, alice);
  console.log(result.join("\n") + "\n");
}

this approach assumes that in case of equal scores Alice should be place last in the score bracket meaning if she scores 90 then she will be ranked 4th, behind 100 and the two other 90s.

function calculatePositions(scores, aliceScores) {
  let positions = [];
  aliceScores.forEach((aliceScore) => {
    let position = scores.findIndex((score) => aliceScore > score);
    position = position === -1 ? scores.length : position + 1;
    positions.push(position);
  });

  return positions;
}

function main() {
  const scores = [100, 90, 90, 80, 75, 60];
  const alice = [50, 65, 77, 90, 102];
  let result = calculatePositions(scores, alice);
  console.log(result.join("\n") + "\n");
}

Answer 3

Here's another take... Maybe not the most efficient method, but believe it does the trick. This in effect is an implementation of Jonas Wilms' comment to the question.

This is somewhat of a brute force solution, as it walks the scores array for each of alice's scores. A more efficient means would involve sorting alice's scores from highest to lowest (but keeping track of the original order in order to organize the results in the proper order), and then walking both the scores array and alice's array simultaneously.

Note that the solution below runs the test case from the question, in addition to running a test case against an array of 1M scores which is populated with random scores in the range from 99,999 to 0.

function climbingLeaderboard(scores, alice) {
  scores.sort( (a, b) => b - a );
  aliceRank = [];
  for ( let aliceScore of alice ) {
    let scoreIndex = 0;
    let rank = 0;
    while ( scoreIndex < scores.length ) {
      if ( scoreIndex === 0 || scores[ scoreIndex - 1 ] !== scores[ scoreIndex ] ) {
        rank++;
      }
      if ( scores[ scoreIndex ] <= aliceScore ) {
        aliceRank.push( rank++ );
        break;
      }
      scoreIndex++;
    }
    if ( scoreIndex === scores.length ) {
      aliceRank.push( ++rank );
    }
  }
  return aliceRank;
}

function main() {
  const scores = [100, 90, 90, 80, 75, 60];
  const alice = [50, 65, 77, 90, 102];
  let result = climbingLeaderboard(scores, alice);
  console.log(result);
  
  console.log( 'Generating array of 1M scores' );
  let scores2 = new Array( 1000000 );
  for ( let i = 0; i < scores2.length; i++ ) {
    scores2[ i ] = Math.floor( 100000 * Math.random() );
  }
  alice2 = [50000, 65000, 77000, 90000, 102000, -1];
  let result2 = climbingLeaderboard(scores2, alice2);
  console.log( `First of the 1M scores is ${scores2[0]} and last score is ${scores2[999999]}` );
  console.log( result2 );
}

main();

Hope this helps.

Answer 4

Change your getPosition function to below and try. Just removed your sort function and doing the full array search with a condition.

const getPosition = (element, scores) => {
    let length = scores.length;
    let rank = 1;
    for(let i=0; i<length; i++) {
        if(scores[i] > element) {
        rank++;
      }
    }
    return rank;
}
const scores = [100, 90, 90, 80, 75, 60];
const alice = [50, 65, 77, 90, 102];

console.log(getPosition(77, scores));