Спасибо всем, кто участвовал в нашем конкурсе по программированию! Мы подвели его итоги и наградили победителей.
Задача состояла в том, чтобы улучшить реализацию двусвязного списка из исходников Node.js. Этот код быстрый и эффективный, но он был написан под конкретное применение — хранение списков неактивных таймеров. Поэтому прямо в хранимые объекты там добавляются поля idleNext и idlePrev. Перед участниками конкурса стояла задача сделать код универсальным (так, чтобы один элемент мог принадлежать одновременно нескольким независимым спискам) без потери производительности.
Очевидное решение состоит в том, чтобы добавить промежуточные объекты — звенья списка — содержащие поля next, prev и value. Но у этого подхода есть серьёзный недостаток: если у нас есть только ссылка на хранимый объект, и его надо удалить из списка, то придётся перебирать всю цепочку. Налицо потеря производительности.
Более высоко мы оценили те решения, где вместо полей idleNext и idlePrev используется пара полей с другими именами, разными в разных списках. Однако при доступе к членам объектов с помощью оператора «квадратные скобки» вместо «точки» компилятор V8 не может выполнить важные оптимизации, поэтому код работает медленнее.
Призовые места получили те участники, которые использовали самомодифицирующийся код. Если в реализации списка заменить idleNext и idlePrev другими именами, а затем заставить интерпретатор исполнять полученный код (использующий оператор «точка»), производительность не падает.
Подробности о том, как и за что мы присуждали баллы участникам, а также все решения, которые мы получили, — в репозитории на GitHub. Поздравлем победителей!
Отдельно мы решили отметить самых младших участников — одному из них 12, а другому 15 лет. Их команда заняла седьмое место. Дмитрий и Руслан получили особый приз — 350 USD.
Уже думаем над задачей для следующего конкурса.
Задача состояла в том, чтобы улучшить реализацию двусвязного списка из исходников Node.js. Этот код быстрый и эффективный, но он был написан под конкретное применение — хранение списков неактивных таймеров. Поэтому прямо в хранимые объекты там добавляются поля idleNext и idlePrev. Перед участниками конкурса стояла задача сделать код универсальным (так, чтобы один элемент мог принадлежать одновременно нескольким независимым спискам) без потери производительности.
Очевидное решение состоит в том, чтобы добавить промежуточные объекты — звенья списка — содержащие поля next, prev и value. Но у этого подхода есть серьёзный недостаток: если у нас есть только ссылка на хранимый объект, и его надо удалить из списка, то придётся перебирать всю цепочку. Налицо потеря производительности.
Более высоко мы оценили те решения, где вместо полей idleNext и idlePrev используется пара полей с другими именами, разными в разных списках. Однако при доступе к членам объектов с помощью оператора «квадратные скобки» вместо «точки» компилятор V8 не может выполнить важные оптимизации, поэтому код работает медленнее.
Призовые места получили те участники, которые использовали самомодифицирующийся код. Если в реализации списка заменить idleNext и idlePrev другими именами, а затем заставить интерпретатор исполнять полученный код (использующий оператор «точка»), производительность не падает.
Подробности о том, как и за что мы присуждали баллы участникам, а также все решения, которые мы получили, — в репозитории на GitHub. Поздравлем победителей!
- Сергей Шпак — приз 1500 USD
- Ори Шалев — приз 1000 USD
- Александр Лякшев — приз 500 USD
Отдельно мы решили отметить самых младших участников — одному из них 12, а другому 15 лет. Их команда заняла седьмое место. Дмитрий и Руслан получили особый приз — 350 USD.
Уже думаем над задачей для следующего конкурса.
