Блог пользователя pavook

Автор pavook, история, 2 года назад, перевод, По-русски

Иногда я задумываюсь, какую реализацию дерева отрезков написать в задаче. Обычно я при помощи метода "пальцем в небо" выбираю какую-то и в большинстве случаев она проходит ограничения.

Я решил подвести основу, так сказать базу, под этот выбор и протестировал на производительность 4 разные реализации:

  • Простой рекурсивный "Разделяй и властвуй"
    Код
  • Оптимизированный рекурсивный "Разделяй и властвуй", который не спускается в заведомо ненужных сыновей.
    Код
  • Нерекурсивная реализация (взял отсюда: https://mirror.codeforces.com/blog/entry/18051)
    Код
  • Дерево Фенвика
    Код

Все реализации поддерживают такие запросы:

  • get(l, r): сумма на отрезке (полуинтервале) $$$[l; r)$$$
  • add(i, x): прибавление к элементу под индексом $$$i$$$ числа $$$x$$$

Вот результаты:

Примечание: я старался не делать никаких оптимизаций, требовательных к конкретным запросам, чтобы с небольшими изменениями структуры данных могли применяться для любых операций.

Я генерировал запросы следующим образом:

  • Прибавление в точке: случайный индекс (rnd() % size) и случайное число
  • Сумма на отрезке: сначала, генерируется длина отрезка (rnd() % size + 1), затем подходящая левая граница.

Исходники бенчмарка. Примечание: желательно отключить CPU frequency scaling, закрыть все приложения, которые могут мешать бенчмарку (чем больше закроете -- тем в теории стабильнее будет результат) и "прибить" процесс к конкретному CPU.

Скрипт на Python, создающий красивый график

Результаты в формате JSON на случай, если Вы захотите ещё поиграться с данными.

Я компилировал бенчмарк с #pragma GCC optimize("O3") на GNU GCC 11.3.0, запускал его с фиксированной частотой процессора 2.4 GHz, прикрепив к конкретному ядру процессора.

Наверное, это мой первый вклад в сообщество, поэтому любые дополнения/предложения приветствуются.

Полный текст и комментарии »

  • Проголосовать: нравится
  • +126
  • Проголосовать: не нравится

Автор pavook, история, 5 лет назад, По-русски

Сегодня писал Educational Codeforces Round #80. При попытке отправить решение через меню "Submit" в задаче справа я получил ошибку "403 Forbidden" и после перезагрузки страницы это меню пропало. Мне удалось отправить посылку в раунд через верхнее меню "Submit". Я не могу взламывать задачи раунда, всплывает сообщение "Invalid contest ID". Я не могу так же отправить вопрос по задаче, кнопка send просто не работает. Что делать?

Полный текст и комментарии »

  • Проголосовать: нравится
  • +18
  • Проголосовать: не нравится