Большинство соревнований для программистов требуют максимально быстрого решения и реализации алгоритмических задач на любом из языков программирования. Среди мобильных разработчиков популярны хакатоны, но сегодня речь пойдет о контестах. Наиболее известные из них – 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 – это размерность массива, и зависит она от входных данных. Таких данных может быть несколько, а оценка записывается с использованием всех входных параметров, влияющих на количество действий алгоритма.

Есть еще несколько правил оценки – например, сокращение членов с более низкими порядками и объединение одинаковых членов без множителей. Например, 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:

• https://codeforces.com

• https://www.hackerrank.com

• https://atcoder.jp/