Алгоритмы и программирование без привязки к языку программирования

• что такое вообще программирование;

• из чего оно состоит;

• почему так много языков и подходов;

• и чем тип данных отличается от структуры данных.

Поехали!

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

Начнём с Гриса. В своём труде автор говорит следующее:

«Программирование — это не просто ремесло, а дисциплина, стоящая на прочном математическом фундаменте».

Он в своих рассуждениях опирается на математические основы построения программ с использованием формальной логики. Также упоминается, что программа не пишется, а выводится из спецификаций. И последнее, но не по важности: доказуемость. Программист должен точно знать, почему это работает. В нулевой главе своей книги Грис рассказывает, как реализовать операцию деления на процессоре, в котором эта операция отсутствует (да, раньше были и такие).

В свою очередь, Д. Кнут называл программирование именно искусством, в классическом смысле этого слова — как

«применение накопленных знаний и человеческого мастерства для создания объектов, обладающих красотой».

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

Перейдём к следующему вопросу.

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

Вторая часть — обработка данных. Это уже алгоритмы! Поговорим о них подробнее немного позже.

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

Но почему так много языков программирования (ЯП)? Причина на самом деле проста. ЯП — это инструмент. Инструменты создаются под задачи. И видя количество инструментов, можно приблизительно представить, как много работы у программистов! Вообще ЯП — это почти всегда компромисс, система издержек и противовесов. Как пример могу привести замечательный ЯП Python и то, как часто я слышал о его медленном интерпретаторе; но моё предложение написать какую‑либо функцию на невероятно быстром Ассемблере всегда встречалось в штыки.

Но сегодня не об этом. Давайте начнём заниматься алгоритмами! По традиции вводные лекции на эту тему выбирают нотацию «O‑большое» (Big O) — это оценка сложности алгоритма: как много шагов выполняет реализованная программа для решения задачи. Притом что программа якобы запускается на воображаемой машине, у которой каждое действие имеет одинаковое время исполнения, а также при стремлении числа данных к бесконечности. В литературе посерьёзнее так же приводятся метрики для среднего времени выполнения и наименьшего. Но я поступлю иначе. Начнём со структур данных.

В алгоритмах структуры данных — это просто способ их хранить. Первая структура данных — массив, просто выделенный непрерывный участок в оперативной памяти вашего ПК. Вторая — связный список, это набор узлов, разбросанных по оперативной памяти. Массив содержит значения элементов и обеспечивает быстрый доступ для чтения данных. Так как данные хранятся подряд, и зная, с какой ячейки они начинаются, чтобы прочитать, например, пятый элемент массива, нужно, стоя в первой ячейке, сделать один шаг (сместиться) на пять элементов вперёд. Но для того чтобы что‑то вставить, например, в середину массива, придётся выделить другой участок оперативной памяти, записать туда существующий массив до середины, вставить новый элемент и добавить оставшийся массив. В результате — огромный перерасход по памяти и вычислениям.

Связный список устроен иначе: в каждой ячейке хранится значение и адрес следующей ячейки. Мы так же располагаем первым элементом связного списка, его часто называют «головой»; напомню, что в нём хранится само значение и адрес следующего элемента. Поэтому чтобы дойти до того же пятого элемента, нам необходимо сделать пять шагов. Мы начинаем с головы, в голове берём адрес второго элемента списка, далее переходим к нему, игнорируем значение, достаём только адрес третьего элемента, и так далее, пока не дойдём до нужного нам пятого элемента. Зато если нам требуется вставить новый элемент, например в следующую, шестую позицию, нам достаточно у пятого элемента скопировать адрес старого шестого элемента, поместить новый шестой элемент в любую свободную ячейку памяти, поместить в него адрес старого шестого элемента, а в пятый элемент записать новый адрес. Это быстро и почти не потребляет ресурсов; на языке нотации O‑большое это называется O(1) по времени. По сложности всё равно линия, или, более формально, O(n), где n — количество элементов в связном списке. Так же, говоря про структуры, часто упоминают, с чего они начинаются, то есть как индексируются, почему именно с нуля, и всё в таком духе, но знайте: это уже относится к реализации на конкретном ЯП.

Просто приведу любопытный факт: во многих ЯП массивы (встроенные структуры данных, которые по поведению наиболее напоминают описанные выше массивы) начинаются с 0. Почему именно так? Самое любопытное объяснение, которое я встречал, было следующим: при взятии подмассива А из массива Б посредством слайса, то есть Б[n:m] (подмассив А будет содержать элементы массива Б от позиции n до позиции m), можно легко посчитать длину подмассива А путём вычитания n из m. Например, массив Б = [1, 2, 3, 4, 5, 6] с индексами от 0 до 5, а подмассив А содержит элементы массива Б от второго до четвёртого: если от четырёх отнять два, то получится длина подмассива А, а именно 2; А = [3, 4]. Срез включает в себя полуоткрытый интервал: первый указанный элемент в него входит, последний — нет.

И последняя тема — «Типы данных», или можно встретить «Абстрактные типы данных» (АТД). АТД базируются на структурах данных и представляют собой структуру данных с дополнительным поведением. Давайте представим стопку книг по изучению философии древней Эллады. Вам эту стопку принёс преподаватель и сказал читать всё по очереди, начиная с верхней книги. Если захотите перескочить и пропустить одну‑две книжки, внимательный преподаватель даст вам указкой по рукам. Представили? Так вот, это называется стек. Легко представить, что самую нижнюю книгу взяли первой и сверху уже наложили одну за другой последующие. То есть первая выбранная книга будет прочитана последней. Это называется «последним пришёл — первым ушёл»; если встретите аббревиатуру LIFO (Last in First out), знайте, это про стек.

А так уж вышло, что курс по философии Эллады оказался необычайно популярным, и таких студентов, как вы, у профессора много, а стопка книг всего одна. Тогда студенты выстраиваются в очередь; там всё ещё проще: кто первым пришёл — первым и приступает к изучению. Этот АТД так и называется — очередь; в литературе можете встретить название queue (читается как «кью», но так вас никто не поймёт, только «куеуе»). Очередь так же имеет свою аббревиатуру FIFO (First in First out), переводится буквально «первым пришёл — первым ушёл».

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