И опять же, почему все привязались к этим сортировкам, есть много что спросить из алгоритмов и структур данных. алгоритмы != пять основных видов сортировок, да, это достаточно большая и объемная тема и для других алгоритмов, но например задача про этот лидерборд очень показательна, потому что люди иногда такую ересь придумывают, что хочется плакать. И да, многие считают, что можно использовать стабильные сортировки так как это будет быстро, т.к. только часть элементов будет перемещена.
LL в чистом виде тут будет работать плохо, потому что, обращение по индексам, но его модификация — skip list, хорошо бы отработала, но мое решение было написано буквально за пару часов, и черт подери, оно для нашей набора данных работало очень неплохо, оптимизации планировались, но так и не вернулись к ним, банально было лень переделывать и так хорошо работающий механизм
Вот кстати это очень похоже на одну из оптимизаций, которую мы хотели применить, потому что боялись, что все таки вставка работает то o(m), и может быть например o(n) в худшем случае, а это уже очень долго, но все таки погоняв в реальной жизни оба варианта остановились на первом, а косяк с «все зависло на полчаса потому что мы обновляем наши полтора миллиарда записей, потому что кто-то с последнего места выбрался в топ...» решались при помощи несколько апдейтов, гранулярно, например +50000, можно разбить на кучу мелких апдейтов по 1к очков, спайки исчезнут
давай я сошлюсь на том, что я это сделал вдохновившись баблсортом, а не использовал что-то вроде:
idx = getIndexByUserId.get(userId);
leaderboard[ids].addScore(20)
leaderboard.sort()
leaderboard.each(index, entry -> getIndexByUserId.put(entry.userId, index))
Ведь мне нужен отсортированный массив и значит я буду использовать библиотечный метод. А индекс, потому что мне старший сказал, что поиск в списке очень медленный
у нас есть отсортированный список, мы изменяем значение и должны сохранить его в том же отсортированном виде, ну то есть из
30 25 20 15 13 11 5 3 0, если у нас происходит изменение например 11, прилетело +10, мы должны поменять местами несколько записей, это и 13 и 15 и даже 20.
я немного подумал. как бы можно было бы это в базе сделать, но тут один момент, больше связанный в перфомансом: в своем списке, когда сущность всплывает, я меняю еще значения idx, ну то есть есть прилетает UpdateScore(13, 20), я делаю Entry e = entriesByUserId.get(update.userId) и дальше лезу в метод который меняет лидерборд примерно так:
у меня entry выглядит следующим образом idx, score, userId. В базе — userId, score. Мне нужно достать топ и показать пользователю следующим образом — top10 в каждой лиге, а их допустим 5, и они все допустим расположены примерно так 1-10, 11-100, 101-1000, 1001-10000, 10001 — end + 5 окружающих от пользователя, а он в рейтинге на 150 месте с 2420 очками, то есть у меня список, который я отправлю пользователю будет такой:
Ладно, в моем примере действительно не важно потрачу ли я дополнительные миллисекунды на эти две операции (было бы важно, то вполне возможно был бы вручную написан мержсорт, который на стадии merge уже отбрасывал бы все лишнее. Но серьезно, ты не подумал, что вначале надо это отфильтровать все, а потом уже слазять за данными в редис? ну то есть тебя не смущает, что у тебя происходит в 10 раз больше ненужных вызовов.
И да, я понимаю почему это произошло именно так, он не конченный, как может показаться, просто он использовал метод, который возвращает все данные при загрузке, ну то есть лезет в базу, и потом для каждого проходится и дополняет данными из редиса. И дальше происходит фильтрация. Банальная невнимательность? Не понимание, что сейчас достаешь не пяток записей, с которыми придется работать, а там еще дальше куча всего происходит, прежде чем тебе потребуется дополнительная часть данных. В итоге, метод, который должен работать. Хорошо хоть не на каждую запись ходили в редис, а мультигетом…
конечно не хотим, поэтому все данные у нас и так есть в скуле, но вот работаем мы с уже построенной таблицей в памяти, приходит ивент — игрок сыграл в игру +20 очков ему, мы сохраняем это в базу, и в базе у него уже будет обновленное значение, а дальше вставляем в нашу вьюху в памяти.
Все обновления были в одном треде, плюс индекс из map<userId, entry> сразу на нужную запись в list, что бы подвинуть ее при апдейте.
Более того, изначально были апдейты делать list<bucket>, что бы можно было сразу мувнуть запись на очень много позиций вверх, но самая простая реализация работала очень неплохо на таком объеме данных, обычно приходилось делать не больше 20-30 всплываний записи за раз, иногда бывали всплески когда двигали на 3-4 сотни, но это было нечасто.
причем как и любой лидерборд у нее очень большой тейл, особенно игроки, у которых 0 валяется, опять же, так маркируются игроки, которые уже сыграли во время чемпа хотя бы одну игру
у меня тут не так давно была микро задача по оптимизации, страница долго грузиться, происходит следующее, мы достаем 1-2к записей из базы, дальше происходит следующее, делаются некоторые преобразования этой записи, добирается инфа по этим записям из редиса, дальше, программист этот список сортирует и делает distinct по этому листу, в итоге получаем примерно 10% от всех записей, которые и отдаем на клиент.
Моя оптимизация, которая стала работает примерно в 10 раз быстрее заключалась в двух вещах, первая, использование TreeSet, которая делает все эти операции при вставке в него, вторая, добирать данные после того как мы избавились от лишнего мусора. Потому что отсортировать список и сделать из него дистинкт — копейки по сравнению с десятикратным уменьшением доставания данных из редиса.
Когда я спросил, а зачем он так написал, ответ был прост — ну я не подумал, у меня это как-то быстро работало и так. Действительно зачем думать, зачем знать как работают структуры данных, зачем что-то знать про сложность операций. Он же сеньор, это он прошел когда учился в институте.
как я уже говорил выше, многие люди считают, что кроме достать данные из базы, конвертнуть их в другое представление и отдать дальше — задач не бывает.
окей, есть задача, есть таблица лидеров, туда постоянно, 150-200 раз в секунду добавляются данные, кто-то сыграл в игру, получил очки и в рейтинговой таблице должен измениться его статус, у игрока было 20 очков, он получил пять, соотвественно он должен подняться выше (или опуститься ниже), потому что за это время все соседние игроки получили гораздо больше очков.
Плюс мы должны уметь обращаться к этому списку по индексу (требуется отображать кратко эту таблицу топ-10, пяток лиг, и мы должны показывать топ-10 в каждой лиге, и еще +-5 окружающих игрока).
Какую библиотеку мне следует подцепить, что бы оно работало? Ах да, количество ридов этой таблицы примерно 300-400 в секунду.
но задача этого самого инженера может быть написание куска бизнес логики, основанного на одной из этих сортировок, потому что если это делать без пиггибекинга, то решение может занять O(n), а при большом количестве данных, это черт подери очень медленно
Меня изначально предупреждали, что собеседование займет порядка трех часов и будет одна долгая задача, и желательно подготовиться к этому, а если я не люблю маки, то лучше взять собой ноут со своей любимой осью и настроеным рабочим окружением, что бы не тратить время. Какая именно будет задача — не сказали.
насколько мне известно, изначально примерно так и было настроено, что-то вроде реквест лимита и по куке определялось какой лимит у пользователя, но с появлением дополнительных требований, решили это перенести уже в код, а там и свое решение подтянулось
idx = getIndexByUserId.get(userId);
leaderboard[ids].addScore(20)
leaderboard.sort()
leaderboard.each(index, entry -> getIndexByUserId.put(entry.userId, index))
Ведь мне нужен отсортированный массив и значит я буду использовать библиотечный метод. А индекс, потому что мне старший сказал, что поиск в списке очень медленный
30 25 20 15 13 11 5 3 0, если у нас происходит изменение например 11, прилетело +10, мы должны поменять местами несколько записей, это и 13 и 15 и даже 20.
[146] - Entry(146, 2450, 61294)
[147] - Entry(147, 2435, 991223)
[148] - Entry(148, 2430, 67)
[149] - Entry(149, 2420, 13) + 20
и оно превратится в
[146] - Entry(146, 2450, 61294)
[147] - Entry(147, 2440, 13)
[148] - Entry(148, 2435, 991223)
[149] - Entry(149, 2430, 67)
1 (7810), 2-10,
11 (6790), 12-20,
101 (4200), 102-110,
145-149, 150 (2420, наш пользователь), 151-155
1000 (990), 1001-1010
10001-10010
Как это правильно достать из базы?
И да, я понимаю почему это произошло именно так, он не конченный, как может показаться, просто он использовал метод, который возвращает все данные при загрузке, ну то есть лезет в базу, и потом для каждого проходится и дополняет данными из редиса. И дальше происходит фильтрация. Банальная невнимательность? Не понимание, что сейчас достаешь не пяток записей, с которыми придется работать, а там еще дальше куча всего происходит, прежде чем тебе потребуется дополнительная часть данных. В итоге, метод, который должен работать. Хорошо хоть не на каждую запись ходили в редис, а мультигетом…
Все обновления были в одном треде, плюс индекс из map<userId, entry> сразу на нужную запись в list, что бы подвинуть ее при апдейте.
Более того, изначально были апдейты делать list<bucket>, что бы можно было сразу мувнуть запись на очень много позиций вверх, но самая простая реализация работала очень неплохо на таком объеме данных, обычно приходилось делать не больше 20-30 всплываний записи за раз, иногда бывали всплески когда двигали на 3-4 сотни, но это было нечасто.
Моя оптимизация, которая стала работает примерно в 10 раз быстрее заключалась в двух вещах, первая, использование TreeSet, которая делает все эти операции при вставке в него, вторая, добирать данные после того как мы избавились от лишнего мусора. Потому что отсортировать список и сделать из него дистинкт — копейки по сравнению с десятикратным уменьшением доставания данных из редиса.
Когда я спросил, а зачем он так написал, ответ был прост — ну я не подумал, у меня это как-то быстро работало и так. Действительно зачем думать, зачем знать как работают структуры данных, зачем что-то знать про сложность операций. Он же сеньор, это он прошел когда учился в институте.
Плюс мы должны уметь обращаться к этому списку по индексу (требуется отображать кратко эту таблицу топ-10, пяток лиг, и мы должны показывать топ-10 в каждой лиге, и еще +-5 окружающих игрока).
Какую библиотеку мне следует подцепить, что бы оно работало? Ах да, количество ридов этой таблицы примерно 300-400 в секунду.