Blog:Advanced Algorithms

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

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

2022-12-19 Разбор задачи «Хранилище артефактов»

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

2022-12-09 Feedback

Course-2022-balls.drawio.svg

2022-12-09 Feedback 2022-12-09 16-58-43 image0.png


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

2022-12-06 «Воспроизведение статей» — на отл.

Для тех, кому не хватило баллов, обязательная программа (алгоритмические задачи и бизнес-задачи) выполнена, и готовы идти на «отлично».

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

  • Это на «отл»
  • Win-Win!
  • Подготовка к защите дипломов-курсовых-кандидатских — моделирование диплома-научной работы и ее защиты.
  • Анализ научной статьи про алгоритмы, с переложением ключевой части в Jupyter-ноутбук.
    • Полностью «переписывать статью не надо» — не надо переводить-копировать все содержание.
      • Доказательства не нужны.
    • Разобраться в введении
    • Моделировать постановку задачи (обычно это ЦЛП)
      • Возможно придумать тестовые данные, если их там нет или не прилагались к статье.
    • Воспроизвести максимально декомпозировав, основной алгоритм — попробовать смоделировать и воспроизвести алгоритм для решения.
    • Некоторые примеры работ в папке articles2jupyter-examples
    • глобальная проблема воспроизводимости + https://paperswithcode.com/ → мы помогаем решать.
    • Если что не получается — пингуйте.
    • Запишите к ним видеоролик, как в Blog:Advanced Algorithms/2022-12-01 Кто решил бизнес-задачи, запишите по ним видеоролики
    • Научитесь пользоваться OBS — (см. также [1]), попробуйте использовать экранное рисование ([2]) и сделать это живым и доступным.
    • Запишите видео-презентацию и забросьте мне (unlisted youtube, файлохранилища…)


  • Если предлагаемые статьи не понравились, а есть что-то про алгоритмы по теме вашей работы-диплома → можете работать над этим.
    • Может прямо это и будет драфтом дипломной работы
    • Презентацию можно сделать прямо из Jupyter-ноутбука, см RISE.
  • Идем на Lab
  • Оформляем свои ноутбуки в папке «advalg-2022-homeworks»
  • Учимся на готовых решениях коллег в соседних папках и решениях прошлых лет → articles2jupyter-examples

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

Разбор оптимизационной задачи «Группировка людей»

Несколько сумбурный разбор этой задачи сходу (но может это и хорошо, ошибка и поиск ошибок — полезно показать).

Студенту — не забыть доделать визуализацию результатата покрасивей (граф, кластеры, связи там). Например, как-то так → [1], [2]


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

Хорошие практики компактных Pyomo-формулировок на примере решения «Задачи о станках»

  • Старайтесь делать компактные и читаемые Pyomo-формулировки
    • тогда даже не понадобится куча плохочитаемых латех-пояснений.
  • Посмотрите — как индексировать переменные и ограничения, как использовать слайсы в суммах, поменьше лишнего кода (особенно всяких скобок).
  • Задача Optprob/Покупка станков

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

Задача о двух кучах камней и примеры использования различных ЦЛП-солверов

«Задача о двух кучах камней и примеры использования различных ЦЛП-солверов»

  • компактная задача и постановка, однако на которой зафейлился CBC — наш солвер «по умолчанию», и возник повод попробовать другие ЦЛП-солверы, и повод пошевелить постановку.

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

2022-12-02 Feeback

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

2022-12-01 Кто решил бизнес-задачи, запишите по ним видеоролики

Кто решил бизнес-задачи, и чье решение уже проверено и признано правильным, — запишите разьясняющие видеоролики по вашим решениям с помощью OBS (это универсальное решение для создания видеодокументации — можно использовать камеру (и даже с хромакеем), можно использовать стилус для рисования, но на худой конец, просто скринкаст с нормальным звуком, ну и курсор можно сделать побольше... — так тоже пойдет.

Ох, понял, что никто не пошел смотреть ссылки, поэтому полезное тут повторю рядом

  • Не экономьте битрейт при записи OBS — ставьте при записи 3 Mbit, потом видеохостинги сами ужмут. Или перепакуете. Главное, не потратить время, получив замыленный и нечитаемый текст юпитер-ноутбуков, очень обидно. Почти как не записать звук.
  • Сначала запишите минутку видео со звуком и послушайте — например, выяснится, что звука вообще нет, или он ужасный (что-то с уровнем например — можно поиграть настройками OBS), а то и вовсе надо сменить микрофон. Для общажных условий, любой микрофон прищепка (стоит копейки, пригодится вам обязательно — сейчас все айти удаленное, непрерывные созвоны — и возможно вас еле терпят и ненавидят за бубнящий микрофон, но почему-то не говорят) может оказаться лучше обычного встроенного в ноутбук микрофона, который может поймать электрошумы из собственной схемы, эхо плохомеблированной комнаты общежития, и т.п.
2022-12-01 Кто решил бизнес-задачи, запишите по ним видеоролики 2022-12-23 03-08-31 image0.png
  • Сделайте полноэкранный режим броузера — больше места для полезной информации.
  • Лучше в discopal-lab понажимать на кнопочку с плюсиком → это лучше, чем просто увеличивать шрифты во всем броузере, хотя и можно и так.
    • Особенно это важно, когда у вас слабое разрешение — 720 например.
  • Полезно сделать курсор большим — в виндах, KDE и GNOME это настраивается по разному, но настраивается.

Потом можно либо мне файл прислать, либо сами на любой видеохостинг (ну хоть на ютуб в unlisted mode) можете загрузить — подошью ваше обьяснение, и это будет работать как обучающий материал для ваших коллег! Ну или поместите «На проверку» решение, написав, что дописали ролик. Просто если вы это сделаете «тихо», где-то добавив ссылку в ноутбук, я это просто не замечу....


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

2022-11-27 Разбор задачи «Капитальные инвестиции» и решения студента

Задача Optprob/Капитальные инвестиции

Ключевой вывод:

  • Пусть будет больше говорящих переменных (про каждый факт)
  • Их связывают простые ограничения
  • И целевая функция простая
  • Это будет легче верифицировать и модифицировать.
  • Решатели сами выкинут лишние переменные и превратят модель в плоскую.


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

2022-11-03 Feedback

2022-11-03 Feedback 2022-11-18 12-02-47 image0.png

Переходим к «Курс лекций «Эффективные алгоритмы»#Блок 2» (уже несколько недель его делают те, кто приходил на созвоны, несколько задержался придумывая задачи).

Разместил Стас Фомин 18 ноября 2022 09:57 (GMT), нет комментариев.

2022-10-14 Feedback

  • Не забывайте добавлять ссылки на задачи → [1], [2] … теряю время.
  • «Насыпано» несколько сотен задач из литкода (чтобы полегче), по темам, где стало маловато задач
  • возможно с «ошибками» классификации,
  • возможно слабенькие («сложение двух целых»)
  • но это неважно.
  • Многие пришли к финишу →
2022-10-14 Feedback 2022-10-14 17-28-05 image0.png


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

2022-10-07 Feedback

  • Решаем именно на Python!
  • Оформляем именно как подстраницу → [4], [5]
  • Участник:Vshokorov/Codechef/QRYLAND — если никак не решается, делайте генератор тестовых данных (но отдельно, в файл!).
  • A_index
  • Надо насыпать новых. Обещаю много легких, из литкода.
  • Поздравляем первых закрывших блок.
  • Втягивайтесь! Ибо второй блок придется идти без вас!

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

2022-09-30 Feeback


  • Насчет ресерч части — если у вас есть что-то, что хотите потренировать срочно, можно начать с этого.

2022-09-30 Feeback 2022-09-30 13-02-33 image0.png

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

2022-09-22 Feedback

  • Созвона завтра, 23го не будет.
  • Вижу, что начали решать, так держать!
  • Небольшой фидбек

    • все проверю в воскресенье, временно буду малодоступен.

Разместил Стас Фомин 22 сентября 2022 15:41 (GMT), нет комментариев.

2022-09-16

  • Пишем тест для регистрации на занятии.

На дом — проходим квест регистрации


Вопросы?


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

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

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

  • Лекций — не будет. Это бред и бессмыслица, особенно при дистанционке. Созвоны будут при небходимости, в формате семинара, может индивидуальные.
    • Асинхронная коллаборация — видеозаписи.
  • Будет путешествие-квест, с разными активностями.
  • Берем только практические вещи — алгоритмы для разных задач, особенно NP-полных.

Условно будет три блока

Базовая грамотность
  • Python
  • Простые алгоритмические задачи
  • Нужно — везде, даже «собеседование в Яндекс на аналитика»
  • Условно «уд»
2021-10-15 Practical Block 2021-11-03 14-27-56 image0.png

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

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

(Их там 249)

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

(Их там 13)


  • Как легче решать Python
    • Загрузка данных
    • Выбирайте более свежий CPython или PyPy.
Формулировка оптимизационных задач
  • Pyomo
    • ЦЛП-постановки
  • Jupyter-ноутбуки
  • Lab
  • Всегда способны решить (MVP-бизнес задачу)
  • Условно «хор»

На отл:

  • Теор-практический — взять некоторую тему из заданных (свежая статья, я отберу), и сделать ее разбор-презентацию-реализацию в каком-нибудь jupyter или cocalc-ноутбуке (там будет видно). Тут возможно будет и индивидуальная работа и может тренировка презентейшн скиллс, что полезно для ваших дипломов (сколько я смотрел защит, все ужасно).

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

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

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

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

Разместил Стас Фомин 9 сентября 2022 15:56 (GMT), нет комментариев.

2022 - Выход на оценку

Курс в этом году выпал несколько сумбурный, ибо я пытался понять, почему получилась несколько разнородная группа, часть из которой проявляла мало активности, думал проблема в разности уровней и сильно занизил основную цель — вместо глубокой коллаборации с моделированием оптимизационных задач на юпитерноутбуках Lab, сконцентрировался на уровне «может решать простые алгоритмы на питон», «отпуская» тех, кому это явно скучно (хотя мне нравится, когда меня удивляют интересными подходами типа Blog:Advanced Algorithms/Путь хакера — решение задачи с codechef на питон. С машинным кодом).

Но оказалось, что многим из нашего списка вообще не нужны оценки, и собственно идея балансировки была не очень в тему («отпускать» надо было других).

Ну и ладно.jpg

Ну и ладно.

Учитывая, что с «вопросом — когда зачет и как» почему-то бегают к координатору, вместо того, чтобы спросить у меня (и хотя бы разок придти на созвон), пропишу все текстом.

  • Оценки (хоть какие-то) выставил всем кому мог.
    • Если вы среди тех, кому оценка нужна, а у вас никакой нет — ну можно устроить что-то паллиативное типа «прохождение теста» (сборник из разбираемых ранее на созвонах вопросов) на «уд» (ну там хотя бы 50% баллов набрать).

Придете на созвон-зачет с тестом на «уд» 26 мая 2022?

Да0
0%
Нет4
100%
Egorkincbl, Hakob, Nechda, Shishqa

Вы должны войти в систему, чтобы участвовать в этом голосовании.

  • Хорошая новость для тех, кому нужна оценка получше. На самом деле, это базовый курс, и обычно[1] эти оценки попадают в реальные журналы где-то в двадцатых числах июня. Т.е. есть возможность улучшить оценку, что есть, если интересно.

Win-Win → сами решайте, интересно ли, и тратить ли время (в целом, достаточно несложно).

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

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

Путь хакера — решение задачи с codechef на питон. С машинным кодом

В процессе написания Blog:Advanced Algorithms/Python-оптимизация алгоритма динамического программирования из codechef, когда удалось получить питон-решение проходящее таймлимиты на PyPy, возник вопрос-челлендж, можно ли все-таки пройти этот квест на обычном питоне («CPython»).

Казалось, что это невозможно, ведь CPython грубо получает таймлимит больше в 2.5 раза, чем для PyPy (но это совсем небольшая фора), и для PyPy мы еле-еле вписались, а по нашим оценкам, наш же алгоритм на CPython работал на порядок медленней. Возможно ожидалась какая-то магия с использованием модулей numpy или collections, чтобы по сути, дергать питоном функции, написанные на си или даже высокообогащенном оружейном фортране.

Другие методы оптимизации — отдельные скомпилированные модули на С, компиляция Cython или Nuitka, тут явно невыполнимы — на вход принимается только один питон-файл.

Но оказалось, есть еще и путь хакера. 

import copy
import ctypes
import mmap
import sys
 
DIGITS = 19
DP_SIZE = DIGITS * 2 * 2
 
 
def get_input():
    lines = sys.stdin.readlines()
    data = ' '.join(lines).strip()
 
    for token in data.split():
        yield token
 
 
func_bytes = (b'AWA\x89\xf7AVA\x89\xfeAUA\x89\xd5ATUSH\x83\xec8\x85\xd2u5Hc\xc7E1'
              b'\xe4\x8b,\x81\x85\xedy-C\x8d\x04wA\x8dDE\x00H\x98M\x89$\xc1H\x83\xc48L'
              b'\x89\xe0[]A\\A]A^A_\xc3\x0f\x1f\x80\x00\x00\x00\x00\xbd\t\x00\x00\x00A\x8d~'
              b'\x01D\x89\xc0H\x8bt$p)\xf8E\x85\xffH\x98A\x0f\x95\xc2L\x8d\x1c\xc6A9\xf8t'
              b'k\x8d\x04?1\xdbE1\xe4\x89D$\x08\x83\xfb\x02t\x19E\x84\xd2u\x14\x83'
              b'\xfb\x07\x0f\x87|\x00\x00\x00\xb8\xa8\x00\x00\x00H\x0f\xa3\xd8sq9\xddu51'
              b'\xd2\xbe\x01\x00\x00\x00E\x85\xedu)\x8bD$\x08\x01\xf0\x8d\x04BH\x98I\x8b'
              b'\x04\xc1H\x83\xf8\xfftdI\x01\xc4\x83\xc3\x019\xdd}\xb3\xe9U\xff\xff\xff\x0f'
              b'\x1fD\x00\x00M\x03#\xeb\xea\x0f\x1f\x001\xc0E1\xe4\xba\xa8\x00'
              b'\x00\x00\x83\xf8\x02t\x10E\x84\xd2u\x0b\x83\xf8\x07w\nH\x0f\xa3\xc2s\x04I'
              b'\x83\xc4\x01\x83\xc0\x019\xc5}\xe0\xe9\x19\xff\xff\xff\x909\xdd\x0f\x95'
              b'\xc2E\x85\xed\x0f\x95\xc01\xf6\t\xc2\x0f\xb6\xd2\xeb\x8b\x0f\x1f@\x00D\x88T$'
              b'/H\x83\xec\x08L\x89\\$(\xfft$xL\x89L$(D\x89D$8H\x89L$ \x89|$\x1c\xe8\xae\xfe'
              b'\xff\xffI\x01\xc4XZ\x8b|$\x0cH\x8bL$\x10D\x8bD$(L\x8bL$\x18L\x8b\\$ D'
              b'\x0f\xb6T$/\xe9M\xff\xff\xff')
 
assert len(func_bytes) <= mmap.PAGESIZE
 
func_buffer = mmap.mmap(-1, mmap.PAGESIZE, prot=mmap.PROT_READ | mmap.PROT_WRITE | mmap.PROT_EXEC)
 
func_type = ctypes.CFUNCTYPE(ctypes.c_longlong, ctypes.c_int, ctypes.c_int, ctypes.c_int, ctypes.POINTER(ctypes.c_int),
                             ctypes.c_int, ctypes.POINTER(ctypes.c_longlong), ctypes.POINTER(ctypes.c_longlong))
func_pointer = ctypes.c_void_p.from_buffer(func_buffer)
 
func = func_type(ctypes.addressof(func_pointer))
func_buffer.write(func_bytes)
 
token_generator = get_input()
next(token_generator)
 
dp = (ctypes.c_longlong * DP_SIZE)(*(-1 for _ in range(DP_SIZE)))
p10 = (ctypes.c_longlong * DIGITS)(*(10 ** i for i in range(DIGITS)))
 
for input_str in token_generator:
    N = len(input_str)
    input_digits = (ctypes.c_int * N)(*(int(ch) for ch in input_str))
 
    print(func(0, 0, 0, input_digits, N, copy.copy(dp), p10))

Идея — будем действовать как JIT. Мы можем переписать кусок кода на си, взять получившийся машинный код, внутри питона его записать в динамически выделенную память и запустить.

Мы можем выделить память с разрешением на чтение, запись и исполнение. Запись понятно для чего, а разрешение на исполнение означает, что процессор может сделать jmp или call в эту область и не крешнуться (разрешение на чтение казалось бы не нужно, но как ни странно, на x86-64 для исполнения также нужно разрешение на чтение): 

func_buffer = mmap.mmap(-1, mmap.PAGESIZE, prot=mmap.PROT_READ | mmap.PROT_WRITE | mmap.PROT_EXEC)

Дальше мы пользуемся библиотекой ctypes в питоне — она позволяет из питона вызывать сишные функции. Для этого нам нужно указать какие аргументы наша функция будет принимать и что возвращать (чтобы питоновский код знал как нужно передавать аргументы перед тем как сделать call в наш код, а также как распарсить ответ): 

func_type = ctypes.CFUNCTYPE(ctypes.c_longlong, ctypes.c_int, ctypes.c_int, ctypes.c_int, ctypes.POINTER(ctypes.c_int),
                             ctypes.c_int, ctypes.POINTER(ctypes.c_longlong), ctypes.POINTER(ctypes.c_longlong))

Вот как это соответствует нашей сишной функции: 

int64_t calculate(int i, int taken, int ls, int *input_digits, int N, int64_t *dp, int64_t *p10)

Дальше нам нужно создать объект сишной функции и записать байты (о них дальше) в выделенную память: 

func_pointer = ctypes.c_void_p.from_buffer(func_buffer)
func = func_type(ctypes.addressof(func_pointer))
func_buffer.write(func_bytes)

И после всего этого мы можем вызывать эту функцию как обычно, только нужно передавать аргументы нужных типов: 

dp = (ctypes.c_longlong * DP_SIZE)(*(-1 for _ in range(DP_SIZE)))
p10 = (ctypes.c_longlong * DIGITS)(*(10 ** i for i in range(DIGITS)))
 
for input_str in token_generator:
    N = len(input_str)
    input_digits = (ctypes.c_int * N)(*(int(ch) for ch in input_str))
 
    print(func(0, 0, 0, input_digits, N, copy.copy(dp), p10))

Теперь о том как получить нужный машинный код и как вообще выбрать что компилировать.

Наши возможности в том что мы можем запустить довольно ограничены — мы не можем запустить что-либо что использует какие-либо библиотеки, потому что мы загружаем не «честный ELF», в котором можно подгружать библиотеки, делать релокации и многое другое, а только набор машинных инструкций. Это значит что мы не можем использовать ничего из libc — то есть без ввода/вывода, динамического выделения памяти, ничего из стандартной библиотеки плюсов — то есть без каких-либо структур данных сложнее статического массива.

Поэтому идеальный кандидат — функция calculate из оригинального кода на питоне. Она как раз использует только массивы фиксированного размера и простые операции: 

def calculate(i, taken, ls):
    """
    i — индекс цифры
    taken — встречали ли простые цифры раньше
    ls — в текущем индексе можно делать полный перебор
    """
    global input_digits
    global dp
    global N
 
    limit = 9
 
    if not ls:
        limit = input_digits[i]
 
    res = 0
 
    for x in range(limit + 1):
        newtaken = taken or (x == 2) or (x == 3) or (x == 5) or (x == 7)
        newi = i + 1
 
        if newi == N:
            ret = newtaken
        else:
            newls = ls or (x != limit)
 
            if newls and newtaken:
                ret = p10[N - newi]
            else:
                cached = dp[newtaken][newls][newi]
 
                if cached != -1:
                    ret = cached
                else:
                    ret = calculate(newi, newtaken, newls)
 
        res += ret
 
    dp[taken][ls][i] = res
 
    return res

API ctypes позволяет нам запускать сишные функции — поэтому ее и напишем: 

// file: inline.c
# include <stdint.h>
 
int64_t calculate(int i, int taken, int ls, int *input_digits, int N, int64_t *dp, int64_t *p10) {
    int limit = 9;
 
    if (!ls) {
        limit = input_digits[i];
    }
 
    int64_t res = 0;
 
    for (int x = 0; x <= limit; ++x) {
        int new_taken = taken || (x == 2) || (x == 3) || (x == 5) || (x == 7);
        int new_i = i + 1;
        int64_t ret;
 
        if (new_i == N) {
            ret = new_taken;
        } else {
            int new_ls = ls || (x != limit);
 
            if (new_ls && new_taken) {
                ret = p10[N - new_i];
            } else {
                int64_t cached = dp[4 * new_i + 2 * new_taken + new_ls];
 
                if (cached != -1) {
                    ret = cached;
                } else {
                    ret = calculate(new_i, new_taken, new_ls, input_digits, N, dp, p10);
                }
            }
        }
 
        res += ret;
    }
 
    dp[4 * i + 2 * taken + ls] = res;
 
    return res;
}

(глобальные переменные мы создаем на стороне питона и передаем как аргументы, также мы преобразовали многомерный массив dp в одномерный, чтобы не париться с указателями)

Дальше нам нужно это скомпилировать, и нужно передать некоторые нестандарные флаги. Обычно исполнение ELF начинается не с main, а с функции _start, которая вызывает функцию __libc_start_main из libc, которая подгружает переменные окружения, argv и многое другое, а только потом запускает main. Нам ничего такого не нужно, поэтому мы это отключаем с помощью флага -nostartfiles, и к тому же без этого компилятор ожидал бы от нас функцию main, которую мы писать не хотим. Также можем добавить -nolibc чтобы не было соблазна вызывать функции оттуда, хотя на результат это не повлияет. И конечно -O3 чтобы получить все оптимизации что есть. 

$ gcc inline.c -nostartfiles -nolibc -o inline -O3

Можем проверить что в секции .text у нас лежит одна единственная функция (-d — вывод дизассемблера секции с кодом, -M intel — чтобы получить вывод в намного более приятном интеловском синтаксисе, а не в AT&T): 

$ objdump -d -M intel inline
 
inline: file format elf64-x86-64
 
 
Disassembly of section .text:
 
0000000000001000 <calculate>:
    1000:       41 57                   push   r15
    1002:       41 89 f7                mov    r15d,esi
    1005:       41 56                   push   r14
    1007:       41 89 fe                mov    r14d,edi
    100a:       41 55                   push   r13
    100c:       41 89 d5                mov    r13d,edx
    100f:       41 54                   push   r12
    1011:       55                      push   rbp
    1012:       53                      push   rbx
    1013:       48 83 ec 38             sub    rsp,0x38
    1017:       85 d2                   test   edx,edx
    1019:       75 35                   jne    1050 <calculate+0x50>
    101b:       48 63 c7                movsxd rax,edi
    101e:       45 31 e4                xor    r12d,r12d
    1021:       8b 2c 81                mov    ebp,DWORD PTR [rcx+rax*4]
    1024:       85 ed                   test   ebp,ebp
    1026:       79 2d                   jns    1055 <calculate+0x55>
    1028:       43 8d 04 77             lea    eax,[r15+r14*2]
    102c:       41 8d 44 45 00          lea    eax,[r13+rax*2+0x0]
    ...
    ...

Также стоит заметить что наш код не использует никаких глобальных переменных, а значит нам нужна только секция .text из ELF. И еще все инструкции jmp и call используют относительные оффсеты для прыжков, поэтому наш код может быть загружен по любому адресу памяти, что нам и нужно, так как мы не можем полностью контроллировать какой адрес вернет mmap.

Нам осталось сдампить байты нашей функции в отдельный файл (-O binary = вывести сырые байты, -j .text = работать с секцией .text): 

$ objcopy -O binary -j .text inline inline_bytes

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

from pprint import pprint
 
with open('inline_bytes', 'rb') as f:
     pprint(f.read())

Какой будет вывод: 

(b'AWA\x89\xf7AVA\x89\xfeAUA\x89\xd5ATUSH\x83\xec8\x85\xd2u5Hc\xc7E1'
 b'\xe4\x8b,\x81\x85\xedy-C\x8d\x04wA\x8dDE\x00H\x98M\x89$\xc1H\x83\xc48L'
 b'\x89\xe0[]A\\A]A^A_\xc3\x0f\x1f\x80\x00\x00\x00\x00\xbd\t\x00\x00\x00A\x8d~'
 b'\x01D\x89\xc0H\x8bt$p)\xf8E\x85\xffH\x98A\x0f\x95\xc2L\x8d\x1c\xc6A9\xf8t'
 b'k\x8d\x04?1\xdbE1\xe4\x89D$\x08\x83\xfb\x02t\x19E\x84\xd2u\x14\x83'
 b'\xfb\x07\x0f\x87|\x00\x00\x00\xb8\xa8\x00\x00\x00H\x0f\xa3\xd8sq9\xddu51'
 b'\xd2\xbe\x01\x00\x00\x00E\x85\xedu)\x8bD$\x08\x01\xf0\x8d\x04BH\x98I\x8b'
 b'\x04\xc1H\x83\xf8\xfftdI\x01\xc4\x83\xc3\x019\xdd}\xb3\xe9U\xff\xff\xff\x0f'
 b'\x1fD\x00\x00M\x03#\xeb\xea\x0f\x1f\x001\xc0E1\xe4\xba\xa8\x00'
 b'\x00\x00\x83\xf8\x02t\x10E\x84\xd2u\x0b\x83\xf8\x07w\nH\x0f\xa3\xc2s\x04I'
 b'\x83\xc4\x01\x83\xc0\x019\xc5}\xe0\xe9\x19\xff\xff\xff\x909\xdd\x0f\x95'
 b'\xc2E\x85\xed\x0f\x95\xc01\xf6\t\xc2\x0f\xb6\xd2\xeb\x8b\x0f\x1f@\x00D\x88T$'
 b'/H\x83\xec\x08L\x89\\$(\xfft$xL\x89L$(D\x89D$8H\x89L$ \x89|$\x1c\xe8\xae\xfe'
 b'\xff\xffI\x01\xc4XZ\x8b|$\x0cH\x8bL$\x10D\x8bD$(L\x8bL$\x18L\x8b\\$ D'
 b'\x0f\xb6T$/\xe9M\xff\xff\xff')

И это нужно скопировать, чтобы можно было в codechef послать только один файл: 

func_bytes = (b'AWA\x89\xf7AVA\x89\xfeAUA\x89\xd5ATUSH\x83\xec8\x85\xd2u5Hc\xc7E1'
              b'\xe4\x8b,\x81\x85\xedy-C\x8d\x04wA\x8dDE\x00H\x98M\x89$\xc1H\x83\xc48L'
              b'\x89\xe0[]A\\A]A^A_\xc3\x0f\x1f\x80\x00\x00\x00\x00\xbd\t\x00\x00\x00A\x8d~'
              b'\x01D\x89\xc0H\x8bt$p)\xf8E\x85\xffH\x98A\x0f\x95\xc2L\x8d\x1c\xc6A9\xf8t'
              b'k\x8d\x04?1\xdbE1\xe4\x89D$\x08\x83\xfb\x02t\x19E\x84\xd2u\x14\x83'
              b'\xfb\x07\x0f\x87|\x00\x00\x00\xb8\xa8\x00\x00\x00H\x0f\xa3\xd8sq9\xddu51'
              b'\xd2\xbe\x01\x00\x00\x00E\x85\xedu)\x8bD$\x08\x01\xf0\x8d\x04BH\x98I\x8b'
              b'\x04\xc1H\x83\xf8\xfftdI\x01\xc4\x83\xc3\x019\xdd}\xb3\xe9U\xff\xff\xff\x0f'
              b'\x1fD\x00\x00M\x03#\xeb\xea\x0f\x1f\x001\xc0E1\xe4\xba\xa8\x00'
              b'\x00\x00\x83\xf8\x02t\x10E\x84\xd2u\x0b\x83\xf8\x07w\nH\x0f\xa3\xc2s\x04I'
              b'\x83\xc4\x01\x83\xc0\x019\xc5}\xe0\xe9\x19\xff\xff\xff\x909\xdd\x0f\x95'
              b'\xc2E\x85\xed\x0f\x95\xc01\xf6\t\xc2\x0f\xb6\xd2\xeb\x8b\x0f\x1f@\x00D\x88T$'
              b'/H\x83\xec\x08L\x89\\$(\xfft$xL\x89L$(D\x89D$8H\x89L$ \x89|$\x1c\xe8\xae\xfe'
              b'\xff\xffI\x01\xc4XZ\x8b|$\x0cH\x8bL$\x10D\x8bD$(L\x8bL$\x18L\x8b\\$ D'
              b'\x0f\xb6T$/\xe9M\xff\xff\xff')

Вот и все!

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

Python-оптимизация жадного алгоритма из codechef

Продолжим тему Blog:Advanced Algorithms/Python-оптимизация алгоритма динамического программирования из codechef.

Итак, снова решение, которое вроде как работает, но не проходит по времени и жалобы, что питон плохой «Получаю TimeLimit в системе. Мне кажется, это связано с тем, что использую питон и в решении очень много численных операций а так как в питоне используются BigInteger BigFloats, то решение замедляется».

Первая версия

Видимо легкий перебор, три вложенных цикла (три цикла, что-то дофига, причем явно с зависимостью от длины входа — не к добру), что-то считается, что-то отбирается по максимуму…, суммируется, отбирается по минимуму — типичный жадный алгоритм.

Cмотрим описание задачи Codechef/CHEFSTR2, даже сразу переходим по ссылке на разбор и разъяснение.

Разьяснение немного мутное, и мутность там даже зачем-то подмешивается во входные данные (вторая строчка входа не нужна).

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

Вот, нарисовал картинку в терминах исходной версии программы:

Python-оптимизация жадного алгоритма из codechef 2022-05-05 12-39-25 image0.png

Мы можем попробовать делать циклы из подстрок разной длины («ind»), повторяющиеся разное число раз «ks», чтобы получилась строка, нужной длины или чуть длиннее (не больше чем на «ind»).

Рассмотрим строку «ABCABCAB».

Если делать цикл из одного символа («ind=1, ks=8»), то на «пути» (красным) надо посчитать частоты символов, выбрать самый частый (пусть он остается), остальные поменять на него — оптимальное жадное решение. Тут можно выбрать «А» или «B» и получить или . Сколько операций переименования-добавления? Это будет «len» символов новой строки с повторами, минус те символы, которых мы не переименуем («ok», три символа «A» или «B»). Будет 5 операций. (Если оставлять «C», то их будет 6, не подоходит).

Если делать цикл из двух символов («ind=2, ks=4»), то у нас уже возникают «красный» и «синий» путь — пути для первого и второго символа, на этих путях должны быть одинаковые символы, они совсем независимы, надо на каждом пути посчитать какой символ наиболее часто встречается, и переименовать все остальные в него.


На красном пути — самый частый → «A», на синем → «B». Значит, на «красном» пути оставим «A», остальных переименуем в него, на «синем» → «B». На обоих путях одинаково число оставляемых символов «ok1=2», «ok2=2» → число операций 

ops = len - ok1 - ok2 = 8 - 2 - 2 = 4


Если делать цикл из трех символов («ind=3, ks=3»), то у нас уже возникают «красный», «синий» и зеленый пути — пути от первого, второго и третьего символа … … обратите внимание, что зеленый путь выходит за пределы исходной строки, т.е. один символ по любому придется добавить, ведь длина зацикленной строки «len = ks*ind = 9» больше длины исходной строки («8»).

На красном пути — самый частый → «A», на синем → «B», на зеленом → «С» Значит, на «красном» пути оставим «A», остальных переименуем в него, на «синем» → «B», на зеленом → «С». 

ops = len - ok1 - ok2 - ok3 = 9 - 3 - 3 - 2 = 1

…

можно продолжать дальше, в разъяснении написано, почему «ind» не обязательно перебирать до исходной длины строки, идея понятна, у меня кончились красивые цвета для путей.

Разумеется, из всех вариантов циклов с разной длинной надо будет выбрать тот, где «ops» — минимально.

Итак, поехали. Пишем генератор тестовой строки 

import random
import string
 
print(''.join((random.choice(string.ascii_letters).lower() for i in range(16000))))
print(1)

генерим «big-sample-04.txt» на 16K символов, берем референсный CPP-код из разъяснения, компилируем. 

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

$ time good < big-sample-04.txt
7671 2

real    0m47.380s
user    0m46.872s
sys     0m0.053s

Работать будем сразу с PyPy3, не будем тащить numpy, какие-нибудь хитрые модули подсчета, и даже не будем использовать Counter из collections, хотя он сюда и напрашивается. 

$ time pypy3 chefstr2.py  < big-sample-04.txt
7671 2

real    0m26.806s
user    0m26.286s
sys     0m0.104s

26.2 секунды.

Вау, забавно. Это решение вроде как копия референсного на CPP, а на PyPy работает быстрее. Но по TL не проходит!

Нет, пока чудес не бывает. Компилим CPP код с оптимизацией 

gcc -o good good.cpp -lstdc++ -O3

и после этого наконец-то сишное решение показывает скорость: 

$ time good < big-sample-04.txt
7671 2

real    0m1.968s
user    0m1.947s
sys     0m0.006s

Итак, правильное решение знаем, можем проверить, есть куда стремится по скорости. Первое, что напрягает — зачем нам тут модуль «math», вещественные числа (ересь! у нас тут честная комбинаторика). Только для того, чтобы округлять вверх? Это можно делать не выходя из целых чисел.


Делаем такие правки и получаем версию работающую за 24.5 — чуть лучше.

Для очистки совести уберем хардкод на 26 символов и прочтем входную строку через sys.readline — 26.6 стало даже чуть хуже, но вроде это более надежный ввод, если запускать на серверах кодечифа.

Что еще напрягает? Ну вот зачем такие глубокие косвенности: 

 frequency[symbols[(input_str[j])]]

Пора подумать внимательно, зачем нам так много нужно вложенных циклов.

Пробуем загрузить решение в СС → увы, TL

Ночь, хочеться спать.... и тут оживают Дьявольские Советы Черного Программиста → стоит подумать — а в чем практическая задача нашего кода?

Пройти приемочные испытания! Показать себя хорошо на реальных входных данных. Будут ли среди них такие плохие данные, ради которых стоит перестраховываться и увеличивать перебор? (по сути, можно считать, мы исследуем переход к вероятностным алгоритмам или «эффективности для почти всех исходных данных»).

Возможно конечно когда-нибудь в этой задаче дополнят тест-сет, и это решение не пройдет… так что оставим как челлендж на «отл» (при условии, что есть «одна теоретическая задача») →

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

Челледж на «хор» → подобрать входные данные, на которых вот это решение даст неправильный результат.

  1. ↑ Не надо так весело разбрасываясь памятью оптимизировать в продакшне реальных проектов, если действительно этот размен не будет оправдан!

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

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), нет комментариев.

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