00:19 Введение
04:33 Две определения “алгоритма”
08:09 Большая О
13:10 До сих пор
15:11 Вспомогательные науки (краткое повторение)
17:26 Современные алгоритмы
19:36 Превосходство над “оптимальностью”
22:23 Структуры данных - 1/4 - Список
25:50 Структуры данных - 2/4 - Дерево
27:39 Структуры данных - 3/4 - Граф
29:55 Структуры данных - 4/4 - Хэш-таблица
31:30 Волшебные рецепты - 1/2
37:06 Волшебные рецепты - 2/2
39:17 Тензорные компрехеншены - 1/3 - Обозначение “Эйнштейна”
42:53 Тензорные компрехеншены - 2/3 - Прорыв команды Facebook
46:52 Тензорные компрехеншены - 3/3 - Взгляд на цепь поставок
52:20 Метатехники - 1/3 - Сжатие
56:11 Метатехники - 2/3 - Мемоизация
58:44 Метатехники - 3/3 - Неизменяемость
01:03:46 Заключение
01:06:41 Предстоящая лекция и вопросы аудитории
Описание
Оптимизация цепей поставок основана на решении множества числовых задач. Алгоритмы - это высокоформализованные числовые рецепты, предназначенные для решения конкретных вычислительных задач. Превосходные алгоритмы означают, что с меньшими вычислительными ресурсами можно достичь превосходных результатов. Фокусировка на особенностях цепей поставок позволяет значительно улучшить алгоритмическую производительность, иногда на несколько порядков. “Алгоритмы цепей поставок” также должны учитывать разработку современных компьютеров, которая значительно изменилась за последние несколько десятилетий.
Полный транскрипт
Добро пожаловать на эту серию лекций по цепям поставок. Я - Жоанн Верморель, и сегодня я буду представлять “Современные алгоритмы для цепей поставок”. Превосходные вычислительные возможности являются ключевыми для достижения превосходной эффективности цепей поставок. Более точные прогнозы, более точная оптимизация и более частая оптимизация - все это желательно для достижения превосходной эффективности цепей поставок. Всегда существует превосходный численный метод, немного превышающий вычислительные ресурсы, которые вы можете себе позволить.
Алгоритмы, чтобы упростить, ускоряют работу компьютеров. Алгоритмы являются отраслью математики, и это очень активное направление исследований. Прогресс в этой области исследований часто превосходит прогресс аппаратного обеспечения самого компьютера. Цель этой лекции - понять, в чем суть современных алгоритмов и, более конкретно, с точки зрения управления цепями поставок, как подходить к проблемам, чтобы вы могли максимально использовать эти современные алгоритмы для вашей цепи поставок.
В терминах алгоритмов есть одна книга, которая является абсолютным эталоном: “Введение в алгоритмы”, впервые опубликованная в 1990 году. Это книга, которую обязательно нужно прочитать. Качество презентации и написания просто потрясающее. Эта книга продала более полумиллиона экземпляров за первые 20 лет своей жизни и вдохновила целое поколение академических писателей. Фактически, большинство недавних книг по управлению цепями поставок, посвященных теории управления цепями поставок, которые были опубликованы в последнее десятилетие, часто сильно вдохновлены стилем и презентацией, найденными в этой книге.
Лично я прочитал эту книгу в 1997 году, и это был французский перевод первого издания. Она имела глубокое влияние на всю мою карьеру. После прочтения этой книги я никогда не видел программное обеспечение таким же. Однако стоит отметить, что эта книга принимает точку зрения о компьютерном оборудовании, которая была распространена в конце 80-х и начале 90-х годов. Как мы видели в предыдущих лекциях этой серии, компьютерное оборудование претерпело значительные изменения за последние несколько десятилетий, и некоторые из предположений, сделанных в этой книге, кажутся относительно устаревшими. Например, книга предполагает, что доступ к памяти имеет постоянное время, независимо от того, сколько памяти вы хотите адресовать. Так современные компьютеры уже не работают.
Тем не менее, я считаю, что есть определенные ситуации, когда упрощение является разумным предложением, если взамен вы получаете гораздо большую ясность и простоту изложения. Эта книга прекрасно справляется с этим. Хотя я рекомендую помнить, что некоторые из ключевых предположений, сделанных в книге, устарели, она остается абсолютным эталоном, который я рекомендую всей аудитории.
Давайте проясним термин “алгоритм” для аудитории, которая может быть не очень знакома с этим понятием. Существует классическое определение, согласно которому алгоритм - это конечная последовательность четко определенных инструкций для компьютера. Это такое определение, которое вы найдете в учебниках или на Википедии. Хотя классическое определение алгоритма имеет свои достоинства, я считаю, что оно не впечатляет, так как не уточняет намерение, связанное с алгоритмами. Нас не интересует любая последовательность инструкций; нас интересует очень конкретная последовательность инструкций для компьютера. Таким образом, я предлагаю личное определение термина “алгоритм”: алгоритм в основном является методом программного обеспечения, направленным на решение проблемы с акцентом на производительность и детализацию.
Разберем это определение, хорошо? Во-первых, часть, связанная с решением проблемы: алгоритм полностью характеризуется проблемой, которую он пытается решить. На этом слайде вы можете видеть псевдокод алгоритма быстрой сортировки, который является популярным и хорошо известным алгоритмом. Быстрая сортировка пытается решить проблему сортировки, которая заключается в следующем: у вас есть массив, содержащий элементы данных, и вы хотите, чтобы алгоритм вернул тот же самый массив, но с отсортированными элементами в порядке возрастания. Алгоритмы сосредоточены на конкретной и четко определенной проблеме.
Второй аспект - как вы определяете, что у вас есть лучший алгоритм. Лучший алгоритм - это то, что позволяет вам решить ту же самую проблему с меньшими вычислительными ресурсами, что на практике означает быстрее. Наконец, есть аспект детализации. Когда мы говорим о термине “алгоритмы”, мы имеем в виду, что мы хотим рассмотреть очень элементарные проблемы, которые являются модульными и могут быть бесконечно комбинированы для решения гораздо более сложных проблем. Вот в чем суть алгоритмов.
Одним из ключевых достижений теории алгоритмов является предоставление характеристики производительности алгоритмов в достаточно абстрактной форме. Сегодня у меня не будет времени углубляться в детали этой характеристики и математическую основу. Идея заключается в том, что для характеристики алгоритма мы хотим рассмотреть его асимптотическое поведение. У нас есть проблема, которая зависит от одного или нескольких ключевых узких мест, характеризующих проблему. Например, в проблеме сортировки, которую я ранее представил, характеристическим измерением обычно является количество элементов, которые нужно отсортировать. Вопрос в том, что происходит, когда массив элементов, который нужно отсортировать, становится очень большим? Я буду обозначать это характеристическое измерение числом “n” по соглашению.
Теперь у меня есть такая нотация, как нотация “Big O”, с которой вы могли сталкиваться при работе с алгоритмами. Я просто собираюсь наметить несколько элементов, чтобы дать вам представление о том, что происходит. Во-первых, допустим, у нас есть набор данных, и мы хотим извлечь простую статистическую индикатор, например, среднее значение. Если я говорю, что у меня есть алгоритм с нотацией Big O равной 1, это означает, что я могу вернуть решение этой проблемы (вычисление среднего значения) за постоянное время, независимо от того, является ли набор данных маленьким или большим. Постоянное время, или Big O равное 1, является абсолютным требованием, когда вы хотите делать что-то в режиме реального времени в смысле машинного взаимодействия. Если у вас нет чего-то, что работает за постоянное время, то очень сложно, иногда невозможно, достичь реального времени.
Обычно еще одним ключевым аспектом производительности является Big O равное N. Big O равное N означает, что сложность алгоритма строго линейна относительно размера интересующего нас набора данных. Это то, что вы получаете, когда у вас есть эффективная реализация, которая может решить проблему, просто прочитав данные один раз или фиксированное количество раз. Сложность Big O равная N обычно совместима только с пакетным выполнением. Если вы хотите иметь что-то, что работает онлайн и в режиме реального времени, вы не можете иметь что-то, что проходит через весь набор данных, если только вы не знаете, что ваш набор данных имеет фиксированный размер.
Помимо линейности, у вас есть Big O равное N в квадрате. Big O равное N в квадрате - это очень интересный случай, потому что это точка взрыва производительности. Это означает, что сложность растет квадратично относительно размера набора данных, что означает, что если у вас в 10 раз больше данных, ваша производительность будет в 100 раз хуже. Это обычно тот вид производительности, в котором вы не увидите никаких проблем в прототипе, потому что вы работаете с небольшими наборами данных. Вы не увидите никаких проблем на этапе тестирования, потому что, снова же, вы работаете с небольшими наборами данных. Как только вы переходите к производству, у вас есть программное обеспечение, которое работает очень медленно. Очень часто в мире предприятийного программного обеспечения, особенно в мире предприятийного программного обеспечения для цепочки поставок, большинство проблем с плохой производительностью, которые можно наблюдать на практике, на самом деле вызваны квадратичными алгоритмами, которые не были идентифицированы. В результате вы наблюдаете квадратичное поведение, которое очень медленное. Эта проблема не была идентифицирована заранее, потому что современные компьютеры довольно быстрые, и N в квадрате не так плохо, пока N достаточно маленькое. Однако, как только вы имеете дело с большим набором данных в масштабе производства, это сильно затрудняет работу.
Эта лекция на самом деле является второй лекцией моей четвертой главы в этой серии лекций по цепям поставок. В первой главе, прологе, я представил свои взгляды на цепи поставок как на область исследования и практики. Мы видели, что цепи поставок - это большая коллекция сложных проблем, в отличие от простых проблем. Сложные проблемы нельзя решать наивными методами, потому что повсюду присутствуют антагонистические поведения, и поэтому нужно уделять большое внимание самой методологии. Большинство наивных методов терпят крах весьма зрелищным образом. Именно это я сделал во второй главе, которая полностью посвящена методологиям, подходящим для изучения цепей поставок и улучшения практики управления цепями поставок. Третья глава, которая еще не завершена, по сути, является углубленным изучением того, что я называю “персоналом цепи поставок”, очень специфической методологией, где мы фокусируемся на самих проблемах, а не на решениях, которые мы можем предложить для их решения. В будущем я буду чередовать главу номер три и настоящую главу, которая посвящена вспомогательным наукам цепи поставок.
Во время последней лекции мы увидели, что мы можем получить больше вычислительных возможностей для нашей цепи поставок благодаря лучшему, более современному вычислительному оборудованию. Сегодня мы смотрим на проблему с другой стороны - мы ищем больше вычислительных возможностей, потому что у нас есть лучшее программное обеспечение. В этом и заключается суть алгоритмов.
Краткое повторение: вспомогательные науки - это взгляд на саму цепь поставок. Сегодняшняя лекция не строго говоря о цепи поставок; она о алгоритмах. Однако я считаю, что это имеет фундаментальное значение для цепи поставок. Цепь поставок не является изолированным явлением; прогресс, который может быть достигнут в цепи поставок, в значительной степени зависит от прогресса, который уже был достигнут в других смежных областях. Я называю эти области вспомогательными науками цепи поставок.
Я считаю, что ситуация довольно похожа на отношение между медицинскими науками и химией в 19 веке. В самом начале 19 века медицинские науки совершенно не интересовались химией. Химия была все еще новичком и не считалась действительным предложением для реального пациента. Перейдем к 21 веку, и предложение, что вы можете быть отличным врачом, ничего не зная о химии, будет считаться абсолютно нелепым. Согласно общему мнению, быть отличным химиком не делает вас отличным врачом, но общепринято считать, что если вы ничего не знаете о химии организма, вы не можете быть компетентным в современных медицинских науках. Мое представление о будущем заключается в том, что в течение 21 века область цепи поставок начнет рассматривать область алгоритмов практически так же, как область медицинских наук начала смотреть на химию в 19 веке.
Алгоритмы - это огромная область исследований, ветвь математики, и сегодня мы только коснемся поверхности этой области исследований. В частности, эта область исследований накопила потрясающие результаты на протяжении десятилетий. Это может быть довольно теоретическая область исследований, но это не означает, что это просто теория. Фактически, это область исследований, которая довольно теоретическая, но в ней было множество открытий, которые нашли свое применение в производстве.
Фактически, любой смартфон или компьютер, которыми вы пользуетесь сегодня, буквально использует десятки тысяч алгоритмов, которые изначально были опубликованы где-то. Этот успех на самом деле гораздо впечатляющий по сравнению с теорией цепей поставок, где подавляющее большинство цепей поставок не функционируют на основе результатов теории цепей поставок, пока что. Когда речь идет о современных компьютерах и современных алгоритмах, практически все, что связано с программным обеспечением, полностью определяется всеми этими десятилетиями исследований в области алгоритмов. Это является основой практически каждого компьютера, который мы используем сегодня.
На сегодняшнюю лекцию я отобрал список тем, которые, по моему мнению, являются довольно иллюстративными для того, что вам следует знать, чтобы подойти к теме современных алгоритмов. Сначала мы обсудим, как мы можем превзойти предположительно оптимальные алгоритмы, особенно для цепи поставок. Затем мы кратко рассмотрим структуры данных, а затем - магические рецепты, сжатие тензоров и, наконец, мета-техники.
Сначала я хотел бы прояснить, что я имею в виду под “алгоритмами для цепи поставок”. Я не имею в виду алгоритмы, предназначенные для решения специфических проблем цепи поставок. Правильная перспектива заключается в том, чтобы рассмотреть классические алгоритмы для классических проблем и пересмотреть эти классические проблемы с точки зрения цепи поставок, чтобы увидеть, можем ли мы действительно сделать что-то лучше. Ответ - да, мы можем.
Например, алгоритм быстрой сортировки, согласно общей теории алгоритмов, является оптимальным в том смысле, что вы не можете представить алгоритм, который будет произвольно лучше быстрой сортировки. Таким образом, с этой точки зрения быстрая сортировка настолько хороша, насколько это возможно. Однако, если мы сосредоточимся на цепи поставок, то можно достичь поразительного ускорения. В частности, если мы рассмотрим проблемы сортировки, где мощность интересующих нас наборов данных низкая, такие как даты, цены, уровни запасов или категории, все они являются наборами данных с низкой мощностью. Таким образом, если у вас есть дополнительные предположения, например, нахождение в ситуации с низкой мощностью, то вы можете использовать алгоритм “карманная сортировка”. В производстве существует множество ситуаций, когда можно достичь абсолютно гигантского ускорения, например, в 500 раз быстрее, чем быстрая сортировка. Таким образом, вы можете быть на порядки быстрее, чем предполагалось оптимальным, просто потому что вы не находитесь в общем случае, а в случае цепи поставок. Это очень важно, и я считаю, что здесь лежит суть ключевых поразительных результатов, которые мы можем достичь, используя алгоритмы для цепи поставок.
Я считаю, что эта перспектива ошибочна по крайней мере по двум причинам. Во-первых, как мы видели, не всегда стандартный алгоритм является интересным. Мы видели, что есть предположительно оптимальный алгоритм, такой как быстрая сортировка, но если вы рассмотрите ту же самую проблему с точки зрения цепи поставок, вы можете достичь огромного ускорения. Таким образом, знакомство с алгоритмами является первостепенным интересом, чтобы иметь возможность пересмотреть классику и достичь огромного ускорения просто потому, что вы не находитесь в общем случае, а в случае цепи поставок.
Вторая причина, по которой я считаю, что эта перспектива ошибочна, заключается в том, что алгоритмы очень сильно связаны со структурами данных. Структуры данных - это способы организации данных, чтобы вы могли работать с данными более эффективно. Интересно то, что все эти структуры данных формируют своего рода словарь, и иметь доступ к этому словарю является необходимым условием, чтобы иметь возможность описывать ситуации в цепи поставок таким образом, чтобы они легко переводились в программное обеспечение. Если вы начинаете с описания с использованием терминов для неспециалистов, то обычно получаете вещи, которые чрезвычайно сложно перевести в программное обеспечение. Если вы ожидаете, что программный инженер, который ничего не знает о цепи поставок, реализует этот перевод для вас, это может быть проблемой. На самом деле, намного проще, если вы знаете этот словарь, чтобы вы могли непосредственно говорить терминами, которые легко переводятся в идеи, которые у вас есть, в программное обеспечение.
Давайте рассмотрим самые популярные и простые структуры данных. Первой из них будет список. Список можно использовать, например, для представления маршрута доставки, который будет последовательностью доставок, с одной записью на каждую доставку. Вы можете перечислить маршрут доставки по мере его прохождения. Список также может представлять рабочий процесс, который является последовательностью операций, необходимых для производства определенного оборудования, или цепочку команд, которая определяет, кто должен принимать определенные решения.
Аналогично, деревья являются еще одной всеобщей структурой данных. Кстати, алгоритмические деревья перевернуты вверх ногами, с корнем сверху и ветвями внизу. Деревья позволяют описывать все виды иерархий, а сети поставок имеют иерархии повсюду. Например, ведомость материалов - это дерево; у вас есть оборудование, которое вы хотите произвести, и это оборудование состоит из сборок. Каждая сборка состоит из подсборок, а каждая подсборка состоит из деталей. Если вы полностью развернете ведомость материалов, вы получите дерево. Аналогично, каталог продуктов, где у вас есть семейства продуктов, категории продуктов, продукты, подкатегории и т. д., очень часто имеет древовидную архитектуру. Организационная структура, с генеральным директором на вершине, руководителями уровня C ниже и так далее, также представлена деревом. Алгоритмическая теория дает вам множество инструментов и методов для обработки деревьев и эффективного выполнения операций над ними. Когда вы можете представить данные в виде дерева, у вас есть целый арсенал математических методов для эффективной работы с этими деревьями. Вот почему это представляет большой интерес.
Теперь графы позволяют описывать все виды сетей. Кстати, граф в математическом смысле - это набор вершин и набор ребер, причем ребра соединяют две вершины вместе. Термин “граф” может быть немного обманчивым, потому что он не имеет ничего общего с графикой. Граф - это просто математический объект, а не рисунок или что-то графическое. Когда вы знаете, как искать графы, вы увидите, что сети поставок имеют графы повсюду.
Несколько примеров: ассортимент в розничной сети, который фундаментально является двудольным графом, соединяет продукты и магазины. Если у вас есть программа лояльности, где вы записываете, какой клиент купил какой продукт со временем, у вас есть еще один двудольный граф, соединяющий клиентов и продукты. В автомобильной отрасли, где вам нужно выполнить ремонт, вам обычно нужно использовать матрицу совместимости, которая сообщает вам список деталей, которые имеют механическую совместимость с интересующим вас транспортным средством. Эта матрица совместимости по сути является графом. Существует огромное количество литературы по всевозможным алгоритмам, которые позволяют работать с графами, поэтому это очень интересно, когда вы можете характеризовать проблему как поддерживаемую графовой структурой, потому что все методы, известные в литературе, становятся немедленно доступными.
Наконец, последняя структура данных, которую я рассмотрю сегодня, - это хэш-таблица. Хэш-таблица по сути является швейцарским ножом алгоритмов. Она не нова; ни одна из представленных мной структур данных не является новой по каким-либо стандартам. Хэш-таблица, вероятно, самая новая из всех, она появилась в 1950-х годах, поэтому она не новая. Тем не менее, хэш-таблица - это невероятно полезная структура данных. Это контейнер, который содержит пары ключей и значений. Идея заключается в том, что с помощью этого контейнера вы можете хранить большое количество данных, и он дает вам производительность O(1) для поиска, вставки и удаления. У вас есть контейнер, в котором вы можете в константное время добавлять данные, проверять, присутствуют ли данные (просматривая ключ) и, возможно, удалять данные. Это очень интересно и полезно. Хэш-таблицы буквально повсюду и широко используются внутри других алгоритмов.
Одна вещь, на которую я обращу внимание, и мы вернемся к этому позже, заключается в том, что производительность хэш-таблицы в значительной степени зависит от производительности хэш-функции, которую у вас есть.
Теперь давайте рассмотрим волшебные рецепты, и мы полностью перейдем к другой перспективе. Волшебные числа являются фундаментальным анти-паттерном. В предыдущей лекции, той, которая касается отрицательных знаний для цепочки поставок, мы обсудили, как анти-паттерны обычно начинаются с хороших намерений, но заканчиваются непредвиденными последствиями, которые уничтожают преимущества, предположительно принесенные решением. Волшебные числа - это хорошо известный анти-паттерн программирования. Этот анти-паттерн программирования состоит в написании кода, усеянного константами, которые кажутся совершенно ниоткуда, делая ваше программное обеспечение очень сложным для поддержки. Когда у вас есть тонны констант, неясно, почему у вас есть эти ограничения и как они были выбраны.
Обычно, когда вы видите волшебные числа в программе, лучше изолировать все эти константы в месте, где они более управляемы. Однако есть ситуации, когда тщательный выбор констант делает что-то совершенно неожиданное, и у вас есть почти волшебные, совершенно непреднамеренные преимущества использования чисел, которые, казалось бы, упали с неба. Вот о чем именно речь в очень коротком алгоритме, который я здесь представляю.
В цепочке поставок очень часто мы хотим иметь возможность достичь симуляции определенного вида. Симуляции или процессы Монте-Карло - это один из основных трюков, которые вы можете использовать во множестве ситуаций цепочки поставок. Однако производительность вашей симуляции в значительной степени зависит от вашей способности генерировать случайные числа. Для генерации симуляций обычно используется степень сгенерированной случайности, и поэтому вам нужен алгоритм для генерации этой случайности. Что касается компьютеров, это обычно псевдослучайность - это не настоящая случайность; это просто нечто, похожее на случайные числа и имеющее статистические свойства случайных чисел, но на самом деле не случайное.
Вопрос заключается в том, насколько эффективно вы можете генерировать случайные числа? Оказывается, есть алгоритм, называемый “Shift”, опубликованный в 2003 году Джорджем Марсальей, который довольно впечатляет. Этот алгоритм генерирует очень качественные случайные числа, создавая полную перестановку 2 в степени 64 минус 1 бит. Он будет циркулировать через все комбинации из 64 бит, минус один, с нулем в качестве фиксированной точки. Он делает это с помощью всего шести операций: трех двоичных сдвигов и трех операций XOR (исключающее ИЛИ), которые являются побитовыми операциями. Сдвиги также являются побитовыми операциями.
Мы видим, что в середине есть три волшебных числа: 13, 7 и 17. Кстати, все эти числа являются простыми числами; это не случайность. Оказывается, что если вы выберете эти очень конкретные константы, вы получите отличный генератор случайных чисел, который оказывается очень быстрым. Когда я говорю “очень быстро”, я имею в виду, что вы буквально можете генерировать 10 мегабайт в секунду случайных чисел. Это абсолютно огромно. Если мы вернемся к предыдущей лекции, мы можем увидеть, почему этот алгоритм также настолько эффективен. У нас не только шесть инструкций, которые непосредственно отображаются на инструкции, поддерживаемые нативно поддерживаемым аппаратным обеспечением, таким как процессор, но и у нас нет никаких ветвлений. Нет теста, и это означает, что этот алгоритм, после выполнения, будет использовать максимальную пропускную способность конвейеризации процессора, потому что здесь нет ветвления. Мы буквально можем использовать максимальную глубину конвейеризации, которую мы имеем в современном процессоре. Это очень интересно.
Вопрос в том, можем ли мы выбрать другие числа, чтобы этот алгоритм работал? Ответ - нет. Есть всего несколько десятков или, может быть, около сотни различных комбинаций чисел, которые на самом деле будут работать, и все остальные дадут вам генератор чисел очень низкого качества. Вот где это волшебно. Вы видите, это недавний тренд в разработке алгоритмов - найти что-то совершенно неожиданное, где вы находите какую-то полу-волшебную константу, которая дает вам совершенно непреднамеренные преимущества путем смешивания очень неожиданных бинарных операций определенного вида. Генерация случайных чисел имеет критическое значение для цепочки поставок.
Но, как я уже говорил, хэш-таблицы повсюду, и также очень интересно иметь супер-производительную универсальную хэш-функцию. Существует ли она? Да. Существуют целые классы хэш-функций, доступных уже десятилетиями, но в 2019 году был опубликован еще один алгоритм, который обеспечивает рекордную производительность. Это тот, который вы видите на экране, “WyHash” от Ван Йи. По сути, вы можете видеть, что структура очень похожа на алгоритм XORShift. Это алгоритм без ветвления, как и XORShift, и также использует операцию XOR. Алгоритм использует шесть инструкций: четыре операции XOR и две операции Multiply-No-Flags.
Multiply-No-Flags - это просто обычное умножение двух 64-битных целых чисел, и в результате вы получаете старшие 64 бита и младшие 64 бита. Это фактическая инструкция, доступная в современных процессорах, реализованная на аппаратном уровне, поэтому она считается всего одной инструкцией компьютера. У нас есть две таких инструкции. Опять же, у нас есть три волшебных числа, записанных в шестнадцатеричной форме. Кстати, это простые числа, снова полностью полумагические. Если вы примените этот алгоритм, у вас будет абсолютно отличная нешифровальная хэш-функция, которая работает почти со скоростью memcpy. Она очень быстрая и представляет большой интерес.
Теперь давайте снова перейдем к чему-то совершенно другому. Успех глубокого обучения и многих других современных методов машинного обучения заключается в нескольких ключевых алгоритмических идеях по проблемам, которые могут быть массово ускорены специализированным аппаратным обеспечением. Об этом я говорил в своей предыдущей лекции, когда говорил о процессорах с суперскалярными инструкциями и, если хотите большего, о GPU и даже TPU. Давайте вернемся к этой идее, чтобы увидеть, как все это возникло довольно хаотично. Однако я считаю, что соответствующие идеи укрепились за последние несколько лет. Чтобы понять, где мы находимся сегодня, нам нужно вернуться к эйнштейновской нотации, которая была введена немного более ста лет назад Альбертом Эйнштейном в одной из его статей. Интуиция проста: у вас есть выражение y, которое является суммой от i равного 1 до i равного 3 c_y, умноженное на x_y. У нас есть выражения, записанные таким образом, и идея эйнштейновской нотации заключается в том, чтобы полностью опустить суммирование. В программном плане суммирование было бы циклом for. Идея заключается в том, чтобы полностью опустить суммирование и сказать, что по соглашению мы делаем суммирование по всем индексам для переменной i, которые имеют смысл.
Эта простая интуиция приводит к двум очень удивительным, но положительным результатам. Первый - это правильность проектирования. Когда мы явно записываем сумму, мы рискуем не иметь правильных индексов, что может привести к ошибкам выхода индекса за границы в программном обеспечении. Удалением явного суммирования и утверждением, что мы возьмем все допустимые позиции индексов по определению, мы получаем подход, правильный по своей сути. Это само по себе является первостепенным интересом и связано с массивным программированием, парадигмой программирования, о которой я кратко упоминал в одной из своих предыдущих лекций.
Второе открытие, которое является более новым и в настоящее время представляет большой интерес, заключается в том, что если вы можете записать свою проблему в форме, в которой применима эйнштейновская нотация, ваша проблема может получить значительное аппаратное ускорение на практике. Это изменяющий игру элемент.
Чтобы понять почему, есть очень интересная статья под названием “Tensor Comprehensions”, опубликованная в 2018 году исследовательской командой Facebook. Они представили понятие тензорных пониманий. Сначала позвольте мне определить два слова. В области компьютерных наук тензор по сути является многомерной матрицей (в физике тензоры совершенно другие). Скалярное значение является тензором нулевой размерности, вектор - тензором первой размерности, матрица - тензором второй размерности, и вы можете иметь тензоры с еще более высокими размерностями. Тензоры - это объекты с прикрепленными к ним свойствами, подобными массивам.
Понимание - это нечто похожее на алгебру с четырьмя основными операциями - плюс, минус, умножение и деление - а также другими операциями. Оно более обширно, чем обычная арифметическая алгебра; поэтому у них есть понимание тензоров вместо тензорной алгебры. Оно более всестороннее, но не такое выразительное, как полноценный язык программирования. Когда у вас есть понимание, оно более ограничено, чем полноценный язык программирования, где вы можете делать все, что хотите.
Идея заключается в том, что если вы посмотрите на функцию MV (def MV), она в основном является функцией, и MV означает матрица-вектор. В данном случае это умножение матрицы A на вектор X. Мы видим в этом определении, что используется эйнштейновская нотация: мы пишем C_i = A_ik * X_k. Какие значения мы должны выбрать для i и k? Ответом являются все допустимые комбинации для этих переменных, которые являются индексами. Мы берем все допустимые значения индексов, выполняем суммирование, и на практике это дает нам умножение матрицы на вектор.
Внизу экрана вы можете увидеть ту же самую функцию MV, переписанную с помощью циклов for, явно указывающих диапазоны значений. Основное достижение команды исследований Facebook заключается в том, что каждый раз, когда вы можете написать программу с помощью этого синтаксиса понимания тензоров, они разработали компилятор, который позволяет вам широко использовать аппаратное ускорение с использованием графических процессоров. По сути, они позволяют вам ускорить любую программу, которую вы можете написать с помощью этого синтаксиса понимания тензоров. Каждый раз, когда вы можете написать программу в этой форме, вы будете получать значительное аппаратное ускорение, и мы говорим о чем-то, что будет в два порядка быстрее, чем обычный процессор. Это потрясающий результат сам по себе.
Теперь давайте посмотрим, что мы можем сделать с точки зрения цепочки поставок с помощью этого подхода. Одно из ключевых интересов для современной практики управления цепочками поставок - это вероятностное прогнозирование. Вероятностное прогнозирование, о котором я говорил в предыдущей лекции, заключается в том, что вы не будете иметь точечный прогноз, а вместо этого будете прогнозировать все различные вероятности для интересующей вас переменной. Давайте рассмотрим, например, прогноз срока поставки. Вы хотите прогнозировать срок поставки и иметь вероятностный прогноз срока поставки.
Теперь предположим, что ваш срок поставки может быть разделен на срок производства и срок транспортировки. На практике у вас, скорее всего, есть вероятностный прогноз для срока производства, который будет дискретной случайной величиной, давая вам вероятность наблюдения времени в один день, два дня, три дня, четыре дня и т.д. Вы можете представить себе это как большую гистограмму, которая дает вам вероятности наблюдения этой продолжительности для срока производства. Затем у вас будет аналогичный процесс для срока транспортировки, с другой дискретной случайной величиной, предоставляющей вероятностный прогноз.
Теперь вы хотите рассчитать общий срок поставки. Если прогнозируемые сроки поставки были бы числами, вы просто сложили бы их. Однако два прогнозируемых срока поставки не являются числами; они являются вероятностными распределениями. Поэтому нам нужно объединить эти два вероятностных распределения, чтобы получить третье вероятностное распределение, которое является вероятностным распределением для общего срока поставки. Оказывается, что если мы сделаем предположение, что два срока поставки, срок производства и срок транспортировки, являются независимыми, то операция, которую мы можем выполнить для выполнения этой суммы случайных величин, является одномерной сверткой. Это может показаться сложным, но на самом деле это не так сложно. То, что я реализовал и что вы можете увидеть на экране, - это реализация одномерной свертки между вектором, представляющим гистограмму вероятностей срока производства (A), и гистограммой, связанной с вероятностными прогнозами срока транспортировки (B). Результатом является общее время, которое является суммой этих вероятностных сроков поставки. Если вы используете синтаксис понимания тензоров, это можно записать в очень компактном однострочном алгоритме.
Теперь, если мы вернемся к обозначению Big O, которое я представил ранее в этой лекции, мы увидим, что у нас фундаментально квадратичный алгоритм. Это Big O от N^2, где N - это характеристический размер массивов A и B. Как я уже упоминал, квадратичная производительность является оптимальной точкой прогнозирования проблем. Итак, что мы можем сделать, чтобы решить эту проблему? Во-первых, мы должны учесть, что это проблема цепочки поставок, и у нас есть закон малых чисел, который мы можем использовать в свою пользу. Как мы обсуждали на предыдущей лекции, цепочки поставок в основном основаны на малых числах. Если мы рассматриваем время выполнения заказа, мы можем разумно предположить, что это время будет меньше, скажем, 400 дней. Это уже довольно долгий период для этой гистограммы вероятности.
Итак, что у нас остается, это Big O от N^2, но с N меньше 400. 400 может быть достаточно большим числом, так как 400 умножить на 400 равно 160 000. Это значительное число, и помните, что добавление к этому распределению вероятности - это очень простая операция. Как только мы начинаем делать вероятностный прогноз, мы хотим объединять наши прогнозы различными способами, и, скорее всего, мы будем делать миллионы таких сверток, просто потому что, фундаментально, эти свертки - это ничто иное, как улучшенное сложение, проецируемое в область случайных величин. Таким образом, даже если мы ограничили N, чтобы он был меньше 400, очень интересно привнести аппаратное ускорение в игру, и именно это мы можем достичь с помощью понимания тензоров.
Главное, что нужно запомнить, это то, что как только вы сможете написать этот алгоритм, вы захотите использовать свои знания о концепциях цепочки поставок, чтобы уточнить применимые предположения, а затем использовать инструменты, которыми вы располагаете, чтобы получить аппаратное ускорение.
Теперь давайте обсудим мета-техники. Мета-техники представляют особый интерес, потому что их можно применять поверх существующих алгоритмов, и, следовательно, если у вас есть алгоритм, есть шанс, что вы сможете использовать одну из этих мета-техник для улучшения его производительности. Первое ключевое открытие - это сжатие, просто потому что меньшие данные означают более быструю обработку. Как мы видели на предыдущей лекции, у нас нет равномерного доступа к памяти. Если вы хотите получить доступ к большему количеству данных, вам нужно получить доступ к различным типам физической памяти, и по мере роста памяти вы переходите к типам памяти, которые намного менее эффективны. Кэш L1 внутри процессора очень маленький, около 64 килобайт, но он очень быстрый. Оперативная память, или основная память, в несколько сотен раз медленнее этого маленького кэша, но у вас может быть терабайт оперативной памяти. Таким образом, очень важно убедиться, что ваши данные как можно меньше, поскольку это практически всегда позволит вашим алгоритмам работать быстрее. В этом отношении есть ряд трюков, которые вы можете использовать.
Во-первых, вы можете очистить и упорядочить свои данные. Это относится к сфере корпоративного программного обеспечения. Когда у вас есть алгоритм, который работает с данными, часто есть много неиспользуемых данных, которые не вносят вклад в решение интересующей задачи. Важно убедиться, что вы не оказываетесь с данными, которые вас интересуют, переплетенными с данными, которые случайно игнорируются.
Вторая идея - это упаковка битов. Есть много ситуаций, когда вы можете упаковать некоторые флаги внутри других элементов, таких как указатели. У вас может быть 64-битный указатель, но очень редко вам действительно нужен 64-битный диапазон адресов. Вы можете пожертвовать несколькими битами вашего указателя, чтобы внедрить некоторые флаги, что позволит вам минимизировать ваши данные с практически никакой потери производительности.
Также вы можете настроить точность. Вам нужна 64-битная точность с плавающей запятой в цепочке поставок? Очень редко вам действительно нужна такая точность. Обычно 32 бита точности достаточно, и даже есть много ситуаций, когда 16 бит точности будет достаточно. Вы можете подумать, что снижение точности несущественно, но часто, когда вы можете разделить размер данных на два, вы не просто ускоряете свой алгоритм в два раза, вы буквально ускоряете его в десять раз. Упаковка данных дает полностью нелинейные преимущества в терминах скорости выполнения.
Наконец, у вас есть кодирование энтропии, которое по сути является сжатием. Однако вы не обязательно хотите использовать алгоритмы, которые так же эффективны для сжатия, как, скажем, алгоритм, используемый для ZIP-архива. Вы хотите что-то, что может быть немного менее эффективным с точки зрения сжатия, но намного быстрее в выполнении.
Сжатие в основном основано на идее того, что вы можете пожертвовать немного дополнительного использования ЦП для уменьшения нагрузки на память, и практически во всех ситуациях это является интересным трюком.
Однако есть ситуации, когда вы хотите сделать совершенно противоположное - пожертвовать памятью, чтобы значительно снизить потребление ЦП. Вот что вы делаете с помощью трюка мемоизации. Мемоизация - это в основном идея, что если функция вызывается много раз во время выполнения вашего решения, и та же функция вызывается с теми же самыми входными данными, вам не нужно вычислять функцию заново. Вы можете записать результат, отложить его (например, в хэш-таблицу), и когда вы снова посетите ту же функцию, вы сможете проверить, содержит ли хэш-таблица уже ключ, связанный с входными данными, или содержит ли хэш-таблица уже результат, потому что он был предварительно вычислен. Если функция, которую вы мемоизируете, очень дорогая, вы можете добиться значительного ускорения. Очень интересно становится, когда вы начинаете использовать мемоизацию не с основной памятью, как мы видели в предыдущей лекции, DRAM очень дорогая. Это становится очень интересным, когда вы начинаете помещать свои результаты на диск или SSD, которые дешевы и обильно представлены. Идея заключается в том, что вы можете обменять SSD на снижение нагрузки на ЦП, что, в некотором смысле, является прямым противоположностью описанного мной сжатия.
Последняя мета-техника - это неизменяемость. Неизменяемые структуры данных в основном являются структурами данных, которые никогда не изменяются. Идея заключается в том, что изменения накладываются сверху. Например, с неизменяемой хэш-таблицей, когда вы добавляете элемент, вы возвращаете новую хэш-таблицу, которая содержит все в старой хэш-таблице плюс новый элемент. Очень наивный способ сделать это - сделать полную копию структуры данных и вернуть всю копию; однако это очень неэффективно. Основная идея с неизменяемыми структурами данных заключается в том, что при изменении структуры данных вы возвращаете новую структуру данных, которая реализует только изменение, но эта новая структура данных перерабатывает все части старой структуры данных, которые не были затронуты.
Почти все классические структуры данных, такие как списки, деревья, графы и хэш-таблицы, имеют свои неизменяемые аналоги. Во многих ситуациях использование таких структур данных является очень интересным. Кстати, есть современные языки программирования, которые полностью приняли неизменяемость, например, Clojure, для тех из вас, кто может быть знаком с этим языком программирования.
Почему это очень интересно? Во-первых, потому что это существенно упрощает параллелизацию алгоритмов. Как мы видели в предыдущей лекции, невозможно найти процессор, работающий на частоте 100 ГГц для обычных настольных компьютеров. Однако вы можете найти машину с 50 ядрами, каждое ядро работает на частоте 2 ГГц. Если вы хотите воспользоваться этими множеством ядер, вам нужно параллелизировать свое выполнение, и тогда ваша параллелизация подвержена очень неприятным ошибкам, называемым гонками. Становится очень сложно понять, правильно ли написан ваш алгоритм или нет, потому что у вас может быть несколько процессоров, которые одновременно пытаются записать в одну и ту же область памяти в компьютере.
Однако, если у вас есть неизменяемые структуры данных, это никогда не происходит по дизайну, потому что после представления структуры данных она никогда не изменится - только появится новая структура данных. Таким образом, вы можете достичь значительного увеличения производительности с помощью неизменяемого подхода, потому что вы можете более легко реализовывать параллельные версии ваших алгоритмов. Имейте в виду, что обычно узкое место при реализации ускорения алгоритма - это время, затрачиваемое на саму реализацию алгоритмов. Если у вас есть что-то, что позволяет вам применять некий принцип безопасной параллельности, вы можете намного быстрее внедрять ускорение алгоритмов с меньшими затратами на количество программистов, задействованных в процессе. Еще одно важное преимущество неизменяемых структур данных заключается в том, что они значительно облегчают отладку. Когда вы деструктивно изменяете структуру данных и сталкиваетесь с ошибкой, может быть очень сложно понять, как вы дошли до этого момента. С помощью отладчика может быть довольно неприятно определить проблему. Интересное в неизменяемых структурах данных заключается в том, что изменения являются недеструктивными, поэтому вы можете видеть предыдущую версию вашей структуры данных и более легко понять, как вы дошли до момента, когда возникает некорректное поведение.
В заключение, лучшие алгоритмы могут ощущаться как сверхспособности. С лучшими алгоритмами вы получаете больше от той же самой вычислительной аппаратуры, и эти преимущества неограничены. Это одноразовое усилие, и затем у вас есть неограниченные возможности, потому что вы получили доступ к более высоким вычислительным возможностям, учитывая ту же самую вычислительную мощность, выделенную на интересующую вас проблему в сфере поставок. Я считаю, что такая перспектива предлагает возможности для массовых улучшений в управлении цепями поставок.
Если мы посмотрим на совершенно другую область, такую как видеоигры, они установили свои собственные алгоритмические традиции и находки, посвященные игровому опыту. Потрясающая графика, которую вы видите в современных видеоиграх, является продуктом сообщества, которое потратило десятилетия на переосмысление всего стека алгоритмов для максимизации качества игрового опыта. В игровой индустрии не ставится целью иметь 3D-модель, которая является правильной с физической или научной точки зрения, а максимизировать воспринимаемое качество в графическом отношении для игрока, и они настроили алгоритмы для достижения потрясающих результатов.
Я считаю, что такая работа только начинается для цепей поставок. Программное обеспечение для управления цепями поставок застряло, и по моему собственному восприятию, мы используем даже не 1% того, что современная вычислительная аппаратура может сделать для нас. Большинство возможностей лежат впереди и могут быть реализованы с помощью алгоритмов, не только алгоритмов цепей поставок, таких как алгоритмы маршрутизации транспортных средств, но и пересмотра классических алгоритмов с точки зрения цепей поставок для достижения массового ускорения по пути.
Теперь я посмотрю на вопросы.
Вопрос: Вы говорили о специфике цепей поставок, таких как небольшие числа. Когда мы заранее знаем, что у нас есть небольшие числа в наших потенциальных решениях, какие конкретные примеры упрощений это привносит? Например, когда мы знаем, что мы можем заказать максимум один или два контейнера, можете ли вы представить какие-либо конкретные примеры того, как это повлияет на уровень детализации голистических прогнозов, которые будут использоваться для вычисления функции вознаграждения за запасы?
Во-первых, все, что я представил сегодня, находится в производстве в Lokad. Все эти идеи, одним или другим образом, очень применимы к цепям поставок, потому что они используются в производстве в Lokad. Вы должны понимать, что то, что вы получаете от современного программного обеспечения, не настроено на максимальное использование вычислительной аппаратуры. Просто подумайте, как я показал в своей последней лекции, у нас сейчас есть компьютеры, которые в тысячу раз более мощные, чем компьютеры несколько десятилетий назад. Работают ли они в тысячу раз быстрее? Нет. Могут ли они решать проблемы, которые фантастически сложнее, чем то, что у нас было несколько десятилетий назад? Нет. Поэтому не недооценивайте тот факт, что есть очень большие возможности для улучшения.
Блочная сортировка, которую я представил в этой лекции, является простым примером. В цепях поставок везде есть операции сортировки, и, насколько мне известно, очень редко встречается предприятие, которое использует специализированные алгоритмы, которые хорошо сочетаются с ситуациями в цепях поставок. Теперь, когда мы знаем, что у нас есть один или два контейнера, мы постоянно пользуемся этими элементами в Lokad, и есть множество трюков, которые можно реализовать на этом уровне.
Трюки обычно находятся на более низком уровне, и выгоды просто распространяются на всю систему в целом. Вы должны разбить проблемы заполнения контейнеров на все их составные части. Вы можете получить выгоду, применяя идеи и трюки, которые я представил сегодня, на более низком уровне.
Например, какую числовую точность вам нужно, если речь идет о контейнерах? Возможно, достаточно 16-битных чисел с точностью всего 16 бит. Это делает данные меньше. Сколько различных продуктов мы заказываем? Возможно, мы заказываем всего несколько тысяч различных продуктов, поэтому мы можем использовать блочную сортировку. Распределение вероятностей - это меньшее число, поэтому в теории у нас есть гистограммы, которые могут иметь от нуля единиц, трех единиц и до бесконечности, но мы идем до бесконечности? Нет, не идем. Возможно, мы можем сделать некоторые умные предположения о том, что очень редко мы столкнемся с гистограммой, где превышается 1000 единиц. Когда у нас есть это, мы можем приближать. Нам не обязательно нужна точность 2 единицы, если мы имеем дело с контейнером, содержащим 1000 единиц. Мы можем приближать и иметь гистограмму с более крупными блоками и так далее. Это не столько, я бы сказал, о внедрении алгоритмических принципов, таких как тензорное понимание, которые невероятны, потому что они упрощают все очень круто. Однако большинство ускорений алгоритма в конечном итоге приводят к более быстрому, но немного более сложному алгоритму. Это не обязательно проще, потому что обычно самый простой алгоритм также неэффективен. Более подходящий алгоритм для конкретного случая может быть немного длиннее и сложнее в написании, но в конечном итоге он будет работать быстрее. Это не всегда так, как мы видели с волшебными рецептами, но то, что я хотел показать, - это то, что нам нужно пересмотреть фундаментальные строительные блоки того, что мы делаем, чтобы действительно создавать предприятийное программное обеспечение.
Вопрос: На сколько широко эти идеи реализованы в поставщиках ERP, APS и лучших представителях отрасли, таких как GTA?
Интересно то, что эти идеи фундаментально, большинство из них, полностью несовместимы с транзакционным программным обеспечением. Большинство предприятий используют программное обеспечение, построенное на основе транзакционной базы данных, и все проходит через эту базу данных. Эта база данных не является специализированной базой данных для цепей поставок; это общая база данных, которая должна иметь возможность справиться со всеми возможными ситуациями, от финансов до научных вычислений, медицинских записей и т. д.
Проблема в том, что если рассматриваемое вами программное обеспечение имеет транзакционную базу данных в своей основе, то предложенные мной идеи не могут быть реализованы по своей природе. Это как игра окончена. Посмотрите на видеоигры, сколько видеоигр построены на основе транзакционной базы данных? Ответ - ноль. Почему? Потому что нельзя иметь хорошую производительность графики, реализованную на основе транзакционной базы данных. Нельзя делать компьютерную графику в транзакционной базе данных.
Транзакционная база данных очень хороша; она дает вам транзакционность, но она заключает вас в мир, где почти все ускорения алгоритма, о которых вы можете подумать, просто не могут применяться. Я считаю, что когда мы начинаем думать об APS, в этих системах нет ничего продвинутого. Они застряли в прошлом уже десятилетиями, и они застряли потому, что в основе их конструкции полностью лежит транзакционная база данных, которая не позволяет применять никакие идеи, возникшие в области алгоритмов за последние, вероятно, четыре десятилетия.
Вот в чем суть проблемы в области корпоративного программного обеспечения. Решения, которые вы принимаете в первый месяц проектирования вашего продукта, будут преследовать вас десятилетиями, вплоть до конца времен. Вы не можете обновиться, как только вы решились на конкретное проектирование вашего продукта; вы застряли с ним. Точно так же, как вы не можете просто переоборудовать автомобиль в электромобиль, если вы хотите иметь очень хороший электромобиль, вы полностью переосмыслите автомобиль вокруг идеи, что двигатель будет электрическим. Это не просто замена двигателя и говорить: “Вот электромобиль”. Это не работает так. Это один из тех основных принципов проектирования, когда вы решили производить электромобиль, вам нужно переосмыслить все вокруг двигателя, чтобы это было хорошо. К сожалению, ERPs и APS, которые очень сосредоточены на базах данных, просто не могут использовать ни одну из этих идей, боюсь. Всегда есть возможность иметь изолированный пузырь, где вы получаете выгоду от этих трюков, но это будет пристыкованный дополнительный модуль; он никогда не станет основным.
Что касается впечатляющих возможностей Blue Yonder, пожалуйста, будьте терпеливы, так как Lokad является прямым конкурентом Blue Yonder, и мне трудно быть полностью объективным. На рынке корпоративного программного обеспечения вам приходится делать невероятно смелые заявления, чтобы оставаться конкурентоспособным. Я не убежден, что в этих заявлениях есть какое-либо содержание. Я оспариваю предпосылку, что у кого-либо на этом рынке есть что-то, что можно было бы назвать впечатляющим.
Если вы хотите увидеть что-то потрясающее и ультра-впечатляющее, посмотрите на последнюю демонстрацию Unreal Engine или специализированные алгоритмы видеоигр. Рассмотрите компьютерную графику на аппаратном обеспечении следующего поколения PlayStation 5; она абсолютно потрясающая. Есть ли у нас что-то в том же диапазоне технологических достижений в области корпоративного программного обеспечения? Что касается Lokad, у меня есть супер-предвзятое мнение, но, глядя на рынок более общим образом, я вижу океан людей, которые пытались максимально использовать реляционные базы данных десятилетиями. Иногда они привносят другие типы баз данных, такие как графовые базы данных, но это полностью упускает суть изложенных мной идей. Это не предоставляет ничего существенного для доставки ценности в мир цепочки поставок.
Главное сообщение здесь для аудитории заключается в том, что это вопрос дизайна. Мы должны убедиться, что первоначальные решения, принятые при проектировании вашего корпоративного программного обеспечения, не являются такими, которые бы по своей сути препятствовали использованию этих классов техник в первую очередь.
Следующая лекция состоится через три недели, в среду в 15:00 по парижскому времени. Это будет 13 июня, и мы вернемся к третьей главе, которая посвящена персоналу цепочки поставок, удивительным чертам личности и вымышленным компаниям. В следующий раз мы поговорим о сыре. Увидимся тогда!
