Большинство соревнований для программистов требуют максимально быстрого решения и реализации алгоритмических задач на любом из языков программирования. Среди мобильных разработчиков популярны хакатоны, но сегодня речь пойдет о контестах. Наиболее известные из них – Codeforces Rounds, VK Cup Engine, ACM ICPC. Мы поговорим о том, как они устроены, какие плюсы и минусы есть у разработчиков с «олимпиадным» бэкграундом и как этот опыт влияет на работу с коммерческими задачами в мобильной разработке.
Принципы олимпиадного программирования
Олимпиадное программирование — участие в соревнованиях по решению нетривиальных алгоритмических задач. Программисту важно быстро решить задачу, не сделав багов. Но, как вы знаете, багов нет только в том коде, который не написан.
Принцип всех таких олимпиад один – жюри готовит описание задачи, формат входных и выходных данных программы, эталонное решение и тесты для задачи. Есть и ограничения на используемую память и время исполнения.
Участники пишут программу, которая получает на вход данные по формату задачи и выводит решение. Затем исходный код отправляется на тестирование: его компилирует площадка контеста, на заготовленных тест-кейсах проверяет используемую память и время исполнения. После чего выдается вердикт о правильности решения задачи – всё просто!
Как вы понимаете, в таких условиях самые важные показатели в решении задачи – это затраченные память и время. И нужно из бесконечного количества способов решения найти самый эффективный. Для этого используется понятие алгоритмической сложности, которое можно показать на примерах разных сортировок.
Сортировка пузырьком (в олимпиадном стиле):
import Foundation
var a = [10, 6, 4, 3, 98, 2135, 2, 75, 6] // Массив входных данных
let n = a.count
for _ in 0 ..< n - 1 {
for j in 0 ..< n - 1 {
if a[j] > a[j + 1] {
a.swapAt(j, j + 1)
}
}
}
print(a) // [2, 3, 4, 6, 6, 10, 75, 98, 2135]Сортировка слиянием (в продакшн-стиле):
import Foundation
var a = [10, 6, 4, 3, 98, 2135, 2, 75, 6] // Массив входных данных
func merge(left:[Int], right:[Int]) -> [Int] {
var mergedList = [Int]()
var left = left
var right = right
while left.count > 0 && right.count > 0 {
if left.first! < right.first! {
mergedList.append(left.removeFirst())
} else {
mergedList.append(right.removeFirst())
}
}
return mergedList + left + right
}
func mergeSort(_ list:[Int]) -> [Int] {
guard list.count > 1 else {
return list
}
let leftList = Array(list[0 ..< list.count/2])
let rightList = Array(list[list.count / 2 ..< list.count])
return merge(left: mergeSort(leftList), right: mergeSort(rightList))
}
a = mergeSort(a)
print(a) // [2, 3, 4, 6, 6, 10, 75, 98, 2135]Оба кода приводят к одинаковому результату, но есть разница. Первый выполняет два вложенных цикла, каждый из которых не более чем на N итераций. А второй сливает отсортированные массивы, что выполняется не более чем за N log(N) итераций. Это значит, что верхняя оценка первого алгоритма – N^2 действий, а второго – N log(N). Это принято записывать в нотации O большое, O(N^2) и O(N log N) соответственно. |
N – это размерность массива, и зависит она от входных данных. Таких данных может быть несколько, а оценка записывается с использованием всех входных параметров, влияющих на количество действий алгоритма.
Есть еще несколько правил оценки – например, сокращение членов с более низкими порядками и объединение одинаковых членов без множителей. Например, O(N^2 + N) превратится в O(N^2), а O(N + N) превратится в O(N). Подробнее об этом можно почитать на Википедии.
Плюсы
Рассмотрим плюсы такого подхода.
Ускоряем работу приложения
С опытом спортивного программирования приходит умение ускорять алгоритм, не меняя его асимптотики. Для этого вернемся к сортировке пузырьком
import Foundation
var a = [10, 6, 4, 3, 98, 2135, 2, 75, 6] // Массив входных данных
let n = a.count
for i in 0 ..< n - 1 {
var swapped = false
for j in 0 ..< n - i - 1 {
if a[j] > a[j + 1] {
a.swapAt(j, j + 1)
swapped = true
}
}
if !swapped {
break
}
}
print(a) // [2, 3, 4, 6, 6, 10, 75, 98, 2135]Мы немного модифицировали алгоритм. Из доработок – теперь мы не проверяем правую часть массива, потому что понятно, что она уже отсортирована, так как самый большой элемент перешел в правую часть. И если мы за весь проход не сделали ни одного свапа, значит, массив уже отсортирован, и дальнейшее выполнение алгоритма никаких действий не сделает.
Если применять глубокие навыки спортивного программирования, можно заметно ускорить работу приложения. Допустим, вы используете у себя в приложении какой-то сложный алгоритм обработки словаря с тремя вложенными циклами. Немного разобравшись в новом для себя виде дерева, вы поменяли словарь на самописное дерево и ускорили алгоритм обработки с O(N^3) до O(N log^2 N). Это и правда довольно ощутимый прирост производительности, что можно считать неплохим плюсом и поставить новую ачивку в свое резюме.
Уменьшаем потребляемую память
Олимпиадные программисты за счет грамотного выделения памяти и работы с ней могут не только ускорить работу приложения, но еще и сократить время его запуска и отображения экранов. Там, где обычный разработчик просто накидает lazy property, олимпиадный программист сэкономит пару сотен килобайт оперативной памяти на использовании самописных структур данных.
Увеличиваем скорость написания кода
В спортивном программировании все участники сильно ограничены во времени и пишут код очень быстро. Иметь разработчика, который решает задач на 20 сторипоинтов, когда все остальные закрывают только 10-15, очень классно.
Минусы
Но минусы олимпиадного бэкграунда тоже есть – давайте подробнее рассмотрим некоторые примеры.
Сложно читать ваш код
Вспомним пример про дерево, когда вам удалось ускорить работу приложения. Это было одним из наших плюсов, но теперь превратилось в минус – только вы умеете обращаться со своим деревом.
Схожая ситуация может получиться, когда вы используете много функций высшего порядка в одной строчке (10 фильтров, 5 редьюсов). Все же хочется, чтобы ваш код оставался поддерживаемым.
Требуются доказательства
Иногда для внедрения кода требуется доказать его работоспособность. Не всегда понятно, как это сделать. Даже техлиды не всегда разбираются в сложных алгоритмах и структурах данных.
Есть много полезных структур данных и алгоритмов, легких в освоении и простых в написании. Например, генерация сочетаний из N элементов. Их можно легко использовать, но если вы вдруг решите реализовать в своем приложении АВЛ-дерево (еще ссылка), то новоиспеченный джун на вашем проекте может наложить на вас пару проклятий.
Падает качество кода
Ускоряя написание кода, спортсмены пренебрегают его качеством и тестируемостью. Хоть решение и реализуется достаточно быстро, общая скорость разработки может упасть из-за частых реджектов PR и дополнительных ревью.
Чем программист отличается от разработчика
Тестирование кода
«Олимпиадники» тоже тестируют код, но их тесты довольно специфичны. В спортивном программировании распространены стресс-тесты – они используются, когда придумано два алгоритма: рабочий и быстрый. Рабочим может быть простое, но асимптотически сложное решение, а быстрым – любое придуманное решение, доказывать которое сложно или долго. В таком случае пишется генератор входных данных и поочередно запускаются оба алгоритма, после чего сравниваются результаты и ищутся расхождения.
Так мы быстро находим кейсы, при которых наш оптимальный алгоритм отрабатывает неправильно, и можем на построчном выполнении найти ошибки и исправить их, либо кардинально доработать алгоритм. Но, на самом деле, это не точно, потому что входные данные генерируются рандомно, и такие кейсы стресс-тесты могут просто не отследить.
Выбор решения
Попробуйте разобраться, что делает тело данной функции:
XXItem *item = [self itemForIndexPath:indexPath];
NSPredicate *pr = [NSPredicate predicateWithBlock:^BOOL(XXItem *_Nullable evaluatedObject, NSDictionary<NSString *,id> * _Nullable bindings) {
return [evaluatedObject isEqual:item];
}];
return [self.selectedItems filteredArrayUsingPredicate:pr].count > 0;А вот так:
XXItem *item = [self itemForIndexPath:indexPath];
for ((XXItem *) selectedItem in self.selectedItems) {
if ([selectedItem isEqual:item]) {
return YES;
}
}
return NO;Каждая из этих функций проверяет, выбран ли айтем в данной ячейке:
- (BOOL)isSelectedIndexPath:(NSIndexPath *)indexPathТолько в первом варианте разработчик придумал первое попавшееся решение, а во втором – написал свой поиск, который по факту стал более читаем и понятен. При этом он не проходит по оставшимся элементам, если уже нашел нужный. Поэтому использование уже написанных методов в стандартной библиотеке – не всегда самое верное и простое решение. Стоит иногда анализировать задачу и искать пути ускорения и повышения читаемости.
Архитектурные ценности
В разработке, помимо скорости, важны расширяемость, читаемость и переиспользуемость кода. Программист, в отличие от разработчика, пишет одноразовый код, в одном файле и зачастую в одном классе. На олимпиаде иногда можно пренебречь повторяемостью кода: проще скопировать один и тот же код в два разных места, нежели выносить его в функцию. Также для экономии времени код может быть нагорожен в одну большую кучу, без разделения на переменные и понятного нейминга.
Как я упоминал выше, использовать много функционального кода в одном блоке тоже не самая лучшая идея:
optionsInGroup.reduce(
into: [
PizzaModeOption.left: [Option](),
PizzaModeOption.full: [Option](),
PizzaModeOption.right: [Option]()
]
) { (dict, option) in
dict[option.pizzaMode]?.append(option)
}.sorted { (pair1, pair2) in
pair1.value.reduce(0) { $0 + $1.price } > pair2.value.reduce(0) { $0 + $1.price }
}[1..<3].forEach { pair in
pair.value.forEach {
$0.price = 0
}
}Хотя такой код пишется очень быстро и сходу понятен автору, коллегам по проекту придется тратить дополнительное время для его понимания.
Еще одна проблема fast coding’а в том, что количество ветвлений никак не мешает работе программы, но сильно портит общую картину и читаемость. Например, такой код на Objective-C:
- (void)foo {
if (firstCondition && secondCondition) {
// <code>
}
}можно заменить следующим аналогом:
- (void)foo {
if (!firstCondition || !secondCondition) { return; }
// <code>
}А в случае со Swift нам открывается более крутая возможность – можно использовать guard, оставив неизменными наши условия:
func foo() {
guard firstCondition && secondCondition else { return }
// <code>
}Пока в функции одно такое ветвление, кажется, что все в порядке и никаких проблем нет, но, когда в конце функции 5-10 закрывающих скобок от if’ов без else, это выглядит грязно и крипово.
Немного про джунов
Программисты-спортсмены обычно очень умело используют структуры данных. Там, где обычный джун-разработчик напишет что-то подобное для добавления объекта в массив:
if !self.contents.contains(where: { $0 == newObject }) {
self.contents.append(newObject)
}И будет удалять из него объекты примерно так:
guard let index = self.contents.firstIndex(where: {
$0 == removingObject
}) else { return }
self.contents.remove(at: index)Разработчик с олимпиадным бэкграундом или опытный разработчик поймет, что в данном случае поддерживается инвариант единственности значения. В таком случае он будет просто использовать Set, упростив тем самым код. А заодно обезопасив проект от возможных багов, которые могли возникнуть при расширении функционала. Например, в случае, когда разработчик просто не знает, что в данном массиве должна поддерживаться уникальность элементов.
Финишируем
Олимпиадное прошлое, безусловно, полезно. Но в большинстве случаев код разработчиков-олимпиадников мне кажется не самым читаемым и понятным, если они не перестроились на режим коммерческой разработки. У олимпиадников мозг работает немного иначе, они генерируют сотни крутых идей в минуту, только успевай записывать. Качество и чистота при такой быстрой записи порой хромают, и код требует рефакторинга.
Если программист научился писать читаемый код и разобрался с архитектурой, он быстро станет очень крутым и перспективным разработчиком. Но, скорее всего, столкнется с одной единственной проблемой: такие разработчики живут алгоритмами, и им не так просто в текущих реалиях найти интересный проект, где можно полностью раскрыться и показать себя. К счастью, такие проекты все же есть (пишите в личку).
Где потренироваться
Подборка площадок от золотого медалиста ACM ICPC:
