Постройте конвейер разработки алгоритмов
Алгоритмы лежат в основе современных инноваций. Сама фраза «новая технология для X…», часто встречающаяся в отчетах о технологиях и науке, часто относится к небольшому или большому фрагменту кода, который воплощает в жизнь алгоритм для достижения определенного, часто скрытого, Цель. Это нововведение создает конкуренцию между признанными технологическими гигантами и стартапами, поскольку эта новая технология, то есть алгоритмы, на самом деле помогает решить проблему клиента лучше, чем предыдущие решения.
Алгоритмы могут быть частью:
- Простое мобильное приложение (приложение, которое отслеживает использование вашего приложения и производительность батареи; приложение, которое позволяет вам записывать ваш ежедневный пробег и показатели вашего здоровья; даже и особенно игры, от Candy Crush до Asphalt 9 ).
- Операционная система (архитектура ОС Android, Windows и Mac и т. Д.).
- Служба рекомендаций (думайте, что Netflix предлагает фильмы, или Semantic Scholar предлагает академическую литературу).
- Инструмент управления портфелем (как менеджеры Berkshire Hathaway управляют его активами?)
- Служба совместного использования поездок (какого водителя / такси назначить для данного запроса на поездку?)
- Инструмент поиска (Google, обслуживающий миллиарды результатов поиска за 0,08 секунды, или инструмент поиска в базе данных геномики)
- Приложение виртуальной / дополненной реальности (рендеринг Пикачу на земле рядом с вами; приложения Magic Leap)
- инструмент для высокоточного моделирования (моделирование энергопотребления или экономики нефти, моделирование биологических макромолекул; Disney анимация Симбы с подповерхностным светорассеянием для гиперреализма; Adobe After Effects позволяет удалить движущийся объект из видеоклипа, пока сохраняя свою среду).
Суть проста - современные инновации основаны на алгоритмах. По мере того, как мы становимся в состоянии представить все более и более масштабные требования, набор алгоритмических инструментов расширяется одновременно. Неявно расширяется набор математических инструментов и расширяется набор инструментов кода. И решать эти предстоящие проблемы становится все труднее.
Чтобы еще больше усложнить ситуацию, не все проблемы построены одинаково. Кроме того, алгоритмы являются интеллектуальной собственностью и коммерческой тайной - часто в открытом доступе используются только рудименты.
Каждая новая проблема потребует немного индивидуализированной реализации известного решения. И некоторые проблемы потребуют прорывных инноваций, которые в данном случае могут означать инновации в математических методах, парадигмах реализации (например, новая ОС или библиотека кода) или аппаратном обеспечении (например, улучшенная вычислительная мощность может гарантировать проблемы экономически целесообразно реализовать).
Заявление об ограничении ответственности: слово «алгоритм» используется здесь без разбора для простоты. В целом, однако, предполагаемое значение - это набор методов и логических последовательностей, которые обрабатывают определенные данные для получения определенных полезных результатов. Очевидно, это относится как к математике, так и к коду. В рамках данной статьи этот термин охватывает все уровни сложности - от простой логики if / for / switch до нелинейного динамического программирования, кластеризации больших данных и глубокого обучения.
Весь процесс от концептуализации до развертывания алгоритма состоит из семи ключевых (но не обязательно простых) шагов:
1. Сформулируйте проблему
2. Модель
3. Код
4. Подготовьте данные
5. Оценить
6. Выберите и оптимизируйте
7. Развернуть
Исходя из вашей конечной цели, продукта или специализации / роли, отправной точкой может быть любой из этих шагов.
Но если бы все, что у вас было, было идеей и ручкой и бумагой - или, ну, ноутбуком, - вы бы отправились в плотный мир разработки алгоритмов (ов) для сложных проблем, сначала сформулировав то, чего вы хотите достичь.
Шаг 1: сформулируйте проблему
Знайте, что вам нужно. Опишите, что вы хотите.
- Создайте математическую абстракцию постановки задачи или предметной области. Здесь уровень детализации должен охватывать весь объем функции / продукта, который будет разработан.
(Выберите один из примеров из списка во введении и потратьте некоторое время на понимание и исследование формулировка основной проблемы, лежащей в основе выбранной вами функции / продукта.) - По возможности можно указать функциональные и нефункциональные требования, включая требования, не связанные с фактической разработкой алгоритма. Эти требования могут исходить из вашей среды разработки / развертывания, более широкой области применения продукта и т. Д.
- Определите необходимую информацию и доступную информацию (и пробелы). Определите категорию проблемы с точки зрения методов решения. (Например, простая минимизация цели с двумя переменными может быть задачей линейной оптимизации, но проблема ограничения пропускной способности может быть вариацией гораздо более сложной задачи о рюкзаке).
- Одновременно попытайтесь указать ожидаемую окончательную операционную среду проблемы - запрограммировано на каком языке (C ++, Java), где развернуто (AWS, собственный сервер / вычислительный кластер, персональный ноутбук) и т. Д. Попытка определить более широкую архитектуру родительской продукт: Будет ли алгоритм развертываться как часть внутреннего инструмента или ориентирован на клиента? Это обязательно в реальном времени? Откуда будут поступать данные в развернутом состоянии (например, из базы данных, из клиентского приложения на мобильном устройстве / в Интернете и т. Д.)?
Шаг 2: Модель
Подробно опишите ожидаемое решение.
- После определения категории проблемы с точки зрения методов ее решения создайте структуру для ожидаемого метода решения проблемы (это первая итерация структуры). Фреймворк - это полный набор дополнительных решений подзадач, которые составляют полную проблему / функцию / продукт.
- Чтобы получить наилучшую возможную первую итерацию структуры, неприкосновенно важно знать (академическую) литературу по решениям проблем с аналогичными базовыми моделями - эти проблемы могут быть из разных областей. Чаще всего математика или статистика, необходимые для решения сложных задач, находятся на продвинутом уровне, и лучшие решения постоянно совершенствуются.
(Например, скрытые марковские модели используются в задачах картографирования и маршрутизации, а также в вычислительной биологии, где лежащие в основе параметрические явления такие же, следовательно, моделируются с помощью HMM.) - Используя структуру, добавьте различную степень детализации, чтобы создать фактическую математическую модель для каждой подзадачи, каждая из которых должным образом взаимосвязана.
- Из предыдущего шага сопоставьте прогнозируемые требования к данным с фактическими требованиями к данным на основе окончательного определения модели. Создайте спецификации для данных и наборов данных, которые потребуются и будут сгенерированы во время работы с моделью. (Например, в зависимости от вашего приложения могут потребоваться данные ГИС, данные о населении, данные о частоте механических отказов, прошлые финансовые данные и т. Д.).
- Наконец, сгенерируйте показатели производительности для модели и подмоделей. Метрики должны отражать параметры производительности для абстрактной задачи (только математические), а также для развернутой производительности (время выполнения). Метрики могут быть связаны с решением (эффективность результатов, ошибка, точность), временными характеристиками (временная сложность, фактическая машинно-зависимая производительность), пространственными характеристиками (пространственная сложность) и т. Д. Метрики могут / должны быть заимствованы из известных реализаций из литература.
Шаг 3: Код
Получите лязг клавиатуры. Измените логику на выбранном вами языке программирования.
- Чтобы оценить эффективность и готовность к использованию, необходимо будет написать тестовый код и готовый к работе код. Обычно сначала может быть написан тестовый код, чтобы отсортировать любые второстепенные ошибки или внести изменения в структуру модели. Тестовый код может быть написан в любой подходящей среде, например. MATLAB, Eclipse (Java, C / C ++) и др.
- Напишите тестовый код по модульному принципу, чтобы иметь возможность независимо тестировать каждый модуль и подмодуль, используя соответствующие входные параметры и наборы данных. Это может быть связано как с математикой модели, так и с настройкой кода и средой тестового кода.
- При необходимости напишите код производственного уровня, основанный на тестовом коде и извлеченных из него знаниях.
Шаг 4. Подготовьте данные
Нет данных - нет прибыли. Подготовьте источник данных и в какой форме.
- Основываясь на требованиях к данным, представленных ранее, подготовьте образцы или реальные данные (в зависимости от обстоятельств) в соответствующем формате.
- Для большинства проблем требуются данные высокого качества. В зависимости от вашего домена эти данные могут быть доступны или недоступны. (Например, наборы данных изображений для обучения модели машинного обучения могут быть легко доступны сегодня, но получить точные данные о транзите для всех видов городского транспорта очень сложно.)
Продумайте точную природу и используйте эти данные, чтобы лучше подготовиться к тестированию и развертыванию. Найдите способы получить то, что недоступно - от этого может зависеть сам успех продукта! - В зависимости от вашего приложения здесь могут проявляться некоторые архитектурные особенности, например с использованием баз данных SQL и NoSQL, локальных или облачных данных. Данные должны быть подготовлены соответствующим образом. Требования к данным для кода тестирования и кода производственного уровня могут отличаться.
- Подготовив определенные разделы тестового кода и кода производственного уровня, разумно потратить некоторое время на точную настройку фактических структур данных, используемых в коде, и их эквивалентов в реальных наборах данных. Коду могут потребоваться интерфейсы для преобразования доступных данных в соответствующие структуры данных, или этап подготовки данных может включать автоматическое преобразование набора данных из стандартной в пользовательскую структуру данных in situ.
Шаг 5. Оцените
Создавать и запускать тесты. Узнайте, что работает.
- Для тестового кода: создавайте различные сценарии моделирования, основанные на вариативности, ожидаемой в формулировке проблемы, недостатках данных и т. д. Смоделируйте тестовый код для различных сценариев. Проверьте производительность на основе показателей, описанных ранее. Важно тестирование технических показателей - например, временная и пространственная сложность.
- Для кода производственного уровня: выявите передовые отраслевые методы тестирования кода производственного уровня и по возможности используйте стандартные среды тестирования.
- Используя результаты тестирования, повторите тестовый код / производственный код и повторите соответствующие шаги. Выполните итерации столько раз, сколько возможно (наилучший возможный результат в рамках ограничений по времени и стоимости).
Шаг 6. Выберите и оптимизируйте
Оптимизация - это конкурентоспособность. Оптимизация - это ценность.
- По результатам тестирования доработайте структуру и модели, которые будут использоваться для развертывания. Выберите те, которые работают лучше всего. Заархивируйте остальные для использования в будущем.
- Если проблема / функция / продукт сложны - как это часто бывает в настоящее время - создайте соответствующую документацию для каждого шага, а также для каждой итерации.
Шаг 7. Разверните
Пусть разыграется. Но будьте внимательны.
- Реализуйте окончательный код и разверните в производственной среде. Этот шаг полностью зависит от конечного приложения - алгоритм может быть частью серверной части игры MMORPG, или частью службы совместного использования поездок в реальном времени, или частью одноразового эксперимента по расширенному моделированию материалов и рендерингу графического процессора. Хорошо знайте переменные производственной среды.
- Регулярно отслеживайте производительность, пока ее не передадите для неконтролируемого (или частично контролируемого) развертывания в производственной среде.
- Связывайтесь с любыми обновлениями основной структуры проблем и обновлениями логики и кода тестирования, включая модульность, готовность к будущим функциям и т. Д.
Вот и все, семь шагов! То, что на первый взгляд может показаться простой логической последовательностью, на самом деле очень сложно отслеживать и управлять, когда дело касается сложных продуктов и систем. Вот почему существуют трубопроводы, не так ли?
Дополнительная ссылка
Ниже приведен список документов, относящихся к алгоритму, называемому сопоставлением карт, который обычно используется для определения маршрута транспортного средства на известной карте (доступны данные ГИС) с использованием GPS-трека транспортного средства (например, с мобильного телефона водителя). Идея состоит в том, чтобы использовать каждое известное местоположение GPS и «привязать» его к соответствующему сегменту дороги, который, скорее всего, пересек транспортное средство.
Но поскольку трасса GPS содержит ошибки и представляет собой дискретный набор данных, а дорожная сеть большинства городов очень сложна, сложно вычислить, по какой дороге использовалось транспортное средство, когда оно двигалось из пункта A в пункт B.
- Алгоритм и реализация сопоставления карт общегородских данных о плавающих автомобилях, Луи Хан 2015, Технический университет Мюнхена
Доступно: https://cartographymaster.eu/wp-content/theses/ 2015_Luyi_Thesis.pdf - Сопоставление карт с ограничениями по времени в пути, исследование Microsoft
Доступно: https://www.microsoft.com/en-us/research/wp-content/uploads/2016/11 /map-matching-HMM-01.pdf - Сопоставление скрытой карты Маркова по шуму и разреженности, исследование Microsoft
Доступно: https://www.ismll.uni-hildesheim.de/lehre/semSpatial-10s/script/6 .pdf - Исходный код проекта OSRM для сопоставления карт
Доступен: https://www.github.com/Project-OSRM/osrm-backend
В документах описываются алгоритмы и реализация сопоставления карт с использованием различных методов, но с упором на метод, который включает использование скрытых марковских моделей (HMM). Последняя ссылка предназначена для исходного кода очень известной программы с открытым исходным кодом (Project OSRM), которая реализует сопоставление карт на основе алгоритма на основе HMM.
Изучая эти ресурсы, вы можете начать понимать, как перейти от математики к коду и, наконец, к продукту.
Как вы можете видеть во введении, в современном мире слишком много разнообразия, чтобы иметь возможность предоставлять исчерпывающие ресурсы в одном месте.
Мы надеемся, что приведенный выше пример, который, кстати, не считается чрезвычайно сложной проблемой, прокладывает путь к вашему будущему самостоятельному обучению и помогает разрабатывать алгоритмические решения с возрастающим объемом и ценностью!
Эта статья основана на понимании автором разработки продукта, архитектуры сложных систем, небольшого количества программирования и знаний предметной области в области инженерии. Автор не является штатным разработчиком или практикующим архитектором ИТ-систем, но тесно связан только с архитектурой продукта. Рекомендуем всегда обращаться к лучшим отраслевым практикам, когда речь идет о вашей реальной проблеме / функции / продукте.