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 для хеш-таблицы
(перерасчет при удалении элементов)

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

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

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

TimSort

TimSort - гибридный алгоритм сортировки, опубликованный в 2002 году Тимом Петерсом.

Если верить Википедии:
В настоящее время является стандартным алгоритмом сортировки в Python, OpenJDK 7, Apple Swift Standard Library 5 и реализован в Android JDK 1.5.
___

Основная идея
В реальной жизни данные почти никогда не полностью случайные. Они частично отсортированы.
TimSort создан под реальный мир, а не под худший теоретический случай.
__

Общая идея алгоритма
• разделить входной массив на уже отсортированные подмассивы;
• если подмассив небольшой, применить Insertion Sort;
• объединить полученные подмассивы через Merge Sort.
___

Ключевой момент - runs (уже отсортированный кусок массива).

TimSort проходит по массиву слева направо:
• если последовательность возрастает - оставляем без изменений;
• если убывает - переворачиваем.

TimSort вводит параметр minRun (обычно 32–64).
Откуда такое значение?
Мелкие куски плохо мержить. Накладные расходы начинают доминировать.

Если найденный run слишком маленький, он расширяется с помощью Insertion Sort до minRun.
___

Что происходит дальше?

Все найденные runs складываются в стек. Но не просто "положил и забыл", проверяется условие:
a, b, c - три верхних runs.
а > b + c
b > с

Это необходимо, чтобы глубина стека была O(log n) для сбалансированного слияния без деградации).
___

Фишка TimSort - galloping mode

Пример: Объединяем 2 массива
first: 1 2 3 4 5 6 7 8 9 10
second: 100 101 102

Сравниваем 1 и 100, берем 1
Сравниваем 1 и 101, берем 1
Сравниваем 1 и 102, берем 1
Бесполезные действия, согласитесь. В таких ситуациях подключается galloping mode.

Если один run "выигрывает" слишком часто подряд, перестаем сравнивать по одному элементу. Выполняем экспоненциальный поиск границы (по факту бинарный поиск).

first[i + 1]
first[i + 2]
first[i + 4]
first[i + 8]
first[i + 16]
Ищем место, где элементы перестанут быть меньше second[j]. После этого TimSort возвращается в обычный режим.
___

Сложность TimSort
• Отсортированный массив - O(n)
• Почти отсортированный массив - близко к O(n)
• Случайная последовательность - O(n log n)
• Худший - O(n log n)