Газета "Алгоритмы и Факты"

Курс приобрел дополнительный (необязательный) раздел: "Информация для общего развития". В нем будут собраны интересные факты: математические, исторические да и просто любопытные.

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

Array(s.utf8) -vs- Array(s)

Частенько, решая задачи со строками, не попадаешь в первый столбик, хотя написал оптимальное решение. Наиболее частая ошибка - Array(s).

Давайте разберемся почему в самом быстром решении Array(s.utf8) и что это такое.
___

В Swift строка String - не массив символов.

String:
• хранится в UTF-8;
• поддерживает Unicode;
• каждый Character может занимать различное число байт;
• доступ к Character - операция не O(1).

При такой записи

for ch in s { ... }

Swift под капотом:
• декодирует UTF-8;
• собирает Character;
• проверяет границы;
• создает value type Character.
___

s.utf8 - последовательность байтов (UInt8), уже лежащих в памяти строки.

Array(s.utf8) это:
• линейный массив байтов;
• без Unicode-логики;
• без декодирования;
• с прямым доступом по индексу.
___

String(bytes: array, encoding: .utf8)
• однократное создание строки;
• без поэлементного append;
• без пересчета индексов String.Index;
• без проверки Unicode.
___

Решая задачу на собеседовании важно уточнить:
Т.к. вход ограничен ASCII-символами, можно безопасно работать с UTF-8 байтами и получить линейный алгоритм без накладных расходов Unicode.

Cобеседование би лайк

ASCII

ASCII (American Standard Code for Information Interchange) - стандарт кодирования букв латинского алфавита, цифр, некоторых специальных знаков и управляющих символов, принятый в 1963 году Американской ассоциацией стандартов как основной способ представления текстовых данных в ЭВМ.

Проще говоря: таблица соответствий.
___

Классический ASCII содержит 128 символов, которые делятся на 3 группы:

1. Управляющие символы (0–31)
Это не буквы и не цифры. Их не видно. Необходимы для управления текстом.
0 - конец строки
9 - TAB

2. Печатные символы (32–126)
Пробел и знаки
32 - " "
33 - "!"
64 - "@"

Цифры
48 - "0"
49 - "1"
...
57 - "9"

Большие буквы
65 - "A"
66 - "B"
...
90 - "Z"

Прописные буквы
97 → "a"
98 → "b"
...
122 → "z"

3. DEL (127)
Исторический символ удаления. Сейчас почти не используется.

ASCII - только латиница. Никаких эмодзи, кириллицы или китайских иероглифов.
___

Самое важное свойство ASCII - символы идут подряд
___

Идея в любом языке одинаковая:
Символ = число

Всегда можно:
• получить код символа;
• работать с ним как с числом;
• превратить обратно в символ.
___

Unicode не заменил ASCII - он его включил.
В 70–90-х: операционные системы, файловые форматы, протоколы уже существовали и использовали ASCII. Unicode был вынужден подстроиться, а не диктовать условия.

"A" в ASCII = "A" в Unicode
"0" в ASCII = "0" в Unicode
Байтовые значения совпадают. Это сделано специально, чтобы ничего не сломать.
___

Весь интернет построен на ASCII
GET / index.html HTTP/1.1
Host: example. com

• ключевые слова
• разделители
• управляющие символы
Все это ASCII.

Концовка видео...

Shrink для хеш-таблицы
(перерасчет при удалении элементов)

Други, все чаще всплывают новости про блокировку/замедление телеграм.

В ВК есть группа. Там никакой движухи, только видео с ютуба.

Присоединяйтесь, чтобы не потеряться...