Пару недель назад, необходимо было освежить информацию в голове информацию по структурам данных и алгоритмам для собеседования. Первым делом полез на www.coursera.org, где хотел пробежаться по некоторым лекциям курса Алгоритмы, там же были две сводные таблички, которые в процессе изучения курса взял на заметку — отлично помогали запомнить сложность операций. Но, к моему удивлению, материалы пройденного курса стали недоступны. Быстрое гугление, в надежде, что кто-нибудь выложил лекции на торрентах, к сожалению, не дало результатов. В итоге, я нашел полную коллекцию слайдов по данному курсу. Спешу поделиться. Самое главное, что взял из этих слайдов, — это вышеупомянутые сводные таблички. Думаю многим пригодится.
@Dima_16read-only
User
И еще раз о GIL в Python
9 min
Предисловие
Область, в которой мне повезло работать, называется вычислительная электрофизиология сердца. Физиология сердечной деятельности определяется электрическими процессами, происходящими на уровне отдельных клеток миокарда. Эти электрические процессы создают электрическое поле, которое достаточно легко измерить. Более того оно очень неплохо описывается в рамках математических моделей электростатики. Тут и возникает уникальная возможность строго математически описать работу сердца, а значит — и усовершенствовать методы лечения многих сердечных заболеваний.
За время работы в этой области у меня накопился некоторый опыт использования различных вычислительных технологий. На некоторые вопросы, которые могут быть интересны не только мне, я постараюсь отвечать в рамках этой публикации.
Учимся писать многопоточные и многопроцессные приложения на Python
6 min
Recovery Mode
Эта статья не для матёрых укротителей Python’а, для которых распутать этот клубок змей — детская забава, а скорее поверхностный обзор многопоточных возможностей для недавно подсевших на питон. К сожалению по теме многопоточности в Python не так уж много материала на русском языке, а питонеры, которые ничего не слышали, например, про GIL, мне стали попадаться с завидной регулярностью. В этой статье я постараюсь описать самые основные возможности многопоточного питона, расскажу что же такое GIL и как с ним (или без него) жить и многое другое.
Параллельное программирование в Python при помощи multiprocessing и shared array
6 min
Введение.
Python замечательный язык. Связка Python + NumPy + Matplotlib, на мой взгляд, сейчас одна из лучших для научных расчётов и быстрого прототипирования алгоритмов. Но у каждого инструмента есть свои светлые и тёмные стороны. Одной из самых дискутируемых особенностей Python является GIL – Global Interpreter Lock. Я бы отнёс эту особенность к тёмной стороне инструмента. Хотя многие со мной не согласятся.
Если кратко, то GIL не позволяет в одном интерпретаторе Python эффективно использовать больше одного потока. Защитники GIL утверждают, что однопоточные программы при наличии GIL работают намного эффективнее. Но наличие GIL означает, что параллельные вычисления с использованием множества потоков и общей памяти невозможны. А это достаточно сильное ограничения в современном многоядерном мире.
Один из способов преодоления GIL при помощи потоков на C++ был недавно рассмотрен в статье: Использование Python в многопоточном приложении на C++. Я же хочу рассмотреть другой способ преодоления ограничений GIL, основанный на multiprocessing и shared array. На мой взгляд, этот способ позволяет достаточно просто и эффективно использовать процессы и разделяемую память для прозрачного параллельного программирования в стиле множества потоков и общей памяти.
Почему в Петербурге так сложно построить карьеру VP of engineering
7 min
Привет, Хабр! Меня зовут Святослав Кулаков, я VP of Engineering в Aurea Software. Вся моя жизнь прошла в Питере: я родился и вырос на улице Союза Печатников напротив Мариинского театра, учился во второй гимназии с углублённым изучением английского языка и физмата, поступил в Университет аэрокосмического приборостроения (ГУАП). После учёбы я работал в нескольких софтверных компаниях в России и США, но в итоге всё вернулся в Санкт-Петербург и оставался тут даже когда это казалось верной дорогой к карьерному болоту.
На основании своего личного опыта я расскажу о том, почему многим IT-специалистам нереально найти в Санкт-Петербурге работу по своему уровню, как работает механизм перетягивания лучших специалистов — как минимум, в Москву, а то и сразу в США или другие страны. И о том, как мне всё-таки удалось найти в родном городе свою лучшую работу на данный момент. Но обо всём по порядку.
Моя трудовая биография началась с позиции Java-разработчика в небольшой софтверной компании в 1999 году. За следующие 9 лет я продвинулся по карьерной лестнице до позиции Эккаунт Менеджера, где мне подчинялось более 100 человек. Кризис 2008 года сбил нас на взлёте, и моей следующей записью в трудовой стала должность Lead IT Process Manager в московском отделении Deutsche Bank. Полтора года спустя мне поступило заманчивое предложение из США: консультировать бизнес-клиентов компании Grid Dynamics в вопросах оптимизации процессов разработки.
На основании своего личного опыта я расскажу о том, почему многим IT-специалистам нереально найти в Санкт-Петербурге работу по своему уровню, как работает механизм перетягивания лучших специалистов — как минимум, в Москву, а то и сразу в США или другие страны. И о том, как мне всё-таки удалось найти в родном городе свою лучшую работу на данный момент. Но обо всём по порядку.
Из Санкт-Петербурга в Санкт-Петербург через Санкт-Петербург
Моя трудовая биография началась с позиции Java-разработчика в небольшой софтверной компании в 1999 году. За следующие 9 лет я продвинулся по карьерной лестнице до позиции Эккаунт Менеджера, где мне подчинялось более 100 человек. Кризис 2008 года сбил нас на взлёте, и моей следующей записью в трудовой стала должность Lead IT Process Manager в московском отделении Deutsche Bank. Полтора года спустя мне поступило заманчивое предложение из США: консультировать бизнес-клиентов компании Grid Dynamics в вопросах оптимизации процессов разработки.
Визуальное программирование на языке ДРАКОН
15 min
Визуальное и текстовое программирование
Что является в программе движущей силой? Что порождает полезный результат? Конечно, алгоритм. Алгоритм создает тот эффект, ради которого написана программа. Алгоритм работает не один. Он работает совместно со структурами данных. Но именно алгоритмы составляют наибольшую часть программы.
Исторически сложилось, что алгоритмы в программах записываются в виде исходных текстов. Почти никто не ставит под сомнение, что текст — это и есть лучшее средство представления алгоритмов. Алгоритм кодируется внутри функций на языке программирования, например, C или JavaScript. Для тех, кто хочет разобраться в алгоритме с высоты птичьего полёта, предусмотрен псевдокод. Однако с текстом есть серьезные проблемы. Дело в том, что человек не оптимизирован под сплошной текст. Человек оптимизирован на восприятие графики. Текст — это относительно новое изобретение, а вот графическую информацию организмы обрабатывают уже миллионы лет.
Исходя из этого, логично было бы составлять алгоритмы в графическом виде. Посмотрите на инженеров. Они повсеместно используют чертежи. Чем же программисты хуже? Они тоже могли бы составлять чертежи алгоритмов. Некоторые здесь возразят: визуальное программирование якобы неэффективно. UML неудобен, а в блок-схемах легко запутаться. Уж лучше программировать традиционным способом — текстом. В структурном программировании есть хотя бы структура, и она обеспечивает порядок и единообразие. А кроме того, рисовать диаграммы долго и трудно. Печатать быстрее, чем рисовать.
Так что же, программисты обречены всю жизнь работать только с текстом?
Возможно, не всё так плохо. Существуют визуальные языки для представления алгоритмов, в которых тоже есть порядок и структура, например ДРАКОН, BPMN и LML Action Diagrams. Здесь мы рассмотрим визуальный алгоритмический язык ДРАКОН.
Как программировать на языке ДРАКОН
ДРАКОН не является самостоятельным языком программирования. Он работает в паре с
Комбинаторные алгоритмы: индекс сочетания, индекс разбиения на подмножества
5 min
Короткое предисловие
Комбинаторные алгоритмы применяются достаточно часто. В интернете можно найти много информации касательно комбинаторных алгоритмов. Однако русскоязычный интернет, в основном, выдает простейшие задачи сплошного перебора (генерации) комбинаторных объектов в цикле. Например:
Пример
// Сочетания по 3 из 52
for (int i1 = 0; i1 < 50; ++i1)
for (int i2 = i1+1; i2 < 51; ++i2)
for (int i3 = i2+1; i3 < 52; ++i3)
// ...
Индекс сочетания
Каждому сочетанию, перестановке, размещению и другим комбинаторным объектам можно сопоставить индекс — это номер, в котором он появляется при переборе данным алгоритмом.
Здесь мы рассмотрим более сложную задачу, решения которой в рунете я не нашел (впрочем, приведу одну ссылку, но та формула явно неверная) — исходя из самого сочетания (в данном случае набора трех чисел) найти его индекс.
Заочное обучение в ШАД Яндекса: 570 замечательных часов моей жизни
6 min
Два года назад на меня сильное впечатление произвела хабрастатья «Стивен Вольфрам проанализировал свою жизнь». К тому времени я уже года два записывал в Google-календаре, что и когда я делал, но к тому моменту я не задумывался, о том, что можно сделать с этой информацией. После прочтения той статьи, я понял: эту информацию можно анализировать! Сейчас я могу посчитать сколько раз мы с друзьями собирались играть в баскетбол за эти годы, сколько часов я провёл в больнице и т. п.На этой неделе я сделал последнюю домашнюю работу в ШАД и решил посчитать сколько времени у меня ушло на обучение, сколько я в среднем тратил в неделю, сколько строчек кода я написал и т. д. Построил несколько графиков и гистограмм, показал их друзьям и понял, что, возможно, такая информация будет интересна кому-либо ещё. Так что если вы хотите узнать сколько страниц отчётов было написано, насколько верна оценка нагрузки в ШАД в 15–20 часов в неделю, а также моё субъективное мнение о курсах в ШАД, то добро пожаловать под хабракат.
Пятнашки на LibCanvas
3 min
Недавно на Хабре была статья про пятнашки на Canvas.Отличная статья, уверен, новички найдут в ней много полезного. К сожалению, в комментариях высказались о немного завышеном потреблении процессора.
Это не от недостатка технологии, а от недостаточного опыта и удобных инструментов.
В этом топике я расскажу, как, при помощи LibCanvas, сделать эту игру совершенно нетребовательной к процессору и отлично выглядящей.
Canvas: пятнадцать минут на пятнашки
4 min
Tutorial
CANVAS шаг за шагом:В детстве у меня были пятнашки, я думаю все знают эту головоломку. Двигать пятнашки в пластиковой коробочке до получения заветного порядка цифр было очень интересным занятием. Вот и совсем недавно, в порядке спортивного интереса, я написал для себя пятнашки в которые бы можно было играть не только из окна браузера, но и с смартфона под управлением ОС Андроид или iOS.
Основы Python — кратко. Часть 4. Генераторы списков
3 min
List comprehensions
Продолжим наш цикл уроков. Добрый день.
Генерация списков
Генерация списков (не знаю как адекватно перевести на русский list comprehensions) — яркий пример «синтаксического сахара». То есть конструкции, без которой легко можно обойтись, но с ней намного лучше :) Генераторы списков, как это не странно, предназначены для удобной обработки списков, к которой можно отнести и создание новых списков, и модификацию существующих.
Допустим, нам необходимо получить список нечетных чисел, не превышающих 25.
В принципе, только познакомившись с работой команды xrange решить эту проблему несложно.
В общем-то, полученный результат — целиком нас устраивает всем, кроме длинной записи. тут-то на помощь и придет наш «сахарок». В самом простом виде, он обычно
Продолжим наш цикл уроков. Добрый день.
Генерация списков
Генерация списков (не знаю как адекватно перевести на русский list comprehensions) — яркий пример «синтаксического сахара». То есть конструкции, без которой легко можно обойтись, но с ней намного лучше :) Генераторы списков, как это не странно, предназначены для удобной обработки списков, к которой можно отнести и создание новых списков, и модификацию существующих.
Допустим, нам необходимо получить список нечетных чисел, не превышающих 25.
В принципе, только познакомившись с работой команды xrange решить эту проблему несложно.
>>> res = [] >>> for x in xrange(1, 25, 2): ... res.append(x) ... >>> print res
В общем-то, полученный результат — целиком нас устраивает всем, кроме длинной записи. тут-то на помощь и придет наш «сахарок». В самом простом виде, он обычно
Python: сортировка списков методом .sort() с ключом — простыми словами
2 min
Поводом опубликовать пост стало то, что при детальном изучении списков (массивов) в Python я не смог найти в сети ни одного простого описания метода сортировки элементов с использованием ключа: list.sort(key=...).
Может быть, конечно, это мне так не повезло и я долго понимаю простые для всех вещи, однако я думаю, что приведенная ниже информация будет весьма полезна таким же начинающим питонистам, как и я сам.
Может быть, конечно, это мне так не повезло и я долго понимаю простые для всех вещи, однако я думаю, что приведенная ниже информация будет весьма полезна таким же начинающим питонистам, как и я сам.
Сортировки: key vs cmp
3 min
При сортирование в Python 2 есть как минимум два способа это сортирование «настроить»: это параметры
key и cmp. Первый был добавлен только в Python 2.4, а второй был удален в Python 3.0. Эти факты как-бы наводят на мысль что key действительно лучше. Кто с этим не согласен или не уверен — прошу под кат.
Python: вещи, которых вы могли не знать
8 min
Python — красивый и местами загадочный язык. И даже зная его весьма неплохо, рано или поздно находишь для себя нечто такое, что раньше не использовал. Этот пост отражает некоторые детали языка, на которые многие не обращают внимание. Сразу скажу: многие примеры являются непрактичными, но, оттого, не менее интересными. Так же, многие примеры демонстрируют unpythonic стиль, но я и не претендую на новые стандарты — я просто хочу показать, что можно делать вот так.
Метаклассы в Python
10 min
Translation
Как сказал один из пользователей StackOverflow, «using SO is like doing lookups with a hashtable instead of a linked list». Мы снова обращаемся к этому замечательному ресурсу, на котором попадаются чрезвычайно подробные и понятные ответы на самые различные вопросы.
В этот раз мы обсудим, что такое метаклассы, как, где и зачем их использовать, а также почему обычно этого делать не стоит.
В этот раз мы обсудим, что такое метаклассы, как, где и зачем их использовать, а также почему обычно этого делать не стоит.
Чемпионаты по программированию и не только
9 min
Рассказывая о конференциях, форумах, съездах и лан-пати, нельзя обделить вниманием хакерские и программерские чемпионаты. А ведь их немало, за призовые места там платят неплохие деньги, да и в целом участие в подобных мероприятиях — это очень полезный опыт.
Открыт набор в школу Яндекса
1 min
Около недели назад Яндекс объявил о наборе на новый учебный год в свою школу. Обучение ведётся по двум направлениям: анализ данных и computer science. В качестве вступительного задания абитуриенту школы предлагается рассказать о себе и решить несколько несложных задачек по математическому анализу, теории вероятностей и программированию. Решения можно отправлять до 15 августа.
Кроме того во время обучения в школе можно получить диплом высшей школы экономики, а после — пройти стажировку в Яндексе.
Обучение бесплатное, очно-заочное (вечернее), занятия проходят по вечерам, примерно с 18 до 20. Судя по отзывам моих знакомых, учиться интересно и местами даже сложно.
На сайте ничего не сказано о возрастном ограничении, так что дерзайте!
UPD: после заочной анкеты проводится очное собеседование, на котором вопросы могут быть сложнее. kronos о собеседовании.
Кроме того во время обучения в школе можно получить диплом высшей школы экономики, а после — пройти стажировку в Яндексе.
Обучение бесплатное, очно-заочное (вечернее), занятия проходят по вечерам, примерно с 18 до 20. Судя по отзывам моих знакомых, учиться интересно и местами даже сложно.
На сайте ничего не сказано о возрастном ограничении, так что дерзайте!
UPD: после заочной анкеты проводится очное собеседование, на котором вопросы могут быть сложнее. kronos о собеседовании.
Открылся новый набор в Школу анализа данных Яндекса
3 min
На днях мы открыли новый набор в Школу анализа данных. Чтобы стать её студентом, нужно ответить на вопросы в тесте, сдать экзамены и пройти собеседование. Занятия, как всегда, будут проходить в офисе Яндекса в Москве, а также в Екатеринбурге, Киеве и Минске. В Питере у ШАД есть отделение в Computer Science Center. Если вы живёте в других городах, то можете учиться у нас заочно: общаться с преподавателями по электронной почте и смотреть видеолекции. Обучение в Школе бесплатное.
В ШАД преподают ведущие российские ученые — и те, кто живет в России, и те, кто работает за рубежом. Например, теорию машинного обучения ведёт Алексей Червоненкис, профессор Лондонского университета и один из создателей отечественной школы анализа данных. Автор курса по анализу данных и научный руководитель ШАД — профессор Rutgers University Илья Мучник, который когда-то был научным руководителем Аркадия Воложа.
Интерполяция данных: соединяем точки так, чтобы было красиво
7 min
Как построить график по n точкам? Самое простое — отметить их маркерами на координатной сетке. Однако для наглядности их хочется соединить, чтобы получить легко читаемую линию. Соединять точки проще всего отрезками прямых. Но график-ломаная читается довольно тяжело: взгляд цепляется за углы, а не скользит вдоль линии. Да и выглядят изломы не очень красиво. Получается, что кроме ломаных нужно уметь строить и кривые. Однако тут нужно быть осторожным, чтобы не получилось вот такого:
Линейная алгебра: пробный заезд
7 min
Привет, Хабр!
Аналит, линейка, линал — эти слова ассоциируются скорее с фразой «сдать и забыть», а не с тем, для чего на самом деле нужен замечательный раздел математики под названием линейная алгебра. Давайте попробуем посмотреть на него с разных сторон и разберемся, что же в нем хорошего и почему он так полезен в приложениях.
Часто первое знакомство с линейной алгеброй выглядит как-то так:
Не очень вдохновляет, правда? Сразу возникает два вопроса: откуда это все взялось и зачем оно нужно.
Когда я занимался вычислительной гидродинамикой (CFD), один из коллег говорил: «Мы не решаем уравнения Навье-Стокса. Мы обращаем матрицы.» И действительно, линейная алгебра — «рабочая лошадка» вычислительной математики:
Аналит, линейка, линал — эти слова ассоциируются скорее с фразой «сдать и забыть», а не с тем, для чего на самом деле нужен замечательный раздел математики под названием линейная алгебра. Давайте попробуем посмотреть на него с разных сторон и разберемся, что же в нем хорошего и почему он так полезен в приложениях.
Часто первое знакомство с линейной алгеброй выглядит как-то так:
Не очень вдохновляет, правда? Сразу возникает два вопроса: откуда это все взялось и зачем оно нужно.
Начнем с практики
Когда я занимался вычислительной гидродинамикой (CFD), один из коллег говорил: «Мы не решаем уравнения Навье-Стокса. Мы обращаем матрицы.» И действительно, линейная алгебра — «рабочая лошадка» вычислительной математики: