4 малоизвестные функции Swift

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

Оптимизация хвостовой рекурсии

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

func tailRecursion(n: Int) {
    guard n != 0 else { return }
    print(n)
    tailRecursion(n: n-1)
}

В отличие от обычной рекурсии:

func usualRecursion(n: Int) {
    if n > 0 {
        usualRecursion(n: n-1)
    }
    print(n)
}

Swift использует оптимизацию хвостовой рекурсии, которая не добавляет вызов метода в стек вызовов в памяти, а переходит к началу функции. Это потребляет значительно меньше памяти стека.

В предыдущих примерах normalRecursion(n: 300000) аварийно завершает работу с Segmentation fault, тогда как tailRecursion(n: 1000000) работает нормально.

Эксперименты проводились на моем компьютере. Результаты для этих параметров могут отличаться на других компьютерах.

Вы можете увидеть оптимизацию в сгенерированном ассемблерном коде.

xcrun swiftc -O -S File.swift > main.asm

Даже если вы не знаете язык ассемблера, вы можете увидеть в файле main.asm, что одна из команд jamp (функции, начинающиеся с ‘j’) выполняется для хвостовой рекурсии, в то время как стандартный вызов функции callq вызывает обычную рекурсию.

На основании этой оптимизации можно сделать вывод, что если есть возможность рекурсии в конце самой функции, то лучше сделать именно так.

Хранение отрицательных чисел

Во многих языках программирования числа со знаком хранятся в виде набора битов, где первый бит — это знак числа (0 — положительное число, 1 — отрицательное число).

Остальные биты представляют значение. Например, в типе, который хранит 1 байт, 00000001 — это число 1, 10000001 — это число -1.

Но в Swift система хранения оптимизирована для быстрых операций, а числа хранятся с помощью метода, называемого “дополнением до 2”. Чтобы описать отрицательное число в этой системе, нужно записать это число в битовое представление, затем инвертировать биты и добавить 1. Например, если это число равно -15:

• записать биты десятичного числа 15: 0001111
• инвертировать биты: 1110000
• добавить 1: 1110001
• и, как уже было сказано, в начале нужно добавить бит 1

Окончательный результат будет 11110001.

Если мы хотим преобразовать битовое представление 11110001 в десятичный формат, нам нужно

• инвертировать биты: 0001110 (мы должны опустить первый бит, так как он представляет знак числа)
• добавить 1:0001111
• преобразовать в десятичный формат: 15
• и добавить знак: -15

Такое представление чисел позволяет выполнять арифметические операции быстрее на низком уровне.

// The way to get inner representation of a negative number:
String(UInt8(bitPattern: Int8(-15)), radix: 2)

Одна функция может работать с разной скоростью

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

Например, суффиксная функция в протоколе Sequence работает со сложностью O(n), в то время как та же функция в протоколе RandomAccessCollection (который наследуется от Sequence, примером структуры, соответствующей этому протоколу, является обычный массив) уже работает с сложность O(1). На больших объемах данных эта разница будет хорошо заметна. Поэтому помните о протоколе, с которым вы хотите работать.

// define an array
let array = 0...100_000

print("start array suffix \(Date())")
// suffix(5) works O(1)
array.suffix(5)
print("end array suffix \(Date())")

// define a sequence
let seq = sequence(first: 0, next: { $0 < 100_000 ? $0 + 1 : nil})

print("start sequence suffix \(Date())")
// suffix(5) works O(n), iterates every element of the sequence
seq.suffix(5)
print("end sequence suffix \(Date())")

Разрешение коллизий в словаре

Как мы знаем, при хранении элементов в словаре могут возникать коллизии. Хэш-значения разных элементов могут совпадать, что является типичной ситуацией, которая разрешается специально (для этого в ключевом элементе должна быть реализована операция ==).

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

Когда вы ищете элемент по ключу, а в Словаре уже есть другие элементы по хешу, у нас будет следующая ситуация. Типичный алгоритм проходит по связанному списку и проверяет равенство элементов до тех пор, пока не встретит эквивалентный или не проверит все элементы с одинаковым хешем. Этот метод хорош и относительно прост для объяснения, но на самом деле Swift имеет другую реализацию.

Проще говоря, все записи хранятся в одном массиве, доступ к которому осуществляется по ключевому хешу. Если произошло столкновение, следует записать новый элемент в тот же массив, но на определенном расстоянии от элемента, с которым произошло столкновение. Если эта ячейка тоже занята, проверяют следующую ячейку на таком же расстоянии и т. д. Эти проверки могут переходить с конца массива к его началу (логическое кольцо). Название метода разрешения коллизий — открытая адресация с линейным пробированием (Open Addressing with Linear Probing). В этом решении все элементы хранятся в общем пространстве, и для поддержания работы связанного списка не требуется дополнительная память.

Посмотреть реализацию можно здесь.

Открытый код Swift

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

Кроме того, вместе с сообществом можно разрабатывать библиотеки, среди которых swift-markdown, swift-algorithms, swift-numerics, swift-collections, swift-atomics.

Источник