Четыре огромные сферы передовой деятельности для умных программистов

Начнём издалека.

Возьмём две классические сортировки: вставкой (сложность O(N?)) и слиянием O(N * log N). У merge sort ещё большой коэффициент, значительно больше чем у insert sort.

Даём на вход каждому алгоритму 10 миллионов элементов.

Допустим, у нас есть два компьютера: новый (10 ГГц) и старый (10 МГц).

Коэффициент для сортировки слиянием берут часто 50, для вставки - 2, т.е. в 25 раз больше коэффициент для merge sort.

Для быстрого компьютера получаем

2 * (10^7)^2 / 10^10 = 20,000 секунд

Для медленного компьютера получаем:

50 * 10^7 * log 10^7 / 10^7 = 1163 секунды

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

Вчера я говорил, что закон Мура всё

https://vk.com/wall-152484379_784

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

Ага, щас :)

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

Во-вторых, при увеличении количества ядер стремительно растёт аппаратный оверхед (корректное управление доступом к памяти например), и линейной масштабируемости тут не добиться в принципе. Собственно, это было понятно ещё в 1967-м году, когда американский математик Джин Амдал, считающийся самым великим проектировщиком компьютерных систем 20-го века (IBM System/360, да), сформулировал свой закон, фундаментальное ограничение:

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

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

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

Есть четыре огромные, быстро растущие сферы ИТ, где это всё крайне востребовано.

1) Объёмы данных в мире растут экспоненциально, мэйнстрим этим штампом уже все уши прожужжал, но это действительно так. Пресловутая BigData, поисковые движки, быстрая обработка огромных сырых наборов слабо структурированных данных...

Однако не думайте, что это просто взять да прикрутить map/reduce, которые автоматически распраллелятся, не-не-не

По международным стандартам обучения в университетах мира интеллектуальной элиты -- ACM/IEEE Computing Curricula (я кстати вступил в этом декабре в ACM), тут надо прежде всего грузить в мозг так называемые квазилинейные алгоритмы, которые сегодня проходят только в трёх местах: МФТИ, ВМиК МГУ и ШАД Яндекса. Совсем скоро будет и в нашей Школе! :)

2) Машинное обучение, растёт невероятно, движков мало, и вот там как раз полным-полно алгоритмов, на каждом шагу надо хорошо знать и уметь правильно применять. Только -- сюрприз -- абсолютно не тех алгоритмов, которым вас учили в университете.

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

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

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

https://vk.com/wall-152484379_704

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

Источник: m.vk.com

Комментарии: