Category: наука

Category was added automatically. Read all entries about "наука".

Доклад про многопоточные алгоритмы на BitByte 2014

Через неделю после предыдущего доклада в Москве я выступил с его расширенной версией в Санкт-Петербурге, на конференции BitByte 2014. В формате "мастер класс" у меня было полтора часа на выступление. Сильно больше материала представить у меня не получилось, но, в дополнение к основным теоритическим предпосылкам, я успел затронуть вопрос построения линеаризуемых алгоритмов и основы теории алгоритмов без блокировки.

Моей задачей было заинтересовать слушателей теорией параллельного программирования и, судя по некоторым отзывам, цель была достигнута. Несколько человек, подошедших ко мне после выступления, явно хотели знать больше, и, я надеюсь, займутся самообразованием в этой области. А для сотрудников Devexperts я прочитаю в этом году целый курс из 8 лекций, в котором будет весь этот материал и много, много еще всего. Большую часть материала я возьму из курса лекций, который я читаю в ИТМО, но будет и много нового. Я подготовлю отдельную лекцию исключительно про JMM, где я подробно разберу структуру JMM и научу коллег доказывать и анализировать корректность кода по JMM. Несколько лекций будет посвящено практическим алгоритмам. В плане стоит отдельная лекция только про очереди и отдельная лекция только про хеш-таблицы. Там я не только расскажу и объясню все фундаментальные "классические" многопоточные построения на списках, но и современные достижения в области алгоритмов на массивах которые, как известно и о чем я уже писал, существенно превосходят списочные структуры по производительности на практике.

Collapse )

Теория параллельного программирования для программистов практиков

В этот четверг, 12 июля 2012 года, в 19:00 в большом конференц-зале бизнес-центра "Воронцов" (Санкт-Петербург, там же где офис Devexperts) в рамках сообщества CodeFreeze я прочитаю доклад на тему "Теория параллельного программирования для программистов практиков". Доклад рассчитан на программистов, которые уже имеют практический опыт написания параллельного кода (прочтение книги “Java Concurrency in Practice” или подобной это большой плюс) и хотели бы узнать теоретические основы, на которых строится практика параллельного программирования.

Наверное, почти все из вас проходили в вузе теоретические основы последовательных вычислений (конечные автоматы, регистровые машины, машины Тьюринга и т.п.), а вот аналогичные конструкции для параллельных вычислений, к сожалению, обойдены вниманием в большинстве вузов. Я расскажу о моделях параллельных вычислений, о разделяемых объектах и их консенсусных числах, об отношении "произошло до" и о линеаризуемости, о разных типах синхронизации без ожидания и об универсальной конструкции, о проблеме ABA и о том, чем помогает GC. Кроме того, я объясню, почему все стандартные "Concurrent" алгоритмы основаны на списках, а все алгоритмы на массивах исключительно "Blocking".

Конечно, в рамках одного доклада нельзя рассказать целый курс. Однако, я многое упростил, убрал доказательства и отобрал только те факты и концепции, которые будут полезны программистам-практикам. Я дам общий обзор различных перспективных направлений для тех, кто захочет углубиться в изучение теории параллельного программирования самостоятельно.

UPDATE: Слайды Collapse )

Теория на практике или хеш-таблицы часть 4

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

Collapse )

Искусство многопроцессорного программирования

В 2005 году я начал преподавать в ИТМО курс параллельного и распределенного программирования. В начале мне порой даже было сложно объяснить важность этого курса. Популярность набирало программирование под мобильные платформы, и на вопрос "зачем мне это нужно — я буду программировать приложения под iPhone" я мог возразить только что-то типа "скоро и мобильные устройства станут многоядерными — уже есть отдельные образцы" и приводил графики, показывающие конец эры экспоненциального роста частоты и вычислительной мощности отдельного процессорного ядра. А сейчас двуядерные мобильные процессоры используются повсеместно и четырехъядерные на подходе, так что всё понятно и без графиков даже тем, кто не пишет код для сложных систем работающих под большой нагрузкой, как это мы делаем в Devexperts.

Collapse )

[topcoder SRM 250] В меру сложно и разнообразно

В общем и целом, topcoder SRM 250 оказался интересным и в меру сложным ;) А сдал решение последней задачки буквально за 5 минут до окончания. Чудом решив все задачи правильно я оказался на 6-м месте в общей таблице результатов, что сильно подняло мой рейтинг (до 2215).

Первая задачка была простой, но с подковыркой. Я был уверен, что решение в double-ах пройдет, но, признаюсь, не сильно напрягал голову когда выбирал 1e-9 в качестве эпсилона. К счастью, этого было достаточно.

Над второй задачкой пришлось подумать. Быстро отбросив идеи про жадный алгоритм (не зря я перечитывал теорию матроидов) я придуман динамический алгоритм и приступил к написанию кода. Однако трудность меня подстерегала при вводе данных. Я стал дико тупить и минут 5 не мог сообразить что означает AM/PM нотация для времени. Пытался тщетно сообразить что же именно значит 12:35PM и 12:35AM. Эти потуги происходили когда я уже набил код для разбора строчек вида hh:mmaa самостоятельно. У меня уже было целое число от 1 до 12 обозначающее час, целое число от 0 до 59 обозначающее минуты и флаг AM/PM. Уверенность что я что-то понял у меня так и не появилась, и я удалил написанный код парсинга, поручив всю работу стандартным классам в Java: calendar.setDate(new SimpleDateFormat(“hh:mmaa”).parse(s)). А дальше – calendar.get(Calendar.HOUR_OF_DAY) и calendar.get(Calendar.MINUTE).

Третья задачка была чистой геометрией. Здесь всё было в технике и аккуратности кодирования. На первом этапе надо было найти все точки результирующего многоугольника. Написав этот код, мне пришлось его отлаживать (было несколько опечаток в математике пересечений). Когда отладка была закончена, и у меня был правильный список точек, я просто скопировал свое решение задачки из предыдущего соревнования, которое находит площадь выпуклой оболочки. В первой части решения (ввод данных и нахождение пересечений) я слишком активно пользовался cut-and-paste-ом. Если бы я программировал более структурно (завел бы класс Polygon с методами чтения и проверки точки на принадлежность), то это бы сильно упростило и ускорило бы процесс отладки.