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

Для несортированного массива целых чисел найдите длину самой длинной последовательности последовательных элементов. Например, для [100, 4, 200, 1, 3, 2] самая длинная последовательная последовательность элементов - это [1, 2, 3, 4]. Верните его длину: 4. Ваш алгоритм должен работать с O (n) сложностью.

Первоначальная реализация алгоритма в соответствии со сложностью O (n) была прямолинейной, особенно при использовании только шести целых чисел. Мне стало любопытно, как характеристики производительности алгоритма могут изменяться при использовании разных языков программирования и определенных абстрактных типов данных, а также изменяться при увеличении большего масштаба данных (а не только 6 целочисленных элементов!). После реализации алгоритма с использованием нескольких языков, вот что было измерено с использованием Python 3.8, C ++ 20 с использованием GCC v10.0.1, Rust 1.43.1 и Java 14 для растущего числа целочисленных элементов ...

Таблица содержит время, измеряемое в секундах, для выполнения алгоритма на одном и том же хост-компьютере (ноутбук System76 Oryx Pro под управлением Ubuntu 20.04) с использованием различных абстрактных типов данных, содержащих все большее количество стандартных целочисленных типов. В некоторых случаях, когда присутствует «nan», синхронизированный анализ не проводился - в большинстве этих случаев уже было очевидно, что реализация алгоритма была неэффективной. В других случаях синхронизированный анализ не был завершен из-за невозможности выполнения алгоритма с 64 ГБ памяти. Во всех случаях «nan» означает неспособность конкретной реализации удовлетворить требования к масштабу.

На рисунке ниже показаны наиболее эффективные абстрактные типы данных для каждого из языков программирования, содержащие до 100 миллионов элементов (Примечание: Python и Java не масштабировались после этого момента).

Практические примеры использования алгоритмов - машинное обучение геопространственного и компьютерного зрения

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

Машинное зрение AI Машинное обучение («AI / ML»), в частности обработка Full Motion Video («FMV») и логический вывод машинного обучения - еще один вариант использования, когда производительность данных имеет значение. Это особенно актуально для встроенных систем с ограниченными ресурсами памяти и CPU / GPU.

Сложность времени, которая приводит к экономии средств

Скорость и эффективность важны по нескольким причинам, а не только для получения данных в форме от A до B или выявления конкретных шаблонов. Многие рабочие нагрузки выполняются в облаке и используют структуры распределенной обработки, поэтому максимальная эффективность обработки очень больших наборов данных с использованием большого количества дорогостоящих облачных ресурсов означает, что мы можем экономить и при этом добиваться оптимальных результатов производительности. При обработке миллиардов строк данных в день эти затраты значительно увеличиваются в течение недель, месяцев и лет. Это означает приобретение меньшего количества зарезервированных инстансов (RI) или использование инстансов меньшего размера с меньшим объемом памяти и ЦП. Речь идет не только о том, чтобы «поддерживать 100% использование ЦП», поскольку любой может привязать ЦП с плохим кодом, но и о более тонких нюансах - о максимально эффективном использовании ЦП.

«Написание плохого кода для обработки больших наборов данных в облаке означает написание дорогостоящего кода».

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

Подготовка к тесту

Чтобы создать структуры данных различного размера, случайно сгенерированные целые числа были заполнены в конкретной языковой структуре данных, подобной массиву. Это привело к созданию наборов данных увеличивающегося логарифмического размера, начиная с 10 000 и заканчивая 1 000 000 000 целочисленных значений. Генерация случайных чисел и начальное заполнение данных не были не частью результатов, рассчитанных по времени, поскольку целью не было измерить реализацию генерации случайных чисел на каждом языке. Использовались целочисленные представления языка по умолчанию, выбирая 32-битные представления для языков, для которых была опция.

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

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

По возможности использовались сборки Release и Debug с оптимизацией компилятора по умолчанию.

Подробные результаты

  • Абстрактная структура данных Set с использованием поиска по хэшу идеально подходит для всех языков программирования.
  • Rust и C ++ 20, использующие определенный абстрактный тип данных Set ², показали лучшие результаты при любом масштабе элементов.
  • Ясная, абсолютно наихудшая реализация алгоритма использовала абстрактный тип данных Python List.
  • Python и Java работали аналогично C ++ и Rust при использовании Set до момента, когда память и сборка мусора для Java и Python стали проблемой, приводящей к нехватке памяти («OOM») программе. вылетает.
  • Явный контроль памяти, в частности, использование указателей и ссылок, был важен для сохранения постоянной памяти, что позволило алгоритму масштабироваться и включать больше данных. Для C ++ 20 и, в частности, Rust использование памяти оставалось низким, в то время как программы на других языках падали.
  • Неупорядоченный набор C ++ 20 превзошел контейнер Упорядоченный набор.
  • Совершенно новый метод C ++ 20 contains ³ не оказал очевидного влияния на производительность, хотя управляемость кода C ++ с использованием contains была улучшена по сравнению с использованием нескольких итераторов.
  • Размер памяти неконфигурируемого примитивного типа данных, в частности целочисленный тип, и сборка мусора имели значение для Python. Я редко обращал внимание на размеры примитивных типов данных в Python (или сборку мусора Python, если на то пошло), но эти типы и размеры вызвали сбой Python в меньшем масштабе, чем в других языках⁴.
  • Структура данных массива Python Numpy не работает в этом конкретном сценарии. Массивы Numpy - отличные структуры данных для конкретных случаев использования, но это не было одним из них. Numpy как минимум в 4–5 раз медленнее находил конкретные значения по сравнению с нативной структурой списка Python⁵.
  • Я не обнаружил существенной разницы в производительности при использовании встроенного в Python типа Set и Frozen set абстрактного типа данных.
  • Не всегда было ясно, что происходило в отношении виртуальной машины Java OpenJDK 14 («JVM») ⁶, поскольку ядра ЦП регистрировали 100% загрузку в разное время во время выполнения Java-версии алгоритма. Для Rust и C ++ во время выполнения программы на 100% использовалось только одно ядро ​​ЦП.
  • Максимальный размер кучи, используемый для выполнения реализации Java, составлял 52 ГБ (Xmx52g), и программа по-прежнему аварийно завершала работу из-за нехватки памяти («OOM») в какой-то момент во время выполнения программы.

¹ https://gdal.org/

² https://en.wikipedia.org/wiki/Set_(abstract_data_type)

³ https://en.cppreference.com/w/cpp/container/set/contains

⁴ https://stackoverflow.com/questions/10365624/sys-getsizeofint-returns-an-unreasonably-large-value

⁵ https://stackoverflow.com/questions/13376970/for-huge-arrays-is-numpy-slower-than-list

⁶ https://openjdk.java.net/projects/jdk/14/