Содержание

§ Предисловие

Code Hardcorius — неудачная попытка изложить свои знания относительно программирования.

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

Этот скилл, который я получил за около 8-9 лет моих опытов я и попытаюсь выразить в виде данного произведения. Вообще, я обычно веду отсчёт с 15 лет, когда получил свои первые деньги за код, однако несколько лет до этого я потратил на обучение. Полностью самостоятельное, у меня ни родители нисколько не программисты (и не учёные, не учителя), не было знакомых программистов. Даже интернета какое-то время не было. И книг тоже не было (кроме 2-3 штук, которые были довольно-таки неудачны).

Я не несу никакой ответственности за все изменения, которые могут произойти в вашей жизни в следствии прочитанного, если что. Если я вдруг напишу какую-то неправду и вы запомните это на всю жизнь — я тоже не виноват. Не доверяйте данным, пришедшим от клиента.

План данной «книги» таков: разбираемся с устройством алгоритмов, учимся их строить, разбираемся с базовыми понятиями, начинаем погружаться в мир абстракций, абстрактных типов данных, узнаём про ООП, дополнительно разбираемся в понятии «архитектура», затронем вопросы безопасности, а так же сложностей алгоритмов.

Так же обращаю ваше внимание на то, что здесь я не буду ничего объяснять про код (в смысле про синтаксисы языков). Это не входит в цели данного произведения. Этим займутся, возможно, такие имена как Python Hardcorius™, C++ Hardcorius™, Javascript Hardcorius™. Но до этого ещё далеко.

Ну что ж. Попробуем.

§ Алгоритм

Я надеюсь, что вы понимаете, что значит слово «алгоритм». Если же нет, то сделайте следующим образом. Наберите в адресной строке вашего браузера http://google.com/. Там в строке наберите «алгоритм», узнайте и возвращайтесь. Когда вы чего-то не знаете, но хотите узнать — всегда делайте так. И через какое-то время вы будете знать довольно много. Либо знать, как это найти.

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

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

Я не стану рисовать блок-схемы, хоть это и был бы самый простой способ это объяснить. Но я надеюсь, вы уловите суть. Или же найдёте их и посмотрите.

Внимание! Далее я буду прям с окопа бросать в вас код. Если вас к этому не готовили, то можете смело пропускать его и читать лишь то, что написано «нормальными» буквами. Но я надеюсь, ваше мышление способно уловить суть неизвестного вам кода, связав его строки с текстовыми объяснениями происходящего.

§ Условие

Оператор if, ветвление, условный оператор. Не важно, как называть, суть одна. Данная конструкция позволяет «отправить» выполнение алгоритма по другому пути.

Т.е. например, мы хотим ограничить доступ к нашей программе добросовестным людям, которые ещё не достигли 18-летнего возраста. Для этого нам нужно условие, которое будет сверять разницу между текущим годом и годом рождения человека. Этим и занимается if.

# encoding: utf-8

from time import gmtime

currentYear = gmtime().tm_year # Получаем текущий код
# Получаем год рождения от пользователя:
userYear = int(input('Введите год, в котором вы родились: '))

if currentYear - userYear < 18: # Вот он, например
    print('Извините, но дальше идёт hardporn-раздел, вам нельзя!')
else:
    print('Нет, мы врали. Здесь ничего нет.')

Здесь, конечно, есть множество проблем. Например, не обрабатывается ситуация, если пользователь введёт не число, год может быть неадекватным (например, в будущем или больше чем 150 лет (нежить — не наша целевая аудитория)). Но главная проблема в том, что человеку уже может быть 18, но по разнице лет ещё нет. Можно ввести погрешность в год, либо просить ещё месяц и день. Но этот пример исключительно для демонстрации сути условия, так что не суть важно.

Если хотите это запустить на своём компьютере, вам нужно скачать и установить Python 3. Если это вам не помогло и вы всё равно не знаете как запустить... погуглите что-нибудь вроде «how to run python script». Например, там есть ссылка на FAQ с сайта питона.

§ Цикл

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

Если бы я мог рисовать блок-схемы, было бы легко понять, почему есть несколько разновидностей цикла и чем они отличаются друг от друга. Но, надеюсь, удастся объяснить и текстом.

§ while

Что в переводе с английского дословно «пока». Данный вид цикла сначала проверяет истинность условия, и только если оно истинно выполняет часть алгоритма. Иначе переходит к другой его ветви.

К примеру, попросим пользователя ввести число и пока его квадрат будет меньше миллиона, будем возвозить его в квадрат и выводить результат:

# encoding: utf-8

# Получаем рациональное число от пользователя:
number = float(input('Введите число: '))

while number * number < 1000000:
    number = number * number
    print(number)

У данного алгоритма так же есть недостатки. Во-первых мы снова не проверяем, число ли нам вообще поступило. Во-вторых мы совершаем операцию умножения дважды, это не хорошо. В-третьих, если число находится в промежутке от -1 до 1, то этот цикл никогда не закончится, т.к. оно никогда не станет больше миллиона. Исправим это (кроме проверки на ввод числа):

# encoding: utf-8

# Получаем рациональное число от пользователя:
number = float(input('Введите число: '))

if abs(number) > 1: # abs — функция взятия модуля от числа
    pow = number**2 # ** это оператор возведения в степень.
    while pow < 1000000:
        number = pow
        print(number)
        pow = pow**2 # Следующее умножение
else:
    print('Число от -1 до 1 не подходит. Вы неудачник.')

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

# encoding: utf-8

# Получаем рациональное число от пользователя:
number = float(input('Введите число: '))

if abs(number) > 1: # abs — функция взятия модуля от числа
    while True: # Да-да, цикл будет выполняться «вечно»
        pow = number**2

        if pow < 1000000: # Если меньше миллиона, присваиваем
            number = pow
        else: # Иначе выполняем break, для завершения вышестоящего цикла
            break
else:
    print('Число от -1 до 1 не подходит. Вы неудачник.')

Здесь мы создали цикл, у которого условие всегда истинно. А самое условие выхода поместили внутрь цикла. Всегда следите за тем, чтобы был какой-либо вариант выхода из цикла. Никто не любит, когда программы зависают.

§ do while

Do-while отличается от просто while тем, когда проверяется условие. Если у while оно проверялось перед исполнением части алгоритма, то в do-while оно проверяется после. Т.е. сначала выполняются инструкции алгоритма, а затем проверяется условие. Т.е. инструкции цикла выполнятся хотя бы один раз.

§ for

For это просто «синтаксический сахар» над while. Синтаксическим сахаром называют такие конструкции языка, которые можно привести к другим, более простым. Они вводятся для того, чтобы на языке было проще писать.

Выведем все целые числа от 4 до 12 (пример на C++):

#include <iostream>

int main(int argc, char *argv[]) {

    // Здесь int i = 3 это создание переменной i целого типа,
    // которой мы присваиваем значение 3.
    // i++ это операция увеличения значения i на единицу
    for (int i = 3; i <= 12; i++) {
        std::cout << i << ' ';
    }

    // Переходим на новую строку
    std::cout << std::endl;

    return 0;
}

Семантика оператора for проста. Есть три части: инициализация, проверка условия, пост-действие.

  1. Перед выполнением цикла сначала выполняются некоторые действия по инициализации, например, в данном примере мы создаём переменную, по которой будем итерировать.
  2. Затем идёт условие. У нас оно проверяет, меньше либо равна ли наша переменная i.
  3. Ну и пост-действие (сам назвал, не знаю, как оно на самом деле называется) совершается в момент, когда все инструкции из тела цикла были выполнены (т.е. в конце итерации).

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

#include <iostream>

int main(int argc, char *argv[]) {

    int i = 3;
    while (i <= 12) {
        std::cout << i << ' ';

        i++;
    }

    // Переходим на новую строку
    std::cout << std::endl;

    return 0;
}

Смекаете?

§ Фундаментальное (?)

Знак вопроса здесь стоит потому, что я пока не знаю, как назвать эту часть. Здесь мы будем рассматривать базовые понятия, присущие языкам программирования.

§ Переменная

Понятие переменной является, вероятно одним из самых простых. Вы и сами наверняка знаете, что это такое. Суть такова, что мы можем «объявить» переменную, создав соответствие некоторого имени и участка памяти, где она хранится (нет-нет, это не сложно). А затем присваивать ей различные значения.

Например, мы можем создать переменную «имя» и записать туда «Саша». А потом в ходе выполнения программы записать «Ваня», например. Или переменную, в которую мы можем записывать числа. Или ещё чего-нибудь, что нам нужно сохранить на каком-то промежутке выполнения программы.

У переменной есть такое понятие как «тип». Тип определяет возможные значения, которые может принимать переменная. Есть типы, например, целых чисел, целых неотрицательных чисел, дробных, символов, строк и прочие другие.

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

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

Посмотрим на идентичные примеры на C++ и на Python 3.

#include <iostream>

int main(int argc, char *argv[]) {
    
    int answer = 42; // Целое знаковое число
    int delta = 21;

    int resultAnswer = (answer + delta * 2) / 2;

    std::cout << "Answer is: " << resultAnswer << std::endl;

    float money = 67.41573; // Дробное число

    std::cout << "I have $" << money << std::endl;

}

Как видите, в каждом случае чётко определено, целое это или дробное число.

answer = 42
delta = 21

result_answer = (answer + delta * 2) / 2

print('Answer is: %s' % int(result_answer))

money = 67.41573

print('I have $%s' % money)

В питоне же, типы определяются динамически, в момент выполнения операции присвоения значения. Поэтому, например, в переменной result_answer у нас хранится дробное число, а не целое и при выводе нам пришлось явно указать, что оно целое, чтобы не было выведено лишнее ".0", как у дробного.

§ Массив

Массив это определённое количество переменных одного типа, объединённых под одним именем и с доступом по индексу.

Например, в C++ строки могут быть представлены как массив символов:

#include <iostream>

int main(int argc, char *argv[]) {
    
    char hello[7] = "Hello?";

    std::cout << hello << std::endl; // Hello?

    hello[5] = '!';

    std::cout << hello << std::endl; // Hello!

}

Здесь мы создаём массив символов размером в 7 символов (в нашей строке лишь 6, один «лишний» символ нужен, чтобы хранить нуллбайт, по наличию которого язык определяет конец строки (т.к. она может быть потенциально любого размера и мы не храним её длину где-либо).

Мы выводим исходную строку, а затем меняем шестой символ (нумерация здесь идёт с нуля, об этом в следующей главе о указателях) на символ восклицательного знака а затем выводим строку снова.

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

§ Функция

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

N = 7

prev = 0
current = 1
for i in range(N - 1):
    prevCopy = prev
    prev = current
    current += prevCopy

print(current)

Ряд Фибоначчи начинается так: 1 1 2 3 5 8 13... Программа выше выводит 13, значит всё верно. А теперь представьте, что нам нужно найти не один раз его, а несколько. Не копировать ведь код, верно? Для этого и предназначены функции:

# encoding: utf-8

def fibonacci(N):
    prev = 0
    current = 1
    for i in range(N - 1):
        prevCopy = prev
        prev = current
        current += prevCopy

    return current

a = fibonacci(3)
b = fibonacci(5)
c = fibonacci(7)

print(a, b, c)

Выводит 2 5 13. Всё сходится. Видите написано def fibonacci(N)? N в скобках это аргумент функции. Т.е. когда в программе мы написали fibonacci(5), в блоке кода тела функции будет доступна переменная N, значение которой равно пяти. Так же в конце имеется ключевое слово return. Этот оператор берёт то, что справа от него и «возвращает». Это значит, что программа возобновит свою работу с того места, где эта функция была вызвана, а сама она как бы «заменится» на это значение.

Вот, например, когда мы сделали a = fibonacci(3), начал исполняться код функции fibonacci, затем дошло до return (там у нас число 2), вернулось к строке a = fibonacci(3), но оно уже a = 2. И в итоге переменной a присвоился результат работы функции.

§ Рекурсия

Рекурсией называется метод, когда функция вызывает саму себя. В прошлой заметке мы находили N-ое число Фибоначчи при помощи цикла. Теперь найдём при помощи рекурсии:

# encoding: utf-8

def fibonacci(N):
    if N <= 2:
        return 1
    else:
        return fibonacci(N - 1) + fibonacci(N - 2)

a = fibonacci(3)
b = fibonacci(5)
c = fibonacci(7)

print(a, b, c)

Получилось несколько чуть более компактнее и проще, возможно. Дело в том, что числа Фибоначчи математически определяются следующим образом:

f(1) = 1
f(2) = 1
f(3) = f(2) + f(1) = 2
f(4) = f(3) + f(2) = 3
f(5) = f(4) + f(3) = 5
...

Видите закономерность? Результат функции представляется как сумма результатов функций с аргументом на единицу и на двойку меньше, чем текущий. Ну и первые два элемента определены изначально.

Что мы и сделали в коде. Однако этот вариант хоть и более «по-математически», он обладает существенными недостатками. Во-первых мы дважды выполняем функцию, что не эффективно, т.к. мы лишний раз пересчитываем весь ряд целиком (при этом не просто в два раза, а даже больше, потому что оно каждый раз ещё разветвляется). Во-вторых вызов функции не бесплатен, каждый вызов функции это создание в стеке (позже о нём) дополнительной «переменной», которая указывает на место программы, где мы вызывали эту функцию (чтобы знать, куда вернуться, когда она выполнится), а так же сохранение всех переменных, которые нам ещё понадобятся после возвращения результата из вызванной функции. Если мы сделаем очень «глубокую» рекурсию, то мы рискуем переполнить допустимый размер стека и наша программа будет терминирована.

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

§ Указатель

Относительно сложная тема, но, надесь, мы справимся. Указатели обычно имеются лишь в «низкоуровневых» языках, где предоставлен прямой доступ к памяти. Назначение указателей, как ни странно — указывать на значение какой-либо переменной.

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

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

К примеру, мы можем создать некую переменную A и указатель на неё B. Например, значение переменной A находится по адресу 1334 и оно равно 777, а значение указателя находится по адресу 2048. Т.е. в памяти по адресу 1334 хранится значение 777. А по адресу 2048 находится значение 1334.

Выглядит немного запутанно, да. Давайте посмотрим пример:

#include <iostream>

int main(int argc, char *argv[]) {

    int A = 777;
    int *B = &A;

    std::cout << "A value: " << A << ". A address: " << &A << std::endl;
    std::cout << "B value: " << B << ". B address: " << &B << std::endl;
    std::cout << "*B value: " << *B << std::endl;

}

Данная программа у меня выводит что-то вроде:

A value: 777. A address: 0x7fffe4aed624
B value: 0x7fffe4aed624. B address: 0x7fffe4aed628
*B value: 777

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

Так же, если мы изменим значение A, либо *B, то значение в *B, либо в A соответственно так же изменится, потому что на самом деле оно там не хранится, а указатель лишь указывает на истинное местонахождение значения.

#include <iostream>

int main(int argc, char *argv[]) {

    int A = 777;
    int *B = &A;

    std::cout << "A value: " << A << ". A address: " << &A << std::endl;
    std::cout << "*B value: " << *B << ". B value: " << B << ". B address: " << &B << std::endl;

    A = 12;
    std::cout << std::endl << "A now is 12." << std::endl << std::endl;

    std::cout << "A value: " << A << ". A address: " << &A << std::endl;
    std::cout << "*B value: " << *B << ". B value: " << B << ". B address: " << &B << std::endl;

    *B = 4;
    std::cout << std::endl << "*B now is 4." << std::endl << std::endl;

    std::cout << "A value: " << A << ". A address: " << &A << std::endl;
    std::cout << "*B value: " << *B << ". B value: " << B << ". B address: " << &B << std::endl;

}

Вывод данной программы получился следующим:

A value: 777. A address: 0x7fffeca117c4
*B value: 777. B value: 0x7fffeca117c4. B address: 0x7fffeca117c8

A now is 12.

A value: 12. A address: 0x7fffeca117c4
*B value: 12. B value: 0x7fffeca117c4. B address: 0x7fffeca117c8

*B now is 4.

A value: 4. A address: 0x7fffeca117c4
*B value: 4. B value: 0x7fffeca117c4. B address: 0x7fffeca117c8

Как видите, значение переменной меняется вместе с значением разыменованного указателя и наоборот.

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

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

  • Выделение памяти не на стеке, а в куче (об этом позже).
  • Массивы.
  • Передача ссылок на значение в функцию, чтобы она могла его изменить в процессе выполнения.

Начнём с массивов, потому что мы о них хоть что-то знаем. Как я сказал, массив это определённое количество элементов одного типа, к которым есть доступ по индексу. Как это организовано. Допустим, у нас есть массив из 32-битных чисел, размером в 10 элементов. Т.е. он должен занимать 40 байт, непрерывно.

Переменная, через которую мы работаем с массивом и которая его представляет на самом деле является указателем на первый его элемент. И так как значение указателя (адрес, где размещается этот первый элемент) это просто число и мы знаем, сколько байт занимает каждый элемент, мы можем нехитрыми действиями вычислить адрес, по которому располагается определённый элемент массива. Давайте посмотрим пример.

#include <iostream>

int main(int argc, char *argv[]) {

    int array[3] = {10, 20, 30};

    std::cout << array[0] << ' ';
    std::cout << array[1] << ' ';
    std::cout << array[2] << std::endl;

    int *p = array;

    std::cout << *(p + 0) << ' ';
    std::cout << *(p + 1) << ' ';
    std::cout << *(p + 2) << std::endl;

}

Здесь мы просто создали массив из трёх элементов: 10, 20 и 30. Вывели его. Затем создали указатель, которому присвоили значение массива (обратите внимание, что не пришлось даже адрес брать, как с обычной переменной). И вывели значение, которое получается при разыменовывании указателя плюс смещение (мы не умножали его на размер int'а потому что C++ автоматически делает это за нас и если мы прибавим к указателю, который указывает на переменную типа int, например, 15, то это будет смещение, эквивалентное 15 int'ам).

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

Поэтому можно вызовом специальной функции попросить у операционной системы себе какой-то кусок оперативной памяти. Этот метод вернёт нам его адрес и мы сможем с ним работать, записывать туда что-то и так далее. И самое главное, что в стеке находится лишь значение указателя на этот наш удалённый «островок».

Перейдём к последнему. Мы знаем, что функции принимают аргументы и могут работать с ними. Однако посмотрите на этот пример:

#include <iostream>

// Тип void значит, что функция ничего не возвращает
void addFive(int a) {
    a += 5;
}

int main(int argc, char *argv[]) {

    int a = 5;

    addFive(a);

    std::cout << a << std::endl;

}

Думаете будет выведено 10? Нет. Дело в том, что в функцию передаются значения, а не «сами переменные», в функцию будет передана копия, а изменяя её мы не изменяем переданную переменную. Чтобы иметь возможность изменять значение переменной нужно передать указатель на неё:

#include <iostream>

void addFive(int *a) {
    // Получаем доступ к значению разыменовывая указатель
    // и прибавляем к нему пятёрку
    *a += 5;
}

int main(int argc, char *argv[]) {
    int a = 5;

    addFive(&a); // Берём адрес от a и передаём его в функцию

    std::cout << a << std::endl;

}

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

Однако представим, что у нас есть указатель и мы хотим в функции изменить на что он будет указывать. Здесь то же самое. Нам передаётся значение указателя, лишь копия. Чтобы изменить его, нам нужно передать в функцию... указатель на указатель. Теперь понимаете, для чего они нужны?

§ Структура

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

#include <iostream>

struct Person {
    const char *firstName;
    const char *lastName;
    unsigned short age;
};

int main(int argc, char *argv[]) {

    Person ruliov;
    ruliov.firstName = "Александр";
    ruliov.lastName = "Рулёв";
    ruliov.age = 19;

    std::cout << ruliov.firstName << ' ' << ruliov.lastName << ", " << ruliov.age << " лет" << std::endl;

}

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

§ Концепции

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

§ Чёрный ящик

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

Абстрактно, да. Приведу конкретный пример. Микроволновка. Это некое устройство, внутрь которого можно поместить, например, тарелку с супом, нажать несколько раз на кнопку и ждать сигнала. После достать нагретый суп, с температурой зависящей от того, какие кнопки вы нажали.

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

Так или иначе, нас это не интересует. Нас интересует лишь то, чтобы эта железка могла нагреть нам нашу еду когда это требуется. И она это делает.

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

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

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

Но когда вы имеете сводное время и желание — вы вполне можете поинтересоваться и заглянуть в недры.

§ Состояние

Состояние — одно из свойств чёрного ящика (хотя применимо и более широко). Состояние это то, из-за чего поведение чёрного ящика может меняться от тех же воздействий, которые мы на него оказываем.

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

Приведу пример с простым телевизором (да, сразу так нужно было), с которым всё никак не может разобраться дедушка. Там есть всего 4 кнопки:

  1. Включение/выключение
  2. Вверх
  3. Вниз
  4. «Функциональная кнопка»

Вот наши кнопки. Теперь рассмотрим состояния, в которых может быть телевизор. Изначально он выключен, в этом состоянии он реагирует на нажатие лишь одной кнопки — включения. Когда он включён, кнопки вверх-вниз меняют текущий канал (что так же является частью состояния, по сути). Для того, чтобы изменить громкость, нужно нажать на кнопку функциональную. Одна переведёт состояние телевизора в «изменение уровня звука» и кнопки вверх-вниз будут изменять уже громкость, а не переключать каналы. Если нажать её ещё несколько раз, то можно переключиться в режимы вроде настройки цветов и так далее, но это мы опустим, для упрощения системы. Возьмём лишь изменение цветовой гаммы.

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

Включение/выключение Вверх Вниз Функциональная кнопка
Выключен Включён Ничего Ничего Ничего
Включён Выключен Следующий канал Предыдущий канал Настройка громкости
Настройка громкости Выключен Громче Тише Настройка гаммы
Настройка гаммы Выключен Ярче Темнее Включён

Мне кажется, что вы поняли.

§ Интерфейс

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

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

Интерфейс может быть представлен чем угодно. Кнопками, крутилками, рычажками, звоночком, в который можно позвонить, гонгом, в который можно ударить. Если это конечно как-то повлияет на устройство.

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

Что ж, с абстрактностью закончили, перейдём... к абстрактностям. Но на этот раз к абстрактным типам данных.

§ Абстрактные типы данных

Дело в том, что есть конкретные типы данных (например, переменная (указатель, по сути, это тоже переменная), массив), а есть «абстрактные». Они отличаются тем, что если конкретные заданы явно, то абстрактные заданы неким паттерном использования указателей.

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

§ Список

Список — наиболее простой абстрактный тип данных. Он совсем немного похож на массив с одной стороны, но совершенно им не является.

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

Хотя у списка есть другой недостаток, нельзя получить элемент по его позиции «мгновенно». Почему так происходит, узнаем при рассмотрении односвязного списка.

§ Односвязный список

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

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

Теперь у нас есть указатель, указывающий на структуру с данными нашего первого элемента. Добавим ещё один элемент. Снова создаём структуру, записываем в неё данные. В указатель (который хранится в структуре) записываем значение указателя, который указывает на начало списка. И присваиваем этому указателю адрес на только что созданную структуру.

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

То есть список, по сути — это указатель на первый элемент списка и указатели на следующий элемент у каждого из них. Получается такая «цепочка» элементов. Именно поэтому для того, как я говорил, чтобы получить элемент к определённому элементу списка нам нужно «пройтись» по всем предыдущим. Потому что мы не имеем адреса конкретного элемента, всё что у нас есть — адрес первого из них. И нам нужно за эту «ниточку» вытягивать все остальные, чтобы получить тот, который нам нужен.

Реализую этот список на C++:

#include <iostream>

struct ListElement {
    int data;
    ListElement *next;
};

void addElement(ListElement **list, int x) {
    ListElement *el = new ListElement(); // Создаём структуру для нового элемента
    el->data = x; // Сохраняем данные
    el->next = *list; // Делаем чтобы новая структура указывала на старую первую
    *list = el; // Делаем первым элементом только что созданную структуру
}

int main(int argc, char *argv[]) {

    ListElement *head = NULL;

    addElement(&head, 49);
    addElement(&head, 30);
    addElement(&head, 86);
    addElement(&head, -3);
    addElement(&head, 12);

    ListElement *el = head;
    while (el != NULL) {
        std::cout << el->data << ' ';
        el = el->next;
    }

    std::cout << std::endl;

}

Вывод у программы такой:

12 -3 86 30 49

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

Чтобы добавить элемент в конец списка мы должны пройтись по им всем, чтобы найти последний (который будет указывать на NULL), создать новую структуру и сделать так, чтобы старый последний (который мы нашли) указывал не на NULL, а на созданный элемент. Поэтому кажется логичным, что мы можем пожертвовать 4 или 8 байтами на указатель на последний элемент и не искать его каждый раз.

Удалять из списка элементы не сильно сложнее, чем добавлять. Нужно просто взять элемент, который следует перед тем, который мы хотим удалить и элемент после. Затем сделать так, чтобы элемент перед стал указывать на элемент после. И освободить память, занятую элементом, который мы удаляем.

§ Двусвязный список

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

§ Стек

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

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

Стек легко реализовать при помощи списка:

#include <iostream>

struct ListElement {
    int data;
    ListElement *next;
};

void addElement(ListElement **list, int x) {
    ListElement *el = new ListElement();
    el->data = x;
    el->next = *list;
    *list = el;
}

// Получает и удаляет первый элемент списка
int popElement(ListElement **list) {
    int data = (*list)->data; // Достаём данные
    ListElement *next = (*list)->next; // и указатель на следующий элемент

    delete *list; // Освобождаем память занятую первым элементом
    *list = next; // Старый следующий элемент теперь первый

    return data;
}

int main(int argc, char *argv[]) {

    ListElement *stack = NULL;

    addElement(&stack, 1);
    addElement(&stack, 2);

    std::cout << popElement(&stack) << ' '; // 2

    addElement(&stack, 3);

    std::cout << popElement(&stack) << ' '; // 3
    std::cout << popElement(&stack) << ' '; // 1

    std::cout << std::endl;

}

Вывод, как не сложно догадаться, будет — 2 3 1.

§ Очередь

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

§ Хеш-таблица

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

К сожалению, я не покажу вам примеров реализации, поскольку ни разу не реализовывал её. Впрочем, я и вам бы не сильно советовал бы, разве что для собственного развития. Я лишь расскажу, как это работает.

Предположим, что в качестве ключа у нас выступает обычное число (пусть будет положительным). Так же предположим, что оно может быть совершенно любым (например, 4 миллиарда) и очевидно, что мы не можем себе позволить просто сделать такой огромный массив (это на примерно 4 гигабайта).

Поэтому нам нужен какой-то способ, чтобы «ужать» значения в более компактный промежуток, чтобы мы могли создать массив такого размера. Этот способ предоставляют хеш-функции (поэтому хеш-таблица и называется хеш-таблицей). Такие функции берут большие числа, либо же какие-либо бинарные данные (что, по сути, просто очень большие числа) и возвращают более адекватные числа, заключённые в определённом промежутке.

Самой простой хеш-функцией является такая функция, которая просто берёт N первых или последних бит числа, например.

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

Когда мы хотим достать элемент по ключу, мы опять берём хеш от ключа, получаем ведро, проходимся по этому списку, находим элемент, ключ которого равен тому, который мы достаём и возвращаем значение. Мы не можем сохранять лишь значение по той причине, что хеш-функции подвержены коллизиям. Сами подумайте, если мы можем ужать более просторный промежуток значений в промежуток покороче, то если мы сопоставим каждому значению из короткого промежутка некое значение (одно) из большого, то в большом останется ещё много, у которых нет пары. А на самом деле у них есть отображение в один из элементов короткого. Поэтому несколько элементов могут быть сопоставлены одному. Поэтому нам нужно хранить их все.

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

§ HashMap

HashMap — это просто синоним хеш-таблицы. Он позволяет добавлять и удалять некоторые значения по ключу.

§ HashSet

HashSet (set — множество) — реализация множества при помощи хеш-таблицы. У элементов такой хеш-таблицы нет значений, хранятся лишь ключи. Т.е. мы можем быстро проверить, есть ли в множестве некоторый элемент или нет.

§ Дерево

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

Бинарное дерево, например, имеет два указателя. И, например, может быть использовано для организации поиска по множеству каких-либо элементов. Мы можем создать такое дерево, у которого первый его узел будет средним по медиане элементом из этого множества. Затем сравнивать его значение с тем, которое мы хотим найти, если оно меньше — спускаемся на «левый» узел, иначе на правый. И так далее, пока не найдём.

Искать элемент, если он находится в дереве поиска намного быстрее, чем искать элемент в списке, когда нам нужно обойти все элементы по порядку.

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

§ Парадигмы

В программировании существует такое понятие как парадигмы. Это понятие довольно абстрактное, я не могу его чётко сформулировать, приведу примеры.

Изначально, как я понимаю, существовали большущие «схемы», размером в комнату и больше. И программирование сводилось к тому, чтобы переключать некие тумблеры в определённых местах, либо соединять разные контакты шнурами (на самом деле я вообще ничего не знаю об этом и просто предполагаю). Такое программирование мы можем назвать шнуро-ориентированным, например.

Через много лет появились микросхемы, представляющие из себя чёрные ящики, у которых есть входы и выходы (ножки), на которые следует в определённом порядке подавать ток, чтобы записать туда некий алгоритм и затем тоже в некотором порядке можно подавать ток на другие ножки, чтобы вводить туда данные и алгоритм выполнялся. Ну и так же на некоторых ножках может появляться ток, что мы должны обрабатывать и тоже что-то делать.

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

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

На этом этапе возможно существовали какие-либо парадигмы, но код был в виде большого длинного списка различных команд. На этом программировать так же было затруднительно.

Придумали различные языки, которые являлись более «высокими», чем ассемблер, плюс позволяли компилировать программы написанные на этих языках в разные языки ассемблера, чтобы запускаться на различных устройствах. В этом момент появилось структурно-ориентированное программирование. Появились функции и процедуры (в ассемблере они так же по сути были, но «не так явно»).

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

§ ООП

И сказал человек: «Всё есть объект!». И появилось объектно-ориентированное программирование. Каждый из объектов представлял какой-то объект «реального мира», имел свойства этого объекта, имел методы, чтобы их изменять и получать состояние объекта. Появилось наследование, полиморфизм, начали следить за инкапсуляцией.

Но по сути, ничего не изменилось, поэтому обещанного рая не наступило. Хотя все надеялись.

В данный момент большая часть всего программирования — ООП. Когда вы разберётесь с ним, вы поймёте, что ООП не заключено в рамки каких-либо «объектно-ориентированных» языков вроде Java, C# и прочих. Писать «с объектами» можно на любом языке, хоть на ассемблере. Объекты не в коде, объекты у вас в голове.

§ Функциональное программирование

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

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

§ Объектно-ориентированное программирование

Окей, начнём разбираться с ООП. На это требуется некоторое время, сначала иногда непонятно, зачем вводить все эти штуки. Но тем ни менее все они были введены, потому что были (и сейчас тоже) нужны.

Иногда буква П обозначает «подход», а не «программирование». Не сильно вижу разницы, на самом деле.

§ Объект

«Всё есть объект»

Объект — очевидно, основная компонента ООП. Объект, по сути, представляет некий чёрный ящик, однако чаще всего его реализуете именно вы, поэтому, скорее белый.

Объекты имеют поля и методы. Поля могут хранить некие данные (это просто такие переменные, доступные в методах объекта и уникальные для каждого объекта). Методы же это обычные функции, которые так же принимают аргументы и так же возвращают результат. Только в дополнение к этому имеют доступ к полям объекта.

Объекты создаются вызовом конструктора класса. Конструктор класса представляет из себя функцию, которая ведёт себя так же, как и метод.

Пример класса рационального числа на C++ (дроби с целым числителем и натуральным знаменателем) с методами сложения, вычитания, умножения и деления:

#include <iostream>

using namespace std;

class Rational {
  private:
    int numerator, denominator;
  public:
    Rational(int numerator) {
        this->numerator = numerator;
        denominator = 1;
    }
    Rational(int numerator, int denominator) {
        this->numerator = numerator;
        this->denominator = denominator;

        this->reduce();
    }

    Rational add(const Rational &other) const {
        return Rational(this->numerator * other.denominator +
                            other.numerator * this->denominator,
                        this->denominator * other.denominator);
    }
    Rational subtract(const Rational &other) const {
        return Rational(this->numerator * other.denominator -
                            other.numerator * this->denominator,
                        this->denominator * other.denominator);
    }

    Rational multiply(const Rational &other) const {
        Rational result(this->numerator * other.numerator,
                        this->denominator * other.denominator);

        result.reduce();

        return result;
        
    }
    Rational divide(const Rational &other) const {
        return this->multiply(other.inverse());
    }

    Rational inverse() const {
        return Rational(this->denominator, this->numerator);
    }

    // Друг для перегрузки оператора <<
    friend ostream &operator<<(ostream&, const Rational&);
  private:
    // Сокращение дроби
    void reduce() {
        int gcd = Rational::GCD(this->numerator, this->denominator);
        this->numerator /= gcd;
        this->denominator /= gcd;
    }

    // Нахождение НОД двух чисел
    static int GCD(int a, int b) {
        int min, max;
        if (a < b) {
            min = a;
            max = b;
        } else {
            min = b;
            max = a;
        }

        while (true) {
            int n = max / min;
            max -= min * n;

            if (max == 0) return min;

            int temp = max;
            max = min;
            min = temp;
        }
    }
};

// Перегружаем оператор << для нашего класса
ostream &operator<<(ostream &os, const Rational &rational)
{
    os << '(' << rational.numerator << " / " << rational.denominator << ')';
    return os;
}

int main(int argc, char *argv[]) {

    Rational a(2);
    Rational b(3);
    Rational c(1, 4);
    Rational d(1, 3);
    Rational e(2, 3);
    Rational f(9, 5);

    cout << c << " + " << d << " = " << c.add(d) << endl;
    cout << d << " - " << c << " = " << d.subtract(c) << endl;
    cout << e << " * " << f << " = " << e.multiply(f) << endl;
    cout << a << " / " << b << " = " << a.divide(b) << endl;

}

Если скомпилировать и запустить этот код, мы получим следующий вывод:

(1 / 4) + (1 / 3) = (7 / 12)
(1 / 3) - (1 / 4) = (1 / 12)
(2 / 3) * (9 / 5) = (6 / 5)
(2 / 1) / (3 / 1) = (2 / 3)

Как видите, операции над дробями выглядят так, будто бы работают корректно.

§ Класс

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

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

Так же класс может иметь деструктор, который проведёт некие «освободительные» действия, которые освободят использованные объектом ресурсы.

Класс можно рассматривать как структуру с полями, плюс методы, которые можно вызывать и которые будут тем или иным образом иметь доступ к этой структуре (в разных языках по-разному, в C++, например, через this, в питоне через self, который явно передаётся аргументом в метод.

Однако в дополнение к этому добавляются такие возможности как наследование и полиморфизм.

§ Наследование

Наследование — механизм, который используется для того, чтобы создать более «частный» случай некого класса. При наследовании мы создаём новый класс, у которого мы можем изменить поведение методов и/или добавить новых методов/полей.

§ Интерфейс

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

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

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

§ Полиморфизм

Полиморфизм является наиболее выдающейся частью ООП. У одного человека на рабочем столе была заметка, что «полиморфизм — это многообразие форм». Впрочем... так и есть.

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

§ Ad hoc полиморфизм

Данный вид полиморфизма описывается принципом «много реализаций с похожим интерфейсом». И он заведует перегрузкой функций.

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

И нам бы не хотелось создавать десятки функций вроде addInt, addUInt, addString, addArray, addList, addSet. Хотелось бы иметь одну — add, в которую мы могли бы передать нужные нам значения и получить в результате их сумму/объединение.

public class Main {
    private static int add(int a, int b) {
        return a + b;
    }
    private static String add(String a, String b) {
        return a.concat(b);
    }
    private static String add(String a, int b) {
        return a.concat(Integer.toString(b));
    }
    private static int[] add(int[] a, int[] b) {
        int[] newArray = new int[a.length + b.length];
        System.arraycopy(a, 0, newArray, 0, a.length);
        System.arraycopy(b, 0, newArray, a.length, b.length);
        return newArray;
    }

    public static void main(String[] args) {
        System.out.println(add(add("Hello, ", "World! Answer is "), add(23, 19)));

        int[] a = new int[] {1};
        int[] b = new int[] {2, 3};
        int[] c = add(a, b);

        for (int x : c) {
            System.out.println(x);
        }
    }
}

Здесь мы написали четыре функции на Java, которые складывают числа, строки, строку и число с приведением числа к строке, а так же объединение двух массивов путём создания третьего и копированию в него двух других.

Но теперь посмотрим на полиморфизм относительно ООП. В ООП мы создаём классы, у которых есть методы. И можно наследоваться, а затем переопределять эти методы. Но теперь представьте, что вы определяете классы не «цельно», вот так:

class A {
    protected int value;
    public A(int value) {
        this.value = value;
    }
    public int magic(int x) {
        return this.value + x;
    }
}
class B extends A {
    public B(int value) { super(value); }
    public int magic(int x) {
        return this.value * 2 + x;
    }
}

public class Main3 {
    public static void main(String[] args) {
        A a = new A(5);
        A b = new B(5);

        System.out.println("A value: " + a.magic(2));
        System.out.println("B value: " + a.magic(2));
    }
}

А двумя частями: отдельно структуру, несущую данные и отдельно методы, у которых первым аргументом передаётся то, что будет внутри этой функции this'ом:

class AData {
    public int value;
    public AData(int value) { this.value = value; }
}
class BData extends AData {
    public BData(int value) { super(value); }
}

public class Main {
    public static int magic(AData self, int x) {
        return self.value + x;
    }
    public static int magic(BData self, int x) {
        return self.value * 2 + x;
    }

    public static void main(String[] args) {
        AData a = new AData(5);
        BData b = new BData(5);

        System.out.println("A value: " + magic(a, 2));
        System.out.println("B value: " + magic(b, 2));
    }
}

Хотя довольно грубый пример, из-за некоторых особенностей dispatch'инга методов (если бы я написал AData b, никакой магии бы не произошло), но если бы для функций диспетчеризация происходила динамически, было бы совсем отлично. Но оно работает и примерно видно, что переопределение методов классов это на самом деле перегрузка функций по типу, который несёт данные этого класса.

Что же это всё нам действительно даёт?

Предположим, мы хотим написать функцию, которая принимает список чисел и возвращает их сумму. Однако в Java'е существует множество разных реализаций списков, к примеру, LinkedList, ArrayList. Очевидно, мы не хотим для каждого писать свою реализацию. Мы хотим получить себе в функцию абстрактный «список чисел», а затем использовать методы, которые позволят нам извлечь из него числа и сложить их.

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

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

§ Архитектура

В разработке ПО (программного обеспечения) есть такое понятие как архитектура. Архитектура определяет структуру, благодаря которой будут связаны различные компоненты системы. Архитектура может быть как плохой, так и хорошей. При хорошей архитектуре вашего проекта в него легко добавить новые «фичи», удалить старые, исправить какие-либо баги без проблем и возможности сломать остальные части системы. При плохой же архитектуре написание кода в проекте станет для вас адом и вы будете проклинать тот день, когда решили стать программистом.

Хорошая архитектура строится на модульности, использовании паттернов, обобщённости (посредством полиморфизма), хорошей инкапсуляцией «сложного кода».

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

Но мы будем рассматривать именно её.

§ Инкапсуляция

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

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

Например, возьмём какое-нибудь страшное слово, вроде преобразования Фурье (два слова, окей). Понятия не имею, что это такое, но если оно мне понадобиться, я должен иметь возможность взять объект, и просто передать коэфициенты в его метод и получить результат.

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

Интерфейс должен быть простым.

§ Паттерны

Если перевести слово «паттерн» на русский, может получиться что-то вроде «узор», или около того. Паттерны — типовые структуры, которые вы можете использовать для построения своей системы.

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

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

Я не говорю, что это плохо. Я лишь говорю, что если вы не будете развиваться — вы станете роботом, который лишь выполняет свои задачи. И когда появятся более совершенные роботы — они вас с лёгкостью вытеснят и вы будете никому не нужны.

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

§ Dependency injection

По-русски это звучит как «внедрение зависимости». Суть в том, что когда мы создаём объекты — после создания мы «внедряем» в него объекты, которые реализуют эти самые «зависимости».

Реализуется это крайне просто: классы имеют поля, типа интерфейс, а так методы, которые позволяют присваивать им ссылки на объекты, реализующие эти интерфейсы.

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

Например, у нас есть объект для сбора неких событий, которые происходят (ведение лога). Мы можем выделить зависимость «хранилище» или около того. Сделаем для неё интерфейс IStorage, имеющий метод store, принимающий строку.

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

Так же добавим классу нашего логгера метод setStorage принимающий объект реализующий IStorage и присвоим его какому-нибудь полю. Когда событие происходит — преобразуем его в строку и вызываем метод store объекта, который записан в этом поле. В зависимости от того, экземпляр какого класса мы «внедрили» в наш логгер он будет или выводить строку на экран или записывать её в файл.

Это и есть внедрение зависимостей.

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

§ PubSub

Publisher-Subscriber — тоже что-то около паттерна. Он применяется для уменьшения связности кода.

В данном паттерне существует три сущности — событие, publisher (возможно по-русски это будет «издатель», будем называть его источником событий) и подписчик. Событие имеет имя и свойства. Подписчики могут «подписаться» на событие по имени, т.е. попросить источник уведомить их, когда это событие произойдёт.

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

§ MVC

MVC (Model-View-Controller) — шаблон проектирования, который целиком изменил мои взгляды на программирование и сильно поспособствовал переходу на следующий уровень. Данный шаблон используется для разделения «бизнес-логики» и хранения данных (Model), представления результата (View), взаимодействия с системой (Controller).

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

Представление (View) занимается исключительно... представлением результатов работы системы. В нашем примере представлением будет часть, отвечающая за GUI (Graphical User Interface — графический интерфейс пользователя) наших шахмат. Т.е. у нас есть объект, который может показывать доску, показывать по запросу фигуры на нужных клетках.

Контроллер — это то, что является мостом между моделью и представлением а так же обрабатывает какую-то логику, связанную с действиями пользователя. Например, наше представление является источником событий и при попытке выбора фигуры, которой хочет походить пользователь генерирует событие select. Контроллер подписывается на это событие и когда пользователь выбирает фигуру — спрашивает у модели, можно ли походить этой фигурой или нет. Если можно — вызывает, например, метод представления selected. Который рисует на экране подсветку выбранной фигуры, к примеру.

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

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

Контроллер так же можем заменить. К примеру, на такой, который при ходе оппонента не передаёт снова управление представлению (т.е. получается игра за одним компьютером), а отправляет на своих ходах данные по Интернету, принимает ответ и совершает ход. Т.е. получаем уже сетевые шахматы. Заменяя модель/представление можем изменить правила или вариант отображения.

Если бы мы писали всё монолитно — у нас были бы проблемы и пришлось бы переписывать практически всю программу, а не лишь часть, которую мы хотим подвергнуть изменениям.

§ Безопасность

При обучении программированию есть одна проблема. Иногда бывает, что автор показывает такие примеры, которые будучи использованы в реальности, при определённых обстоятельствах могут вести себя совершенно не так, как хотел программист. И люди их используют в своих решениях. Затем приходят люди с определёнными способностями и без проблем получают доступ к тому, к чему у них не должно быть доступа. Или всё ломают.

Поэтому важно понимать, что ты делаешь и к чему это может привести.

Простейшим примером может быть SQL-запрос. SQL-запрос это просто строка, которая передаётся базе данных, чтобы она что-то сделала. В нём могут быть некие данные, в том числе те, которые пришли от пользователя. Ушлый пользователь может так составить свои данные, чтобы при вставке в ваш запрос он совершил не тот запрос, который вы изначально написали, а тот, который нужен пользователю. Что может привести к чтению не тех данных/модификации/удалению.

§ Входные данные

В прошлом параграфе я привёл пример с SQL-запросом. Чтобы избежать этого, просто никогда не верьте данным клиента. Что бы он вам не передал, всегда проверяйте, точно ли оно то, что вы ожидаете.

Так же требуется фильтровать и экранировать строки, если вы хотите поместить их куда-либо ещё. К примеру, если вы помещаете что-то пришедшее от пользоваля в тот же SQL-запрос, вам нужно заменить все символы, которые могут оказать на него влияние на их экранированные версии (например, кавычку ' нужно заменить на \', косую черту \ на две косых черты \\ и так далее). Но ради котов, не делайте этого самостоятельно, если не уверены. Возможно в вашем языке уже реализована функция или библиотека для этих целей.

Ещё примеры. Если вы вставляете текст от пользователя (например, комментарий) в HTML, чтобы показать его пользователям — вам нужно быть уверенным, что если пользователь сам введёт HTML — это не окажет влияния на страницу и не сделает ничего плохого. Пользователь может, например, встроить вредоносный скрипт и делать что угодно. Нужно избегать таких ситуаций и фильтровать данные.

§ Сложность алгоритма

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

В математике есть «O» большое, которое является верхней границей скорости роста некой функции. Мы будем использовать его для ограничения скорости роста «количества» вычислительных операций.

Рассмотрим различные «сложности» для того, чтобы понять, что это такое.

Например, ваш алгоритм принимает два числа и складывает их. Если записать этот алгоритм в виде кода и скомпилировать его, это будет какое-то количество команд ассемблера. Но там не будет циклов, поэтому наша программа будет выполнена за этих несколько операций и завершится. Предположим, что для этого нам нужно лишь 3 операции. Т.е. мы можем ограничить сверху выполнение нашей программы тремя операциями, вот так: O(3). Однако при обозначении сложности количество операций может отличаться между разными компиляторами/ассемблерами/компьютерами. Поэтому O(3) умножается на константу C, которая означает «коэфициент конкретности» (сам название придумал, не запоминайте), который может быть разным и мы его не знаем. Чуть дальше об этом.

И суть такова, что мы можем вынести константу из-под O и «поглотить» её нашей виртуальной константой C (она ведь всё равно нам неизвестная и может изменяться, какая разница, как она будет меняться?). В итоге получается, что O(3) = O(1). Это значит, что наша программа выполнится за константное время. На одном компьютере это будут мили/микро/пикосекунды, на другом, например, это может быть час (например, выполняются какие-нибудь другие программы и планировщик просто не даёт времени нашему коду).

Теперь возьмём другой случай. У нас есть список длины N и мы проходимся по нему два раза и применяем на каждый его элемент каких-то 5 операций. Т.е. у нас будет O(2 * 5 * N), верно? Однако 10 является константой и может быть убрано, в итоге получается O(N). Что значит, что при размере входных данных (в данном случае длине списка) равным N наша программа выполнится за линейное время. И если прибавить ещё несколько элементов в список — то и время увеличится на константу умноженную на количество добавленных элементов.

Перейдём ещё к более крутым сложностям. Теперь сделаем вложенный цикл, в котором будем проходиться по элементам списка (опять же длиной в N), во внешнем цикле так же будем проходиться по ним же. Т.е. для каждого элемента из списка мы будем получать все остальные и его самого. Здесь наше O будет равно O(N^2). И смотрите. Если мы добавим несколько элементов — время увеличится уже не линейно, а примерно квадратично.

А теперь предположим, что одна часть программы у нас имеет линейную сложность, а другая квадратичную. Получается O(N + N^2). Однако тут действует хитрое «правило». Если мы устремим N к бесконечности, то N будет расти намного медленнее, чем N^2 и практически не будет оказывать влияния на итоговое время. Поэтому мы можем отбросить его. Так, O(N + N^2) = O(N^2).

Для того, чтобы рассчитывать сложность своих алгоритмов необходим опыт, но простые случаи можно легко видеть. Если вы проходитесь по чему-то один раз — это O(N), если два раза — всё равно O(N). Но если вы сделали три вложенных цикла — это уже O(N^3).

Так же существуют и другие классы сложностей, вроде O(N^3), O(2^N), O(log N), O(N log N).

Для чего это нужно? Смотрите. Допустим, вы написали сортировку таким образом, что каждый элемент проверяете с каждым. Это получается O(N^2). А Вася написал сортировку, которая имеет O(N log N). Т.е. N умножить на логарифм (не суть важно основание) N. И при N → ∞, ваше N^2 будет выглядеть... медленно, по сравнению с N log N. Потому что N log N растёт куда медленнее. Если не верите — нарисуйте график того и другого. А время — деньги. При увеличении данных вам придётся покупать куда больше ресурсов, чем Васе, хотя его алгоритм выполняет ту же задачу, что и ваш. Только лучше.

§ Заключение

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

Так же, если вы нашли какую-либо нестыковку, пожалуйста, уведомите меня об этом. Мои контакты можно найти на страничке про меня.

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

Удачи!


Если вы считаете, что Код Хардкориус вам помог, не стесняйтесь, расскажите о нём своим друзьям:

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

Разработано в Коммуне