Computer Science

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

Алгоритмы. Бинарный поиск

Мы уже начинали объяснять алгоритмы, но заленились и они увязли. Вот статьи, которые мы успели написать: про математические матрицы, краткий ввод в алгоритмы и разные способы вычислений чисел Фибоначчи.

Основы

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

Для некоторых алгоритмов нет смысла рассматривать объём памяти, например для нескольких видов сортировок, линейного и бинарного поиска. Где надо — покажем и расскажем почему.

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

  • О для худшего времени исполнения
  • Омега для лучшего
  • Тетой обозначают ширину эффективности

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

Бинарный поиск

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

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

Возьмём отсортированный массив чисел от 1 до 50 и будем там искать 33. Делим самый большой индекс на два, помним про нумерацию с нуля: 49/2 = 24.5, округляем до 24. Элемент с индексом 24 это наш центр, от него будут все движения.

  1. Первое что делает поиск, проверяет равно ли искомое число центральному — 33 ≠ 25.
  2. Тогда он сравнивает числа: если искомое меньше центра — оставляем только левый массив, если больше — правый. 33 > 25, значит остаётся массив от 26 до 50.
  3. Опять делим уже новый массив пополам: 24/2 = 12; проверяем центральный элемент и сравниваем:
    33 < 38. Делаем так пока искомое число не попадёт в центральный элемент или пока не останется массив на один элемент, тогда он и попадёт в центральный.
На каждом проходе алгоритм получает новый массив в два раза меньше предыдущего

Бинарный поиск ищет данные по индексам элементов, поэтому если нужно найти что-то символьное — он тоже справится.

На примере Вконтакте

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

Вы начинаете логиниться и ждёте пока ВК сопоставит ваши данные с уникальным скрытым IDшником. Если бы в базах использовался поиск перебором сверху вниз и на каждую операцию уходило хотя бы миллисекунда, в худшем случае вы бы зашли через 7 дней.
Бинарный поиск найдёт вашу учётку за 0.029 секунд — чистое время поиска, без интернет передач.

Пример выдуманный, потому что домашние компьютеры работают быстрее и мы не знаем как на самом деле ВК ищет эти данные. Но он наглядно объясняет разность между линейным и логарифмическим временем выполнения.

 53   4 дн   алгоритмы

Сборник по СИКПу

В прошлой статье мы закончили третью главу СИКПа. Всего их пять, но остальные две объясняют как сделать транслятор, а это не наша область. Этой статьёй собираем статьи по СИКПу в кучку, чтобы было удобно пройти его за вечер.

I — Абстракция функций

Вводная в СИКП

В первой статье мы объяснили основы: синтаксис языка Scheme, рассказали про базу любого языка программирования и объяснили почему переменные и функции используют для абстракции.

Основы СИКПа

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

Чёрные ящики и блочная структура

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

Функции, области видимости и структуры

Там же повторили области видимости: как и зачем их разделять. Про области мы писали в статьях по пайтону

Процессы исполнения

Когда интерпретатор выполняет функцию, она порождает какой-то процесс. Мы разобрали три простых процесса — рекурсивный процесс, итеративный процесс и древовидную рекурсию. Ещё рассказали про хвостовую рекурсию и отличия между рекурсией, рекурсивной функцией и рекурсивным процессом.

Простые процессы в СИКПе

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

Высшие функции в СИКПе

II — Абстракция данных

Библиотека обыкновенных дробей

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

Введение в абстрактные данные

Добавили интервалы

Чтобы закрепить составные данные добавили к библиотеке дробей библиотеку интервалов и протестили её на примере с резисторами.

Абстракция данных с интервалами

Иерархические данные

Сначала мы разобрали простые одноранговые списки. Доставали элемент по индексу и измеряли размер на скиме.

Простые списки в СИКПе

Потом мы сделали список списков и получили иерархическое дерево. Это ещё абстрактней, потому что в список чисел можно вставить список строк, а к нему ещё, и ещё, и ещё. Получается дерево — иерархическая схема данных.

Иерархические структуры данных в СИКПе

III — Объекты и потоки

Посмотрели на принцип написания кода с модульностью по объектам и потокам.

В модульности по объектам, логические блоки собирают по смыслу и кладут их в один файл. Получается в одном файле — один модуль, а вся система состоит из нескольких модулей.

Модульность в коде и файлах

В модульности с потоками код делится по принципу вычисления: код для параллельного вычисления в одном месте, код для последовательного вычисления — в другом.

Модульность и потоки в исполнении



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

 12   18 дн   sicp

SICP. Потоки

В прошлой статье мы разобрали модульность по файлам и по коду. Суть такая: делим код на объекты, распихиваем их по файлам и получается двойная модульность.
В этой статье разберёмся с модульностью через потоки.

Поток выполнения

Программный код — это алгоритм для компьютера чтобы решить какую-нибудь задачу. Интерпретатор читает код сверху вниз и выполняет команды. Процесс исполнения этих команд называется потоком выполнения. По стандарту он один, значит если нужно подождать пока старый ХДДшник выгрузит сериал, будем ждать.
Чтобы перекачка была на фоне, появляется многопоточность — расслоение потока на ветви.

Это пример для наглядности, потому что на самом деле это процессы внутри ОСки, но суть та же

Затраты на ветви

Когда появляется ветвь, она забирает под себя память и производительность у основного потока, либо просит ещё ресурсов. С расслоением потоков нужно следить за двумя вещами:
Контроль очерёдности
Код выполняется параллельно и приходится запоминать, какой выполнять первее. Сейчас значение переменной равно 2, через две секунды в переменной уже лежит 5, а ещё через три секунды там уже строка.
Общие переменные
Когда потоки начинают работать с одной и той же переменной или объектом начинаются ошибки. Пока первый поток читает список товаров из базы данных, второй удаляет оттуда купленные товары. Третий поток запрашивает список, а там белиберда из товаров на складе и уже купленных.

Такое происходит потому что потоки на самом деле работают не параллельно. В ОСке есть хитрая система для работы с потоками: она запускает поток и даёт ему какое-то время на выполнение, когда время закончится она остановит этот поток и запустит второй, потом третий, а потом снова первый. ОСка делает это быстро, поэтому на выходе кажется, что все потоки работают одновременно.

Реализация в коде

Чтобы решать такие проблемы, можно использовать блокировки или очереди. Например, потоки работают с файлом:

  • Блокировка — это ручное управление. Пока первый поток не снимет блокировку, второй не сможет забрать файл себе.
  • Очередь — автоматическое, как только первый поток закончился, сразу запускается второй.

Чтобы писать хороший многопоточный код нужно глубже залезть в ОС и знать её особенности, потому что это её владения. Мы разберём простые и искусственные примеры для наглядности.

Библиотека

Чтобы создать поток нужно импортировать библиотеку threading и вызвать класс Thread. У Thread пять аргументов, но обязательный только один — имя функции, которая будет выполняться в потоке. Чтобы запустить поток нужно вызвать у него метод start

Чтобы заставить второй поток ждать пока закончит первый, нужно вызвать у первого потока метод join в коде второго потока. Тогда второй поток будет ждать пока первый закончит со своей работой.
Для примера сделаем два потока: первый вычисляет сумму чисел от 1 до 9, второй произведение чисел после первого потока.

Запускаем и видим, что код работает не так. Второй поток начал работать раньше, поэтому на выходе мы получили только сумму чисел от 1 до 9.

$ total после mul_sequence = 0
$ total после add_sequence = 45

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

Запускаем и видим, что всё хорошо:

$ total после add_sequence = 45
$ total после mul_sequence = 16329600

Чтобы потоки не соревновались при работе с общими данными, можно использовать блокировку, в библиотеке threading их четыре: mutex, semaphore, event и condition. Нам нужны мьютексы.

Это объект в состоянии истина или ложь. Поток захватывает мьютекс на какой-то объект и пока он у него, другие потоки не получат доступ к объекту. Чтобы другой поток смог получить объект, предыдущий должен освободить мьютекс. Этим занимается программист. Если он забыл освободить мьютекс в потоке, программа зависнет из-за одного бесконечного потока, это называется deadlock

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

После выполнения в файле будет что-то такое

Потоки соревнуются между собой и перебивают друг друга

Теперь добавим блокировку через мьютекс

Теперь потоки не соревнуются и терпеливо ждут пока другой поток закончит запись
 35   25 дн   sicp
Ранее Ctrl + ↓