save_and_load.md

Разбор задачи «Save & Load»

Условие

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

#include <iostream>
#include <vector>

class Model {
public:
    std::vector<int> data;

    void save(std::ostream& out) const;
    void load(std::istream& in);
};

void Model::save(std::ostream& out) const {
    out << data.size();
    for (auto elem : data)
        out << " " << elem;
}

void Model::load(std::istream& in) {
    size_t sz;
    in >> sz;
    data.resize(sz);
    for (size_t i = 0; i != sz; ++i)
        in >> data[i];
}

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

Перепишите функции save и load, чтобы ускорить процесс и по возможности уменьшить объём данных. Вы можете написать эти функции как хотите, но требуется, чтобы функция load восстанавливала исходные данные по результату, записанному save. В частности, load должна очищать данные модели, если они до этого как-то уже были заполнены. Мы будем тестировать Вашу программу примерно так:

#include "model.h"

#include <iostream>
#include <sstream>

int main() {
    // заклинание для ускорения потокового ввода-вывода
    std::ios::sync_with_stdio(false);

    Model m1;

    // как-то заполняем m1.data случайными числами

    std::stringstream ss;  // записываем данные не в файл, а просто в память (в строку)
    m1.save(ss);

    Model m2;
    m2.load(ss);

    if (m1.data != m2.data)
        std::cout << "Models differ\n";
}

В проверяющую систему надо сдать весь переписанный класс Model целиком.

Решение

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

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

out.write(reinterpret_cast<const char*>(&data[0]), sizeof(int) * data.size());

Но нам при загрузке надо будет как-то узнать размер куска. Проще всего записать этот размер перед записью самого вектора:

size_t sz = data.size();
out.write(reinterpret_cast<char*>(&sz), sizeof(size_t));

Мы здесь сохраняем размер вектора в переменную sz, чтобы потом можно было взять её адрес в памяти. Применить оператор взятия адреса & к результату выражению data.size() не получится. Далее мы используем reinterpret_cast, чтобы посмотреть на память как на отдельные байты (точнее, элементы типа char), а не как на size_t целиком.

Соберём всё вместе:

#include <iostream>
#include <vector>

class Model {
public:
    std::vector<int> data;

    void save(std::ostream& out) const;
    void load(std::istream& in);
};

void Model::save(std::ostream& out) const {
    size_t sz = data.size();
    out.write(reinterpret_cast<const char*>(&sz), sizeof(size_t));
    if (!data.empty()) {
        out.write(reinterpret_cast<const char*>(&data[0]), sizeof(int) * sz);
    }
}

void Model::load(std::istream& in) {
    size_t sz;
    in.read(reinterpret_cast<char*>(&sz), sizeof(size_t));
    data.resize(sz);
    if (sz > 0) {
      in.read(reinterpret_cast<char*>(&data[0]), sz * sizeof(int));
    }
}

Примечания

1. Мы существенно пользовались тем, что числа типа int в векторе лежат непрерывным куском. Если бы мы имели дело с двумерным массивом std::vector<std::vector<int>> data, то во внешнем векторе непрерывно лежали бы лишь метаописания внутренних векторов. А сами строки матрицы жили бы, вообще говоря, в разных местах памяти. В таком случае нам пришлось бы воспользоваться циклом, чтобы сериализовать эти данные построчно.

2. Было бы ошибкой оставить запись и считывание размера вектора по-старому:

void Model::save(std::ostream& out) const {
    out << data.size() << " ";
    if (!data.empty()) {
        out.write(reinterpret_cast<const char*>(&data[0]), sizeof(int) * data.size());
    }
}

void Model::load(std::istream& in) {
    size_t sz;
    in >> sz;
    data.resize(sz);
    if (sz > 0) {
      in.read(reinterpret_cast<char*>(&data[0]), sz * sizeof(int));
    }
}

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