Сортировки

Алгоритмы бывают разные. Их принято делить на “хорошие” и “плохие”, подразумевая “быстрые” и “медленные”.

Однако это не значит, что стоит бросать все и оптимизировать все алгоритмы вашей программы / проекта, делая их на ваш взгляд “быстрее” и “лучше”.

Это называется преждевременной оптимизацией. Зачастую ведет только к проблемам и не сулит ничего хорошего. Это видео передаст все гораздо лучше, чем я смогу: Premature Optimization

Но представим, что мы все-таки этого хотим. Тогда как понять, что, переделав что-то, стало лучше?

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

Для этого нам понадобятся:

1. Реализации алгоритмов
2. Данные, которыми будут оперировать алгоритмы
3. Возможность замерить время
4. Сравнить результаты

Реализации алгоритмов

Предлагается реализовать:

1. Очень плохую сортировку пузырьком
2. Хорошую сортировку пузырьком (не забыть всякие -1 и - i - 1 в циклах)
3. Сортировка вставками Видео: сортировка вставками за 3 минуты
4. MergeSort Видео: сортировка слиянием за 3 минуты
5. QuickSort Видео: быстрая сортировка за 4 минуты

Обязательно сделать 1, 2 и (3 || 4 || 5). Если это будет интересно, стоит сделать больше!

Данные (массивы целых чисел)

Предлагается сделать замеры на следующих массивах данных:

1. 10 элементов
2. 100 элементов
3. 1_000 элементов
4. 10_000 элементов
5. 100_000 элементов

Создаем данные

Для того, чтобы сделать себе файлы с числами, можете воспользоваться следующим js скриптом:

// достаем аргументы из командной строки
const [, , length, outputFile] = process.argv
const [MIN, MAX] = [-1_000_000, 1_000_000]

// создаем массив из length элементов
const data = Array.from({ length })
  // Заполняем его случайными числами
  .map(() => getRandomInt(MIN, MAX))
  // Преобразуем в строку: "ЧИСЛО\nЧИСЛО\n ... \nЧИСЛО"
  .join('\n')

// записываем в файл с названием outputFile
require('fs').writeFileSync(outputFile, data)

// Функция для генерации случайного целого числа
function getRandomInt(min = 0, max = 100) {
  // Math.random() генерирует числа (0, 1]
  return Math.floor(Math.random() * (max - min) + min)
}

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

# Здесь мы будем вызывать скрипты и передавать в них 2 аргумента
#      количество чисел в файле 👇 и   👇 название выходного файла
node generate-numbers-script.js 10 ./array-10
node generate-numbers-script.js 100 ./array-100
node generate-numbers-script.js 1000 ./array-1000
node generate-numbers-script.js 10000 ./array-10000
node generate-numbers-script.js 100000 ./array-100000

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

Для того, чтобы этот файл сработал, необходимо, чтобы был установлен node.js. Выбирайте LTS версию

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

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

// Название файла, а заодно и размер массива
const int LENGTH = 10 * 1000;

int *readFile(int length = LENGTH) {
  // читаем файл с названием `./array-ДЛИНА`, например, `.array-50`
  string filename = "./array-" + to_string(length);
  ifstream file(filename);

  if (!file.is_open()) {
    cout << "Unable to open the file. "
         << "Check that 'array' file exists in the project folder" << endl;
    exit(2);
  }

  // о, да! Указатели!
  int *array = new int[length];
  int i = 0;
  string line;

  // пока не конец файла
  while (getline(file, line)) {
    // преобразуем строку в число и записываем в массив
    array[i++] = stoi(line);
  }
  file.close();
  return array;
}

Использовать его мы можем так:

// Читаем файл `./array-50`
int *a = readFile(50);
// ... ЗДЕСЬ МОГ БЫ БЫТЬ ВАШ КОД!
// не забываем очистить место за собой!
delete[] a;

Как будем мерить время?

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

Консольная утилита time

В консоли мы можем использовать утилиту time (она есть в Linux, для Windows она должна быть в WSL), которая выдает время исполнения любой команды, выполненной в консоли:

➜ time ./sorts
./sorts  27.64s user 0.04s system 99% cpu 27.846 total

Здесь мы видим, что скрипт выполнялся 27.64s

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

Поэтому, эта утилита нам не подходит

C++ clock()

Можно воспользоваться функцией clock.

Выглядит она так:

#include <time.h>
#include <iostream>

using namespace std;

int main(int argc, char *argv[]) {
  clock_t start = clock();
  // сложный код, который надо померить
  clock_t stop = clock();

  // Тут нужно поделить на CLK_TCK, чтобы получить что-то, вроде "секунд"
  // Еще не забываем привести к float, чтобы увидеть дробную часть
  cout << "Результат " << float(stop - start) / CLK_TCK << endl;

  return 0;
}

C++ chrono

Принцип такой же:

#include <chrono>
#include <iostream>

using namespace std;
using namespace std::chrono;

int main() {
  auto start = high_resolution_clock::now();
  // ... здесь код, который нужно померить
  auto stop = high_resolution_clock::now();
  // будем мерить в миллисекундах,
  // но можно выбрать любую точность, которая нужна
  auto duration = duration_cast<milliseconds>(stop - start);

  cout << "Результат " << duration.count() << endl;

  return 0;
}

Результаты

Что такое результат?

Если мы запустим нашу программу один раз, покажет ли она нужный результат?

Не совсем, из-за того, что процессор, помимо нашей программы занимается еще бог знает чем. Показания одного запуска будут иметь погрешность. Для минимизации погрешности, стоит запустить программу несколько раз и найти медиану (почему не среднее?) результатов. Такой результат будет гораздо более показателен.

Результаты стоит записать в табличку для разных размеров данных, чтобы понять, как ведут себя сортировки на разных объемах: