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 also 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 work. However, this does not seem to be very effective. 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

The following function sort of agrees with your function. Except that for example your function given scores = [ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ] and alice = [ 0, 0, 0, -1 ] gets 1,1,1,5, while I think it should be 1,1,1,2.

Anyway, it easily handles scores arrays of sizes 10^7 for scores and 10^5 for alice.

The idea is, we already know scores is sorted as per your comment. We can then go through the scores array. We sort the alices array while remembering the original order. Then we go through the scores array, we first look at the largest alice, once we hit an element >= it, it is time to note that down, we remember the score and whether it was a tie and the position it happened at. We continue traversing scores, now looking at the next biggest alice, etc.

At the end of this we know where each alice would be ranked in the original array. Now we just need to account for the rank increases that come from prior alices, basically the rule is, if you are alice 7, then you look at the previous scores from alices 1 to 6 which resulted in a rank increase, and count 1 each time their score was larger than yours. We can do this fairly quickly by maintaining a sorted array of the previous scores using a binary search to find where to insert the next element. Remembering to account for ties amongst Alices scores.

function binarySearch(array, targetValue) {
    if (array.length === 0) {
        return 0;
    }
    let min = 0;
    let max = array.length;
    let guess;

    while (max - min > 1) {
        guess = Math.floor((max + min) / 2);

        if (array[guess] > targetValue) {
            min = guess;
        } else {
            max = guess;
        }
    }

    return array[min] < targetValue ? min : min + 1;
}


function climbingLeaderboard(scores, alice) {
    if (alice.length === 0) {
        return [];
    }
    const sortedAliceWithIndex = alice.map((s, i) => [s, i]).sort(([a], [b]) => b - a);

    let aliceInd = 0;
    let currAlice = sortedAliceWithIndex[aliceInd][0];
    const ranks = [];
    let i = 0;
    let effectiveCount = 0;
    while (true) {
        const currScore = scores[i];
        if (currScore !== undefined && currScore > currAlice) {
            i++;
            if (!(scores[i] === scores[i - 1])) {
                effectiveCount++;
            }
            continue;
        }

        ranks.push([
            effectiveCount,
            sortedAliceWithIndex[aliceInd][1],
            currAlice === currScore,
            currAlice
        ]);
        aliceInd++;

        if (aliceInd >= alice.length) {
            break;
        }
        currAlice = sortedAliceWithIndex[aliceInd][0];
    }

    const inOriginalAliceOrder = ranks.sort(([, i1], [, i2]) => i1 - i2);

    const accountingForRanks = [];
    let rankIncreases = [];
    for (let [i, _, tie, score] of inOriginalAliceOrder) {
        let rankUp = binarySearch(rankIncreases, score);

        if (rankIncreases[rankUp - 1] === score) {
            accountingForRanks.push(i + rankUp);
        } else {
            accountingForRanks.push(i + rankUp + 1);
            if (!tie) {
                rankIncreases.splice(rankUp, 0, score);
            }
        }
    }
    return accountingForRanks;
}

The following runs in a couple of seconds for me.

function main() {
    let scores = new Array(10 ** 6);
    for (let i = 0; i < scores.length; i++) {
        scores[i] = 1 * Math.random();
    }
    scores.sort((a, b) => b - a);
    let alice = new Array(10 ** 5);
    for (let i = 0; i < alice.length; i++) {
        alice[i] = 2 * Math.random() - 1;
    }

    let result1 = climbingLeaderboard(scores, alice);

    console.log(result1);
}