Большинство соревнований для программистов требуют максимально быстрого решения и реализации алгоритмических задач на любом из языков программирования. Среди мобильных разработчиков популярны хакатоны, но сегодня речь пойдет о контестах. Наиболее известные из них – 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:
ссылка на оригинал статьи https://habr.com/ru/articles/592445/
Добавить комментарий