Comments 8
Расскажите, как вычисляли среднюю оценку посещения достопримечательности?
Просто шли по массиву, считали сумму и делили на количество?
Просто шли по массиву, считали сумму и делили на количество?
Практически. Для каждой достопримечательности в какой то момент оптимизации сервера я стал хранить список ее посещений. Соответственно когда нужно было посчитать среднюю оценку я просматривал не весь массив с посещениями, а только те, которые относятся к этой достопримечательности. А так да, считал сумму и делил на количество
Есть способ делать это за O(lg(n))
Нужно хранить с каждым посещением ещё и сумму оценок до этой даты для данной достопримечательности. Делать это надо до первой волны и после окончания второй, нет смысла при каждой вставке их пересчитывать.
Как происходит выборка: выбираем последнее посещение до даты «from» и последнее посещение до даты «to», бинарным поиском, за O(log(n))
берем разницу сумм оценок — получаем сумму в этом отрезке
по разнице индексов найденных границ получаем число оценок
и всё
ЗЫ: я сам не участвовал, но эти оптимизации в голове пытался продумывать
В принципе, вроде больше нечего оптимизировать, если все данные в памяти, есть общий доступ всех процессов к ним, нет data race-ов
Нужно хранить с каждым посещением ещё и сумму оценок до этой даты для данной достопримечательности. Делать это надо до первой волны и после окончания второй, нет смысла при каждой вставке их пересчитывать.
Как происходит выборка: выбираем последнее посещение до даты «from» и последнее посещение до даты «to», бинарным поиском, за O(log(n))
берем разницу сумм оценок — получаем сумму в этом отрезке
по разнице индексов найденных границ получаем число оценок
и всё
ЗЫ: я сам не участвовал, но эти оптимизации в голове пытался продумывать
В принципе, вроде больше нечего оптимизировать, если все данные в памяти, есть общий доступ всех процессов к ним, нет data race-ов
deleted(ошибся веткой)
Читаю описания чужих решений и думаю: как же нас всё таки развратили все эти фреймворки, стандартные либы и подходы. Среди знакомых программистов никто не может даже на шаг отступить от привычных решений, типа «юзаем редис» или «создай индекс в базе» и т.п.
Побольше бы таких конкурсов. И по ширше освещать их на популярных ресурсах.
Руки чешутся поучавствовать ) Хоть я и нуб.
Побольше бы таких конкурсов. И по ширше освещать их на популярных ресурсах.
Руки чешутся поучавствовать ) Хоть я и нуб.
Просто сначала получаешь некий baseline, используя проверенные и подходящие решения. Возможно, он окажется достаточно хорош, возможно нет. В последнем случае начинаешь аккуратно искать «узкие» места.
Иначе, скорее всего, просидишь весь конкурс в попытках написать свой http и закончишь конкурс с неполноценным творением, до сути задачи так и не добравшись.
Иначе, скорее всего, просидишь весь конкурс в попытках написать свой http и закончишь конкурс с неполноценным творением, до сути задачи так и не добравшись.
Мне кажется, тут самый интересный момент это «5 дней», ибо показывает тот удачный компромисс в Go между скоростью разработки / производительностью (+читабельностью кода, хотя в конкурсе это не важно было :) ).
У меня тоже было решение на fasthttp+ffjson, всё в памяти. Оно было написано за чуть более половину дня (субботы) — вот с нуля, с прочтения задания, и до попадания в в десятку на тот момент в рейтинговом обстреле. В воскресенье я провозился с залипшими обстрелами (это ещё было до того, как организаторы выложили ammos для yandex tank), а в будние дни уже было не до этого и интерес пропал.
У меня тоже было решение на fasthttp+ffjson, всё в памяти. Оно было написано за чуть более половину дня (субботы) — вот с нуля, с прочтения задания, и до попадания в в десятку на тот момент в рейтинговом обстреле. В воскресенье я провозился с залипшими обстрелами (это ещё было до того, как организаторы выложили ammos для yandex tank), а в будние дни уже было не до этого и интерес пропал.
Sign up to leave a comment.
Как написать хорошее решение для Highload Cup, но недостаточно хорошее чтобы выйти в топ