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

Барбара Лисков изобрела архитектуру, лежащую в основе современных программ. Создание чего-либо достаточно мощного это искусство.

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

Но к концу 1960-х годов достижения в области вычислительной мощности превзошли возможности программистов. Многие специалисты по информатике создавали программы, не задумываясь о дизайне. Они писали длинные, бессвязные алгоритмы, пронизанные операторами goto машинными инструкциями для перехода к другой части программы, если выполняется определенное условие. Первые программисты полагались на эти операторы, чтобы исправлять непредвиденные последствия своего кода, но они делали программы трудными для чтения, непредсказуемыми и даже опасными. Плохое программное обеспечение в конечном итоге стоило людям жизни, например, когда радиационная установка Therac-25, управляемая компьютером, стала причиной серьезных передозировок радиацией у больных онкологией.

В те времена, когда Барбара Лисков получала докторскую степень по информатике в Стэнфордском университете в 1968 году, она завидовала инженерам-электрикам, потому что они работали с аппаратным обеспечением, соединенным проводами. Эта архитектура, естественно, позволяла им дробить задачи и разделять их на модули подход, который давал им больше контроля, поскольку позволял им независимо рассуждать о дискретных компонентах.

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

Там предо мной были серьезные задачи. Все, что мне нужно было сделать, это без промедления начать решать их.

Барбара Лисков

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

Когда она была еще молодым профессором Массачусетского технологического института, она возглавляла команду, создавшую первый язык программирования, который не полагался на операторы goto. Язык CLU (сокращение от cluster) основывался на изобретенном ею подходе абстракции данных который организовывал код в модули. Все используемые сегодня важные языки программирования, включая Java, C++ и C#, являются потомками CLU.

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

Журнал Quanta встретился с Лисков в ее доме после Гейдельбергского форума лауреатов закрытого собрания (исключительно по приглашениям) ученых-информатиков и математиков, получивших самые престижные награды в своих областях. Лисков была приглашен в Гейдельберг, но ей пришлось отменить свое участие за несколько недель до форума по личным причинам. Интервью было сокращено и отредактировано в целях лучшего понимания.

Вы достигли профессионального совершеннолетия во время разработки искусственного интеллекта. Как изменилось представление об искусственном интеллекте и машинном обучении за время вашей карьеры?

Я защитила докторскую диссертацию с Джоном Маккарти в области искусственного интеллекта. Я написала программу для разыгрывания шахматных эндшпилей. Эту тему предложил Джон, потому что я не играла в шахматы. Я прочитала [шахматные] учебники и перевела эти алгоритмы в поле информатики. В то время, вершиной научной мысли было сделать так, чтобы программа вела себя так, как поступал бы человек. Сейчас уже дела обстоят иначе.

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

Искусственный интеллект это скорее прикладная, нежели обособленная дисциплина. Его всегда использовали для чего-то конкретного.

Вас он больше интересовал как отдельная дисциплина?

Честно говоря, в то время искусственный интеллект мало на что был способен. Меня интересовали основополагающие задачи. Вопрос как организовать программное обеспечение? был для меня действительно интересен. В процессе проектирования вы сталкиваетесь с необходимостью выяснить, как вам следует реализовать приложение. Вам нужно организовать код, разбив его на части. В этом помогает абстракция данных. Это очень похоже на доказательство теоремы. Невозможно доказать теорему одним махом. Вместо этого вы придумываете несколько лемм и дробите задачу.

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

Первые компьютеры использовали перфокарты для ввода как программ, так и данных.

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

Если бы у вас была волшебная палочка, и вы могли бы направить развитие информатики вперед, как бы это выглядело?

Я очень переживаю за интернет. У нас целая куча проблем, включая фейковые новости и проблемы с безопасностью. Меня беспокоит разведенная пара, в которой муж публикует клевету на жену, в том числе информацию о том, где она живет. Происходят ужасные вещи. Частично это выросло из настроений 80-х. В то время у нас было 15 университетов и пара государственных лабораторий, соединенных интернетом. Мы все были друзьями. Позиция заключалась в том, что сайты не должны нести ответственности за контент. Это задушит их развитие. Вы можете наблюдать, что такое отношение пока сохраняется.

Было ли такое мышление следствием академической свободы?

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

Видео: Барбара Лисков говорит о вызовах, с которыми сталкиваются компьютерные науки.

Расскажите мне о своем личном опыте в качестве женщины в информатике.

Меня поощряли хорошо учиться в школе. Не знаю, подбадривала ли меня мама, но она точно не мешала мне и не говорила: О нет, это плохая идея. Я прошла все курсы математики и естествознания, к чему девочек не поощряли. В Беркли я была одной из двух женщин (или даже единственной) в классе из 100 человек. Никто никогда не говорил: Вот это да, дела у тебя идут хорошо, почему бы тебе не поработать со мной? Я не знал, что такое вообще может происходить. Я поступила в аспирантуру Стэнфорда. Когда я закончила учебу, со мной никто не разговаривал о работе. Я заметил, что коллег-мужчин, таких как Радж Редди, который был моим другом, брали на академические должности. Мне такую работу никто не предлагал.

В то время научные руководители трудоустраивали выпускников по контрактам с ведомствами по всей стране.

Да, но мне никто ничего не предлагал. В 90-х я вернулась в Стэнфорд на день факультета. Группа старых профессоров, не осознавая, что они делают, рассуждали о подобном кумовстве (old boy network). Они говорили: О, мой друг сказал мне, что у меня есть хороший молодой парень, которого ты должен нанять. Так обстояли дела. Они не понимали, что тут не так. Они говорили о молодой женщине, которая так преуспела, потому что вышла замуж за профессора! Разве это правильно? У другого коллеги в офисе была пинап-фотография кинозвезды. Я спросил его: Что это за пинап-фотография в твоем офисе? Никакого вразумительного ответа.

Я подала заявление в Массачусетский технологический институт, но меня даже не рассматривали на должность преподавателя. Когда такое происходит, вы думаете: Я недостаточно хороша. Вы ничего не можете с этим поделать. Но также я думала: Информатика - открытая наука. Моя промышленная работа в Mitre была хорошей исследовательской работой. Там я работала над методологией программирования и проводила исследования, которые принесли мне мою первую премию. Затем в 1971 году я выступила с докладом, после которого Корби [Фернандо Корбато] пригласил меня в Массачусетский технологический институт. Меня также пригласили в Беркли. Ситуация менялась.

Тем не менее, правда ли, что когда вы начали работать в Массачусетском технологическом институте, было около 1000 преподавателей, из которых только 10 были женщинами?

Насколько я помню.

Так что прогресс был, но

Раздел IX еще не был законом, но давление нарастало. Президент Массачусетского технологического института Джерри Визнер был источником давления. Давление должно идти сверху. Оно не пузырится снизу. В Массачусетском технологическом институте было несколько выдающихся женщин, которых не было в составе факультета. Примерно тогда нескольких из них неожиданно пригласили войти в состав факультета. Конечно, в математике их никогда не было. В математике с этим дела обстоят очень плохо.

В 2018 году Лисков была награждена премией Computer Pioneer Award в знак признания ее достижений.

Мне кажется, что ни одна научная область не признала какой-либо фундаментальный вклад женщин.

За 10 лет до того, как я возглавила факультет информатики в Массачусетском технологическом институте, департамент нашел только одну женщину достойной предложения работы. Когда я была руководителем [с 2001 по 2004 год], я наняла семь женщин. По сусекам скрести не приходилось. Все три молодые женщины, которых я наняла выдающиеся. Долгое время женщины вообще не рассматривались.

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

Бьюсь об заклад, что да! Был еще один комментарий о котором я никогда не рассказываю в котором говорилось: О, это не она проделал эту работу. [Коллега-мужчина] сделал это вместо нее. Это полная чушь. Я не смотрела комментарии. Мой муж смотрел. Это была пара, о которых он мне поведал. Иногда я выступаю с докладами, на которых мне задают враждебные вопросы (и к этому нужно быть готовым), будь то из-за того, что я женщина, или потому, что люди пытаются сконфузить меня, понимаете

Сконфузить лауреата премии Тьюринга?

Ага! Тогда я не понимала, что некоторые люди в моем отделе поддерживают меня. И к тому времени, когда я начала путешествовать, я была уже хорошо известна. Но вот в чем загадка: почему некоторые женщины способны стойко, упорно продолжать двигаться вперед?

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

Было бы неплохо узнать, как применять этот тефлон. Только проработав достаточное количество времени в Массачусетском технологическом институте, я разрушила в себе блок задавать вопросы публично. Потребовалось много времени, чтобы развить эту уверенность в себе

Это достаточно деликатно. В вашей истории обнаруживается скрытый подтекст: не высовывайся, пока не сможешь по-настоящему стоять прямо, а затем всецело отдайся этому.

Да, возможно, это была моя стратегия. Это, вместе с отсутствием потребности угождать другим людям. Женщины социализированы, чтобы угождать.

Это уже конкретный совет: откажитесь от потребности угождать.

Вы знаете, сейчас дела обстоят не лучше, чем тогда. Может мне повезло. Если бы я вышла замуж сразу после колледжа, я бы, наверное, попала в совершенно другое место.

Вы действительно так думаете? Ваш вклад изменил компьютерные технологии и общество.

Вы знаете, вы просто идете по этому извилистому пути, и кто знает, что будет?

Узнать подробнее о курсе Архитектура и шаблоны проектирования.

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

С детства нас учили, что 0,1 + 0,2 равно 0,3. Однако в загадочном мире вычислений все работает по-другому. Недавно я начал писать код на JavaScript и, читая о типах данных, заметил странное поведение 0,1 + 0,2, не равного 0,3. Я обратился за помощью к Stack Overflow и нашел пару сообщений, которые помогли. Посмотрите ниже:

Проведя много исследований и вычислений, я пришел к выводу, что это не ошибка. Это математика: арифметика с плавающей запятой. Давайте копнем глубже, чтобы понять, что происходит за кулисами.

Постановка задачи: как получилось, что 0,1 + 0,2 = 0,30000000000000004?

Что ж, если вы программировали на таких языках, как Java или C, вы должны знать о различных типах данных, используемых для хранения значений. В предстоящем обсуждении мы будем рассматривать два типа данных: целые числа и числа с плавающей запятой.

Целочисленные типы данных хранят целые числа, а типы данных с плавающей запятой хранят дробные числа.

Прежде чем продолжить, давайте разберемся с одной маленькой концепцией: как числа представлены в вычислительных целях? Очень маленькие и очень большие числа обычно хранятся в экспоненциальном представлении. Они представлены как:

Кроме того, число нормализуется, если оно записано в экспоненциальном представлении с одной ненулевой десятичной цифрой перед десятичной точкой. Например, число 0,0005606 в экспоненциальном представлении и нормализованное будет представлено как:

Significant- это количество значащих цифр, которые не включают нулей, а основание представляет собой используемую базовую систему, которая здесь десятичная (10). Экспонента представляет собой количество мест, на которое необходимо переместить точку счисления влево или вправо для правильного представления.

Теперь есть два способа отображения чисел в арифметике с плавающей запятой: одинарная точность и двойная точность. Одинарная точность использует 32 бита, а двойная точность использует 64 бита для арифметики с плавающей запятой.

В отличие от многих других языков программирования, JavaScript не определяет различные типы числовых типов данных и всегда хранит числа как числа с плавающей запятой двойной точности в соответствии с международным стандартом IEEE 754.

В этом формате числа хранятся в 64 битах, где число (дробь) хранится в битах от 0 до 51, показатель степени - в битах с 52 по 62, а знак - в битах 63.

Давайте представим 0,1 в 64-битном формате в соответствии со стандартом IEEE754.

Первым шагом является преобразование (0,1) основания 10 в его двоичный эквивалент (основание 2).

Для этого мы начнем с умножения 0,1 на 2 и отделим цифру перед десятичной дробью, чтобы получить двоичный эквивалент.

Повторив это для 64 бит, мы собираемся расположить их в порядке возрастания, чтобы получить мантиссу, которую мы собираемся округлить до 52 бит в соответствии со стандартом двойной точности.

Представляя его в научной форме и округляя до первых 52 бит, получим:

Часть мантиссы готова. Теперь для показателя степени мы будем использовать следующий расчет:

Здесь 11 представляет количество битов, которые мы собираемся использовать для 64-битного представления показателя степени, а -4 представляет показатель степени из научной записи.

Окончательное представление числа 0,1:

Точно так же 0.2 будет представлено как:

Добавление двух после того, как экспоненты будут одинаковыми для обоих, даст нам:

В представлении с плавающей запятой это становится:

Это представлено как 0,1 + 0,2.

Это и есть причина получения 0,1 + 0,2 = 0,30000000000000004.

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

Сегодня остановимся на общих темах, а в следущий раз перейдем к специализированным.

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

Fun Fun Function

^{245 тысяч подписчиков}

Заметим сразу, что автор канала приостановил выпуск роликов. Но библиотеку записей, собранную за пять с лишним лет работы, он сохранил. Наибольшее количество просмотров 600k набрала первая часть разбора техник функционального программирования на JavaScript. Из более свежих в лидеры вырвались такие темы как React Hooks (123k) и когнитивно-поведенческая психотерапия (28,5k), ставшая частью длительной серии из нескольких десятков роликов о культуре разработки, карьере в IT, лайфхаках для программистов, продуктивной работе и эмоциональной гигиене.

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

Отличительная черта канала информативность и хорошее чувство юмора ведущего. Благодаря им все публикации в общей сложности набрали более десяти миллионов просмотров. Кстати, загляните и в дружественный проект DevTip (хотя тут апдейты перестали появляться еще раньше).

Art of The Problem

^{70 тысяч подписчиков}

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

Одни из наиболее популярных передач по теме нейронок и глубокого обучения. В последнем видео из этой серии авторы объясняют базовые концепции и математику, задействованную в этой области, с помощью различного рода визуализаций. На канале есть огромное количество разборов: от механик рекомендательных до основных принципов работы криптографических систем.

Подойдет для всех, кто интересуется технологиями и не хочет буксовать на одном месте.

Отличительная черта аккуратный подход к видеоряду, подготовленная закадровая читка, высокая информативность и темп подачи материала (в самом хорошем смысле). Эти качества справедливы для всех роликов, которых здесь не так и много, но свои 6,5 млн просмотров они все-таки набрали.

Канал Гурава Сена

^{287 тысяч подписчиков}

Это одна из находок среди точечных рекомендаций участников сообщества Hacker News. Автор канала выбрал для себя следующие тематические направления: проектирование систем, алгоритмы, спортивное программирование и работа над системами ИИ. Но на них он не ограничивается.

Суммарно ролики Гурава набрали более одиннадцати миллионов просмотров, хотя всего на канале чуть меньше 170 публикаций. Наиболее популярное видео 720k это разбор устройства системы обмена сообщениями. Сразу за ним самый быстрый алгоритм сортировки (668k), третье место занимает шардинг баз данных, четвертое архитектура сервисов вроде Tinder.

Понравится тем, кто учится на одной из CS-специальностей и развивает карьеру в этой области, а более продвинутым программистам поможет найти свежий взгляд на некоторые вопросы.

Отличительная черта скорость подачи материала, которая существенно отличается от того, к чему многие привыкли в вузе; разнообразие и достаточно глубокое погружение в определенные темы.

Канал Бэна Итера

^{559 тысяч подписчиков}

Продолжаем движение от каналов, где новые видео не появлялись около месяца, к более активным. Этим проектом занимается человек, известный по технической части Khan Academy и независимым начинанием в области разработки электроники и моделирования компьютерного железа.

Его ролики набрали более 33 млн просмотров, а отдельные видео регулярно выходят на миллионный охват. В топе рассказ о том, как собрать худшую в мире видеокарту (2,8M), еще мы выделили бы знакомство с работой TCP (333k) и обсуждение проблемы сетевого нейтралитета.

Подойдет тем, кто хотел бы на практике погрузиться в мир компьютерного железа.

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

The Coding Train

^{1,19 млн подписчиков}

Если при просмотре действительно полезного YouTube-туториала вы задумывались о том, как было бы круто, если его автор преподавал бы в вашем вузе, то это именно такой случай. Здесь есть все: от алгоритмов и машинного обучения до генеративной поэзии и проведения различных симуляций.

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

Этот канал подойдет всем, кто читает Хабр каждый день. Опытные разработчики и те, кто только начинают путь в сфере IT, точно смогут найти для себя что-то подходящее и полезное.

Отличительная черта прекрасное чувство юмора ведущего, профессиональное отношение к разбору тем, высокий уровень подачи материала в формате live-презентации (без редактирования).

Новые публикации у нас на Хабре:

• Квантовые коммуникации: система распределения ключа для десяти участников сети

• Полный граф в квантовой сети для восьми участников обсуждаем этот эксперимент

• Перестройка IT-монополий, слом cookie-стен и открытый госсофт облачный TL;DR

Привет, хабровчане. В преддверии старта курса "Python Developer. Basic" подготовили для вас перевод интересной статьи. Также приглашаем на открытый вебинар Карьера для "Python Developer. Basic".

Python один из самых популярных и доступных языков программирования, но далеко не самый быстрый. Многие создатели библиотек и фреймворков прибегали к использованию расширения на С, чтобы их код работал быстрее, чем код на нативном Python.Этот способ вполне рабочий, но если вы не знакомы с С, сборка мусора и управление памятью станут вашим адом на Земле. И тут на сцену выходит Nim.

Что такое Nim?

Nim статически типизированный, компилируемый, объектно-ориентированный язык программирования. Nim создавался, чтобы быть таким же быстрым как С и таким же выразительным как Python, и к тому же, расширяемым как Lisp. Благодаря синтаксическому сходству с Python, Nim станет отличным выбором языка для расширения, если с C вам не по пути.

Начало работы с Nim

Чтобы начать писать на Nim, его нужно установить в свою систему. Скачайте и установите его с сайта nim-lang.org.

Как только вы закончите, мы начнем писать свой первый код на Nim. Во-первых, мы создаем файл, я назову его hello.nim, а вы можете назвать его как захотите. Теперь мы откроем его в любом текстовом редакторе и напишем:

static:    echo("Hello, world!")

Сохраните и закройте файл, затем откройте терминал из текущей директории и введите:

nim compile hello.nim

И вуаля! В консоль выведется Hello, World!. После получения первого представления о Nim перейдем к основной теме статьи.

Встраиваем Nim в приложения на Python

Nim поставляется с модулем nimpy и nimporter, которые доступны для Python.Последний можно установить с помощью pip install nimporter. Эти два пакета будут иметь важное значение при совместной работе двух языков.

Чтобы продемонстрировать возможности Nim, мы создадим простой тест, который будет сравнивать скорость работы обоих языков, на примере функции находящей n-ое число последовательности Фибоначчи.

Давайте создадим папку под названием Benchmark с 3 файлами внутри:

• main.py файл, который мы будем запускать

• nmath.nim файл с версией функции fib на Nim

• pmath.py файл с версией функции fib на Python

Сначала напишем функцию fib на Python:

def fib(n):    if n == 0:        return 0    elif n < 3:        return 1    return fib(n - 1) + fib(n - 2)

А теперь переместимся в nmath.nim. Для начала нам нужно импортировать nimpy:

import nimpy

Прямо как в Python, не так ли? А теперь сама функция:

import nimpyproc fib(n: int): int {.exportpy.} =    if n == 0:        return 0    elif n < 3:        return 1    return fib(n-1) + fib(n-2)

Давайте разберемся

Мы определяем функцию fib с помощью ключевого слова proc. Дальше указываем тип возвращаемого значения как целочисленный, а (вау, что это такое?) {.exportpy.} сигнализирует Nim, что эта функция предназначена для использования в другом модуле Python. В остальном все также, как в Python.

Тестирование на время

В main.py создадим простой бенчмарк:

import nimporterfrom time import perf_counterimport nmath  # Nim imports!import pmathprint('Measuring Python...')start_py = perf_counter()for i in range(0, 40):    print(pmath.fib(i))end_py = perf_counter()print('Measuring Nim...')start_nim = perf_counter()for i in range(0, 40):    print(nmath.fib(i))end_nim = perf_counter()print('---------')print('Python Elapsed: {:.2f}'.format(end_py - start_py))print('Nim Elapsed: {:.2f}'.format(end_nim - start_nim))

Вот и все!

Пакет importer позволяет импортировать Nim в обычные модули Python, которые будут использоваться также, как и собственные. Круто, не правда ли?

Чтобы запустить код, просто введите python main.py в командную строку и смотрите, что будет!

Python Elapsed: 33.60Nim Elapsed: 1.05

Заключение

Вот и все, что нужно сделать, чтобы быстро встроить Nim в Python. Nim оказался примерно в 30 раз быстрее, но имейте ввиду, что разница в скорости может варьироваться в зависимости от выполняемой задачи. Чтобы узнать больше о Nim, рекомендую ознакомиться с официальной документацией и почитать про него в Википедии.

Что ж, на этом я закончу свой туториал! Спасибо, что дотерпели до конца. Надеюсь, эта статья окажется для вас полезной.

Узнать подробнее о курсе "Python Developer. Basic".

Смотреть запись открытого demo-урока Три кита: map(), filter() и zip().

До 10 апреля продолжается набор на вечерние курсы по математике и программированию в CS центре. Computer Science Center это совместный проект Школы анализа данных Яндекса, JetBrains и Computer Science клуба при ПОМИ РАН. Курсы проходят очно в Санкт-Петербурге и Новосибирске, жители других городов могут заниматься дистанционно. Обучение в Computer Science Center бесплатное.

На какие направления открыт набор, как поступить, и зачем вообще оно вам надо, подробно рассказываем под катом.

Большинство наших студентов учатся в вузах или работают, поэтому расписание составлено так, чтобы занятия можно было совмещать с основной деятельностью. Однако будьте осторожны: на учёбу в Computer Science Center придется тратить не менее 15 часов в неделю. Если у вас недостаточно времени (или мотивации), советуем начать с онлайн-курсов на платформе Stepik.

Длительность обучения два или три года по выбору студента. За это время нужно пройти не менее 12 курсов: часть из них обязательная, часть вы выбираете сами. Обязательные курсы зависят от направления обучения. Для поступающих в 2021 году будут открыты три направления (позже вы сможете выбрать одно из них или даже несколько сразу):

• Computer Science,

• Data Science,

• Software Engineering.

Подробнее обо всех направлениях на сайте. Для выпуска студенты проходят три семестра практики или научно-исследовательской работы (примеры есть на этой странице).

Чтобы стать студентом или студенткой CS центра, нужно справиться с вступительными испытаниями:

• заполните анкету на сайте до 10 апреля,

• решите задания онлайн-теста до 11 апреля,

• участвуйте в онлайн-экзамене в конце апреля-начале мая,

• пройдите собеседование в мае-июне.

Для кандидатов, которые успешно прошли отбор, занятия начнутся в сентябре 2021 года.

Если вы еще не решили, стоит ли ввязываться в эту авантюру, посмотрите на отзывы выпускников:

Станислав Гордеев, разработчик игрового движка в People Can Fly (Варшава), выпускник 2018 года направления Software Engineering:

Когда-то давно, в сентябре 2014, будучи ещё студентом-физиком, я случайно наткнулся на хабро-статью про онлайн-курсы на Stepik, заинтересовался и прошёл курсы по C++ и алгоритмам, кроме того, узнал о CSC. На тот момент у меня помимо интереса появилась довольно амбициозная цель попасть в большой gamedev. Поступление оказалось совсем не лёгким и до последнего дня с письмом о зачислении я не верил, что всё получится. Моё обучение началось в 2016, и с тех пор я семимильными шагами приближался к своей цели. А все из-за неповторимой атмосферы знаний, амбиций, дружелюбия, которая не позволяет сидеть на месте, которая заставляет поверить в себя. Сейчас я с уверенностью могу сказать, что моя цель осуществилась в первую очередь благодаря CS центру, потому что это больше, чем просто курсы. Старайтесь, и у вас всё получится.

Анна Атаманова, разработчица в Яндексе, выпускница 2016 года направления Data Science:

Почему СS центр это дико круто:

курсы! (всё новое и интересное по основным направлением центра тут-тут-тут);

увлечённые своим делом преподаватели (таких людей в любом случае приятно слушать);

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

проекты! стажировки! (опыт, реальные задачи);

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

Артемий Пестрецов, разработчик в JetBrains, преподаватель CS центра, выпускник 2019 года направлений Data Science и Software Engineering:

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

Все отзывы можно посмотреть на этой странице.

Для тех, кто нашел в себе силы дочитать до этого места, бонус! Перед тестом вы можете потренироваться и порешать задачи прошлых лет. Но помните, что 10 апреля тренажёр превратится в тыкву, так что лучше не откладывать.

Ну и самое последнее: 31 марта состоится День открытых дверей для поступающих в CS центр. Кураторы подробно расскажут про направления и формат обучения и ответят на все ваши вопросы. Зарегистрироваться можно здесь.

Ждем будущих студентов Computer Science Center!

Базовые алгоритмы сортировки

Пирамидальная сортировка (или сортировка кучей, Heap Sort)

Куча (heap) это не что иное, как двоичное дерево с некоторыми дополнительными правилами, которым оно должно следовать: во-первых, оно всегда должно иметь структуру кучи, где все уровни двоичного дерева заполняются слева направо, и, во-вторых, оно должно быть упорядочено в виде max-кучи или min-кучи. В качестве примера я буду использовать min-кучу.

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

Ниже приведен псевдокод пирамидальной сортировки:

HeapSort(A[1n]):1 - H = buildHeap(A[1n])2 - for i = 1 to n do:3 -   A[i] = extract-min(H)

В самом начале мы имеем несортированный массив. Первый шаг взять этот массив и превратить его в кучу; в нашем случае мы хотим превратить его в min-кучу. Итак, нам нужно преобразовать данные несортированного массива и построить из них min-кучу. Обычно это инкапсулируется одной функцией, которую можно назвать, например, buildHeap.

Ниже приведен псевдокод buildHeap:

buildHeap():1 - Изначально H пустая2 - for i = 1 to n do:3 -   Add(H, A[i])

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

Теперь самый маленький элемент в куче находится в последнем узле, что нам и нужно. Мы знаем, что он находится в отсортирован относительно остальных элементов, поэтому его можно полностью удалить из кучи (функция extract-min). Но нам нужно сделать еще кое-что: убедиться, что новый элемент корневого узла находится на своем месте! Маловероятно, что элемент, который мы сделали корневым узлом, находится на своем месте, поэтому мы переместим элемент корневого узла вниз в его корректное положение, используя функцию, которая обычно называется heapify (приведение к виду кучи).

Ниже приведен псевдокод extract-min и heapify:

extract-min(H):1 - min = H[1]2 - H[1] = H[H.size()]3 - уменьшаем H.size() на 14 - heapify(H, 1)5 - return minheapify():1 - n = H.size()2 - while (LeftChild(i) <= n and H[i] > H[LeftChild(i)]) or (RightChild(i) <= n and H[i] > H[RightChild(i)]) do:3 -   if (H[LeftChild(i)] < H[RightChild(i)]) then:4 -     j = LeftChild(i)5 -   else:6 -     j = RightChild(i)7 -   меняем местами H[i] и H[j]8 -   i = j

Вот и все! Алгоритм продолжает повторять эти шаги до тех пор, пока куча не сократится до одного единственного узла. На момент, когда это произойдет, мы будем уверенны, что все элементы в несортированном массиве находятся в своих отсортированных позициях и что последний оставшийся узел в конечном итоге станет первым элементом в отсортированном массиве. Общее время работы этого алгоритма составляет O(n log n).

Сортировка слиянием (Merge Sort)

Алгоритм сортировки слиянием это алгоритм сортировки, который сортирует коллекцию, разбивая ее на половины. Затем он сортирует эти две половины и объединяет их вместе, чтобы сформировать одну полностью отсортированную коллекцию. В большинстве реализаций сортировки слиянием все это делается посредством рекурсии.

Сортировка слиянием это алгоритм разделяй и властвуй, который можно свести к 3 шагам:

• Разделите (разбейте) задачу на минимально возможные подзадачи одного типа.

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

• Объединяйте результаты и соединяйте более мелкие подзадачи, пока вы, наконец, не примените то же решение к более крупной и сложной задаче, с которой вы начинали!

Суть алгоритмов разделяй и властвуй проистекает из того факта, что решить сложную проблему намного проще, если вы сможете понять, как разбить ее на более мелкие части. Если разбить проблему на отдельные части, решить ее станет намного проще. И обычно, когда вы выясняете, как решить подзадачу, вы можете применить это решение к более крупной задаче. Именно эта методология делает рекурсию предпочтительным инструментом для алгоритмов разделяй и властвуй, и именно по этой причине сортировка слиянием является отличным примером рекурсивных решений.

Функция mergeSort в свою очередь состоит из двух функций:

• функции слияния, которая фактически объединяет два списка вместе и сортирует их в правильном порядке.

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

Ниже приведен псевдокод сортировки слиянием:

Merge(A, B):1 - i = 1; j = 1; k = 1;2 - a_(m+1) = ; b_{n+1} = 3 - while (k <= m+n) do:4 -   if (a_i < b_j) then5 -     c_k = a_i; i++;6 -   else7 -     c_k = b_j; j++;8 -   k++;9 - return C = {c_1, c_2, , c_(m+n)}MergeSort(X, n)1 - if (n == 1) return X2 - middle = n/2 (round down)3 - A = {x_1, x_2, , x_middle}4 - B = {x_(middle+1), x_{middle+2), , x_n}5 - As = MergeSort(A, middle)6 - Bs = MergeSort(B, n - middle)7 - return Merge(As, Bs)

Именно потому, что сортировка слиянием реализована рекурсивно, это делает ее быстрее, чем другие алгоритмы, которые мы рассмотрели до сих пор. Сортировка слиянием имеет время выполнения O(n log n).

Выпуклая оболочка (или выпуклый контур, Convex Hull)

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

Подход 1 Упаковка подарков (Gift Wrapping) O(n)

Идея проста, мы начинаем с самой левой точки (или точки с минимальным значением координаты x) и продолжаем оборачивать точки против часовой стрелки. Если точка p является текущей точкой, следующая точка выбирается как точка, которая перекрывает все остальные точки по ориентации против часовой стрелки. Ниже приводится псевдокод:

1 - ConvexHull = пустой список2 - Ищем точку с наименьшим x и присваиваем ее u (:= u_original)3 - Пусть L будет вертикальной линией, проходящей через u3 - Do:4 -   Пусть v будет точкой с наименьшим углом между L и u * v5 -   Добавляем v в ConvexHull6 -   Пусть L = uv линии7 -   u := v8 - Until v = u_original9 - Выводим ConvexHull

Подход 2 Алгоритм Грэхема (Graham Scan) O(n log n)

Этот алгоритм можно разделить на 2 этапа:

• Этап 1 (сортировка точек): сначала мы находим самую нижнюю точку. Идея состоит в том, чтобы предварительно обработать точки, сортируя их по самой нижней точке. После сортировки точек они образуют простой замкнутый путь. Какими должны быть критерии сортировки? Вычисление фактических углов было бы неэффективным, поскольку тригонометрические функции не являются простыми в вычислении. Идея состоит в том, чтобы использовать ориентацию для сравнения углов без их фактического вычисления.

• Этап 2 (включении или отбрасывание точек): после того, как у нас есть замкнутый путь, следующим шагом будет прохождение по пути и удаление из него вогнутых точек. Первые две точки в отсортированном массиве всегда являются частью выпуклой оболочки. Для оставшихся точек мы смотрим на последние три точки и находим угол, образованный ими. Пусть это три точки: prev(p), curr(c) и next(n). Если ориентация этих точек (рассматривая их в том же порядке) не против часовой стрелки, мы отбрасываем c, в противном случае мы оставляем ее.

1 - ConvexHull = пустой список2 - Пусть u - точка с наименьшим значением x (если таких точек несколько, выбираем ту, у которой наименьший y)3 - Сортируем оставшиеся точки по угловой фазе в порядке против часовой стрелки вокруг u4 - Добавляем u и первую точку в ConvexHull5 - For i = 2 to n - 1:6 -   While угол между предпоследней, последней и точкой i > 180 градусов:7 -     Удаляем точку из ConvexHull8 -   Добавляем i в ConvexHull9 - Return ConvexHull

Если вам интересно следить за моей работой в области компьютерных наук и машинного обучения, вы можете посетить мои Medium и GitHub, а также другие проекты на https://jameskle.com/. Вы также можете написать мне мне в Твиттере, но электронной почте или найти меня в LinkedIn. Или подписывайтесь на мою рассылку, чтобы получать мои последние статьи прямо на ваш почтовый ящик!

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

Приглашаем также посетить бесплатный демо-урок на тему Пирамидальная сортировка. На этом бесплатном демо-занятии мы: сначала реализуем алгоритм сортировки выбором, потом превратим массив в пирамиду (кучу) и ускорим время поиск максимального элемента в неотсортированной части массива с линейного до логарифмического.В итоге у нас получится алгоритм Пирамидальной сортировки. Мы наглядно продемонстрируем работу алгоритма на визуальных примерах с конкретными числами.

Почему Курс по стартапам и бизнесу от Стэнфордского Университета, является одним из самых лучших в мире для стартаперов? Дело в том, что лекторами данного курса являются лучшие из лучших стартап-предприниматели, такие как: Сем Альтман президент самого известного венчурного фонда Y Combinator, Дастин Московиц сооснователь Facebook, Питер Тиль сооснователь PayPal и первый инвестор, который вложил деньги в Facebook, Брайан Чески основатель Airbnb, Альфред Лин основатель Zappos, Алан Кей отец ООП и много других гуру современного интернет-бизнеса.

В этом курсе отсутствуют сложные теории, а присутствуют только практические примеры и советы.
Например, как найти бизнес-идею и оценить её, как привлечь клиентов и постоянно увеличивать свои продажи, как построить успешную бизнес-стратегию и подобрать сильную команду и т. д.
В первой лекции будут выступать Сэм Альтман гений-программист, который сейчас возглавляет венчурный фонд Y Combinator, с чьей помощью успешно реализовано более 400 стартапов и также Дастин Московиц сооснователь Facebook.

В этой небольшой статье я хочу кратко описать содержимое лекции 2 - Команда и реализация стартапа из курса по стартапам и бизнесу от Стэнфордского Университета.

Итак, из Лекции 2 - Команда и реализация стартапа вы узнаете слендующее:

00:43 - Как определить какие рынки будут развиваться и расти в будущем?

01:35 - Как преодолеть усталость от стартапа основателям?

02:45 - Как найти со-основателя или партнера и выстроить с ним хорошие отношения?

05:15 - Какие характеристики должен иметь каждый партнер?

07:47 - Какое количество со-основателей желательно должен иметь стартап?

08:00 - Как и когда нанимать новых сотрудников?

08:24 - Как подбирать персонал и какими качествами должны обладать ваши работники?

12:20 Сколько времени нужно выделить на поиски сотрудников?

14:15 Источники поисков кандидатов.

15:27 Какой опыт должны иметь кандидаты в сотрудники?

16:05 Три вещи на которые стоит обращать внимание при найме людей.

16:55 Лучший способ с помощью которого можно понять качество кандидата.

17:54 Почему важны коммуникативные способности?

19:47 - Как распределять доли компании между работниками компании?

21:07 - Как удержать в компании хороших сотрудников?

23:27 - Когда нужно увольнять неподходящего для вашей компании человека?

24:30 Как найти баланс между быстрым увольнением работника и обеспечением чувства безопасности вашей команды?

25:55 - Когда со-основатели должны принимать решение об разделении капитала?

26:42 - Как узнать, что работник вырастит до хорошего уровня в будущем?

27:32 - Как сохранить компанию в случае ухода одного из со-основателей на раннем этапе?

29:00 - Что делать если при приеме сотрудника компания теряет свою конкурентную способность

29:37 - Как работать с основателями, которые находятся в другой географической локации?

30:20 - Несколько слов про основные правила реализации стартапа.

31:50 - Какие задачи должен выполнять основатель в стартапе?

32:50 - Как уделённое внимание на задачи, а также концентрация на выполнении определённой задачи и интенсивность её выполнения влияют на развитие стартапа?

40:20 Один из основных критериев хорошего стартапа.

41:15 Почему важна интенсивность выполнения задач?

41:50 Как нужно бороться за клиента?

43:50 - Почему для стартапа жизненно важен его рост?

45:05 Почему продажи самый лучший показатель успешности стартапа?

45:50 Один из вариантов решения проблем стартапа.

47:05 - Как стоит реагировать на новости от конкурентов?

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

Оригинал на сайте http://startupclass.samaltman.com/

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

Сегодня остановимся на общих темах, а в следущий раз перейдем к специализированным.

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

Fun Fun Function

^{245 тысяч подписчиков}

Заметим сразу, что автор канала приостановил выпуск роликов. Но библиотеку записей, собранную за пять с лишним лет работы, он сохранил. Наибольшее количество просмотров 600k набрала первая часть разбора техник функционального программирования на JavaScript. Из более свежих в лидеры вырвались такие темы как React Hooks (123k) и когнитивно-поведенческая психотерапия (28,5k), ставшая частью длительной серии из нескольких десятков роликов о культуре разработки, карьере в IT, лайфхаках для программистов, продуктивной работе и эмоциональной гигиене.

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

Отличительная черта канала информативность и хорошее чувство юмора ведущего. Благодаря им все публикации в общей сложности набрали более десяти миллионов просмотров. Кстати, загляните и в дружественный проект DevTip (хотя тут апдейты перестали появляться еще раньше).

Art of The Problem

^{70 тысяч подписчиков}

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

Одни из наиболее популярных передач по теме нейронок и глубокого обучения. В последнем видео из этой серии авторы объясняют базовые концепции и математику, задействованную в этой области, с помощью различного рода визуализаций. На канале есть огромное количество разборов: от механик рекомендательных до основных принципов работы криптографических систем.

Подойдет для всех, кто интересуется технологиями и не хочет буксовать на одном месте.

Отличительная черта аккуратный подход к видеоряду, подготовленная закадровая читка, высокая информативность и темп подачи материала (в самом хорошем смысле). Эти качества справедливы для всех роликов, которых здесь не так и много, но свои 6,5 млн просмотров они все-таки набрали.

Канал Гурава Сена

^{287 тысяч подписчиков}

Это одна из находок среди точечных рекомендаций участников сообщества Hacker News. Автор канала выбрал для себя следующие тематические направления: проектирование систем, алгоритмы, спортивное программирование и работа над системами ИИ. Но на них он не ограничивается.

Суммарно ролики Гурава набрали более одиннадцати миллионов просмотров, хотя всего на канале чуть меньше 170 публикаций. Наиболее популярное видео 720k это разбор устройства системы обмена сообщениями. Сразу за ним самый быстрый алгоритм сортировки (668k), третье место занимает шардинг баз данных, четвертое архитектура сервисов вроде Tinder.

Понравится тем, кто учится на одной из CS-специальностей и развивает карьеру в этой области, а более продвинутым программистам поможет найти свежий взгляд на некоторые вопросы.

Отличительная черта скорость подачи материала, которая существенно отличается от того, к чему многие привыкли в вузе; разнообразие и достаточно глубокое погружение в определенные темы.

Новые публикации у нас на Хабре:

• Квантовые коммуникации: система распределения ключа для десяти участников сети

• Полный граф в квантовой сети для восьми участников обсуждаем этот эксперимент

• Перестройка IT-монополий, слом cookie-стен и открытый госсофт облачный TL;DR