Постройте конвейер разработки алгоритмов

Алгоритмы лежат в основе современных инноваций. Сама фраза «новая технология для 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.

В документах описываются алгоритмы и реализация сопоставления карт с использованием различных методов, но с упором на метод, который включает использование скрытых марковских моделей (HMM). Последняя ссылка предназначена для исходного кода очень известной программы с открытым исходным кодом (Project OSRM), которая реализует сопоставление карт на основе алгоритма на основе HMM.

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

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

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

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