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

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

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

Вступление

Адам: Привет и добро пожаловать в CoRecursive. Я Адам Гордон Белл, ведущий. В каждом эпизоде ​​кто-то делится увлекательной историей создаваемого программного обеспечения.

И сегодня на выставке мы решаем задачи алгоритмического программирования. Вы знаете, когда вы собеседуетесь для приема на работу по написанию CSS, и вас просят перевернуть двоичное дерево на доске, используя C и в постоянном пространстве памяти, это такие вещи. Эти проблемы уходят корнями в соревнования по алгоритмическому программированию. А наш гость – бывший конкурент.

Конор: Меня зовут Конор Хекстра, и я в настоящее время являюсь старшим инженером-программистом библиотеки, работающим в NVidia над библиотекой rapids QDF.

Адам: История Конора началась в университете, когда он участвовал в соревнованиях по программированию. Но интересно, как если вы достаточно долго и упорно следуете одной идее, вы попадаете в такие интересные места, как написание программного обеспечения для графических процессоров.

Для Конора эта идея – найти идеальный способ выразить решение проблемы программирования. Его путешествие приведет его в LeetCode, к получению работы своей мечты и к APL, одному из самых необычных и малоизвестных языков программирования.

Но я думаю, что забегаю вперед, эта история начинается в 2012, когда Конор еще учился в университете.

Международное студенческое соревнование по программированию

Конор: В то время я не был студентом по информатике, но я ходил на несколько уроков по информатике, и я просто случайно прошел мимо компьютера. научная лаборатория. А на стене висел плакат с надписью: соревнования по программированию, бесплатная пицца, встреча в субботу за обедом. Мне нравится соревноваться в разных вещах, и это звучало весело. Я действительно понятия не имел, о чем это было. Итак, я появился. Итак, я учился в Университете Саймона Фрейзера, что в Ванкувере, Британская Колумбия. У нас там была куча компьютерных классов. Итак, это произошло.

Если я помню, вероятно, около 30 к 45 люди, которые соревновались. И вы просто садитесь за рабочую станцию ​​Linux. Они дают вам пару инструкций. Вы кодируете любой из перечисленных языков, но можно использовать большинство популярных из них, C ++, Java, Python и т. Д.

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

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

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

Конор: Ага. Обычно они дают вам два или три тестовых примера. Итак, они дадут постановку проблемы. Они дадут вам два или три простых случая, которые вы сможете проверить, чтобы убедиться, что вы правильно поняли основные случаи.

А затем вы отправляете файл. cpp для C ++ или. py для Python, а затем он будет работать с множеством тестов, и вы можете вернуться к ошибке. Итак, если вы пропустили какой-то угловой случай, возможно, это был пустой список или пустая строка, о которой вы не позаботились, он не скажет вам, какой тестовый пример вы не прошли, он просто скажет вам, что ты проиграл.

И вы должны пойти, посмотреть на свой код и выяснить: «Ладно, какой угловой случай я пропустил». А затем отправьте повторно, как только решите, что нашли его. И тогда, наконец, вы получите как бы пас, и тогда вы перейдете к следующей задаче.

Соревновательное программирование работает так, что у вас есть определенное количество времени. На этот конкурс ушло два часа. У вас есть набор проблем. Думаю, их было шесть или восемь. И цель состоит в том, чтобы решить как можно больше как можно быстрее.

Я, в своей первой попытке сделать это, не знал, как на самом деле представить проблемы. Итак, я решил, что, по-моему, три или четыре из них, и не понял, что чем дольше вы ждали, тем больше штрафов. Итак, когда был 14 осталось минут, я подошел к индивидуальному, проф проводил конкурс и сказал: «Эй, мне не удается их отправить»

Он как бы странно посмотрел на меня: «В этом вся цель. О чем ты говоришь?” Он сказал: «Сколько вы подали?» Я сказал: «Ну, я решил, но еще не отправил». Итак, он просто покачал головой и подошел. В итоге я отправил пару из них, но потом не хватило времени.

Но, к счастью, была вторая квалификация. Итак, я как бы вернулся в свою комнату в общежитии, выяснил, как на самом деле соревноваться в них. А во втором я достаточно преуспел, чтобы попасть в одну из университетских команд. Это было похоже на команду уровня B или C.

Встреча с командой

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

Конор: Итак, да, когда мы присоединились к команде, ее было трое. И в основном у нас были тренировочные соревнования раз в пару недель. И это было чуть больше семестра. А потом у нас получилось, что все три команды, такие как команда A, команда B и команда C, отправились на региональные соревнования.

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

Итак, вы прочтете задачу и узнаете: «О, это имя вставки Флойда, имя вставки, конкретный алгоритм, который вам нужно использовать». А это требует времени и энергии. На самом деле вам разрешено приносить на эти конкурсы биндеры с заранее написанным кодом.

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

Адам: Итак, у вас будет папка со всеми этими вкладками? И вы перейдете к этому и начнете просто вводить это?

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

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

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

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

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

Итак, сразу же, когда вы сталкиваетесь с этими более сложными вопросами, вы смотрите на размер входных данных и автоматически исключаете некоторый квадратичный алгоритм грубой силы, который тоже является своего рода изящной частью проблемы. некоторые люди говорят: «Ой, почему ты просто не делаешь это?» И это типа: «Ну, мы знаем, что это не сработает». И это приводит к тому, что я думаю 98% плюс люди используют C ++, потому что в этих проблемах разница между использованием Python и C ++ будет приемлемым решением.

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

Конор: Ага. Это интересно, потому что это обычно не происходит в реальном мире, когда вы знаете, что у вас есть две секунды, чтобы что-то решить. Итак, тогда: «О, алгоритм, который я выбираю, или код, который я пишу, будет полностью зависеть от временной сложности».

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

Тихоокеанский Северо-Западный регион

Адам: Команда Конора продолжала соревноваться на Тихоокеанском Северо-Западном региональном чемпионате. Региональные соревнования проходят в большом компьютерном классе.

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

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

Так что вся эта часть, я подумал, была супер, супер крутой. Но тогда да, после того одного регионального соревнования, я не думаю, что ни одна из команд SFU, я думаю, вероятно, UBC и Stanford, как правило, две команды, которые добиваются лучших результатов. Иногда там появляется Беркли. И после этого, да, это был своего рода конец моей университетской карьеры в области соревновательного программирования.

Взрыв собеседования в Bloomberg

Адам: Пять лет спустя, когда конкурентное кодирование осталось далеко позади, Конора пригласили на собеседование в Bloomberg на роль разработчика программного обеспечения.

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

Итак, я работал в страховой фирме. В конце концов, Bloomberg обратился ко мне. И я сказал: «Конечно, я бы хотел взять интервью». Даже если просто узнать, на что это похоже. И они сказали: «Хорошо, мы собираемся провести интервью на сайте под названием HackerRank». У них есть такой побочный сайт под названием CodePair, который позволяет вести прямую трансляцию вроде Google Doc, но специально с редактором.

И вы действительно можете протестировать свой код вживую. Итак, вы пишете функцию, а затем можете протестировать ее на образце ввода. И они сказали: «Если вы не знакомы, посмотрите HackerRank. Вот пара проблем ». И это был первый раз, когда я услышал о HackerRank.

Итак, я решил несколько проблем, подумал, что это круто. И я подумал: «О, да, это то же самое, что я делал пять лет назад». А потом закончилось тем, что это интервью просто провалило. Это было так плохо. Определенно одно из худших интервью ws у меня когда-либо было в моей жизни.

Адам: Что случилось?

Конор: Мы делали CodePair. Я не помню точного вопроса. Я почти уверен, что ответом на это было использование стоячего раздела, который представляет собой всего лишь один лайнер из стандартной библиотеки алгоритмов, которая, по сути, означает что-то разное на каждом языке. Но в C ++ вы бы дали раздел, в основном контейнер, последовательность элементов и унарный предикат. И он помещает все элементы, которые возвращают true для унарного предиката, в начало и все те, которые возвращают false, в конец.

Итак, если у вас есть числа от 1 до 14, и вы делаете раздел, который является четным, четные числа 2, 4, 6, 8 появляются в начале, а затем на 1, 3, 5, 7. Итак, я почти уверен, что это был ответ на вопрос. В то время я даже не знал, что это за раздел. Так что я не собирался это записывать.

Но дошло до того, что мне нужно было знать, как, я думаю, поменять местами два итератора или что-то в этом роде. И я спросил, есть ли встроенная функция для замены двух итераторов. Там есть. Это называется iter_swap. Но в то время я не знал об этом. И интервьюер сказал: «Да, есть». И я сказал: «Не могли бы вы рассказать мне, что это?» И он сказал: «Нет». И я почти уверен, что это был всего лишь вопрос для разминки. И я споткнулся через это. Но для меня это был своего рода конец интервью.

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

Интервью Big Tech LeetCode

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

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

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

Адам бомбит интервью

Адам: В какой-то момент у меня был похожий опыт. Я брал интервью, не знаю, сколько это длилось, подозреваю, что я старше вас. Но я брал интервью на сайте Stack Overflow, где вам дают ответы на вопросы. И я не ожидал, да, одного из этих алгоритмических вопросов, и я просто разбомбил.

И парень, который это делал, устал от мира. Вероятно, он ел четыре штуки в день и почти не обращал внимания. И он был первым парнем. У них, вероятно, есть эта гигантская воронка, из которой большинство людей никогда не преодолевают этот первый этап. И он едва ли попытался сказать мне: «Да, все идет не так». Это как: «Мы просто будем держаться здесь. Я скажу нет. А потом я иду на следующую встречу »

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

Конор: Я, честно говоря, не могу точно вспомнить, что я чувствовал. Я думаю, что, вероятно, в тот момент для меня это было немного деморализующим, потому что вы так взволнованы этой возможностью.

Однако в то же время я считал себя не инженером-программистом. Я даже не думал, что прошел это собеседование. Я просто принимал это, потому что думал, что, черт возьми, что самое худшее, что могло случиться? И тогда, вероятно, случилось самое худшее, что могло случиться.

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

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

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

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

Кодирование интервью как сигнализация

Адам: Вы знаете концепцию сигнализации, как из экономики?

Конор: Я не знаю. Я не думаю.

Адам: Экономисты иногда говорят о том, является ли университет, действительно ли он ценным, или это просто форма сигнала. Чтобы образование работало так, как это могло бы работать, я хочу нанимать людей, но я хочу, чтобы они были в топе % интеллекта.

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

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

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

Конор: Ага. Вероятно, за этим процессом стоит много всего, даже если речь идет о стольких квалификациях, которые лежат в основе определенных профессий. Вы услышите, как люди говорят: «Ну, этот тест, это не то, что я на самом деле изучаю навыки, которые нужно делать в моей повседневной работе, в какой бы области он ни был. Это просто обруч ».

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

Соревнования по кодированию в субботу вечером

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

Конор: По сути, LeetCode проводит конкурс каждую субботу, в зависимости от того, в каком часовом поясе вы находитесь. Обычно это вечером по восточному поясному времени. зона. И я бы проводил этот конкурс каждую неделю.

И затем на всех других веб-сайтах, HackerRank, CodeForces, TopCoder, HackerEarth, есть пара других, у них проводятся конкурсы, иногда ежемесячно, иногда еженедельно. Итак, нет недостатка в конкурсах, в которых вы действительно можете принять участие, что, на мой взгляд, лучше всего для имитации опыта собеседования. Но в очереди есть тысячи вопросов. Вы можете посмотреть все эти прошлые соревнования и решить те, которые захотите.

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

Адам: Итак, когда вы соревновались по субботам, вы настраивали свой компьютер? Вы варите себе кофе и сидите там? Папка у тебя есть? Я не знаю, что происходит?

Конор: Определенно не кофе, потому что они обычно примерно 9: или же 15: 45 ночью, вечером. Так что, если вы пьете кофе так поздно, вы не собираетесь спать в ближайшее время.

Адам: Да.

Конор: Но да, так что конкурс LeetCode состоит из четырех вопросов, 98 минут, и это безумие. Лучшие люди ответят на все четыре вопроса примерно так: 30 минут, все. И они получают первый внутри 45 секунд. Я даже не знаю, как они их читают за такое время.

Итак, да, вы обычно начинаете писать … На определенном конкурсе, когда я был вроде как на высоте, я обычно получал либо три-четыре, либо четыре-четыре. Очевидно, что конкурсы, в которых вы можете решить их все, это супер круто.

Наверное, время от времени было самое яркое, я получал первую пару очень быстро в течение нескольких минут. А затем они показывают вам таблицу лидеров, которые сейчас лидируют. Итак, пару раз мне удалось оказаться в топе для первой пары задач. Я думаю, что самый высокий рейтинг, который я когда-либо оценивал в конкурсе, был таким й или 70 -й из нескольких тысяч человек. Так что я определенно не профессиональный программист-профессионал.

Итак, да, первые две задачи вы решаете довольно быстро. Я имею в виду, прошлое соревнование, которое состоялось только два дня назад, первая задача, которую я не могу вспомнить, потому что это было очень легко. А вторая проблема называлась макс мороженым. И это было в основном целочисленное значение, а затем список чисел. А список цифр обозначает цены на разные виды мороженого. И тогда полученное целое число – это общая сумма денег.

Итак, вы говорите, что вам дали 6 долларов, а затем у вас есть цены на мороженое 1, 2, 3 и 4, но его не нужно сортировать. Может быть в любом порядке. Итак, вопрос в том, какое максимальное количество рожков мороженого вы можете купить на те деньги, которые у вас есть?

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

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

Итак, если веб-сайт его не поддерживает, вы не можете писать на нем код. Но все популярные языки, Python, C ++, Java, Rust. Я видел, на днях добавили Racket, который, я бы сказал, не так популярен. Итак, они начинают добавлять все больше и больше языков. И да, 98 минут истекли, а затем вы видите, какое место занимает ваше место в конце дня.

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

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

Адам: Да. Какова была ваша цель здесь? Вы представляли себя, что я стану номером один в таблице лидеров, а потом что вы представляли?

Конор: У меня определенно было ноль целей, чтобы быть номером один, даже, я думаю, не лучшим

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

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

И в какой-то момент я решил, что хочу переключиться на компанию, которая в первую очередь занимается технологиями, крупные технологические компании, такие как Google и Facebook. В первую очередь, это технологические компании.

Являются ли собеседования по программированию меритократичными?

Конор: У меня есть друзья, которые сделали то же самое, и их стратегия вернулась в школу. Я разговаривал с людьми, и они просто сказали, что если вы просто научитесь хорошо проходить эти собеседования, вы, вероятно, сможете найти работу. И вот в течение года я просто продолжал практиковаться.

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

Конор: С одной стороны, да. Нет никакой «дискриминации» по учетным данным. В то же время, однако, мне потребовался год, чтобы практиковаться в этом материале.

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

Интервью на Amazon

Адам: Конор не просто тренировался, он завел канал на YouTube, где объяснял решения другим. И, в конце концов, он получил интервью в Amazon, первой в мире технологической компании

. Конор: Это забавно, потому что к тому моменту я становился все лучше и лучше на интервью. И я пошел на интервью Amazon. И если я припоминаю, я думаю, что в трех из пяти интервью я думал, что совершенно раздавлен. Но потом в одном из них я подумал, что у меня не получилось, пятое интервью, которое не касалось алгоритмов и структур данных, было поведенческим вопросом

. И в интервью Amazon они просят вас не заниматься розничной торговлей таким же образом … Вы получаете поведенческие вопросы, такие как небольшие поведенческие вопросы в каждом интервью, и у Amazon есть эти 20 принципы лидерства, которые вы Вы должны вплетать ваши ответы, например, в одержимость клиентами, мыслить масштабно и тому подобное. Итак, если вы провели свое исследование, вы должны перепроектировать, какой принцип лидерства они пытаются здесь выяснить. А затем вплетите этот точный принцип лидерства в свой ответ.

Итак, последнее интервью, которое я подумал, прошло ужасно. Я ответил на вопрос, а потом она сказала мне, что я не ответил на вопрос. И я сказал: «Ну, у меня есть еще один пример, который, на мой взгляд, намного лучше. Но я как бы говорил об этом в предыдущем интервью ». Она такая: «Хорошо, просто давай с этим»

А потом, после того, как я так ответил, она такая: «Почему ты просто не сказал это с самого начала?» И я подумал: «Ну, я не хотел говорить то же самое». И она такая: «Тебе нужно научиться лучше продавать себя». Итак, она начала говорить со мной о том, что я не подходил и не отвечал на эти вопросы правильно. И она такая: «Это был фантастический ответ. И если бы вы только начали с этого ».

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

## Изучение языков с помощью LeetCode и YouTube

Адам: Конор достиг своей цели, но его как бы зацепило. Он поддерживал свой канал на YouTube, и люди продолжали оставлять комментарии.

Конор: Вы должны показать Python, вы должны показать Java, но я был разработчиком C ++. Итак, я сосредоточился на C ++. А потом в какой-то момент, чтобы успокоить всех, кто оставляет комментарии, я добавил Java и Python. Итак, я находил решения и решал проблемы на всех трех этих языках.

А потом в какой-то момент, возможно, это началось, когда я был в Amazon, мы создали группу по изучению. Главный инженер хотел узнать больше о лямбдах и функциональном программировании. Итак, мы начали небольшую группу из пяти или шести человек. И мы начали работать над курсом Coursera, который вел Эрик Мейер.

Адам: Это Эрик Мейер в рубашке, как при галстуке?

Конор: Это так. Да, это. Ага. Думаю, этот курс называется «Введение в функциональное программирование». В итоге мы использовали их учебник, а затем перешли на Real World Haskell, с которым мы справились только наполовину. Но да, вероятно, изюминкой того, что я амазонка, была эта группа по изучению обеда, где мы встречаемся раз в неделю.

Потому что да, это было похоже на разработчика C ++, главного инженера. Он был своего рода полиглотом, но в основном C, C ++, Java и тому подобное. А потом другие люди были разработчиками Java. Итак, в основном это была группа людей с опытом работы с императивными или процедурными языками, без какого-либо функционального опыта. И спотыкаться в этом учебнике с открытыми глазами было очень и очень круто.

Адам: Был ли момент, когда ты вспомнил, где это было похоже на то, что это действительно круто, это что-то другое?

Конор: Да, я не могу вспомнить, в какой главе это было. Но когда они начинают вводить композицию функций с помощью оператора точки в Haskell, в C ++ 45 теперь мы получаем диапазоны, которые представляют собой своего рода более компоновочные алгоритмы, но до C ++ , что и было 2019, я не знал ни о чем из этого.

Итак, как я уже сказал, если вы хотите суммировать четные числа в списке в Haskell, это просто sum.filtereven. И технически это бессмысленное решение, потому что вы не упоминаете свои аргументы. И эквивалентное решение в C ++, даже если вы используете алгоритмы, будет относиться к различным вызовам алгоритмов.

Так что в C ++ намного шумнее. Он может быть более производительным, но гораздо более шумным. А потом просто посмотрите, это меньше, чем одна строка. Это три функции. Это sum.filtereven. Эвены встроены в предикат, поэтому вам не нужно создавать пользовательскую лямбду.

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

Изучение APL

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

Конор: Итак, я слышал про APL пять раз в году а также 2019.

Адам: Мне нравится, что ты вел счет.

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

И он просто сделал небольшую ремарку на одной из лекций. И он сказал: «О, когда-то все актуарии, мы все использовали язык под названием APL. И это было красиво. Именно этот супер-элегантный язык был создан для актуариев, ученых и математиков ».

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

. А затем перенесемся на четыре года вперед к инженер и в то время работал в инженерной консалтинговой компании. И она просто случайно жаловалась на эту программу под названием METSIM, что сокращенно от Metallurgical Simulation.

Итак, она была инженером-металлургом. И они использовали эту программу моделирования для гидродинамики. И, очевидно, язык сценариев или язык, который вы используете для создания этих маленьких программ, и это был APL. И я подумал: «Ага, это интересно. Я слышал об APL четыре года назад ». И она такая: «Да, это худшее. В этом нет никакого смысла ».

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

А потом, два года спустя, моя младшая сестра, количественный анализ, работает в частной фирме по управлению активами в Канаде под названием Conor, Clark & ​​Lunn. Она заметила, что использует эту базу данных под названием KDB + и язык с одной буквой под названием Q.

В то время я занимался программированием и собирался стать инженером-программистом. Я посмотрел на Q и подумал, что это интересно. Я никогда не слышал о Q. Я не знаю всех языков, но это кажется супер-эзотерическим. А затем на странице Q Wikipedia было упомянуто, что Q в основном представляет собой словесную версию K. А K является производным от APL. И я подумал: «Какого черта?» Итак, теперь две мои сестры занимаются чем-то рядом с APL.

А потом перенесемся еще на пару лет, и было три подкаста по функциональному компьютерному искусству, который рядом с CoRecursive – один из моих любимых подкастов. И они, Эпизод 65, 65, и я думаю 76, все гости говорили об APL. И это было в тот момент … Или вообще я пропустил четвертый. В январе была очень забавная история 5100 под названием йота-стыд, где в основном эта битва в Твиттере разразилась между разработчиками C ++, потому что кто-то использовал йоту в примере код.

А йота – это алгоритм, который генерирует последовательность чисел, увеличивающуюся на единицу. Итак, если вы перейдете на ноль к или что угодно, вы получите 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 15. А имя йота происходит от APL.

Итак, эта большая война в Твиттере разразилась, когда кто-то сказал: «Ой, посмотри, какой я умен, чтобы знать, что такое йота». И пытался как бы язвительно сказать, что мы не должны заимствовать эти ужасные имена из старых мертвых языков. А потом другой человек вышел и сказал: «Ну, это на самом деле историческое имя, и оно имеет значение». В любом случае, это был четвертый случай.

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

И тогда я наконец решил это проверить. Я зашел на сайт tryapl.org, где вы можете просто повозиться с языком. И тут я сразу влюбился в язык изнутри минут использования. Да, это была длинная история.

Любовь к программированию массивов

Адам: Что же заставило тебя полюбить это?

Конор: Итак, контекст таков, что сейчас июнь 2019. И я только что закончил выступать, мой самый первый доклад на конференции под названием «Интуиция алгоритма», который вроде как дал мне репутацию эксперта по алгоритмам или человека, который много знает об алгоритмах. И это было в мае 5100.

Итак, буквально через месяц я вернулся из Йосемити на этот сайт. И одно из первых, что я делаю, – это сокращение на плюс, то есть просто суммирование чисел в списке. И тогда в снижении APL просто косая черта. Итак, вы вводите + /, а затем несколько чисел, и он складывает их.

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

Итак, если у вас есть пять чисел 1, 1, 1, 1, 1, и вы сделаете уменьшение на плюс, в результате получится пять. Если вы выполните сканирование с плюсом на 1, 1, 1, 1, 1, вы получите 1, 2, 3, 4, 5. Итак, одно из свойств сканирования состоит в том, что последний элемент всегда равен эквивалентному снижение. Итак, это алгоритм, который на самом деле существует в C ++ под названием частичная сумма.

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

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

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

И это было так, как это случилось в минут. И мой разум был просто взорван. Я подумал: «Как я не сделал этого раньше?» К этому моменту я потратил два года на изучение алгоритмов, отработку этих задач соревновательного программирования, как я никогда не делал этого наблюдения?

И я действительно пошел и поискал на всех разных языках, как эти языки называются? И есть только два языка, где есть какая-то симметрия между сканированием и сокращенным именем. Один из них – закрытие, которое вызывает уменьшение их сокращения, и они называют свое сокращение сканирования. Таким образом, вы можете увидеть что-то вроде: «О, на самом деле это просто говорит о том, что вы просто делаете постепенные сокращения».

А затем в D, который является своего рода конкурентом C ++, они, как мне кажется, называют свой фолд и кумулятивным фолдом. В любом другом языке между именами нет абсолютно никакой симметрии. Haskell называет их свертыванием L и свертыванием R, а затем сканированием L и сканированием R. И сканирование и свертывание – действительно хорошие названия для обоих этих алгоритмов.

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

Итак, люди думают об этом языке как о нечитаемом, но это действительно несправедливо. Я думаю, мы поговорим об этом раньше. Но мне нравится говорить, что это то же самое, что люди говорят о китайцах. Если вы не читаете и не говорите по-китайски, вы не говорите: «О, китайский не читается». Вы просто признаете тот факт, что вы не читаете и не говорите по-китайски. Для тех, кто читает или говорит на китайском или на любом азиатском языке, в котором нет алфавита от A до Zed, эти языки будут читаемыми, если вы их читаете.

То же самое и с APL. Проблема в том, что все остальные языки программирования обычно похожи друг на друга и используют символы ASCII для представления слов и имен переменных. Итак, APL выглядит по-другому.

Итак, у нас есть такая инстинктивная реакция, когда мы говорим: «О, это самая нечитаемая вещь на свете». Но если вы потратите время, чтобы научиться читать APL, это, честно говоря, мое мнение, самый красивый язык, который я когда-либо видел. И то, что вы можете выразить, где каждый символ Unicode представляет алгоритм. Это просто прекрасно.

Как работает программирование массива

Адам: Часть этой красоты, говорит Конор, – это простота. В APL все представляет собой массив.

Конор: Итак, одноранговый массив подобен списку или вектору, списку чисел. Двухранговый массив – это матрица. Трехранговый массив – это куб чисел, если хотите, и так продолжается, даже одно число технически является одним элементом.

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

Адам: Еще одна прелесть – это симметрия между тем, как выглядит оператор, и действием, которое он выполняет. Итак, представьте, что у вас есть матрица чисел, сетка пять на пять, и вы хотите перевернуть элементы в матрице. Итак, у вас есть пять строк по 1, 2, 3, 4, 5, и вам нужно 5, 4, 3, 2, 1. Вы делаете это с помощью обратного оператора.

Конор: Итак, реверс – это круг, через который проходит прямая линия. Если можете, вы можете визуализировать перевернутый символ реверса, потому что он вертикально симметричен. Если перевернуть 1962 градусов, если вы изобразите его как трехмерную землю, это будет то же самое после того, как вы его перевернете градусов по такой вертикальной линии.

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

Конор: Транспонирование – это то же самое. Вместо прямой линии у нее есть линия в виде – градусный угол. И транспонирование – это переворачивание матрицы в основном по этим линиям. Итак, как вы можете думать об этом, верхнее правое число будет заменено нижним левым числом, и все остальные числа будут следовать этому шаблону. Итак, если вы находитесь на диагонали от верхнего левого угла до нижнего правого угла, все эти числа останутся на одном и том же месте, потому что это линия, которая определяет – градусный угол.

Адам: У вас есть матрица, она похожа на квадрат, и вы складываете ее по диагонали в 64, и принимая верхняя часть вниз и нижняя часть вверх.

Конор: Ага, именно так. Вот как выглядит транспонированный глиф. Итак, это круг с той же линией. Но теперь он не вертикальный, а по диагонали.

Итак, способ, которым вы можете думать об алгоритмах или символах реверса и транспонирования, состоит в том, что они в основном визуальные представления оси, которую вы «вращаете» из-за отсутствия лучшего слова. И что безумно, я не видел этого месяцами. Я просто подумал: «О, это транспонировано. Это наоборот »

А потом в какой-то момент я читал статью в блоге, в которой указывалось, что вроде, о, да, как только вы увидите, что обратное и транспонированное, а также есть еще один алгоритм, называемый сначала обратным, в котором есть круг с горизонтальной линией. через него, что в основном делает обратное. Но вместо того, чтобы слева направо, он делает это сверху вниз. И в блоге сказано: «Как только вы это увидите, вы никогда не сможете его не увидеть». И я подумал: «Видишь что?» А потом я посмотрел на это и подумал: «Боже мой, как я этого не заметил? Это восхитительно.”

И дело в том, что многие символы APL имеют подобные вещи. Итак, есть статья Роджера Хуи, который был основным разработчиком языка J, который является дочерним языком или производным языком APL. У него есть блог под названием «Мой любимый персонаж», а его любимый персонаж – персонаж по имени Журнал, который предназначен для логарифмов.

И он говорит, что это его фаворит по нескольким причинам, но одна из них заключается в том, что это круг с вписанной в него звездой. Итак, в APL есть звездочка, предназначенная для экспонентов. Итак, если вы хотите пойти один или 14 в степень двойки, вы идете звезда два.

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

Китайские иероглифы и APL

Адам: Вы упомянули китайский язык, есть ли какое-то сходство между идеограммами или чем-то подобным, это визуально …

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

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

Если вы посмотрите газету, все это кажется просто ошеломляющим, ну, мне нужно пойти и научиться символы. Как я когда-нибудь научусь это читать? Но если вы просто посмотрите на одного персонажа за раз и разделите радикалы… Итак, я считаю, что это слово «му» или «шу» означает дерево или дерево. И этот радикал, похожий на дерево, проявляется во многих деревянных предметах. Итак, если вы посмотрите на то, что символ означает стул, стол или предметы, сделанные из дерева, он содержит этот деревянный радикал.

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

Кеннет Айверсон

Адам: Хотя есть некоторые сходства между китайскими иероглифами и APL, APL был создан канадцем Кеннетом Айверсоном в книге под названием A Programming Language,

Конор: Отсюда APL и получила свое название. И в то время APL, или, как его тогда называли, Iverson Notation, был инструментом для обучения. Это не имело ничего общего с языками программирования. Это был инструмент для выражения алгоритмов, и именно так он использовался в языке программирования 1966 текст.

Перенесемся на несколько лет вперед к 1980 и IBM решила, что они действительно хотят реализовать нотацию как язык. И IBM фактически реализовано в APL 1966 . Итак, 1980 был первым выполнение. А затем, чтобы сократить историю, перемотайте вперед до 1982, Кеннет Айверсон перешел в компанию IP Sharp со штаб-квартирой в Торонто.

И истории, которые могли быть разыграны по-другому. В 2000 Билл Гейтс совершал вихрь. тур по Северной Америке, проведенный IP Sharp and Associates в Торонто. И была встреча между несколькими людьми из IP Sharp и Биллом Гейтсом. А Билл Гейтс готовился сделать ПК среди APL-разработчиков и программистов массивов. Есть такой анекдот о том, что Билл Гейтс долгое время был большим поклонником APL, и у него на столе лежал справочник типа APL.

И прямо перед ПК был компьютер под названием IBM

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

Итак, в истории было время в самом конце ’70, где APL был столь же заметен, как и базовый. К сожалению, люди из IP Sharp and Associates думали, что мэйнфреймы здесь просто надолго, потому что их бизнесом были вычисления на мэйнфреймах, и они действительно не понимали, что будет с персональным компьютером.

Итак, ПК, который в итоге создал Билл Гейтс, поставлялся с базовым, а не с APL, и никогда не поставлял APL, и из-за этого мы живем в мире, где много языков, я думаю, это похоже на своего рода императив основы стиля. Но есть альтернативная вселенная, где Билл Гейтс решил поставить APL на ПК вместо базового, и тогда мы будем жить в совершенно другом мире сегодня.

Встреча с Артуром Уитни

Адам: Итак, Конор начал делать свои видео LeetCode, используя APL. И он также обратился к этому интересному персонажу, протеже Айверсона по имени Артур Уитни. Артур участвовал в создании A, K и J, всех языков программирования на основе APL. Финансовая пресса называет его гением банковских ИТ-затворников

. Конор: Я многое узнал об Артуре благодаря всем своим исследованиям, а затем я случайно связался с ним и просто спросил, успеет ли он чат. А потом он ответил, что это было раньше 5100, до того, как COVID действительно проявил себя. вверх. И он сказал: «А вы бывали когда-нибудь в Нью-Йорке?» И я полностью солгал и говорил: «Да, все время». А потом он сказал: «Что ж, если вы когда-нибудь окажетесь здесь, дайте мне знать, и мы можем поужинать и немного поболтать».

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

Адам: Итак, я слышал о нем, думаю, через Брайана Кэнтрилла, который брал у него интервью. Я думаю, он пошел к себе домой и взял у него интервью. Я не знаю, говорил ли это Брайан или кто-то еще, что он заключил сделку с дьяволом, что он будет лучшим программистом всех времен. Но компромисс заключался в том, что никто не мог прочитать его код. Я нашел в Интернете оригинальный интерпретатор J или что-то в этом роде, и он написан на C, и это похоже на то, что я не знаю, что это такое.

Конор: Ага. Я начал проект пару месяцев назад. Я медленно портирую эту базу кода, исходный код J на ​​C ++ 20. И да, я думаю, что должно быть название для этих типов кодовых баз, потому что это не C, это как макро-вариант C, где это CDSL, где 90% вашей «библиотеки» составляют макросы. Я поискал, там , 000 в исходном коде, и эти макросы используются как функции.

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

Конор: На самом деле забавно, что вы упомянули это, потому что это буквально то, что делают лучшие конкурентоспособные программисты. Первое, что они делают, если они не в реальном ICPC, а просто соревнуются в Top Coder или CodeForces, – это копируют и вставляют шаблон, который включает все заголовки, включает основную функцию, но также имеет тонна макросов определена. Куча которых на самом деле похожи на макросы для циклов, потому что вы можете сокращать как или же 20 символы, которые вы должны ввести с помощью простого макрос.

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

Программирование на GPU – это программирование массива

Адам: Это не просто конкурентное кодирование, которое имеет сходство со стилем программирования массивов Артура. Но наука о данных в некотором роде тоже очень похожа на APL. И по странному совпадению, когда Конор был глубоко в APL, он ушел из Amazon в NVidia, чтобы работать над библиотекой науки о данных с ускорением на GPU.

Конор: Да, это безумие, что это произошло, что теперь я работаю над библиотекой с открытым исходным кодом, вдохновленной пандами, а панды были написаны отдельным человеком. по имени Уэс МакКинни, который раньше работал в фирме AQR, занимающейся количественной оценкой. И он находился под непосредственным влиянием J, дочернего языка APL.

Адам: В NVidia способность Конора решать что-то в стиле APL очень удобна для написания кода, который будет распределяться по тысячам ядер. современный GPU.

Конор: Например, мы ранее объясняли сокращение количества сканирований. Сокращение – это то, что в основном вы берете элемент и применяете к нему бинарную операцию. Вы можете делать это последовательно, просто беря по одному элементу за раз. И если у вас есть пять чисел, 1, 1, 1, 1, 1, вы можете просто пройти, и один плюс один равен двум, два плюс один равен трем и так далее. Это последовательный алгоритм.

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

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

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

Адам: Почему язык массивов, почему это полезно для их выражения?

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

Итак, сокращения и сканирование – две наиболее распространенные операции в APL. И если вы посмотрите на библиотеку с открытым исходным кодом, которую NVidia выпускает под названием Thrust, которая, по сути, представляет собой просто ускоренные на GPU версии стандартной библиотеки и C ++, у них в основном есть постоянное уменьшение или уменьшение тяги и включающее и эксклюзивное сканирование тяги, которое это всего лишь две разные версии сканирования. И это параллельные алгоритмы хлеба с маслом. Итак, многие примитивы в APL просто распараллеливаются по своей сути.

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

Адам: На самом деле это не случайность. Как будто этот язык был разработан Айверсоном, чтобы иметь возможность воспринимать эти массивы и матрицы. И из-за этого он в конечном итоге имеет такую ​​форму, в которой он оказывается параллельным по данным. А то вроде бы графические процессоры существуют. И разве это не удобно? Графические процессоры великолепны, если вы можете обрабатывать данные параллельно.

Конор: Совершенно верно. Да, все в порядке. Итак, все работает отлично.

Изучение парадигм программирования

Адам: Есть клише о том, что разные парадигмы программирования меняют ваш образ мышления. Иногда я думаю, когда слышу это, я немного закатываю глаза, но в этом определенно есть правда. И трудно понять, где именно правда.

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

Конор все еще работает на C ++. Но когда он это делает, иногда он думает о том, как бы решить проблему в APL. И я думаю, что та другая точка зрения, которую вы привносите в свой основной язык программирования, это сила обучения тому, как решать проблемы в другой парадигме.

Окончание

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

Кроме того, Конор, Боб Териолт и несколько других начали подкасты, посвященные языкам программирования массивов. Я также помещу ссылку на это на странице эпизода. До следующего раза большое спасибо за внимание.

Выдержка из программирования массива

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

Адам: Сделайте обратную кавычку на четвертой смене, вот и все.

Конор: Да.

Адам: Я смотрю на странную стрелку, указывающую на точку … Что это? Это треугольник?

Конор: Это треугольник с линией, проходящей через него. Ага.

Адам: Со сквозной строкой, хорошо.

Конор: А затем снова введите X и правую скобку.

Адам: Правая скобка.

Конор: А затем нажмите Enter.

Адам: Хорошо. Позвольте мне взглянуть, стрелка вверх вправо.

Конор: Или да, стрелка вверх тоже может сработать. А затем, если вы поставите шестерку в начале выражения, а затем сделаете обратную кавычку, сдвиньте шесть. Это транспонирование.

Адам: Обратный ответ.

Конор: Так, да, обратная смена шестая. Может я ошибаюсь. О нет, извините, без смены. Обратный апостроф шесть.

Адам: Упс, обратная кавычка на шесть. Вот и все.

Конор: Итак, если вы сейчас нажмете Enter, мы получим наш логический массив.

Адам: О, хорошо.