Сложности алгоритмов с примерами или что такое нотация Big O?

Многие из вас о ней слышали, кто-то даже раскладывает за 3 секунды сложность для любого алгоритма, который увидел в первый раз (привет 10x-инженерам), но остальные могут столкнуться c трудностями при оценке. Если вы новичок, Big O может быть одной из первых вещей, с которыми вы столкнётесь при изучении языка.

Цель поста — доступно объяснить, что это такое. Погнали!🚀

🟢 Понятие Big O
Нотация Big O используется для описания производительности функции или алгоритма, применяемого к набору данных, размер которого может быть неизвестен. Это делается с помощью нотации, которая выглядит следующим образом: O(1).

1️⃣ O(1) — эта производительность является лучшей из тех, что можно достичь.
Производительность алгоритма, которая равна O(1), не связана с размером набора данных, к которому он применяется. Поэтому не имеет значения, работаете ли вы с набором данных, содержащим 2, 5 или 1 000 000 элементов. Производительность алгоритма должна оставаться неизменной в любое время.

Пример алгоритма: получение элемента массива по индексу.

2️⃣ O(n) - пример сложности, которая растет по мере роста набора данных .
Эта нотация передает линейный рост. Время выполнения алгоритма или его производительность линейно уменьшается с ростом размера набора данных.

Пример алгоритма: map(), filter() и так далее. Ещё один пример это first(where:).
Если вы думаете, что как же так, first(where:) вернёт первый найденный и производительность точно лучше, чем O(n) — это не совсем так. Нотация предназначена для учёта наихудшего (или наиболее общего) сценария из возможных. Так и в этом примере нужный нам элемент с лёгкостью может быть в конце массива и тогда алгоритм переберёт все элементы.

3️⃣ O(n²) — квадратичная производительность, она характерна для некоторых простых алгоритмов сортировки.

Пример: сортировка пузырьком.

Генерация squareCoords из примера требует, чтобы мы перебирали целые числа с помощью flatMap. В этом flatMap снова цикл по squareCoords, используя map. Это означает, что строка return (i, j) вызывается 25 раз, что равно 5^2. Или, другими словами, n^2. Для каждого элемента, который мы добавляем в массив, время, необходимое для генерации squareCoords, растет экспоненциально. Создание координат для квадрата 6x6 займет 36 циклов и так далее. Уверен, вы понимаете, почему O(n^2) - не самая лучшая производительность.

4️⃣ O(log n) - сложность, которая растет в логарифмическом масштабе.
Алгоритм со сложностью O(log n) часто будет работать хуже, чем некоторые другие алгоритмы для небольшого набора данных. Однако по мере роста набора данных и приближения n к бесконечному числу производительность алгоритма будет снижаться все меньше и меньше.

Пример: бинарный поиск.

Что в итоге?
Big O — это одна из тех вещей, которые нужно часто практиковать, чтобы овладеть ими. Кому-то это даётся проще, кому-то сложнее, но всё приходит с опытом.

Что можно почитать?

📊 Примеры графиков.
📖 Здесь можно увидеть больше примеров.
📖 Cracking the Coding Interview — к этой книге можно относиться по-разному, но вычёркивать её точно не стоит.
📖 Тим Рафгарден: Совершенный алгоритм. Основы.
🛠 Примеры кода и графиков в Swift Algorithm Club на Github.

@iOS Dev

Пять стоп-слов для вашего iOS-приложения

Чтобы лучше понять, когда их использовать, нужно рассмотреть уровни оптимизации (Swift Optimization Levels). Когда вы собираете свое приложение, компилятор выполняет оптимизацию вашего кода.

Вы можете использовать различные уровни оптимизации для различных конфигураций сборки:

1️⃣ -Onone. Предназначен для обычной разработки. Он выполняет минимальную оптимизацию и сохраняет всю отладочную информацию.

2️⃣ -O. Компилятор выполняет агрессивную оптимизацию, которая может радикально изменить и тип, и количество выпускаемого кода. Отладочная информация будет передаваться, но с потерями.

3️⃣ -Osize. Это специальный режим оптимизации, в котором компилятор отдает приоритет размеру кода, а не производительности.

Чтобы изменить уровень оптимизации, можно перейти в Build Settings -> Optimization Level.

Нам доступно пять вариантов остановки приложения, кроме exit() и abort().

⚪ assert.
⚪ assertionFailure.
⚪ precondition.
⚪ preconditionFailure.
⚪ fatalError.

📖 Детально каждый из способов описал в статье на telegraph.

Когда их использовать и в каком количестве — тема не такая однозначная, как может показаться на первый взгляд. Но при разработке приложения каждый из перечисленных вариантов может быть полезен в той или иной степени.

@iOS Dev

Сохранение паролей c использованием Keychain в Swift

Keychain — это место для безопасного хранения небольших объемов данных, таких как пароли и API-токены. Полезно знать, как работать с Keychain в приложениях для iOS и Mac с помощью фреймворка Keychain Services.

Существует четыре общих действия для элементов связки ключей: добавление, обновление, чтение и удаление. Чтобы любое из них, нужно создать запрос и запустить функцию Keychain Services.

📖 В этой статье автор уделил внимание паролям, которые использует большинство приложений.

@iOS Dev

Как изменить status bar в симуляторе с помощью терминала?

Это может быть полезно при подготовке скриншотов для App Store или других маркетинговых материалов.

Возможно, вы знаете, что Apple всегда показывает 9:41 на всех своих скриншотах, когда видны часы — это потому, что первый iPhone был впервые показан миру именно в это время.

😉 Сделал сводный материал со списком команд и возможными параметрами, который может пригодиться.

Пример использования:

xcrun simctl status_bar booted override --time 09:46 --cellularBars 3 --dataNetwork LTE --wifiMode failed

@iOS Dev

CoreText в Swift в трёх частях: от HelloWorld к Typesetter
Вы когда-нибудь хотели создать компонент редактирования текста с нуля?

📖 Core Text предоставляет низкоуровневый программный интерфейс для компоновки текста и работы со шрифтами.

Механизм верстки Core Text разработан для обеспечения высокой производительности, простоты использования и тесной интеграции с Core Foundation. API обеспечивает высококачественный набор текста, включая преобразование символов в глифы, лигатуры, кернинг и так далее. Дополнительная технология шрифтов Core Text обеспечивает автоматическую замену шрифтов (каскадирование), дескрипторы и коллекции шрифтов, легкий доступ к метрикам шрифтов и данным глифов, а также многие другие возможности.

В серии статей рассматриваются его аспекты:

1️⃣ HelloWorld c использованием CoreText.

2️⃣ Font Descriptor, Font Metrics, Line height и не только разбираются в этой части.

3️⃣ Верстка текста — нетривиальная задача. CoreText предоставляет несколько полезных функций для отрисовки текста в прямоугольной рамке или вдоль заданного пути. И об этом пойдет речь в третьей части.

@iOS Dev

Как переместить фокус ввода, если у вас открыто два и более редактора?

Используйте CMD+J, а затем стрелки и Enter для подтверждения выбора.

#xcode #shortcuts

@iOS Dev

Конкурсные приложения для Swift Student Challenge

Apple поддерживает студентов по всему миру, которые любят программировать, с помощью захватывающего конкурса Swift Student Challenge.

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

Победители получают мерч #WWDC, индивидуальный набор значков и годовое членство в Apple Developer Program.

🛠 Подготовил для вас список репозиториев со всеми работами участников за прошедшие годы.

🔗 2022
🔗 2021
🔗 2020
🔗 2019
🔗 2018
🔗 2017
🔗 2016
🔗 2015
🔗 2014

@iOS Dev

Create ML в Xcode: создание, обучение и настройка моделей

Create ML — встроенный инструмент Apple для создания и обучения моделей. Create ML фактически позволяет нам обучать наши модели без использования кода, и входит в состав инструментов IDE.

Доступно несколько шаблонов моделей для работы с различными ресурсами: изображениями, видео, звуком, текстом, движениями, позами и таблицами.

Create ML использует инфраструктуру машинного обучения, встроенную, например, в такие продукты Apple, как Photos и Siri. Это означает, что ваша классификация изображений и модели естественного языка компактнее и требует гораздо меньше времени для обучения.

Наш читатель Максим Скорынин — iOS Engineer в Evil Martians. Делюсь двумя крутейшими статьями за авторством Максима на эту тему.

📖 Обнаружение объектов с помощью Create ML: изображения и датасет.
В этой статье пошагово описывается процесс подготовки демо для iOS. Это приложение поможет идентифицировать и отмечать расположение номерных знаков автомобилей из видеопотока в реальном времени.

📖Анализ текста в реальном времени с помощью Word Tagger.
В этом материале автор делится опытом подготовки данных и создания ML-модели для распознавания кулинарных рецептов.

Тема Create ML обладает невероятным потенциалом, прочтите, и, возможно вы придумаете идею своего следующего приложения, которое ворвётся в топ аппстора.

@iOS Dev — расширяем базу знаний 😉

Управление памятью — важная тема в Swift и iOS-разработке. Cуществует множество руководств, объясняющих, когда следует использовать weak self в замыканиях.

📖 Это короткая история, когда утечка памяти все же может произойти.

Для целей этой статьи предполагается, что у нас есть класс с двумя функциями. Каждая функция выполняет что-то с помощью замыкания. В примерах из этого материала автор рассмотрел случаи увеличения счетчика ссылок и случаев, когда это может привести к утечке памяти.

💡 Совет от автора: если у нас слишком много замыканий, лучшим вариантом будет рефакторинг в виде отдельной функции.

————————————
Кстати! Если вы хотели бы поделиться своим опытом разработки с сообществом, то есть хорошая новость.

😎 Mobius начинает сбор докладов на свою осеннюю конференцию, и это отличный повод стать спикером. Посмотрите список тем и выберите ту, которая близка именно вам.

Рефакторинг UICollectionView с использованием дженериков в компании Etsy

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

1️⃣ Более старый код может не быть спроектирован так, чтобы использовать все преимущества оптимизации платформы и новых возможностей.

2️⃣ Производительность разработчиков также может пострадать.

3️⃣ Сложнее привлекать разработчиков к работе с кодом, который неоднократно изменялся и расширялся в течение многих лет, а также сложнее проверять и тестировать изменения.

Когда приложение Etsy только создавалось, экраны были относительно простыми вещами с ограниченной ответственностью. Имело смысл программировать их более или менее монолитно. Но когда в компании посмотрели на производительность и подумали о болевых точках инженеров, пришло решение, что пора обратить внимание на легаси-код.

В старой реализации, чем больше и сложнее становился экран, тем больше страдала его производительность: сборка одного огромного view заставляла приложение выполнять множество вычислений лэйаута заранее, включая те, которые лучше отложить. Гораздо менее затратный и более гибкий подход предполагает переосмысление экрана как набора независимых views.

📖 В этом материале идет речь о том, что предприняли в компании Etsy для улучшения ситуации. С примерами кода, конечно же.

@iOS Dev

Пример реализации модульной архитектуры в компании Just Eat

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

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

⚪ Бизнес-причины. Например, переиспользование кода между крупными проектами компании.

⚪ Технические причины. Сложно поддерживать код, замедляется разработка.

⚪ Несколько команд. Распределение модулей между командами позволит повысить скорость итераций.

⚪ Существующая база знаний. Возможно, члены команды уже знакомы с конкретными решениями (Carthage, CocoaPods, Swift Package Manager, ручная настройка фреймворков в Xcode). В случае конкретного знакомства с какой-либо системой рекомендуется начать с неё.

📖 На примере этой статьи можно познакомиться с опытом компании, понять, через что они прошли. А также посмотреть на структуру модулей и общую архитектуру в целом.

🛠 Кстати, опенсорнсные модули доступны на Github.

@iOS Dev

Ускоряем запуск приложения: 7 советов для увеличения производительности

Важно, чтобы запуск приложения был плавным и максимально быстрым. Длительное время запуска может означать потерю большого количества пользователей.

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

📖 Вот эти советы:

1️⃣ Установите целевую продолжительность запуска. На #WWDC 2019 в Apple рекомендовали не превышать 400 мс.

2️⃣ Напишите тесты, чтобы создать последовательный мониторинг и предотвратить регрессию.

3️⃣ Используйте органайзер Xcode для сбора статистики производительности времени запуска приложения.

4️⃣ Управляйте фреймворками с помощью статистики DYLD.

5️⃣ Замените или удалите зависимости, где это возможно.

6️⃣ Отложите логику приложения до рендера первого фрейма.

7️⃣ Оптимизируйте производительность логики запуска. Не всегда шестой пункт достижим, поэтому по возможности посмотрите на важные методы и способы их улучшения.

Производительность запуска приложения зависит от многих факторов. Все начинается с измерений и установки целевой продолжительности запуска. Xcode Instruments и статистика DYLD дают нам правильное направление, чтобы начать улучшать время запуска нашего приложения.

@iOS Dev

Использование кортежей в Swift на примере switch/case

Вы можете использовать кортежи и для проверки нескольких значений в одном операторе switch.

Каждый элемент кортежа может проверяться на разное значение или интервал значений.

В качестве альтернативы можно использовать символ подчеркивания (_) для поиска любого возможного значения.

В приведенном ниже примере берется точка (x, y), выраженная как простой кортеж типа (Int, Int), и классифицируется на графике, который следует за примером.

let somePoint = (1, 1)
switch somePoint {
case (0, 0):
print("\(somePoint) в начале координат")
case (_, 0):
print("\(somePoint) на оси x")
case (0, _):
print("\(somePoint) на оси y")
case (-2...2, -2...2):
print("\(somePoint) внутри рамки")
default:
print("\(somePoint) за пределами рамки")
}
// Выведется "(1, 1) внутри рамки"

Оператор switch определит, находится ли точка в начале координат (0, 0), на красной оси x, на зеленой оси y, внутри синей рамки 4 на 4 с центром в начале координат или за ее пределами.

😉 В отличие от языка C, Swift позволяет в switch/case рассматривать одно и то же значение или интервал значений.

Фактически, точка (0, 0) может соответствовать всем четырем вариантам в этом примере.

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

@iOS Dev

Продвинутые координаторы в iOS

📖 В этой статье рассматривается решение для шести распространенных проблем, с которыми мы можем столкнуться при использовании паттерна координатора в приложениях для iOS:

⚪ Как и когда использовать дочерние координаторы?

⚪ Как быть с навигацией «Назад»?

⚪ Как передавать данные между контроллерами?

⚪ Как работать с координаторами при наличии таббара?

⚪ Как работать с segues?

⚪ Как вместо этого использовать протоколы или замыкания?

Кроме этого, в материале много практического кода для реальных примеров решения этих проблем.

@iOS Dev

🎉 В iOS 16 появилось API для обновления текущей ориентации интерфейса!

Если вы вдруг используете решение со скриншота ниже, то вы с лёгкостью сможете выпилить старое решение в новой оси.

Для этого достаточно будет использовать новый метод:

requestGeometryUpdate(.iOS(interfaceOrientations: .portrait))

👨‍💻 Обратил внимание на это Simon B. Støvring.

@iOS Dev

Что нового в MapKit в iOS 16?

MapKit — это фреймворк для отображения Apple Maps в вашем приложении. Это помогает разработчикам обеспечить поддержку навигации и многое другое.

Что же поменялось?

⚫ Новый UI — это совершенно точно изменит пользовательский опыт с 3D: не только зданиями, но и картой в целом.

⚫ Конфигурация карты. Теперь нужно использовать MKStandardMapConfiguration, MKHybridMapConfiguration или MKImageryMapConfiguration.

⚫ Улучшили оверлэй. В iOS 16 оверлеи теперь также будут отображать 3D-здания, при этом они будут скрыты при просмотре в 2D.

⚫ Режимы наложения. Вы можете затемнить остальную часть карты, чтобы сфокусироваться на нужном участке.

⚫ Look Around. Наконец-то Apple предоставила свой Look Around API для использования в наших приложениях. С ним доступен MKLookAroundSceneRequest, который принимает координаты для поиска участка LookAround. Когда он будет создан, вы можете инициализировать MKLookAroundViewController с указанием местоположения.

Что можно прочесть на эту тему?

📖 Описание фреймворка на сайте Apple.
📖 Статья с разбором фич.

🛠 Пример демо-приложения.

@iOS Dev

😲 Посмотрите, какую красоту можно сделать с помощью эффекта увеличения в SwiftUI!

@iOS Dev

Как добавить фото или видео на симулятор?

Есть два способа добавить мультимедиа в системное приложение Photos.

1️⃣ Если вам просто нужно быстро добавить медиафайлы в симулятор, вы можете просто перетащить медиафайл из любого места на вашем Mac в симулятор.

2️⃣ Воспользуйтесь командой xcrun simctl addmedia SIMULATOR_UUID|booted ~/path/to/file/test.jpg

Здесь path это путь к вашему файлу, а test.jpg это его название.

@iOS Dev