Blog:Advanced Algorithms

Материал из DISCOPAL
Перейти к: навигация, поиск

Новости курса «Эффективные алгоритмы» для 6 курса ФУПМ МФТИ.

Python-оптимизация алгоритма динамического программирования из codechef

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

Попробую кратко показать, как можно системно поработать с улучшением решения, даже не особо вьезжая в алгоритм (ну при условии, что идея будет правильна).

Первая версия digprime.py

Видим вроде типичный алгоритм ДП, смотрим описание задачи Codechef/DIGPRIME, переходим по ссылке Editorial на разбор и разъяснение задачи, но даже если этой ссылки не будет, смотрим список принятых решений:

Python-оптимизация алгоритма динамического программирования из codechef 2022-05-01 02-47-12 image0.png

Берем из них любое принятое CPP-решение, сохраняем его в файл digprime-good.cpp компилируем его 

 gcc -g -o digprime-good digprime-good.cpp -lstdc++

Итак, у нас есть референсное решение.

Смотрим на описание задачи, особенно на секцию «ограничения»…

Python-оптимизация алгоритма динамического программирования из codechef 2022-05-01 02-50-11 image0.png

и пишем примитивных генератор «digprime-generate.py», такой, чтобы задействовать все ограничения (вдруг все проходит на минимальных данных, но где-то что-то переполняется на самых крайних случаях), плюс большой тестсет даст возможность разумно измерять время работы. 

import numpy as np
num = 100000
print(num)
for t in range(num):
    print(np.random.randint(1,1000000000000000000))

Генерим наш тестовый набор: 

python digprime-generate.py > big-samples.txt

Генерим результаты нашего алгоритма и референсной реализации на тех же входных данных: 

digprime-good < big-samples.txt > reference-good.txt
python digprime.py < big-samples.txt > big-our-results.txt

Сравниваем («meld», «winmerge», «fc», ) — используйте то, что ставится на вашу ось и есть под рукой, но в данном случае, совпадение добайтовое даже по ответу «md5sum»: 

md5sum big-our-results.txt
  e602cd2d36e9c6749764cace13774bdc  big-our-results.txt

md5sum reference-good.txt
  e602cd2d36e9c6749764cace13774bdc  reference-good.txt

Вроде же все в абсолютном порядке, но что выдает codechef?

Python-оптимизация алгоритма динамического программирования из codechef 2022-05-01 02-58-12 image0.png

Ошибка «NZEC» — «какая-то ошибка», увы, без малейших подсказок на чем, и что за ошибка. Но по времени работы — доли секунды, предположим, что что-то сразу с вводом.

Тут на самом деле наблюдались разные проблемы в этих (codechef, spoj) тестовых системах. То что-то не так с буферизацией, и какой-то перевод строки становился пробелом, или длинная строка, и input() не вычитывал ее до конца, то большое количество операций input, а там перенаправление на чтение из файла, много IO операций, срабатывают какие-то контейнерные ограничения или просто будет тормозить.

Поэтому, лучше сразу сделать чтение типа 

    lines = sys.stdin.readlines()
    content = " ".join(lines).strip()

А потом парсить и отдавать результаты генератором.

Делаем такие правки и получаем


версию, которая работает абсолютно также по результату, возможно чуть медленней перекопированием ввода в память (если померять у себя), но возможно быстрее, чем у них на сервере, с задушенным IO.

В любом случае, сначала надо избавиться от NZEC, потом уже заниматься оптимизацией.

Ага, от NZEC уже избавились, но теперь здравствуй TL.

Python-оптимизация алгоритма динамического программирования из codechef 2022-05-01 03-36-58 image0.png

Может если перейти на PYPY, скомпилируется и пройдет?

Увы, нет.

Python-оптимизация алгоритма динамического программирования из codechef 2022-05-01 03-34-48 image0.png

Обращаю внимание — 10.01 и 4.01 секунды это не время работы программы! Это только таймлимиты (плюс сколько мгновений, пока программу не убили), которые выделены питону (Python 3.6) и скомпилированному питону (PYPY).

Хотя обычному питону дается фора, в 2.5 раза времени, выигрыш PYPY обычно бывает больше. Есть конечно минусы PYPY — в нем нет numpy, удобных многомерных массивов и эффективных матричных операций, есть модуль «array», который иногда полезен… но в нашем случае, попробуем обойтись без всего этого, используя обычные питоновые списки-вектора, структуры, которые были изначально.

А вот что необходимо — начать замерять время выполнения (экзаменационная система вам не поможет — там только да или нет), и профилировать выполнение.

У меня древний десктоп нулевых годов, цифры могут отличатся от ваших, если вы повторяете эксперименты, плюс у вас будут другие входные данные, но буду приводить свои данные. Обычная linux утилита time, где нужно смотреть только «user time» нам вполне подойдет. 

time python digprime.py < big-samples.txt > big-our-results.txt

real    1m8.108s
user    1m6.412s
sys     0m0.351s



time pypy3 digprime.py < big-samples.txt > big-our-results.txt

real    0m4.519s
user    0m4.143s
sys     0m0.143s

Впечатляющая разница? Но нам увы, недостаточно.

Давайте посмотрим, что «жрет». Всегда можно сделать стандартное профилирование (разумная сортировка по общезатраченному времени «-s cumulative») 

python -m cProfile -s cumulative digprime.py < big-samples.txt >profile-results.txt
ncallstottimepercallcumtimepercallfilename:lineno(function)
10.0000.000103.393103.393{built-inmethodbuiltins.exec}
12.7162.716103.393103.393digprime.py:2(<module>)
43546528/10000093.6910.000100.0710.001digprime.py:19(calculate)
435465286.3800.0006.3800.000{built-inmethodbuiltins.len}

Что видно — огромное количество (43.5M) рекурсивных вызовов функции «calculate», ну и еще там где-то зря дергаются лишний раз «len()».

Начинаем оптимизировать, учитываем пропущенную эвристику[1], делаем правку, получаем версию, для которой 

CPython time → 41.203s
Pypy time → 2.722s
Вызовов calculate → 26874678

Уберем кстати, хардкодинг, число цифр в константу.

делаем правку, получаем версию, для которой 

CPython time → 40.610s
Pypy time → 2.749s
Вызовов calculate → 26874678

(ничего интересного не достигли)


Введем глобальную переменную N c длиной текущего числа, уберем перерасчитывание высчитывание длины внутри функции.


… делаем правку, получаем версию, для которой … 

CPython time → 37.117s
Pypy time → 2.907s
Вызовов calculate → 26874678

… чуть ускорили обычный питон, где байткода такие вещи не оптимизирует, но скомпилированный PyPy лучше не стал.

Потом в коде видим странные штуки типа «taken | (x == 2) | (x == 3) | (x == 5) | (x == 7)» — ох тыж, считается «бинарное или» вместо логического, а ведь в везде «логическое или» оптимизируется слева направо, т.е. если левый операнд уже «истина», то дальше ничего считать не надо.

… делаем правку, получаем версию, для которой … 

CPython time → 24.413s
Pypy time → 2.907s
Вызовов calculate → 26874678

Большой прорыв по обычному питону, но PyPy3 об этом похоже, догадался сам, тут не помогло.

Небольшие правки, вроде убираем ненужные требования о преобразованиях типов

… делаем правку, получаем версию, для которой …

… если и есть экономия, то копеечная.

Пора заняться важным, оптимизацией хвостовой рекурсии.

Мы видим, что в рекурсивной функции, в самом начале у нас куча эвристик по выходу из этой функции… так может ее сразу не вызывать в рекурсивных вызовах? А в первом вызове они не сработают.

Начинаем, переносить каждое условие по одному

… делаем правку, получаем версию, для которой …

… экономия начинает появлятся, хотя во времени на уровне колебаний измерения, но вот количество рекурсивных вызовов уменьшилось: 

CPython time → 24.718s
Pypy time → 2.413s
Вызовов calculate → 25324715

Переносим «эвристику с десятками»

… делаем правку, получаем версию, для которой …

радикально уменьшились рекурсивные вызовы (хотя внутри функции теперь больше работы), но время тоже падает 

CPython time → 21.763s
Pypy time → 2.270s
Вызовов calculate → 11972222

Переносим «кеширование DP»

… делаем правку, получаем версию, для которой …

радикально уменьшились рекурсивные вызовы (хотя внутри функции теперь больше работы), но время тоже падает 

CPython time → 17.762s
Pypy time → 2.099s
Вызовов calculate → 3477870

Явно улучшилось!

Да, тут многое чешеться еще улучшить, но пора попробовать, вдруг уже пройдет → ура, проходит!

Python-оптимизация алгоритма динамического программирования из codechef 2022-05-01 05-40-36 image0.png

Да, тут многое можно было написать красивей[2], очень желательны комментарии для будущих читателей кода… но для целей иллюстрации, как оптимизировать питоновский код, думаю, достаточно, чтобы не перегружать статью!

Удивительно, что один из наших студентов решил эту задачу на на CPython, хотя это конечно хак, запускать питоном чистый ассемблер! Не надо так делать в наших задачах, лучше подумать над алгоритмом, но всеже тема интересная и попробуем написать про такой подход статью-заметку.



  1. ↑ что когда у нас «230» → то на второй цифре можно сразу вернуть число десятков, не перебирая глубже
  2. ↑ жалко, что пришлось вставлять лишний парсинг входа, с точки зрения чистых алгоритмов это конечно хак, хотя в любом случае это читаемый код, а не С++шный «лишбыработало» [1], [2])

Разместил Стас Фомин 1 мая 2022 02:48 (GMT), нет комментариев.

2022-04-28

Так делать не надо:

  • Профилирование
python -m cProfile -s cumulative mycode.py < bigcase.txt  >profile.log
  • Отладка в VSCode
       {
           "name": "mycode",
           "type": "python",
           "request": "launch",
           "program": "mycode.py",
           "console": "integratedTerminal",
           "justMyCode": true,
           "args": ["<", "mycode.txt"]
       },


  • Розыгрыш «хор»-зачета за баллы.
  • Двойной выигрыш → «отл»


Если что не получилось — посмотрите, там дальше ссылка с видео



Поразбираем:

Разместил Стас Фомин 28 апреля 2022 06:23 (GMT), нет комментариев.

2022-04-21

Так делать не надо:


Поразбираем:

Розыгрыш «хор»-зачета за баллы.


Если что не получилось — посмотрите, там дальше ссылка с видео


  • Категория:На_проверку
  • «Отл» за 5 задач из Spoj/Codechef (не LeetCode) + одна теоретическая
  • «Хор» за 3 задачи из Spoj/Codechef (не LeetCode).



Разместил Стас Фомин 21 апреля 2022 06:36 (GMT), нет комментариев.

2022-04-14

2022-04-07 2022-04-07 08-06-39 image0.png

Если что не получилось — посмотрите, там дальше ссылка с видео


  • Категория:На_проверку
  • «Отл» за 5 задач из Spoj/Codechef (не LeetCode) + одна теоретическая
  • «Хор» за 3 задачи из Spoj/Codechef (не LeetCode).


Кому скучно:

Поразбираем:


Разместил Стас Фомин 14 апреля 2022 07:04 (GMT), нет комментариев.

2022-04-07

2022-04-07 2022-04-07 08-06-39 image0.png

Если что не получилось — посмотрите, там дальше ссылка с видео



Кому скучно:

Поразбираем:

Разместил Стас Фомин 7 апреля 2022 07:01 (GMT), нет комментариев.

2022-03-31 Feedback

Решения задач — ищем решения именно на Python! «4 из 6» колонок чтобы были накрыты (некоторые задачи могут накрыть две колонки — две темы.

2022-03-31 Feedback 2022-03-31 08-19-37 image0.png

  • «Отл» за 3 задачи из Spoj/Codechef (не LeetCode).
    • До сих пор открыто после будет за 4 задачи.

Кому скучно:

Поразбираем:

Разместил Стас Фомин 31 марта 2022 06:48 (GMT), нет комментариев.

2022-03-24 Feedback

Решения задач — так держать!

«отл» автоматом для тех, кому не лень
  • «Отл-автоматом» — теперь, при условии хотя бы одной теорзадачи.
  • Эта неделя → «Отл» за 3 задачи из Spoj/Codechef.

Разместил Стас Фомин 24 марта 2022 07:36 (GMT), нет комментариев.

2021-12-20 Feedback по jupyter-ноутбукам

2021-12-20 Feedback по jupyter-ноутбукам 2021-12-20 17-13-53 image0.png

Просмотрел несколько видеопрезентаций по юпитер-ноутбукам.

  • Часто встречается паттерн «свалка кода сбоку» в рядом лежащих питон-файлах, в ноутбуке только интерфейс к какому-нибудь простому интерфейсу. Это конечно, не то, что хотелось бы.
    • Почему это плохо?
    • Такой ноутбук «не работает» как передача знаний, он бесполезен, он не лучше, чем кусок кода, ибо все равно
      • разбирающемуся придется реинженирить код, его функциональные связи, что там и что означает…
      • такой ноутбук не «расшарить» в colab.research.google.com или cocalc.com (там всегда плохо на тему шаринга рядом лежащих файлов).
      • он не работает как презентация-пояснение-живой плейграунд («а что если тут поменять XXX»?).
  • Посмотрите реально примеры и разбор из Blog:Advanced Algorithms/2021-12-01 Как делать лучше jupyter по статьям
    • Последовательно вводите понятия, каждая питон функция в отдельной ячейке, в ячейке перед ней — описание, в ячейке после нее — примеры вызова с характерными данными.
    • Не бойтесь, если будет длинно — никогда не жалейте места для лишних слайдов или ячеек в ноутбуках — в зависимости от аудитории, слайды-ячейки можно пропустить, зато гарантирует, что хоть кто-то разберется в теме (включая вас, такой рефакторинг для научного ресерча — самый эффективный способ найти проблему).
  • Вот пример неплохого доклада вашего однокурсника → https://youtu.be/XeZTpQWTDUU (ноутбук)
    • При записи доклада, разумно использовать какой-нибудь экранный аннотатор (рисовалку), на худой конец, поставьте курсор побольше, это поможет.
    • В идеале — добавляйте вебкамеру и научится хромакею. Учитывая, что защита в этом году будет скорее всего дистанционная — хороший повод потренироваться записывать себя, чтобы потом вырезать неудачное, остальное ускорить, и потом прокрутить на защите идеально выведенный по таймлимиту ролик защиты (на вопросы подключится живьем).
  • По срокам — я выторговал в деканате до 25го декабря, но лучше не задерживать до последнего момента.

StasFomin 13:56, 20 декабря 2021 (UTC)

Разместил Стас Фомин 20 декабря 2021 13:56 (GMT), нет комментариев.

2021-12-01 Как делать лучше jupyter по статьям

→ продолжить чтение…

Разместил Стас Фомин 10 декабря 2021 16:28 (GMT), нет комментариев.

2021-11-15 Research Block

Концептуально:

  • Свежие статьи на относительно знакомые темы
  • Надо «воспроизвести»
  • Юпитер-ноутбук или SageWorksheet или …
  • Наш сервис — https://discopal-lab.0x1.tv
    • Почему наш?
    • https://colab.research.google.com — хорошая альтернатива, но
    • все теряется, сложно собрать все времесте.
    • только ядро Python (нет R/Sage/… возможно у нас будет Coq и т.п.)
    • Почему не jupyterlab или jupyterhub — нет коллаборации.
2021-11-15 Research Block 2021-11-24 12-20-26 image0.png
    • Почему не cocalc.com — стал хотеть денех.
2021-11-15 Research Block 2021-11-24 12-19-13 image0.png
  • Введение будет отдельно
    • Но разобраться что есть юпитер-ноутбук можно и самостоятельно
  • Доступ к https://discopal-lab.0x1.tv (логин/емейл-пароль) получите лично (почта или тг)
    • Как только пройдете более простые квесты (по задачам и тестам).
2021-10-15 Practical Block 2021-11-03 14-22-47 image0.png


  • Полностью «переписывать статью не надо»
    • Разобраться в введении
    • Воспроизвести максимально декомпозировав, основной алгоритм.
    • Доказательства не нужны.
    • «Модель»-«Алгоритм»
  • Если что не получается — пингуйте.
    • Можно конечно
      • Работать с локальным Jupyter
      • Использовать colab
      • Но регулярно перегружайте в discopal-lab — чтобы я видел прогресс, и мог комментировать-корректировать.
  • Как что получится.
    • Научитесь пользоваться OBS — (см. также [1]), попробуйте использовать экранное рисование ([2]) и сделать это живым и доступным.
    • Запишите видео-презентацию и забросьте мне (unlisted youtube, файлохранилища…)
  • Срок — первая группа — давайте попробуем до 5 декабря.

Разместил Стас Фомин 3 декабря 2021 14:56 (GMT), нет комментариев.

2021-11-21 Feedback

©

  • Если проблемы в решении → исправляем и снова «на проверку». (1)
2021-11-21 Feedback 2021-11-24 19-12-10 image0.png
2021-11-21 Feedback 2021-11-25 06-38-20 image0.png
  • Не гонитесь за количеством литкодов — это на «уд», база.
    • Выгнал из резервированных кому хватит!
2021-11-21 Feedback 2021-11-25 05-47-01 image0.png
2021-11-21 Feedback 2021-11-25 05-45-27 image0.png
2021-11-21 Feedback 2021-11-25 05-46-17 image0.png
  • Никого левого не пускаем! — не зовите.
  • Совсем плохо с решением задач — ну гуглите решения, или даже смотрите ютуб-каналы с разбором.


2021-11-21 Feedback 2021-11-25 12-06-48 image0.png
2021-11-21 Feedback 2021-11-25 12-13-35 image0.png
    • Вариант без «теории»
    • Неделя «отл» за два «не LeetCode»-решения (Spoj/CodeChef). → до 22.11 включительно. (ну при этом надо чтобы было 4х-задачное покрытие тем, как обычно». А 23го подведем итоги по задачам (чтобы больше их не решать), откинем и удачливых, и тех, кто не осилил, и будет очередной созвон по теории.
      • Как отлаживать без тестов?
      • Написать генератор
      • Проверить существующими решениями на других языках

Разместил Стас Фомин 25 ноября 2021 10:32 (GMT), нет комментариев.

2021-10-15 Practical Block

2021-10-15 Practical Block 2021-11-03 14-27-56 image0.png

Концептуально:

  • Win-Win!
  • Абсолютно практические задачи с собеседований.
    • LeetCode
    • CodeChef
    • SpojCode
    • Сотни решенных и нерешенных
  • Условно поделены на «Dynamic Programming», «Greedy», «Random», «Sorting», «Numbers»
  • Нужно быть залогиненным
    • Скрыто из интернета
  • Изучайте Решенные практические задачи (Их там 1400)
  • Надо решить 4 задачи из разных разделов.
    • Или взять бонусную задачу — «отл» автоматом.
2021-10-15 Practical Block 2021-11-03 15-02-30 image0.png

2021-10-15 Practical Block 2021-11-03 14-24-09 image0.png

(Их там 261)

    • Не нужно брать десятки задач на себя сразу, и освобождайте то, что не получается.
  • Решенное
    • Ну смотрите, как оформлено в прошлые годы
    • Решение на подстранице вашей личной страницы
      • Вики-ссылка на задачу
      • Python-код в «<source lang="python"></source>»
      • Метка «{{checkme}}», когда решите.
2021-10-15 Practical Block 2021-11-03 14-22-47 image0.png

(Их там 7)


  • Как легче решать Python
    • Загрузка данных
    • Выбирайте более свежий CPython или PyPy.

Разместил Стас Фомин 3 ноября 2021 20:16 (GMT), нет комментариев.

2021-09-03 Анонс «Эффективных алгоритмов-2021»

Кратко, что будет, чего не будет и что ждать.

  • Лекций — не будет. Это бред и бессмыслица, особенно при дистанционке. Созвоны будут при небходимости, в формате семинара, может индивидуальные.
  • Будет путешествие-квест, с разными активностями.
  • Берем только практические вещи — алгоритмы для разных задач, особенно NP-полных.
  • Условно будет три блока
    • Теоретический — прочитать темы, посмотреть записи лекций, пройти тестирование, возможно решить некоторые теорзадачи.
    • Тут будет первый отсев — если не проходите тесты (отсеим, скажем, 25% нижних), то «досвидания».
      • Не рекламируйте этот курс — чем меньше народу, тем будет лучше. Я заинтересован сократить численность всеми способами. Особенно нафиг я посылаю всех, кто пытается запрыгнуть в курс в середине семестра и позже. Без шансов. Когда-то прогибался в виде исключения, сейчас не буду.
    • Легкий практический — решение нескольки задач, даваемых на собеседованиях в IT-компаниях, типа LeetCoding, SpojCoding, CodeChefing и т.п.
    • Тут будет второй отсев — но можно будет тут свалить, получив «уд» — кому нужно время, и не очень все это интересно.
    • Теор-практический — взять некоторую тему из заданных (свежая статья, я отберу), и сделать ее разбор-презентацию-реализацию в каком-нибудь jupyter или cocalc-ноутбуке (там будет видно). Тут возможно будет и индивидуальная работа и может тренировка презентейшн скиллс, что полезно для ваших дипломов (сколько я смотрел защит, все ужасно).

Ну остальные новости будут в группе, если что. Вопросы тоже там или напрямую.

Как зарегистрироваться — написано на основной странице курса, где все и будет https://discopal.ispras.ru/Advanced-algorithms

Регистраций открыта до 15 октября.

Подумайте еще раз — надо ли вам это. «Халявы», «Лекций», «Оценок за удаленную посещаемость» тут не будет. Даже «уд. нахаляву». Посмотрите, вокруг полно интересных курсов по выбору.


Разместил Стас Фомин 3 сентября 2021 10:35 (GMT), нет комментариев.

2021-05-20

  • Большой тест в подарок.
  • Кучу тем Курс лекций «Сложность алгоритмов» (ИСПРАН, 3 курс МФТИ)#не берем в этом году
  • «A»-фактор поделен на 5.
  • Больше баллов за самостоятельную работу.
  • Continuous Integration — оценки выставляются непрерывно до середины июня. Или нет?
    • Похоже выставляем скрочно, до конца пятницы.
    • С 15:00 до 17:00 меня можно найти в ИСПРАН, 301 комнате, и попробовать сдать лично (кому не хватает баллов и т.п.).
  • Проблемы с оформлением:
  • Как бороться с NZEC с задачами.
    • Пишите генератор тестов.
    • Сравнивайте с имеющимися решениями на C
  • Непитоновые задачи засчитывались — Участник:Srip09/USelection
  • Много совсем не проходит тесты — 1, 2


©
  • Новый блок задач (отдельная графа в суммировании)
  • Сегодня и завтра даются баллы за решения с нарушением TL за 3 балла!, разумеется, если запускать в PyPy режиме — Почти как полное решение, хотя тут даже не факт, что пройдет нетривиальные тесты. Пользуйтесь!


Распорядок передачи знаний на этот период.webp


Разместил Стас Фомин 20 мая 2021 08:35 (GMT), нет комментариев.

2021-03-12

[1]


Разместил Стас Фомин 12 марта 2021 19:59 (GMT), нет комментариев.

2021-03-11

, где — очки за задачу. Т.е. выгодно решить 1-2 задачи в каждой из тем, вместо того, чтобы выгрызать только одну тему, насобачившись решать что-то одно.

Разместил Стас Фомин 11 марта 2021 08:17 (GMT), нет комментариев.

2020-12-22 Feedback

2020-12-22 Feedback 2020-12-23 10-53-41 image0.png
Понижены
  • Стартовые штрафы ленивым
  • Границы перцентилей
  • «Отлично» в два раза меньше «Лидеров»
Numb3rs
  • 18/30 финишировали с оценкой
  • Только в SpojCoding
    • 39 нерешенных задач
    • 147 решенных и не питонизированных
    • А еще LeetCoding
    • {{checkme}}

  • Давайте отгружайте активней!
  • Можно срубать «чужие блоки», если старше 5 дней.
    • Бывают столкновения правок [1]
  • Quest-D — на самом деле легкий способ улучшить оценку на балл, не пренебрегайте.
    • User:Easik — c самых больших штрафов, до «отл»

Разместил Стас Фомин 23 декабря 2020 17:57 (GMT), нет комментариев.

2020-12-15 Feedback

2020-12-15 Feedback 2020-12-17 17-35-10 image0.png
  • Решение каждой задачи на отдельной странице, а не как [1]
  • 1, 2, 3, 4, 5, … — проверяйте перед записью!
  • «Time Limit Exceeded» — если не питон, то скорее всего алгоритм сильно не оптимален (квадрат вместо nlogn, экспонента вместо полинома и т.п.).
  • «1 → 2» — списывать и передавать решения неспортивно!
  • Штраф для «раздолбаев» понижен — включайтесь!
  • Новая возможность — написать питон решение к задачам решенным не на Python

2020-12-15 Feedback 2020-12-16 16-54-15 image0.png

    • Иногда это может быть сложно — понять длинное решение на C или Rust
      • Но в целом, полезный навык
      • Можно использовать для тестирования своего решения
      • по 2 балла за задачу
      • Таких много, несколько десятков.
      • Можно даже если это вы сами
      • Если не укладываетесь по времени — пробуйте PyPy
      • Местами есть проблемы Участник:Andriygav/BAT3
  • Привлечь внимание {{checkme}} (новое решение, исправление старого, и т.п.)

  • Для тех, кому надоели задачи и хочеться чуть лекций
    • Quest-D — три балла отдельно.
  • Сроки — скажем до 29 декабря.
    • Может можно будет продолжить, не уверен.
    • «запланированные даты экзамена» — игнорируйте.
  • Оптимально — баланс по темам!
  • Leet/Spoj
    • Хороший питон — numpy
    • Leetcoding — мягче, показывает, где фейл
    • Несравнимо с CodeForces — издевательство, все в ведро…
  • В целом — мы делаем полезное!
    • Можете рекламировать себя («подпишись на мой гитхаб»).
  • Можно добавлять новонайденные задачи с этих ресурсов в соответствующие разделы.
  • Насколько часто проверяю?
    • Служебная:Свежие_правки
    • Стараюсь раз в несколько дней «начать проверочный обход»
    • Убираю «Блокирующие метки» старше 5 дней!
  • Начиная со следующей недели можно фиксировать отметки!

Разместил Стас Фомин 17 декабря 2020 14:35 (GMT), нет комментариев.

2020-12-01 Feedback

2020-12-01 Feedback 2020-12-02 15-13-15 image0.png

Проблемы

  • Зависания и «блокировки» задач
    • Это четыре тильды, не три.
    • Теперь 5 дней.
    • «Блокировку» можно стирать после решения.
  • Красивее код
    • Он не только для задачи, но и для ваших коллег.
    • тег «code-python», «code-cpp»
    • Ссылку на исходную задачу
    • Лишних категорий не надо.

Оценки

  • Участник:Phokov — молодец.
    • Порадуем трех первых сразу!
    • Лучше понадкусывать везде!
  • Автоматического «уд» нет, обязанности «принимать» — тоже нет.
    • Курсов по выбору много.
  • A_index
  • Квест по машинлернингу.
    • 0x1-classification — 20 баллов за разумное, 12 — за минимально вменяемое. Наверное можно даже троих параллельно.

Разместил Стас Фомин 2 декабря 2020 12:39 (GMT), нет комментариев.

2020-05-19 Дистанционный зачет по «Эффективным алгоритмам»


Всем привет. Пора выходить на финишную прямую в весеннем курсе 2020.

Как обычно, в курсе учитывалась разнородная активность:

  • реальные занятия (до карантина), активность на оффлайн занятии, прохождение там же тестов,
  • дистанционная работа:


Тезисы:

  • Активность последний месяц была не очень высока (хотя возможностей была масса).
    • Неполенившиеся уже получили «отл»
  • «Win-Win» — оценка справедливо соответствуюет трудозатратам.
  • Никакого каргокульта («зачетных дней») — все распределенное и асинхронное.
  • Есть еще время (минимум неделя).
  • Оставшиеся квесты:

    • У кого совсем плохо с кодом — три раза будут проведены тесты — они будут появятся сверху на странице курса.
      • Окна:
        • Пятница, 22 мая, 13:00-13:30
        • Суббота, 23 мая, 14:00-14:30
        • Понедельник, 25 мая, 15:00-15:30
        • Вторник, 26 мая, 22:00-22:30
  • У кого «хор», но очень хочется улучшить оценку до «отл» — свяжитесь со мной, есть квест (смотреть и комментировать околонаучные доклады), как можно улучшить оффлайн (что-то типа Quest-O).


Предновогодний цейтнот преподавателя.jpg


Разместил Стас Фомин 19 мая 2020 17:55 (GMT), нет комментариев.

« новейшие … старейшие »
Источник — «https://discopal.ispras.ru/index.php?title=Blog:Advanced_Algorithms&oldid=142»