Алгоритмическое мышление заключается в том, чтобы, объединив строгую логику и творческие способности, структурировать, решать и анализировать задачи, чаще всего с помощью компьютера. С алгоритмическим мышлением тесно связаны задачи на упорядочивание, поиск и оптимизацию — именно с ними часто приходится иметь дело в Data Science — проектах.
Алгоритмическое мышление помогает решать такие задачи с эффективным использованием времени и места — дискового пространства или памяти компьютера. В результате получаются быстрые и экономичные алгоритмы.
Хотя стоимость хранения и вычислительных ресурсов будет и дальше снижаться в обозримом будущем, алгоритмическое мышление не потеряет важности в Data Science — проектах, и вот почему.
Во-первых, во многих коммерческих сценариях использования требования заказчиков превосходят возможности доступных решений при любой исходной сложности Data Science — пайплайнов: от работы с источниками и преобразования данных до моделирования и подготовки ресурсов. Другими словами, у заказчиков часто бывают завышенные ожидания. Они надеются, что задачи, которые занимают дни или часы, можно сделать за минуты или секунды, а те, что занимают минуты или секунды, — в мгновение ока.
Во-вторых, растёт число аналитических задач, выполняющихся напрямую на локальном устройстве: в контексте встроенных систем, IoT, пограничных вычислений. Для них эффективное использование вычислительных ресурсов имеет принципиальное значение. Пространства и памяти всегда не хватает, при этом иногда нет возможности перенести вычислительные ресурсы в более мощную и централизованную облачную среду.
В-третьих, на работу промышленных Data Science — пайплайнов часто уходят значительные объёмы энергии, что усугубляет климатический кризис. Уверенные навыки алгоритмического мышления помогают аналитикам создавать эффективные экологичные решения, которые учитывают эти особенности.
Выпускники профильных вузов, конечно, знакомы с основными концепциями алгоритмического мышления. Но всё больше людей приходят в Data Science из других предметных областей — от естественных и социальных наук до искусства. Скорее всего, в ближайшие годы эта тенденция только усилится за счёт достижений в области генеративного ИИ и преподавания Data Science в школах и вузах. Эта статья написана преимущественно для тех, кто незнаком с алгоритмическим мышлением. Мы начнём с общего обзора алгоритмического процесса решения задач, а затем перейдём к формированию алгоритмического мышления на материале программистских задач с платформы HackerRank, где компании подбирают дата-аналитиков. Приведём и несколько полезных источников для дальнейшего изучения. В завершение кратко рассмотрим применимость алгоритмического мышления в разработке программного обеспечения с помощью искусственного интеллекта и подведём итоги.
Как решать задачу
Название этого раздела вторит названию книги, написанной Дьёрдем Пойа, профессором Стэнфордского университета, американским математиком венгерского происхождения, и опубликованной в 1945 году. В книге «Как решать задачу» Пойа предлагает обманчиво простой, но чрезвычайно эффективный подход, который можно применять к алгоритмическому решению задач. Он состоит из четырёх этапов:
Понять задачу. Обстоятельно сформулируйте задачу, обращая внимание на любые ограничения самой задачи и её решения: допустимые типы и диапазоны данных на вводе, формат на выходе, максимальное время выполнения и т. п. Для проверки спросите себя: «Могу ли я переформулировать задачу собственными словами?», «Хватает ли у меня данных для реализации полезного решения?». Используйте конкретные примеры или датасеты, чтобы сделать задачу и её пограничные случаи более рельефными. Если как следует поразмыслить на этом этапе, можно заметно упростить выполнение следующих шагов.
Разработайте план. На этом этапе лучше разбить задачу на подзадачи, для которых уже известны эффективные решения. Навык находить подходящие решения и применять их к подзадачам разных типов (например, при поиске или сортировке) приходит с опытом. Но бывает, что требуется и творческий взгляд на задачу: когда нужно объединить несколько подходов, придумать новый или по аналогии позаимствовать решение из другой предметной области. Пойа даёт несколько рекомендаций в помощь мыслительному процессу, например: рисовать схемы, идти в обратном направлении, от искомой цели. На этом этапе полезно хотя бы в общих чертах прикинуть, поможет ли разработанный план решить задачу.
Реализуйте план. Внедрите решение, используя подходящий инструментарий. Применительно к Data Science — проекту это могут быть библиотеки scikit-learn, PyTorch или TensorFlow для машинного обучения, платформы AWS, GCP и Azure для хостинга и запуска пайплайнов. На этом этапе нужно очень внимательно относиться к деталям, ведь даже из-за небольших ошибок в коде могут возникнуть отклонения от разработанного плана, которые не позволят решить задачу. Не скупитесь на модульные тесты: тщательно проверяйте разные части кода даже для пограничных случаев.
Обернитесь. Привычка смотреть назад — неотъемлемая часть валидации Data Science — проектов. На вопросы вроде «У новой модели машинного обучения производительность выше, чем у старой?» можно ответить только в ретроспективе, собрав и оценив необходимые метрики по каждому эксперименту. Но для доработки текущего проекта и оптимизации будущих принципиально важно проверить и другие аспекты Data Science — пайплайна (код ETL, тестовые случаи, скрипты коммерческого внедрения), и управление жизненным циклом ИИ (уровень автоматизации, вопросы конфиденциальности и безопасности, реализацию цикла обратной связи в продакшн-среде). Это обязательный этап, даже если в динамичной рабочей атмосфере трудно найти время для такого обзорного взгляда на вещи.
В процессе решения задачи по Пойа особенно трудно выполнить правильно первый и второй этапы. Структурировать условия или решение концептуально логическим и непротиворечивым образом — во многих случаях нетривиальная задача. И здесь поможет знакомство с концептуальными моделями — аналитическими структурами для представления абстрактных концепций. К концептуальным моделям относятся диаграммы процессов, матрицы, древовидные и реляционные диаграммы. В книге Conceptual frameworks: a guide to structuring analyses, decisions and presentations, написанной автором этой статьи, простыми словами объясняется, как понимать, создавать, применять и оценивать такие концептуальные модели.
Сложность алгоритма
В контексте алгоритмического решения задач следует отдельно остановиться на теме сложности. Сравнивая два разных алгоритма, нужно учитывать их временную и пространственную сложность, то есть как время и пространство (память), необходимые для каждого алгоритма, соотносятся с размером задачи или данных. Ориентируйтесь на пять уровней сложности: от минимального (лучшего) до максимального (худшего). Чтобы упростить ход мысли, опишем только временную сложность:
Константная. Независимо от масштаба задачи, этот алгоритм всегда выполняется за одно и то же время. Формально константные алгоритмы считаются самыми быстрыми. Например, чтобы определить, является ли целое число чётным, вне зависимости от размера целого числа можно просто выяснить, делится ли его крайняя правая цифра на два без остатка. Доступ к элементу списка по индексу тоже выполняется практически мгновенно, независимо от длины списка.
Логарифмическая. Для датасета размером n алгоритм выполняется в log(n) интервалов времени. Не забудьте, что у логарифма бывают разные основания, например log2(n) для бинарного поиска, когда объём данных уменьшается в два раза с каждой итерацией. Как и константные алгоритмы, алгоритмы с логарифмической сложностью привлекательны тем, что масштабируются сублинейно по отношению к размеру задачи.
Линейная. Как ясно из названия, для датасета размером n алгоритм с линейной сложностью выполняется примерно в n временных интервалов.
Полиномиальная. Для некоторого положительного целого числа m алгоритм выполняется в x^2 (квадратичное время), x^3 (кубическое время) или, в общем смысле, в x^m временных интервалов. Чтобы проверить полиномиальную сложность в коде, можно прибегнуть к одной хитрости: посчитать количество вложенных циклов. Например, функция с двумя вложенными циклами (цикл в цикле) имеет сложность x^2, а функция с тремя вложенными циклами — x^3 и так далее.
Экспоненциальная. Для некоторого положительного целого числа m алгоритм выполняется в 2^x, 3^x или, в общем смысле, в m^x временных интервалов. В этих статьях на StackExchange (ссылка 1, ссылка 2) объясняется, почему экспоненциальные функции в итоге становятся больше полиномиальных, и, следовательно, в плане алгоритмической сложности они хуже для больших задач.
Для некоторых алгоритмов характерны кумулятивные или мультипликативные сочетания уровней сложности. Например, если за циклом for loop следует бинарный поиск, мы имеем дело с сочетанием линейной и логарифмической сложности, которое отличается последовательным выполнением режима цикла и поиска соответственно. И наоборот, когда в цикле for loop в каждой итерации выполняется бинарный поиск, мы сталкиваемся с мультипликативным сочетанием линейной и логарифмической сложности.
Хотя мультипликативные сочетания обычно оказываются дороже кумулятивных, иногда они неизбежны. Но их всё же можно оптимизировать. Например, алгоритм сортировки слиянием (merge sort) с временной сложностью n log(n) обходится дешевле, чем сортировка выбором (selection sort), которая характеризуется квадратичной временной сложностью. Таблицу сравнения уровней сложности разных алгоритмов сортировки можно посмотреть здесь или ниже.
BIG-O |
Сложность |
Пример |
O (1) |
Константная |
Поиск по ключу в хеш-таблице, арифметическая операция с числом |
O (log2(n)) |
Логарифмическая |
Бинарный поиск, сложность, вставка, сбалансированное бинарное дерево |
O (n) |
Линейная |
Поиск перебором, среднеквадратическое отклонение |
O (n × log2(n)) |
Квазилинейная |
Самые быстрые алгоритмы сортировки |
O (n2) |
Квадратичная |
Простые алгоритмы сортировки, перемножение n-значных чисел столбиком |
O (nx) |
Полиномиальная |
LU-разложение матрицы, мощность графа |
O (cn) |
Экспоненциальная |
Задача коммивояжёра (динамическое программирование) |
O (n!) |
Факториальная |
Задача коммивояжёра перебором |
Учимся на примере нескольких задач
Далее рассмотрим подборку задач, опубликованных на HackerRank — социальной платформе, которая предлагает задания разной сложности по программированию. Похожие задачи можно найти и на сайтах LeetCode и Codewars. Изучайте задачи, которые выкладывают на этих платформах. Так вы натренируете мышцу алгоритмического мышления, будете лучше проходить технические интервью (а эйчары любят спрашивать претендентов на аналитические должности об алгоритмах) и соберёте коллекцию фрагментов кода, которые можно использовать в работе.
Все примеры сниппетов кода ниже написаны автором статьи на C++. Разработчики быстрых дата-пайплайнов часто предпочитают этот язык программирования. При необходимости эти сниппеты можно легко перевести на другие языки, например Python или R. Чтобы упростить сниппеты кода, допустим, что вверху файла с кодом есть строки:
#include <bits/stdc++.h>
using namespace std;Так мы сможем везде опустить std:: и сосредоточиться исключительно на алгоритмах. Конечно, в рабочий код на C++ войдут только соответствующие библиотеки и std::, написанный в строгом соответствии с правилами разработки.
Когда хватит и формулы
Иногда задачу, для которой мы собираемся использовать итеративное решение с полиномиальной сложностью (например, циклы for loop и while loop, генераторы списков), можно решить алгебраически с помощью формулы, выдающей нужный результат мгновенно.
Возьмём задачу «Прыжки по числовой оси». Два кенгуру находятся где-то на числовой оси — на позициях x1 и x2 соответственно. Они перемещаются прыжками. Первый кенгуру может прыгнуть за один раз на v1 метров, второй — на v2 метров. Имеются вводные значения для x1, v1, x2 и v2. Надо определить, могут ли оба кенгуру в какой-то точке времени в будущем оказаться на одной и той же позиции на числовой оси, если допустить, что каждый кенгуру может в каждый шаг времени прыгнуть только один раз. Решение функции должно представлять собой ответ ДА или НЕТ.
Допустим, x1 меньше x2. Тогда решение задачи заключается в реализации цикла, который проверяет, сможет ли кенгуру, стартующий с x1, когда-нибудь догнать кенгуру, стартующего с x2. Другими словами, мы проверяем, существует ли положительный (целочисленный) шаг по времени, при котором x1 + v1 × t = x2 + v2 × t. Если x1 больше x2, можно просто поменять местами значения соответствующих переменных в этом подходе. Но при большом t такое решение может выполняться долго и даже затянуться до бесконечности, вызвав тайм-аут или сбой, если один кенгуру так и не догонит второго.
Есть куда более эффективное решение. Выразим t из приведённого выше уравнения, чтобы найти целое положительное число. Получаем t = (x1 – x2) / (v2 – v1). Это уравнение для t не может быть решено, если v2 = v1, поскольку на ноль делить нельзя. Но в этом случае ответ будет ДА: если оба кенгуру стартуют с одной позиции, очевидно, что они добегут до одной и той же позиции на числовой оси на следующем же шаге по времени. Более того, если оба кенгуру прыгают на одинаковое расстояние с разных стартовых позиций, ответ будет НЕТ: кенгуру, стартующий слева, никогда не догонит кенгуру, который стоит справа. Наконец, если мы находим положительное решение для t, нужно убедиться, что это целое число. Для этого нужно привести t к целочисленному типу данных и проверить, равно ли оно исходному значению. Вот сниппет кода, который реализует это решение:
string kangaroo(int x1, int v1, int x2, int v2) {
if((v2 == v1) && (x1 != x2)) return "NO";
float t = 1.*(x1 - x2)/(v2 - v1);
return ((0 < t) && (t == (int) t)) ? "YES" : "NO";
}Выбор из нескольких вариантов
Одну и ту же задачу можно решить несколькими способами. Если вы нашли одно решение, это не значит, что нет других стоящих решений. У каждого подхода есть свои за и против, за счёт которых он лучше или хуже вписывается в контекст задачи. Чтобы подтвердить этот тезис, рассмотрим три задачи с разной степенью углубления в детали.
Первая задача — «Кино в прекрасный день». Изучив её условия, вы поймёте, что ключевая часть решения — это поиск функции для инверсии положительного целого числа. Например, 123 в обратном порядке будет 321, а 12000 — 21 (обратите внимание, что в этом случае нули опущены).
Первое решение назовём reverse_num_v1. Здесь используется сочетание операций деления и деления по модулю, с помощью которых крайняя правая цифра переносится в крайнее левое положение. Начальные нули по традиции опускаются: см. пример ниже. Поскольку количество цифр относительно размера числа растёт логарифмически, reverse_num_v1 отличается сублинейной временной сложностью, его пространственная сложность тоже ничтожна. Поэтому это достаточно привлекательный подход.
int reverse_num_v1(int x) {
long long res = 0;
while (x) {
res = res * 10 + x % 10;
x /= 10;
// Check for integer overflow
if (res > INT_MAX || res < INT_MIN) return 0;
}
return res;
}В другом решении (назовём его reverse_num_v2) мы конвертируем целое число в строковый тип данных, меняем цифры местами, отсекаем начальные нули, преобразуем строку обратно в целое число и получаем результат:
int reverse_num_v2(int x) {
string str = to_string(x);
reverse(str.begin(), str.end());
// Remove leading zeros
str.erase(0, min(str.find_first_not_of('0'), str.size()-1));
int res = stoi(str);
// Check for integer overflow
return (res > INT_MAX || res < INT_MIN) ? 0 : res;
}Такое преобразование типов — распространённый приём во многих языках программирования: C++, Python и прочих. Есть готовые библиотечные функции для инверсии строк и обрезания начальных нулей, а цепочки функций для формирования пайплайна операций преобразования данных — это типичный паттерн для Data Science — проектов.
Так что в первую очередь многим аналитикам приходит в голову именно решение reverse_num_v2. Но если памяти не хватает, возможно, reverse_num_v1 подойдёт больше, поскольку строковое представление целого числа занимает больше места, чем само целое число (в этой документации можно ознакомиться с требованиями к памяти для разных типов данных в C++).
Далее кратко рассмотрим ещё две задачи: «Пересчёт времени» и «Рисуем магический квадрат». Хотя на первый взгляд кажется, что это совершенно разные задачи, для решения обеих можно использовать один и тот же приём — использование таблиц или схем подстановки.
В задаче «Пересчёт времени» можно использовать таблицу подстановки, чтобы мгновенно определять соответствие между 12- и 24-часовыми форматами послеобеденного времени. Например, восемь часов соответствует 20, девять — 21 и так далее.
Задача «Рисуем магический квадрат» ограничивается квадратами, состоящими из трёх строк и трёх столбцов. Всего таких квадратов 8. Сохранив конфигурации этих магических квадратов в таблице поиска, можно реализовать относительно простое решение задачи, несмотря на её средний уровень сложности на HackerRank.
Предлагаю вам перейти по указанным выше ссылкам и самостоятельно продумать эти задачи. Для сравнения рассмотрим соответствующие сниппеты кода для каждого решения ↓
«Пересчёт времени»
string timeConversion(string s) {
// substr(pos, len) starts at position pos and spans len characters
if(s.substr(s.size() - 2) == "AM") {
if(s.substr(0, 2) == "12") return "00" + s.substr(2, s.size() - 4);
else return s.substr(0, s.size() - 2);
}
else {
// PM means add 12 to hours between 01 and 11
// Store all 11 mappings of afternoon hours in a lookup table/map
map<string, string> m = {
{"01", "13"}, {"02", "14"}, {"03", "15"}, {"04", "16"},
{"05", "17"}, {"06", "18"}, {"07", "19"}, {"08", "20"},
{"09", "21"}, {"10", "22"}, {"11", "23"}
};
string hh = s.substr(0, 2);
if(m.count(hh)) return m[s.substr(0, 2)] + s.substr(2, s.size() - 4);
else return s.substr(0, s.size() - 2);
}
}«Рисуем магический квадрат»
Обратите внимание, что, хотя во фрагменте кода используются три вложенных цикла for loop, для решения задачи нужно только 8 × 3 × 3 = 72 цикла простых операций.
int formingMagicSquare(vector<vector<int>> s) {
// Store all 8 possible 3x3 magic squares in a lookup table/matrix
vector<vector<int>> magic_squares = {
{8, 1, 6, 3, 5, 7, 4, 9, 2},
{6, 1, 8, 7, 5, 3, 2, 9, 4},
{4, 9, 2, 3, 5, 7, 8, 1, 6},
{2, 9, 4, 7, 5, 3, 6, 1, 8},
{8, 3, 4, 1, 5, 9, 6, 7, 2},
{4, 3, 8, 9, 5, 1, 2, 7, 6},
{6, 7, 2, 1, 5, 9, 8, 3, 4},
{2, 7, 6, 9, 5, 1, 4, 3, 8},
};
int min_cost = 81; // Initialize with maximum possible cost of 9*9=81
for (auto& magic_square : magic_squares) {
int cost = 0;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
cost += abs(s[i][j] - magic_square[3*i + j]);
}
}
min_cost = min(min_cost, cost);
}
return min_cost;
}Разделяй и властвуй
Если задача кажется слишком большой и сложной, чтобы решить её в один заход, имеет смысл разделить её на подзадачи, решить которые по отдельности будет проще. В каждом случае это будут разные подзадачи: на сортировку, поиск или преобразование, с разным отношением к исходной задаче как части к целому.
В Data Science часто возникает задача очистки данных. Здесь каждая подзадача представляет собой отдельный этап процесса очистки: удаление стоп-слов, лемматизацию и пр. В задачах типа go/no-go каждая подзадача заточена на более мелкое решение, в результате сложения которых получается общее решение исходной задачи go. С логической точки зрения её можно представить как сложное логическое выражение вида A AND B.
Чтобы посмотреть, как подход «разделяй и властвуй» работает на практике, разберём две задачи, которые на первый взгляд кажутся совсем разными.
Сначала возьмём задачу «Магазин электроники». По сути это задача на оптимизацию в заданных пределах.
Дано: общий бюджет b и неотсортированные прайс-листы на клавиатуры и флешки. Назовём их K и D соответственно. Нужно купить самую дорогую клавиатуру и флешку, не превышая бюджет. В этой задаче в прайс-листах содержится до 1 000 наименований, но в реальности встречаются и варианты подлиннее.
Примитивный подход к решению — перебирать элементы прайс-листов K и D с помощью двух вложенных циклов в поисках i-ой клавиатуры и j-ой флешки по максимальной цене, вписывающейся в бюджет. Это решение легко реализовать, но на него уйдёт слишком много времени, если прайс-листы K и D длинные и тем более неотсортированные. У этого примитивного подхода квадратичная временная сложность, и это не сулит ничего хорошего при масштабировании до больших датасетов.
Вот как сработает более эффективный подход. Сначала отсортируем оба прайс-листа. Затем выберем для выполнения циклов прайс-лист покороче. Для каждого элемента x в циклическом списке выполним в другом списке бинарный поиск элемента y (если такой будет) так, чтобы сумма x + y не превышала заданный бюджет b. Сохраняем полученный результат в переменной max_spent за пределами цикла. В каждой последующей итерации цикла max_spent обновляется, только если стоимость последней пары «клавиатура + флешка» вписывается в бюджет и при этом превышает нынешнее значение max_spent.
Хотя в этой задаче в любом случае придётся выполнять поиск в обоих прайс-листах, при эффективном подходе значительно сокращается общее время поиска, поскольку для циклов мы выбираем более короткий прайс-лист. Очень важно: бинарный поиск выполняем в более длинном прайс-листе, то есть имеем дело с логарифмическим или сублинейным временем выполнения. Более того, сначала может показаться, что предварительная сортировка двух прайс-листов только усложняет решение. На самом деле сортировку можно выполнить довольно эффективно, например с помощью merge sort. Самое важное, что она позволяет произвести бинарный поиск по более длинному прайс-листу. В результате мы получаем алгоритм, который работает гораздо быстрее первого предложенного варианта. Вот пример реализации эффективного решения:
int findLargestY(int x, int b, const vector<int>& v) {
// Simple implementation of binary search
int i = 0, j = v.size(), y = -1, m, y_curr;
while (i < j) {
m = (i + j) / 2;
y_curr = v[m];
if (x + y_curr <= b) {
y = y_curr;
i = m + 1;
}
else j = m;
}
return y;
}
int getMoneySpent(vector<int> keyboards, vector<int> drives, int b) {
int max_spent = -1;
sort(keyboards.begin(), keyboards.end());
sort(drives.begin(), drives.end());
// Use smaller vector for looping, larger vector for binary search
vector<int> *v1, *v2;
if(keyboards.size() < drives.size()) {
v1 = &keyboards;
v2 = &drives;
}
else {
v1 = &drives;
v2 = &keyboards;
}
int i = 0, j = v2->size(), x, y;
for(int i = 0; i < v1->size(); i++) {
x = (*v1)[i];
if(x < b) {
y = findLargestY(x, b, *v2); // Use binary search
if(y != -1) max_spent = max(max_spent, x + y);
}
else break;
}
return max_spent;
}Переходим к задаче «Вверх в таблице результатов». Представьте, что вы играете в аркаду и хотите отслеживать свой рейтинг в таблице результатов после каждой игры. В таблице используется dense ranking, т. е. функция ранжирования DENSE_RANK() в упорядоченном наборе данных продолжает ранжирование без пропусков (например, 1, 1, 2), так что игроки с одинаковым числом баллов получают одинаковый рейтинг. Допустим, в таблице результатов есть 100, 90, 90 и 80 баллов. Тогда игрок, набравший 100 баллов, получает рейтинг 1, два игрока, набравшие по 90 баллов, получают рейтинг 2, а игрок с 80 баллами занимает третье место. Таблица результатов представляет собой массив или список целых чисел — лучших результатов каждого игрока — в порядке убывания. Подноготная задачи в том, что когда в таблицу добавляется новый результат, то определить рейтинг игрока не так-то просто, ведь он может совпадать с рейтингом других игроков. В описании задачи есть наглядный пример.
Хотя задачам «Магазин электроники» и «Вверх в таблице результатов» на HackerRank присвоены уровни «лёгкий» и «средний» соответственно, вторая задача в каком-то смысле проще, потому что таблица результатов уже отсортирована. В примере решения ниже используется как раз эта особенность. Мы выполняем бинарный поиск по отсортированной таблице результатов, чтобы рассчитать рейтинг после каждого нового результата:
int find_rank(int x, vector<int>& v) {
// Binary search of rank
int i = 0, j = v.size(), m_pos, m_val;
while(i < j) {
m_pos = (i + j)/2;
m_val = v[m_pos];
if(x == m_val) return m_pos + 1; // Return rank
else if(m_val > x) i = m_pos + 1; // Rank must be lower
else j = m_pos; // Rank must be higher since val < x
}
if(j < 0) return 1; // Top rank
else if(i >= v.size()) return v.size() + 1; // Bottom rank
else return (x >= m_val) ? m_pos + 1 : m_pos + 2; // Some middle rank
}
vector<int> climbingLeaderboard(vector<int> ranked, vector<int> player) {
// Derive vector v of unique values in ranked vector
vector<int> v;
v.push_back(ranked[0]);
for(int i = 1; i < ranked.size(); i++)
if(ranked[i - 1] != ranked[i]) v.push_back(ranked[i]);
// Binary search of rank in v for each score
vector<int> res;
for(auto x : player) res.push_back(find_rank(x, v));
return res;
}Что почитать по теме
Задачи, которые мы рассмотрели, дают общее представление о том, что такое алгоритмическое мышление, но эта тема заслуживает углублённого изучения. Книга Даниэля Зингаро с говорящим названием «Алгоритмы на практике. Решение реальных задач» — отличный учебник, который поможет совершенствоваться дальше. Зингаро увлекательно пишет и доходчиво объясняет базовые понятия курса: рандомизированные таблицы, рекурсию, динамическое программирование, поиск по графу и прочее. В книге есть приложение о Big O notation, с помощью которого можно аргументированно определять сложность алгоритмов.
Ещё одна книга, в которой автор понятно рассказывает о нескольких основных алгоритмах, — «Грокаем алгоритмы» Адитьи Бхаргавы. В книге есть несколько полезных иллюстраций и сниппетов кода на Python плюс полезная информация об основах алгоритмического мышления, которая пригодится на собеседованиях.
Андрей Грехов записал и выложил на YouTube несколько роликов, которые составляют отличное введение в динамическое программирование. Динамическое программирование — это мощное оружие, которое стоит добавить в свой арсенал. Освоив его, вы научитесь находить несколько способов решения задач в Data Science — проектах: задач на оптимизацию, когда то или иное количество (скажем, расходы или прибыль) надо максимально уменьшить или увеличить, или задач на комбинаторику, где нужно что-то посчитать, ответив на вопрос «Сколькими способами можно сделать XYZ?».
Динамическое программирование хорошо подходит для решения задач с двумя свойствами:
оптимальная подструктура, когда оптимальное решение части задачи помогает решить задачу в целом или её более крупную часть;
частичное совпадение подзадач, когда результат, полученный при решении одной подзадачи, можно использовать в решении другой подзадачи без его пересчёта — то есть с помощью сохранения результатов в памяти или кеширования.
Алгоритмическое мышление в эпоху искусственного интеллекта
В октябре 2023 года Мэтт Уэлш, бывший профессор информатики и технический директор Google, прочитал в Гарварде интересную лекцию с провокационным названием: «Большие языковые модели и конец программирования». Из неё следует, что развитие генеративного ИИ в целом, как и больших языковых моделей в частности, может кардинально изменить подход к разработке программного обеспечения. Да, люди, скорее всего, продолжат работать в области управления продуктом: за ними останется решение, какие программы нужно создавать и почему, в области тестирования и контроля качества — ведь кто-то должен убедиться, что программа работает как надо. Но, как считает Мэтт Уэлш, само преобразование спецификации задачи в код, готовый к работе в продакшн-среде, можно будет автоматизировать с помощью ИИ уже в обозримом будущем.
К концу 2023 года инструменты на базе ИИ, например GitHub Copilot, уже демонстрировали способность дописывать базовые типы кода: сценарии тестирования, простые циклы и условные конструкции. У таких инструментов явно виден потенциал, они повысят продуктивность работы программистов, а может быть, и вовсе заменят их. С тех пор ИИ неизменно добивается впечатляющих успехов, а прогнозы о его работе в мультимодальном режиме сбываются всё точнее.
В этом контексте стоит задуматься, насколько востребованным навыком будет алгоритмическое мышление для дата-сайентистов в эпоху искусственного интеллекта. Если вкратце, то, скорее всего, алгоритмическое мышление станет более важным, чем когда-либо.
Если отвечать чуть подробнее, стоит признать, что уже сегодня во многих случаях черновик алгоритма вроде сниппетов кода, которые мы использовали в разделах выше, можно создать с помощью инструментов генеративного ИИ, таких как ChatGPT или GitHub Copilot. В конце концов, такие ИИ-инструменты обучаются, собирая данные из интернета, и, конечно, в сети дефицита кода не наблюдается. Но это вовсе не означает, что каждый код качественный, так что мы вполне можем вернуться к ситуации «мусор на входе — мусор на выходе».
Любой код, генерируемый ИИ, обязательно нужно тщательно проверять и только после этого использовать в Data Science — проекте. А это значит, что ревьюеры с соответствующими техническими навыками останутся востребованными специалистами.
Более того, возможно, созданный ИИ код нужно будет оптимизировать или подстраивать под требования конкретного сценария использования, и, скорее всего, промпт-инжинирингом тут не ограничишься. На самом деле составить промпт, с помощью которого можно адекватно генерировать нужный код, уловив при этом неписаные ноу-хау и мотивацию промпт-инженера, иногда труднее и дольше, чем просто сразу написать код на выбранном языке.
При этом ни один подход не отменяет необходимости правильно сформулировать задачу и составить разумный план для реализации решения.
Для таких заданий, как формулирование и планирование задачи, доработка, кастомизация и ревью сгенерированного ИИ программного кода в соответствии с требованиями сценариев, скорее всего, и дальше потребуется изрядный уровень алгоритмического мышления наряду с глубоким пониманием намерения написания кода, то есть ответа на вопросы «зачем», «для чего». Маловероятно, что такую работу в скором времени удастся делегировать искусственному интеллекту, и не в последнюю очередь по этическим и юридическим соображениям. Только представьте, что программу по предотвращению столкновений с объектами в системе самоуправляемого автомобиля создаёт искусственный интеллект без надлежащего надзора людей.
Чтобы расти, нужно выйти из привычной зоны и сделать шаг к переменам. Можно изучить новое, начав с бесплатных занятий:
Аналитик данных и Data Scientist: как выбрать профессию;
Специалист по информационной безопасности: старт карьеры;
1С-аналитика: как стать специалистом по автоматизации процессов;
Вводный курс бакалавриата «Аналитика и Data Science».
Или открыть перспективы с профессиональным обучением и переподготовкой:
Онлайн-бакалавриат «Аналитика и Data Science»;