Алгоритмы и структуры данных

3.5. Демонстрация - Разбор предыдущей задачи

Шаг 1

Итак, рассмотрим пару вариантов решения.


import {log} from './logger';

/*
searchScore(data, 4) => {
  "league": 1,
  "placement": 4,
}

searchScore(data, 14) => null
*/
function searchScore(leaderboard, leaguePoints) {
  return null;
}

const data = [
  [
    {
      "login": "stypeano",
      "leaguePoints": 4
    },
    {
      "login": "rstrazir",
      "leaguePoints": 45
    },
    {
      "login": "cathead",
      "leaguePoints": 143
    },
    {
      "login": "cavernous",
      "leaguePoints": 324
    }
  ],
  [
    {
      "login": "ConspiracyLil",
      "leaguePoints": 356
    },
    {
      "login": "CzarStories",
      "leaguePoints": 568
    },
    {
      "login": "GottaSaiyan",
      "leaguePoints": 598
    },
    {
      "login": "Mountaintrid",
      "leaguePoints": 785
    }
  ],
  [
    {
      "login": "Rectionom",
      "leaguePoints": 930
    },
    {
      "login": "JoshChase",
      "leaguePoints": 931
    },
    {
      "login": "DreamLess",
      "leaguePoints": 956
    },
    {
      "login": "BlondiePlanet",
      "leaguePoints": 1045
    }
  ],
  [
    {
      "login": "Breakingbing",
      "leaguePoints": 1056
    },
    {
      "login": "Goldenelox",
      "leaguePoints": 1130
    },
    {
      "login": "SaiyanBroadway",
      "leaguePoints": 1432
    },
    {
      "login": "BoostScooby",
      "leaguePoints": 1476
    }
  ]
]

log(4, searchScore(data, 4));
log(14, searchScore(data, 14));

Шаг 2

Самый простой и неоптимальный способ, который отрабатывает за O(n*m) (где n — количество лиг, а m — количество игроков в самой большой) — перебрать полностью все счета (линейный поиск). Но на миллионах человек он будет работать очень медленно — вдруг нам понадобится рассмотреть вообще всех игроков, чтобы найти лучшего.


import {log} from './logger';

/*
searchScore(data, 4) => {
  "league": 1,
  "placement": 4,
}

searchScore(data, 14) => null
*/
function searchScore(leaderboard, leaguePoints) {
  for (let i = 0; i < leaderboard.length; i++) {
    for (let j = 0; j < leaderboard[i].length; j++) {
      const player = leaderboard[i][j];

      if (player.leaguePoints === leaguePoints) {
        const league = i + 1;
        const placement = leaderboard[i].length - j;

        return {league, placement};
      }
    }
  }

  return null;
}

const data = [
  [
    {
      "login": "stypeano",
      "leaguePoints": 4
    },
    {
      "login": "rstrazir",
      "leaguePoints": 45
    },
    {
      "login": "cathead",
      "leaguePoints": 143
    },
    {
      "login": "cavernous",
      "leaguePoints": 324
    }
  ],
  [
    {
      "login": "ConspiracyLil",
      "leaguePoints": 356
    },
    {
      "login": "CzarStories",
      "leaguePoints": 568
    },
    {
      "login": "GottaSaiyan",
      "leaguePoints": 598
    },
    {
      "login": "Mountaintrid",
      "leaguePoints": 785
    }
  ],
  [
    {
      "login": "Rectionom",
      "leaguePoints": 930
    },
    {
      "login": "JoshChase",
      "leaguePoints": 931
    },
    {
      "login": "DreamLess",
      "leaguePoints": 956
    },
    {
      "login": "BlondiePlanet",
      "leaguePoints": 1045
    }
  ],
  [
    {
      "login": "Breakingbing",
      "leaguePoints": 1056
    },
    {
      "login": "Goldenelox",
      "leaguePoints": 1130
    },
    {
      "login": "SaiyanBroadway",
      "leaguePoints": 1432
    },
    {
      "login": "BoostScooby",
      "leaguePoints": 1476
    }
  ]
]

log(4, searchScore(data, 4));
log(14, searchScore(data, 14));

Шаг 3

Можно вспомнить про более оптимальный поиск, который работает по отсортированным данным — бинарный поиск. Однако в своём самом простом проявлении он работает только по одномерным массивам. Тогда давайте просто сложим наш массив массивов в массив! Есть небольшая проблема: у нас пропадёт знание о том, в каком месте находится игрок. Поэтому данную информацию придётся как-то добавлять в новый массив. Есть и более серьёзная проблема. Наш поиск будет работать за O(log(n*m)) (напомним, бинарный поиск работает за log(количество элементов), а элементов у нас аж n столбцов и m строк) — и это гораздо оптимальнее нашего первого поиска. Однако само перекладывание в новый массив займёт те же O(n*m), поэтому и общая оценка алгоритма придёт к такому же значению...


import {log} from './logger';

/*
searchScore(data, 4) => {
  "league": 1,
  "placement": 4,
}

searchScore(data, 14) => null
*/
function searchScore(leaderboard, leaguePoints) {
  const leaderboardArray = [];

  for (let i = 0; i < leaderboard.length; i++) {
    for (let j = 0; j < leaderboard[i].length; j++) {
      const {leaguePoints} = leaderboard[i][j];

      leaderboardArray.push({
        league: i + 1,
        placement: leaderboard[i].length,
        leaguePoints,
      })
    }
  }

  // бинарный поиск...

  return null;
}

const data = [
  [
    {
      "login": "stypeano",
      "leaguePoints": 4
    },
    {
      "login": "rstrazir",
      "leaguePoints": 45
    },
    {
      "login": "cathead",
      "leaguePoints": 143
    },
    {
      "login": "cavernous",
      "leaguePoints": 324
    }
  ],
  [
    {
      "login": "ConspiracyLil",
      "leaguePoints": 356
    },
    {
      "login": "CzarStories",
      "leaguePoints": 568
    },
    {
      "login": "GottaSaiyan",
      "leaguePoints": 598
    },
    {
      "login": "Mountaintrid",
      "leaguePoints": 785
    }
  ],
  [
    {
      "login": "Rectionom",
      "leaguePoints": 930
    },
    {
      "login": "JoshChase",
      "leaguePoints": 931
    },
    {
      "login": "DreamLess",
      "leaguePoints": 956
    },
    {
      "login": "BlondiePlanet",
      "leaguePoints": 1045
    }
  ],
  [
    {
      "login": "Breakingbing",
      "leaguePoints": 1056
    },
    {
      "login": "Goldenelox",
      "leaguePoints": 1130
    },
    {
      "login": "SaiyanBroadway",
      "leaguePoints": 1432
    },
    {
      "login": "BoostScooby",
      "leaguePoints": 1476
    }
  ]
]

log(4, searchScore(data, 4));
log(14, searchScore(data, 14));

Шаг 4

Тогда модифицируем обычный бинарный поиск так, чтобы он работал с нашим массивом массивов! Например, тем же бинарным поиском найдём сначала нужную лигу. Только вместо попадания по точному количеству очков будем делить таблицу пополам и смотреть, попадёт ли наше количество очков в промежуток этой лиги, и делить пополам дальше уже относительно этой середины. Чтобы не переусложнять функцию, вынесем поиск по лигам отдельно. Если вы не дошли до решения с бинарным поиском и так и не написали его самостоятельно, внимательно присмотритесь к функции поиска и убедитесь, что ничего сложного в этом нет. Мы всё так же делим пополам наш интервал поиска и идём искать дальше в одну из половинок, если нам не подходит середина. Попробуйте пройтись по алгоритму и поискать с его помощью.

{
  time: 0,
  isEntering: true, // если в этот момент человек входил — true, выходил — false
}

И перегоним наблюдения системы в него. Это займет у нас O(n) времени.

import {test} from "./tester.js"
import {log} from './logger';

/*
searchScore(data, 4) => {
  "league": 1,
  "placement": 4,
}

searchScore(data, 14) => null
*/
function searchScore(leaderboard, leaguePoints) {
  const leagueIndex = searchLeagueByScore(leaderboard, leaguePoints)

  return null;
}

function searchLeagueByScore(leaderboard, leaguePoints) {
  let left = 0;
  let right = leaderboard.length - 1;

  const firstPlacePoints = leaderboard[right][leaderboard[right].length - 1].leaguePoints;
  const lastPlacePoints = leaderboard[0][0].leaguePoints;

  // Если количество очков вообще не входит в промежутки в таблице
  // (меньше минимального или больше максимального)
  if (lastPlacePoints > leaguePoints
    || firstPlacePoints < leaguePoints) {
    // значит, такой лиги точно нет
    return null;
  }

  // пока концы промежутка, в котором мы ищем, не сошлись
  while (left <= right) {
    // делим наш промежуток (примерно) пополам
    const middleIndex = Math.floor((right + left) / 2);
    const middle = leaderboard[middleIndex];

    const firstPlayerPoints = middle[middle.length - 1].leaguePoints;
    const lastPlayerPoints = middle[0].leaguePoints;

    // если очки входят в лигу по середине - значит, это то, что мы ищем
    if (lastPlayerPoints <= leaguePoints && leaguePoints <= firstPlayerPoints) {
      return middleIndex;
    }

    // если очков для этой лиги слишком мало
    if (lastPlayerPoints > leaguePoints) {
      // то двигаем правый край нашего поиска до серединки
      // (ищем от начала до текущей середины)
      right = middleIndex - 1;
    // а если наоборот слишком много
    } else if (leaguePoints > firstPlayerPoints) {
      // то ищем справа
      left = middleIndex + 1;
    }
  }

  // если края всё-таки сошлись - значит, такой лиги нет
  return null;
}

const data = [
  [
    {
      "login": "stypeano",
      "leaguePoints": 4
    },
    {
      "login": "rstrazir",
      "leaguePoints": 45
    },
    {
      "login": "cathead",
      "leaguePoints": 143
    },
    {
      "login": "cavernous",
      "leaguePoints": 324
    }
  ],
  [
    {
      "login": "ConspiracyLil",
      "leaguePoints": 356
    },
    {
      "login": "CzarStories",
      "leaguePoints": 568
    },
    {
      "login": "GottaSaiyan",
      "leaguePoints": 598
    },
    {
      "login": "Mountaintrid",
      "leaguePoints": 785
    }
  ],
  [
    {
      "login": "Rectionom",
      "leaguePoints": 930
    },
    {
      "login": "JoshChase",
      "leaguePoints": 931
    },
    {
      "login": "DreamLess",
      "leaguePoints": 956
    },
    {
      "login": "BlondiePlanet",
      "leaguePoints": 1045
    }
  ],
  [
    {
      "login": "Breakingbing",
      "leaguePoints": 1056
    },
    {
      "login": "Goldenelox",
      "leaguePoints": 1130
    },
    {
      "login": "SaiyanBroadway",
      "leaguePoints": 1432
    },
    {
      "login": "BoostScooby",
      "leaguePoints": 1476
    }
  ]
]

log(4, searchScore(data, 4));
log(14, searchScore(data, 14));

Шаг 5

После того как мы нашли нужную лигу (либо сразу отдали null, если не нашли), нам остаётся написать ещё один бинарный поиск уже по ней.


import {log} from './logger';

/*
searchScore(data, 4) => {
  "league": 1,
  "placement": 4,
}

searchScore(data, 14) => null
*/
function searchScore(leaderboard, leaguePoints) {
  const leagueIndex = searchLeagueByScore(leaderboard, leaguePoints);

  if (leagueIndex === null) {
    return null;
  }

  const placementIndex = searchInLeague(leaderboard[leagueIndex], leaguePoints);

  return null;
}

function searchLeagueByScore(leaderboard, leaguePoints) {
  let left = 0;
  let right = leaderboard.length - 1;

  const firstPlacePoints = leaderboard[right][leaderboard[right].length - 1].leaguePoints;
  const lastPlacePoints = leaderboard[0][0].leaguePoints;

  // Если количество очков вообще не входит в промежутки в таблице
  // (меньше минимального или больше максимального)
  if (lastPlacePoints > leaguePoints
    || firstPlacePoints < leaguePoints) {
    // значит такой лиги точно нет
    return null;
  }

  // пока концы промежутка, в котором мы ищем, не сошлись
  while (left <= right) {
    // делим наш промежуток (примерно) пополам
    const middleIndex = Math.floor((right + left) / 2);
    const middle = leaderboard[middleIndex];

    const firstPlayerPoints = middle[middle.length - 1].leaguePoints;
    const lastPlayerPoints = middle[0].leaguePoints;

    // если очки входят в лигу по середине - значит, это то, что мы ищем
    if (lastPlayerPoints <= leaguePoints && leaguePoints <= firstPlayerPoints) {
      return middleIndex;
    }

    // если очков для этой лиги слишком мало
    if (lastPlayerPoints > leaguePoints) {
      // то двигаем правый край нашего поиска до серединки
      // (ищем от начала до текущей середины)
      right = middleIndex - 1;
    // а если наоборот слишком много
    } else if (leaguePoints > firstPlayerPoints) {
      // то ищем справа
      left = middleIndex + 1;
    }
  }

  // если края всё-таки сошлись - значит, такой лиги нет
  return null;
}

function searchInLeague(league, leaguePoints) {
  let left = 0;
  let right = league.length - 1;

  while (left <= right) {
    const middleIndex = Math.floor((right + left) / 2);
    const {leaguePoints: middleLeaguePoints} = league[middleIndex];

    if (middleLeaguePoints === leaguePoints) {
      return middleIndex;
    }

    if (middleLeaguePoints > leaguePoints) {
      right = middleIndex - 1;
    } else if (leaguePoints > middleLeaguePoints) {
      left = middleIndex + 1;
    }
  }

  return null;
}

const data = [
  [
    {
      "login": "stypeano",
      "leaguePoints": 4
    },
    {
      "login": "rstrazir",
      "leaguePoints": 45
    },
    {
      "login": "cathead",
      "leaguePoints": 143
    },
    {
      "login": "cavernous",
      "leaguePoints": 324
    }
  ],
  [
    {
      "login": "ConspiracyLil",
      "leaguePoints": 356
    },
    {
      "login": "CzarStories",
      "leaguePoints": 568
    },
    {
      "login": "GottaSaiyan",
      "leaguePoints": 598
    },
    {
      "login": "Mountaintrid",
      "leaguePoints": 785
    }
  ],
  [
    {
      "login": "Rectionom",
      "leaguePoints": 930
    },
    {
      "login": "JoshChase",
      "leaguePoints": 931
    },
    {
      "login": "DreamLess",
      "leaguePoints": 956
    },
    {
      "login": "BlondiePlanet",
      "leaguePoints": 1045
    }
  ],
  [
    {
      "login": "Breakingbing",
      "leaguePoints": 1056
    },
    {
      "login": "Goldenelox",
      "leaguePoints": 1130
    },
    {
      "login": "SaiyanBroadway",
      "leaguePoints": 1432
    },
    {
      "login": "BoostScooby",
      "leaguePoints": 1476
    }
  ]
]

log(4, searchScore(data, 4));
log(14, searchScore(data, 14));

Шаг 6

Осталось привести наше решение к виду, который хотели наши заказчики! В итоге мы получили гораздо больше кода, чем в изначальном решении с полным перебором, но работает он быстрее. Если оценить его, то мы получим O(log(n) + log(m)), что преобразуется в наше обещанное O(log(n*m)) по свойству сложения логарифмов. Запомните его для последующей оценки алгоритмов.


import {log} from './logger';

/*
searchScore(data, 4) => {
  "league": 1,
  "placement": 4,
}

searchScore(data, 14) => null
*/
function searchScore(leaderboard, leaguePoints) {
  const leagueIndex = searchLeagueByScore(leaderboard, leaguePoints);

  if (leagueIndex === null) {
    return null;
  }

  const placementIndex = searchInLeague(leaderboard[leagueIndex], leaguePoints);

  if (placementIndex === null) {
    return null;
  }

  const league = leagueIndex + 1;
  const placement = leaderboard[leagueIndex].length - placementIndex;

  return {league, placement};
}

function searchLeagueByScore(leaderboard, leaguePoints) {
  let left = 0;
  let right = leaderboard.length - 1;

  const firstPlacePoints = leaderboard[right][leaderboard[right].length - 1].leaguePoints;
  const lastPlacePoints = leaderboard[0][0].leaguePoints;

  // Если количество очков вообще не входит в промежутки в таблице
  // (меньше минимального или больше максимального)
  if (lastPlacePoints > leaguePoints
    || firstPlacePoints < leaguePoints) {
    // значит такой лиги точно нет
    return null;
  }

  // пока концы промежутка, в котором мы ищем, не сошлись
  while (left <= right) {
    // делим наш промежуток (примерно) пополам
    const middleIndex = Math.floor((right + left) / 2);
    const middle = leaderboard[middleIndex];

    const firstPlayerPoints = middle[middle.length - 1].leaguePoints;
    const lastPlayerPoints = middle[0].leaguePoints;

    // если очки входят в лигу по середине - значит, это то, что мы ищем
    if (lastPlayerPoints <= leaguePoints && leaguePoints <= firstPlayerPoints) {
      return middleIndex;
    }

    // если очков для этой лиги слишком мало
    if (lastPlayerPoints > leaguePoints) {
      // то двигаем правый край нашего поиска до серединки
      // (ищем от начала до текущей середины)
      right = middleIndex - 1;
    // а если наоборот слишком много
    } else if (leaguePoints > firstPlayerPoints) {
      // то ищем справа
      left = middleIndex + 1;
    }
  }

  // если края всё-таки сошлись - значит, такой лиги нет
  return null;
}

function searchInLeague(league, leaguePoints) {
  let left = 0;
  let right = league.length - 1;

  while (left <= right) {
    const middleIndex = Math.floor((right + left) / 2);
    const {leaguePoints: middleLeaguePoints} = league[middleIndex];

    if (middleLeaguePoints === leaguePoints) {
      return middleIndex;
    }

    if (middleLeaguePoints > leaguePoints) {
      right = middleIndex - 1;
    } else if (leaguePoints > middleLeaguePoints) {
      left = middleIndex + 1;
    }
  }

  return null;
}

const data = [
  [
    {
      "login": "stypeano",
      "leaguePoints": 4
    },
    {
      "login": "rstrazir",
      "leaguePoints": 45
    },
    {
      "login": "cathead",
      "leaguePoints": 143
    },
    {
      "login": "cavernous",
      "leaguePoints": 324
    }
  ],
  [
    {
      "login": "ConspiracyLil",
      "leaguePoints": 356
    },
    {
      "login": "CzarStories",
      "leaguePoints": 568
    },
    {
      "login": "GottaSaiyan",
      "leaguePoints": 598
    },
    {
      "login": "Mountaintrid",
      "leaguePoints": 785
    }
  ],
  [
    {
      "login": "Rectionom",
      "leaguePoints": 930
    },
    {
      "login": "JoshChase",
      "leaguePoints": 931
    },
    {
      "login": "DreamLess",
      "leaguePoints": 956
    },
    {
      "login": "BlondiePlanet",
      "leaguePoints": 1045
    }
  ],
  [
    {
      "login": "Breakingbing",
      "leaguePoints": 1056
    },
    {
      "login": "Goldenelox",
      "leaguePoints": 1130
    },
    {
      "login": "SaiyanBroadway",
      "leaguePoints": 1432
    },
    {
      "login": "BoostScooby",
      "leaguePoints": 1476
    }
  ]
]

log(4, searchScore(data, 4));
log(14, searchScore(data, 14));

File logger.js


const results = document.getElementById('results')

export function log(points, placement) {
  const result = document.createElement('li');

  if (!placement) {
    result.innerHTML = `Вы — единствнный игрок со счетом ${points}`;
  } else {
    result.innerHTML = `Ваш счет — ${points}. Скорее всего, вы попадете в лигу ${placement.league} и займете там ${placement.placement} место`;
  }

  results.appendChild(result);
}