# C: Отчёт по второй лабораторной работе
## Оглавление.
[[_TOC_]]
## Задача 1.
### Условие.
Найти среднее геометрическое положительных элементов массива.
### Решение.
Обратился к [википедии](https://en.wikipedia.org/wiki/Geometric_mean) для ознакомления с этой операцией.

$`(\prod^n_{i=1}x_i)^{1 \over n}`$, где $`n`$ -количество элементов.

Разбил задачу на следующие функции:
- `input_array` - ввод массива
- `filter_positive_array` - создание нового массива, содержащего только положительные элементы
- `geometric_mean` - нахождение среднего геометрического элементов массива
- `print_result` - вывод результата
### Тестироание.
Написал тесты и произвёл тестирование программы. Проверяю покрытие тестами.

$ gcov main.c
File 'main.c'
Lines executed:100.00% of 19
Creating 'main.c.gcov'

$ gcov array.c
File 'array.c'
Lines executed:90.63% of 32
Creating 'array.c.gcov'

Не удалось достичь 100% покрытия кода. Рассмотрим вывод утилиты `gcov`.

        -:    0:Source:array.c
        -:    0:Graph:array.gcno
        -:    0:Data:array.gcda
        -:    0:Runs:8
        -:    0:Programs:1
        -:    1:#include <stdio.h>
        -:    2:#include <math.h>
        -:    3:
        -:    4:#include "array.h"
        -:    5:
        8:    6:int input_array(int *array, int *lenght)
        -:    7:{
        8:    8:    if (!array || !lenght)
    #####:    9:        return POINTER_ERROR;
        -:   10:    
        8:   11:    int err = INPUT_SUCCESS;
        -:   12:
        8:   13:    printf("Input lenght of array: ");
        8:   14:    if (scanf("%d", lenght) != 1 || *lenght <= 0 || *lenght > MAX_ARRAY_SIZE)
        3:   15:        err = INPUT_ERROR;
        8:   16:    if (!err)
        5:   17:        printf("Input array elements: ");
        -:   18:    
       39:   19:    for (int i = 0; i < (*lenght) && !err; i++)
        -:   20:    {
       31:   21:        if (scanf("%d", array + i) != 1)
        1:   22:            err = INPUT_ERROR; 
        -:   23:    }
        -:   24:    
        8:   25:    return err;
        -:   26:}
        -:   27:
        4:   28:int filter_positive_array(int *array, int *lenght, int *filtered_array, int *filtered_lenght)
        -:   29:{ 
        4:   30:    if (!array || !lenght || !filtered_array || !filtered_lenght)
    #####:   31:        return POINTER_ERROR;
        -:   32:
        4:   33:    *filtered_lenght = 0;
       32:   34:    for (int i = 0; i < *lenght; i++)
       28:   35:        if (array[i] > 0)
        -:   36:        {
       12:   37:            filtered_array[*filtered_lenght] = array[i];
       12:   38:            (*filtered_lenght)++;
        -:   39:        }
        -:   40:            
        4:   41:    return 0;
        -:   42:}
        3:   43:double geometric_mean(int *array, int *lenght)
        -:   44:{
        3:   45:    if (!array || !lenght)
    #####:   46:        return POINTER_ERROR;
        -:   47:    
        3:   48:    int product = 1;
        -:   49:
       15:   50:    for (int i = 0; i < *lenght; i++)
       12:   51:        product *= array[i];
        -:   52:    
        3:   53:    return pow(product, 1.0 / (double)(*lenght));
        -:   54:}
        -:   55:
        3:   56:void print_result(double result)
        -:   57:{
        3:   58:    printf("Result is %lf", result);
        3:   59:}

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

## Задача 2.
### Условие.
Сформируйте новый массив из элементов исходного массива. При этом в новый массив
помещаются (копируются) элементы исходного массива, которые являются числами Армстронга.
### Решение.
Обратился к [википедии](https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%BE_%D0%90%D1%80%D0%BC%D1%81%D1%82%D1%80%D0%BE%D0%BD%D0%B3%D0%B0) для ознакомления с данным понятием.

Любое число Армстронга можно представить в виде $`n=\sum _{{i=1}}^{k}{d_i}^{k}`$, где $`k`$ - количество разрядов числа, а $`d_i`$ - $`i`$-ый разряд числа.

Разбил задачу на следующие функции:
- `input_array` - ввод массива
- `output_array` - вывод массива
- `filter_armstrong_array` - создание нового массива, содержащего только числа Армстронга
- `is_armstrong_number` - проверка числа на число Армстронга
- `get_digits_of_number` - возращает количество разрядов числа
- `my_pow` - возведение в степень целого числа

### Тестирование.
Написал тесты для задачи и произвел тестирование. Провел покрытие кода решения тестами.

$ gcov main.c
File 'main.c'
Lines executed:100.00% of 16
Creating 'main.c.gcov'

$ gcov untils.c
File 'untils.c'
Lines executed:94.34% of 53
Creating 'untils.c.gcov'

Не удалось достичь 100% покрытия кода. Рассмотрим результаты работы `gcov`.

        -:    0:Source:untils.c
        -:    0:Graph:untils.gcno
        -:    0:Data:untils.gcda
        -:    0:Runs:8
        -:    0:Programs:1
        -:    1:#include <stdio.h>
        -:    2:#include "untils.h"
        -:    3:
        8:    4:int input_array(long long *array, int *lenght)
        -:    5:{
        8:    6:    if (!array || !lenght)
    #####:    7:        return POINTER_ERROR;
        -:    8:    
        8:    9:    int err = INPUT_SUCCESS;
        -:   10:
        8:   11:    printf("Input lenght of array: ");
        8:   12:    if (scanf("%d", lenght) != 1 || *lenght <= 0 || *lenght > MAX_ARRAY_SIZE)
        3:   13:        err = INPUT_ERROR;
        8:   14:    if (!err)
        5:   15:        printf("Input array elements: ");
        -:   16:    
       36:   17:    for (int i = 0; i < (*lenght) && !err; i++)
        -:   18:    {
       28:   19:        if (scanf("%lld", array + i) != 1)
        1:   20:            err = INPUT_ERROR; 
        -:   21:    }
        -:   22:    
        8:   23:    return err;
        -:   24:}
        -:   25:
        3:   26:int output_array(long long *array, int lenght)
        -:   27:{
        3:   28:    if (!array)
    #####:   29:        return POINTER_ERROR;
        -:   30:    
        3:   31:    printf("Your array is \n");
       17:   32:    for (int i = 0; i < lenght; i++)
       14:   33:        printf("%lld ", array[i]);
        3:   34:    printf("\n");
        -:   35:
        3:   36:    return 0;
        -:   37:}
        -:   38:
        4:   39:int filter_armstrong_array(long long *array, int *lenght, long long *filtered_array, int *filtered_lenght)
        -:   40:{ 
        4:   41:    if (!array || !lenght || !filtered_array || !filtered_lenght)
    #####:   42:        return POINTER_ERROR;
        -:   43:
        4:   44:    *filtered_lenght = 0;
       29:   45:    for (int i = 0; i < *lenght; i++)
       25:   46:        if (is_armstrong_number(array[i]))
        -:   47:        {
       14:   48:            filtered_array[*filtered_lenght] = array[i];
       14:   49:            (*filtered_lenght)++;
        -:   50:        }
        -:   51:            
        4:   52:    return 0;
        -:   53:}
        -:   54:
       25:   55:int is_armstrong_number(long long number)
        -:   56:{
       25:   57:    int result = number >= 0;
        -:   58:
       25:   59:    int digits = get_digits_of_number(number);
        -:   60:
       25:   61:    long long temp_result = 0;
       25:   62:    long long temp_number = number;
        -:   63:
       25:   64:    if (result)
        -:   65:    {
      123:   66:        while (temp_number > 0 && temp_result <= number)
        -:   67:        {
       91:   68:            temp_result += my_pow(temp_number % 10, digits);
       91:   69:            temp_number /= 10;
        -:   70:        }
       16:   71:        result = temp_result == number;
        -:   72:    }
        -:   73:
       25:   74:    return result;
        -:   75:}
        -:   76:
       91:   77:long long my_pow(const long long number, const int power)
        -:   78:{
       91:   79:    long long result = 1;
      816:   80:    for (int i = 0; i < power; i++)
      725:   81:        result *= number;
       91:   82:    return result;
        -:   83:}
        -:   84:
       25:   85:int get_digits_of_number(const long long number)
        -:   86:{
       25:   87:    int digits = 1;
       25:   88:    long long temp = 10;
      126:   89:    while (temp < number)
        -:   90:    {
       76:   91:        digits++;
       76:   92:        temp *= 10;
        -:   93:    }
       25:   94:    return digits;
        -:   95:}

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

## Задача 3.
### Условие.
Вставьте в исходный массив после каждого положительного элемента этот же элемент,
записанный наоборот.
### Решение.
Заметил, что размер массива может увеличиться максимум в два раза, поэтому принял решение выделять в два раза больше пямити для нового массива, для предотвращения ошибок выхода за пределы выделенной памяти.

Разбил решение на следующие функции:
- `input_array` - ввод массива
- `output_array` - вывод массива
- `generate_new_array` - обработка массива согласно условию
- `insert_array` - вставка элемента в определённую позицию массива со сдвигом всех элементов
- `copy_array` - копирование массива в новую область памяти
- `reverse_number` - функция возвращает обращенное число

### Тестирование.
Написал тесты для задачи и произвел тестирование. Провел покрытие кода решения тестами.

$ gcov main.c
File 'main.c'
Lines executed:100.00% of 16
Creating 'main.c.gcov'

$ gcov untils.c
File 'untils.c'
Lines executed:92.16% of 51
Creating 'untils.c.gcov'

Не удалось достичь 100% покрытия кода. Рассмотрим результаты работы `gcov`.

        -:    0:Source:untils.c
        -:    0:Graph:untils.gcno
        -:    0:Data:untils.gcda
        -:    0:Runs:7
        -:    0:Programs:1
        -:    1:#include <stdio.h>
        -:    2:#include "untils.h"
        -:    3:
        7:    4:int input_array(long long *array, int *lenght)
        -:    5:{
        7:    6:    if (!array || !lenght)
    #####:    7:        return POINTER_ERROR;
        -:    8:    
        7:    9:    int err = INPUT_SUCCESS;
        -:   10:
        7:   11:    printf("Input lenght of array: ");
        7:   12:    if (scanf("%d", lenght) != 1 || *lenght <= 0 || *lenght > MAX_ARRAY_SIZE)
        3:   13:        err = INPUT_ERROR;
        7:   14:    if (!err)
        4:   15:        printf("Input array elements: ");
        -:   16:    
       28:   17:    for (int i = 0; i < (*lenght) && !err; i++)
        -:   18:    {
       21:   19:        if (scanf("%lld", array + i) != 1)
        1:   20:            err = INPUT_ERROR; 
        -:   21:    }
        -:   22:    
        7:   23:    return err;
        -:   24:}
        -:   25:
        3:   26:int output_array(long long *array, int lenght)
        -:   27:{
        3:   28:    if (!array)
    #####:   29:        return POINTER_ERROR;
        -:   30:    
        3:   31:    printf("Your array is \n");
       28:   32:    for (int i = 0; i < lenght; i++)
       25:   33:        printf("%lld ", array[i]);
        3:   34:    printf("\n");
        -:   35:
        3:   36:    return 0;
        -:   37:}
        -:   38:
        -:   39:
        3:   40:int generate_new_array(const long long *array, const int lenght, long long *generated, int *generated_lenght)
        -:   41:{
        3:   42:    int err = copy_array(generated, array, lenght);
        -:   43:    
        3:   44:    if (!err)
        -:   45:    {
        3:   46:        *generated_lenght = lenght;
       21:   47:        for (int i = 0; i < *generated_lenght; i++)
        -:   48:        {
       18:   49:            if (generated[i] > 0)
        -:   50:            {
        7:   51:                insert_array(reverse_number(generated[i]), i + 1, generated, *generated_lenght);
        7:   52:                (*generated_lenght)++;
        7:   53:                i++;
        -:   54:            }
        -:   55:        }
        -:   56:    }
        -:   57:
        3:   58:    return err;
        -:   59:}
        -:   60:
        7:   61:int insert_array(long long element, int position, long long *array, int lenght)
        -:   62:{
        7:   63:    if (!array)
    #####:   64:        return POINTER_ERROR;
        -:   65:    
       18:   66:    for (int i = lenght; i > position; i--)
       11:   67:        array[i] = array[i - 1];
        -:   68:    
        7:   69:    array[position] = element;
        -:   70:
        7:   71:    return 1;
        -:   72:}
        -:   73:
        3:   74:int copy_array(long long *dest_array, const long long *source_array, const int lenght)
        -:   75:{
        3:   76:    if (!dest_array || !source_array)
    #####:   77:        return POINTER_ERROR;
        -:   78:
       21:   79:    for (int i = 0; i < lenght; i++)
       18:   80:        dest_array[i] = source_array[i];
        -:   81:    
        3:   82:    return 0;
        -:   83:}
        -:   84:
        7:   85:long long reverse_number(long long number)
        -:   86:{
        7:   87:    long long result = 0;
        -:   88:
       57:   89:    while (number > 0)
        -:   90:    {
       43:   91:        result *= 10;
       43:   92:        result += number % 10;
       43:   93:        number /= 10;
        -:   94:    }
        -:   95:
        7:   96:    return result;
        -:   97:}

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

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

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

Разбил решение на следующие функции:
- `input_array` - ввод массива
- `output_array` - вывод массива
- `selection_sort` - сортировка массива

### Тестирование.
Написал тесты для задачи и произвел тестирование. Провел покрытие кода решения тестами.

$ gcov main.c
File 'main.c'
Lines executed:100.00% of 12
Creating 'main.c.gcov'

$ gcov untils.c 
File 'untils.c'
Lines executed:91.18% of 34
Creating 'untils.c.gcov'

Не удалось достичь 100% покрытия кода. Рассмотрим результаты работы `gcov`.

        -:    0:Source:untils.c
        -:    0:Graph:untils.gcno
        -:    0:Data:untils.gcda
        -:    0:Runs:7
        -:    0:Programs:1
        -:    1:#include <stdio.h>
        -:    2:#include "untils.h"
        -:    3:
        7:    4:int input_array(long long *array, int *lenght)
        -:    5:{
        7:    6:    if (!array || !lenght)
    #####:    7:        return POINTER_ERROR;
        -:    8:    
        7:    9:    int err = INPUT_SUCCESS;
        -:   10:
        7:   11:    printf("Input lenght of array: ");
        7:   12:    if (scanf("%d", lenght) != 1 || *lenght <= 0 || *lenght > MAX_ARRAY_SIZE)
        3:   13:        err = INPUT_ERROR;
        7:   14:    if (!err)
        4:   15:        printf("Input array elements: ");
        -:   16:    
       40:   17:    for (int i = 0; i < (*lenght) && !err; i++)
        -:   18:    {
       33:   19:        if (scanf("%lld", array + i) != 1)
        1:   20:            err = INPUT_ERROR; 
        -:   21:    }
        -:   22:    
        7:   23:    return err;
        -:   24:}
        -:   25:
        3:   26:int output_array(long long *array, int lenght)
        -:   27:{
        3:   28:    if (!array)
    #####:   29:        return POINTER_ERROR;
        -:   30:    
        3:   31:    printf("Your array is \n");
       33:   32:    for (int i = 0; i < lenght; i++)
       30:   33:        printf("%lld ", array[i]);
        3:   34:    printf("\n");
        -:   35:
        3:   36:    return 0;
        -:   37:}
        -:   38:
        3:   39:int selection_sort(long long *array, const int lenght)
        -:   40:{
        3:   41:    if (!array)
    #####:   42:        return POINTER_ERROR;
        -:   43:    
       30:   44:    for (int i = 0; i < lenght - 1; i++)
        -:   45:    {
       27:   46:        long long min_element = array[i];
       27:   47:        int min_position = i;
        -:   48:        
      162:   49:        for (int j = i + 1; j < lenght; j++)
        -:   50:        {
      135:   51:            if (min_element > array[j])
        -:   52:            {
       50:   53:                min_element = array[j];
       50:   54:                min_position = j;
        -:   55:            }            
        -:   56:        }
        -:   57:
       27:   58:        array[min_position] = array[i];
       27:   59:        array[i] = min_element;
        -:   60:    }
        -:   61:
        3:   62:    return 0;
        -:   63:}

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

## Задача 5.
### Условие.
Выполните обработку массива указанным образом:
Вычислить значение `x[0]*y[0] + x[1]*y[1] + ... + x[k]*y[k]`, где `x[i]` – отрицательные элементы массива `a` из `n` элементов, взятые в порядке их следования; `y[i]` – положительные элементы этого массива, взятые в обратном порядке; `k = min(p,q)`, где `p` – количество положительных элементов массива `a`, `q` – количество отрицательных элементов этого массива.

При решении пятой задачи в методических целях нельзя использовать выражение вида `a[i]` и вообще квадратные скобки. Вместо указанного выражения используется выражение `*pa`, где `pa` - указатель на `i`-ый элемент массива (именно на `i`-ый элемент, а не выражение вида `*(pa + i)`). Также нельзя передавать как аргумент размер массива в элементах. Вместо этого предлагается использовать пару указателей: на первый элемент массива и на элемент массива, расположенный за последним. Ситуация, когда эти указатели совпадают, означает пустоту обрабатываемого массива.
### Решение.

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

Разбил решение на следующие функции:
- `input_array` - ввод массива
- `process_array` - обработка массива согласно условию
- `print_result` - вывод результата
### Тестирование.
Написал тесты для задачи и произвел тестирование. Провел проверку покрытия кода решения тестами.

$ gcov main.c
File 'main.c'
Lines executed:100.00% of 13
Creating 'main.c.gcov'

$ gcov untils.c
File 'untils.c'
Lines executed:94.12% of 34
Creating 'untils.c.gcov'

Не удалось достичь 100% покрытия кода. Рассмотрим результаты работы `gcov`.

        -:    0:Source:untils.c
        -:    0:Graph:untils.gcno
        -:    0:Data:untils.gcda
        -:    0:Runs:8
        -:    0:Programs:1
        -:    1:#include <stdio.h>
        -:    2:#include "untils.h"
        -:    3:
        8:    4:int input_array(long long *array, long long **end)
        -:    5:{
        8:    6:    if (!array || !end)
    #####:    7:        return POINTER_ERROR;
        -:    8:    
        8:    9:    int err = INPUT_SUCCESS;
        -:   10:
        8:   11:    int lenght = 0;
        -:   12:
        8:   13:    printf("Input lenght of array: ");
        -:   14:
        8:   15:    if (scanf("%d", &lenght) != 1 || lenght <= 0 || lenght > MAX_ARRAY_SIZE)
        3:   16:        err = INPUT_ERROR;
        -:   17:    
        8:   18:    if (!err)
        5:   19:        printf("Input array elements: ");
        -:   20:    
        8:   21:    *end = array + lenght;
        -:   22:    
       38:   23:    for (long long *i = array; i != *end && !err; i++)
        -:   24:    {
       30:   25:        if (scanf("%lld", i) != 1)
        1:   26:            err = INPUT_ERROR; 
        -:   27:    }
        -:   28:    
        8:   29:    return err;
        -:   30:}
        -:   31:
        4:   32:int process_array(long long *array, long long *end, long long *result)
        -:   33:{
        4:   34:    if (!array || !end || !result)
    #####:   35:        return POINTER_ERROR;
        -:   36:    
        4:   37:    *result = 0;
        -:   38:
        4:   39:    long long *i = array;
        4:   40:    long long *j = end - 1;
        -:   41:
       22:   42:    while (i < end && j > array)
        -:   43:    {        
       45:   44:        while (*i >= 0 && i < end) 
       17:   45:            i++;
       39:   46:        while (*j <= 0 && j > array) 
       11:   47:            j--;
        -:   48:        
       14:   49:        if (i < end && j > array)
       10:   50:            *result += (*i) * (*j);
        -:   51:        
       14:   52:        i++;
       14:   53:        j--;
        -:   54:    }
        -:   55:    
        4:   56:    return *result == 0;
        -:   57:}
        -:   58:
        3:   59:void print_result(long long result)
        -:   60:{
        3:   61:    printf("Result is %lld\n", result);
        3:   62:}

Не достигаюся только строки кода, отвечающие за обработку нулевых указателей.
### Возникшие проблемы.
Не понял из условия задания, что массив нулевых элементов является исключительной ситуацей. Исправил решение в ревизии 8380141069d5c1b4bc82d8498f1284ea18d12489 и тесты в ревизии 1f2b3f934b1941f0508d675f819580c9f9117989.
## Задача 6.
### Условие.
На основе задачи 5 проведите сравнение производительности разных способов работы с
элементами массива
- использование операции индексации `a[i]`;
- формальная замена операции индексации на выражение `*(a + i)`;
- использование указателей для работы с массивом.
### Решение.
Ознакомился с работой функции `gettimeofday` из библиотеки `<sys/time.h>`. Повторил стандарт оформления таблиц в Markdown для их автоматической генерации. Ознакомился функциями `rand`, `srand` библиотеки `<stdlib.h>` для генерации псевдослучайных массивов.

Переписал функцию, изменив способ обращения к массиву. Написал функции тестирования каждого способа. Решение разбито на следующие функции:
- Первый метод идексации с помощью `a[i]`
- `process_1` - нахождение результата
- `test_process_1` - тестирование функции
- Второй метод идексации с помощью `*(a + i)`
- `process_2` - нахождение результата
- `test_process_2` - тестирование функции
- Третий метод идексации, использую указатели.
- `process_3` - нахождение результата
- `test_process_3` - тестирование функции
- Вывод таблицы
- `print_table_header` - печать заголовка таблицы
- `print_table_row` - печать строки таблицы
- Работа с генератором псевдослучайных чисел
- `init_random_generator` - сброс генератора
- `random_array` - заполнения массива случайными значениями
- Работа с массивами
- `copy_array` - копирования массива в другую область памяти
- `output_array` - вывод содержимого массива

### Тестирование.

Для достижения более объективных результатов тестирования, использовал виртуальную машину со следующими характеристиками:
- CPU: 1 виртуальное ядро Intel(R) Core(TM) i7-5500U CPU @ 2.40GHz
- RAM: 512 MB DDR3 1600 MHz
- Виртулизация: Hyper-V
- ОС: Ubuntu 19.10 (GNU/Linux 5.3.0-18-generic x86_64)

> В следущей задаче буду ссылаться на данную сборку.

Провел тестирование, привожу результаты с включенной оптимизацией компиляции и выключенной.

**Таблица 1. Тестирование с включенной оптимизацией компилятора `gcc`**

|Repeats| Size| a[i]| *(a+i)|Pointer|
|-------|-------|-------|-------|-------|
| 10| 10| 50| 54| 52|
| 10| 100| 67| 60| 64|
| 10| 500| 90| 83| 81|
| 10| 1000| 272| 120| 110|
| 100| 10| 683| 564| 545|
| 100| 100| 703| 620| 594|
| 100| 500| 1142| 978| 968|
| 100| 1000| 2073| 1216| 1169|
| 500| 10| 3669| 3809| 3630|
| 500| 100| 3400| 2910| 3246|
| 500| 500| 7689| 4976| 4755|
| 500| 1000| 10208| 6701| 6793|
| 1000| 10| 6123| 6554| 6011|
| 1000| 100| 7350| 6468| 10068|
| 1000| 500| 14422| 10400| 11466|
| 1000| 1000| 19898| 13782| 13574|
| 10000| 10| 66971| 60695| 65082|
| 10000| 100| 68703| 79796| 64733|
| 10000| 500| 121940| 99124| 109348|
| 10000| 1000| 178541| 143954| 130838|
| 100000| 10| 604342| 598117| 597620|
| 100000| 100| 727283| 668063| 667098|
| 100000| 500|1118172| 987837| 933543|
| 100000| 1000|1692489|1433616|1285605|

**Таблица 2. Тестирование без оптимизаций компилятора**

|Repeats| Size| a[i]| *(a+i)|Pointer|
|-------|-------|-------|-------|-------|
| 10| 10| 66| 65| 67|
| 10| 100| 66| 66| 63|
| 10| 500| 295| 98| 84|
| 10| 1000| 147| 148| 126|
| 100| 10| 609| 522| 514|
| 100| 100| 737| 814| 954|
| 100| 500| 998| 1033| 955|
| 100| 1000| 3187| 1687| 1414|
| 500| 10| 3291| 3415| 2922|
| 500| 100| 3896| 3155| 3331|
| 500| 500| 6852| 5061| 5217|
| 500| 1000| 9676| 8137| 7013|
| 1000| 10| 6478| 6427| 6074|
| 1000| 100| 8543| 7179| 6560|
| 1000| 500| 15227| 10956| 10276|
| 1000| 1000| 20738| 17018| 14030|
| 10000| 10| 62789| 63287| 63125|
| 10000| 100| 76243| 67858| 67356|
| 10000| 500| 125126| 106430| 95977|
| 10000| 1000| 170570| 151215| 127776|
| 100000| 10| 606538| 592828| 591332|
| 100000| 100| 714777| 685026| 658594|
| 100000| 500|1234805|1094469| 964170|
| 100000| 1000|2252282|1733109|1472254|

### Ответы на вопросы.
1. На что влияет размер массива?

Так как данный алгоритм линейный, время выполнения программы линейно зависимо от размер массива. С бо́льшим количеством элементов массива более явно видны различия методов.

2. Почему приходится выполнять не один замер, а несколько?

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

3. Какой способ работы с элементами массива оказался самым производительным? Как вы объясняете этот результат?

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

## Задача 7.
### Условие.
Проведите профилирование программы, написанной для решения задачи 4. Проанализируйте полученные данные профилирования. Часть этих данных приведите в отчете.
### Внесенные правки и особенности решения.
Изменил количество выделяемой памяти до 20 000 элементов. (исправил константу)

Тестированиее проводил на виртуальной машине, характеристики которой описал в задаче 6.
### Ответы на вопросы.
1. **Совпадают ли ваши представления о времени работы той или иной функции с тем, что вы получили на практике? Если нет, то для какой функции и почему?**

Мои представления совпадают.

2. **Увеличьте количество элементов в массиве до 10000, выполните профилирование. Что
изменилось? В ответе приведите как сами данные, так и объяснение полученных
результатов.**

  %   cumulative   self              self     total
time   seconds   seconds    calls  ms/call  ms/call  name
100.85      0.71     0.71        1   705.95   705.95  selection_sort
  0.00      0.71     0.00        1     0.00     0.00  input_array
  0.00      0.71     0.00        1     0.00     0.00  output_array

Ввод и вывод массива выполняются практически мгновенно, из-за того, что их сложность линейна относительно размера массива $`O(n)`$. Сортировка занимает бо́льшую часть времени, так как её сложность, как минимум $`O(n!)`$.

3. **Уменьшите количество элементов до 10, выполните профилирование. Что изменилось?
В ответе приведите как сами данные, так и объяснение полученных результатов.**

%   cumulative   self              self     total
time   seconds   seconds    calls  Ts/call  Ts/call  name
0.00      0.00     0.00        1     0.00     0.00  input_array
0.00      0.00     0.00        1     0.00     0.00  output_array
0.00      0.00     0.00        1     0.00     0.00  selection_sort

Произвести профилирование не удалось из-за очень быстрой работы алгоритма.

4. **Изучите, что делают ключи “-O1”, “-O2”, “-O3”. Выполните профилирование вашей
программы, увеличив размер массива до 10000 элементов, для каждого из этих ключей.
Проанализируйте полученные результаты, сделайте выводы.**

Тестирование произвожу на 20 000 элементов. Хочу приложить отрывок [статьи](https://wiki.gentoo.org/wiki/GCC_optimization/ru#-O)

>>>
Давайте исследуем каждый уровень оптимизации:

- `-O0`: Этот уровень (буква "O" и ноль за ней) отключает оптимизацию полностью и является уровнем по умолчанию, если никакого уровня с префиксом `-O` не указано в переменных `CFLAGS` или `CXXFLAGS`. Это сокращает время компиляции и может улучшить данные для отладки, но некоторые приложения не будут работать должным образом без оптимизации. Эта опция не рекомендуется, за исключением использования в целях отладки.
- `-O1`: Это наиболее простой уровень оптимизации. Компилятор попытается сгенерировать быстрый, занимающий меньше объема код, без затрачивания наибольшего времени компиляции. Он достаточно простой, но должен всегда выполнять свою работу.
- `-O2`: Шаг вперед от `-O1`. *Рекомендуемый* уровень оптимизации, до тех пор пока не понадобится что-то особенное. `-O2` активирует несколько дополнительных флагов вдобавок к флагам, активированных `-O1`. С параметром `-O2`, компилятор попытается увеличить производительность кода без нарушения размера, и без затрачивания большого количества времени компиляции. На этом уровне могут быть использованы SSE и AVX, но YMM-регистры не будут использоваться пока не будет включена опция `-ftree-vectorize`.
- `-O3`: Это наибольший возможный уровень оптимизации. Включает оптимизации, являющейся дорогостоящей с точки зрения времени компиляции и потребления памяти. Компиляция с `-O3` не является гарантированным способом повышения производительности, и на самом деле во многих случаях может привести к замедлению системы из-за больших двоичных файлов и увеличения потребления памяти. `-O3` известен также тем, что ломает несколько пакетов. Использование `-O3` не рекомендуется. Хотя, это также включает `-ftree-vectorize`, и циклы в коде векторизируются и используют регистры AVX YMM.
- `-Os`: На этом уровне код будет оптимизирован по объему. Он активирует все параметры `-O2`, которые не приводят к увеличению размера генерируемого кода. Он может быть полезным на компьютерах, которые обладают чрезвычайно ограниченным пространством жесткого диска и/или процессоры с небольшим размером кэша.
- `-Og`: В GCC 4.8 был введен новый общий уровень оптимизации `-Og`. Он удовлетворяет потребность в быстрой компиляции и имеет превосходные возможности для отладки, обеспечивая при этом приемлемый уровень производительности во время выполнения. Общий опыт разработки должен быть лучше, чем с уровнем оптимизации по умолчанию `-O0`. Обратите внимание, что `-Og` не означает `-g`, он просто отключает оптимизацию кода, которая может помешать отладке.
- `-Ofast`: Новое в GCC 4.7, состоит из `-O3` плюс `-ffast-math`, `-fno-protect-parens`, и `-fstack-arrays`. Этот параметр нарушает строгое соответствие стандарту, и не рекомендуется для использования.

Как упомянуто ранее, параметр `-O2` - рекомендуемый уровень оптимизации. Если компиляция пакета выдает сообщение об ошибке и не используется параметр `-O2`, то попробуйте перекопилировать с этой опцией. В качестве выхода, попробуйте установить переменные `CFLAGS` и `CXXFLAGS` на наименьший уровень оптимизации, такой как `-O1`, или даже `-O0 -g2 -ggdb` (для сообщения об ошибках и проверки возможных проблем).
>>>

0. Без оптимизации (Ключ компиляции `-O0`)

      %   cumulative   self              self     total
      time   seconds   seconds    calls   s/call   s/call  name
    100.85      2.71     2.71        1     2.71     2.71  selection_sort
      0.00      2.71     0.00        1     0.00     0.00  input_array
      0.00      2.71     0.00        1     0.00     0.00  output_array

1. Оптимизация (Ключ компиляции `-O1`)

    Each sample counts as 0.01 seconds.
      %   cumulative   self              self     total
      time   seconds   seconds    calls  ms/call  ms/call  name
    100.97      0.97     0.97        1   969.32   969.32  selection_sort
      0.00      0.97     0.00        1     0.00     0.00  input_array
      0.00      0.97     0.00        1     0.00     0.00  output_array

2. Оптимизация (Ключ компиляции `-O2`)

    Each sample counts as 0.01 seconds.
      %   cumulative   self              self     total
      time   seconds   seconds    calls  Ts/call  Ts/call  name
    101.17      1.90     1.90                             selection_sort

3. Оптимизации с применением эксперементальных методов (Ключ компиляции `-O3`)

    Each sample counts as 0.01 seconds.
      %   cumulative   self              self     total
      time   seconds   seconds    calls  Ts/call  Ts/call  name
    101.17      1.88     1.88                             selection_sort

### Некоторые выводы.

Из результатов сборки программы с разными параметрами оптимизации можем сделать некоторые выводы:
- опитимизация может сильно увеличить скорость программы (в наших примерах на 170% быстрее с ключем `-O1`, по сравнению с отключенной оптимизацией)
- применения избыточных оптимизаций компилятора может наоборот снизить скорость работы программы, особенно для реализации стандартных алгоритмов
- применение некоторых оптимизаций может повлечь за собой не работоспособность программы