Как сортировать и искать в большом наборе JavaScript

Question

Массив «scores» показывает общее количество баллов для каждого участника конкурса. Так, например:

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

В соответствии с приведенными выше оценками у нас будет следующий рейтинг:

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

Этот метод ранжирования соответствует методу плотного ранжирования.

Тогда мы имеем пользователь по имени Алиса. Если она наберет 55 баллов, она займет шестую позицию (согласно рейтингу выше). Если она наберет 90 баллов, она займет позицию №2. И так далее.

На самом деле у меня есть массив, содержащий разные «сеансы» для Алисы. Так, например, имея: [55, 90]

Это означает, что в первый раз Алиса будет ранжирована на позицию №6. Во второй раз она займет позицию №2.

Я закодировал это, и это работает. Однако это не кажется очень эффективным. Для больших наборов данных, содержащих полмиллиона записей в массиве оценок, время ожидания истекает. Это код:

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");
}

Я полагаю, что проблема заключается в функции «сортировки» и / или поиске элемента в массиве с indexOf. Но я не мог найти способ сделать эти две операции более эффективными.

Answer 1

этот подход предполагает, что в случае равных баллов Алиса должна быть первой в рейтинге, то есть если она наберет 90, то она будет занимать 2-е место, после 100, но выше остальных 90

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");
}

этот подход предполагает, что в случае равных баллов Алиса должна занимать последнее место в таблице оценок, что означает, что если она наберет 90, то она будет занимать 4-е место, уступив 100 и двух других 90-х.

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 2

Вот еще один вариант ... Может быть, не самый эффективный метод, но верю, что он помогает. По сути, это реализация комментария Джонаса Вильмса к вопросу.

Это в некотором роде решение грубой силы, поскольку оно проходит по массиву оценок для каждой оценки Алисы. Более эффективный способ заключается в сортировке оценок Алисы от наивысшего к наименьшему (но с отслеживанием исходного порядка, чтобы организовать результаты в правильном порядке), а затем одновременный ход по массиву оценок и массиву Алисы.

Обратите внимание, что приведенное ниже решение запускает тестовый пример из вопроса, в дополнение к запуску тестового примера для массива из 1M оценок, который заполняется случайными оценками в диапазоне от 99,999 до 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();

Надеюсь, это поможет.

Answer 3

Измените свою getPosition функцию на ниже и попробуйте. Просто удалили функцию сортировки и выполнили поиск по всему массиву с условием.

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));

Answer 4

Объедините вашу функцию в одну. возврат ранга как объекта в формате { 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);