Как получить массив или вектор слов из словаря используя поменьше памяти?

Question

я новичок в с++. Итак есть файл словаря. это текстовый файл размером 136 мб. файл rockyou.txt отсюда: https://github.com/brannondorsey/naive-hashcat/releases/download/data/rockyou.txt

Хочется прочитать это файл в память в виде массива строк или вектора строк для дальнейшей обработки/сортировки. Что есть на данный момент:

std::ifstream infile;
infile.open("D:\\dict\\rockyou.txt", std::ios::binary); // откроем файл как бинарный
infile.seekg(0, std::ios::end);
size_t file_size_in_byte = infile.tellg();
std::vector<char> data; // будем использовать для хранения текста
data.resize(file_size_in_byte);
infile.seekg(0, std::ios::beg);
infile.read(&data[0], file_size_in_byte);

Время выполнения кода 263 мс. Объем памяти занимаемой приложением 148 мб. на выходе получаем массив типа char, разделённых '\n' в моём понимании работать с такими данными тяжело. далее пытаемся перевести этот массив в вектор слов:

string tmp;
vector<string> stringList;
int returnPos = 0;

for (int i = 0; i < file_size_in_byte; i++)
{
    if (data[i] == '\n')
    {
        tmp.reserve(i - returnPos);
        memmove(&data[returnPos + 1], &tmp[0], i - returnPos);
        stringList.push_back(tmp);
        returnPos = i;
    }
}

спасибо за подсказку Mbo. Время выполнения при этом получается 73585 мс. и объём памяти 2051 Мб(!!!)

Далее самый избитый вариант чтения текстового файла в вектор слов:

string fileName = "D:\\dict\\rockyou.txt";

std::ifstream input(fileName);

string line;

vector<string> lines;

while (getline(input, line))
{
    lines.push_back(line);        
}

Время выполнения 130481 мс. Объем памяти 2369 мб (!!!)

Вопрос в том, как получить массив слов из словаря или вектор слов из словаря и при этом остаться в пределах объема занимаемой оперативной памяти не более 2 x РазмерВходногоСловаря Мб.

Answer 1

Вы как минимум неверно используете ваш stringList. Дело в том, что это вообще не list, а vector. Если вам кажется, что это не существенно, то вы глубоко заблуждаетесь! Дело в том, как используется память в векторе. Предположим у вас в векторе 10 элементов - добавление еще одного элемента повлияет на уже существующие элементы? Ответ зависит от того, есть ли зарезервированная память у вектора, если ее нет - то все содержимое вектора будет релоцировано! При этом будет создан вектор (как правило) размера prev_size * 2. Короче из-за неверного использования вектора вы ОЧЕНЬ!!! сильно проседаете по скорости и не эффективно используете память. Чтобы этих проблем не было либо используете настоящий список, либо резервируйте память под вектор (что сложновато, так как нужно будет подсчитать сколько строк в исходном файле).

А вообще, я бы не использовал построковае чтение из файла - эффективнее считать весь файл и разбить данные как вам необходимо.

Answer 2

Во-первых, в цикле парсинга строк используется грязный хак:

tmp.reserve(i - returnPos);
memmove(&data[returnPos + 1], &tmp[0], i - returnPos);
stringList.push_back(tmp);
returnPos = i;

Непосредственная запись данных в объект std::string с выходом за размер string::size() — это UB. Это может вызвать всё что угодно от, как-минимум, инвалидации объекта std::string до, как обычно, транснозальной демоноорнитации...

В данном случае, похоже, в stringList вставляется строка с произвольным количеством мусора на конце.

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

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

for (const char *lstart=data.data(),*lend=strchr(data.data(),'\n');
     lend;
     lstart = lend+1, lend = strchr(lstart,'\n')) {
  stringList.emplace_back(lstart, lend - lstart);
}

Также std::string — довольно тяжёлый объект: каждая строка дополнительно к своему объёму требует ~16 – 40 байт (4 — 5 sizeof(void*)) на служебные цели: указатели/объём/размер/служебные данные аллокатора/менеджера памяти. т.к. строки в данных выше, судя по всему, исключительно короткие, то это составляет значительный объём потребления памяти.

Альтернативы std::string здесь:

Использовать голые указатели, char *. Накладные расходы: ~1 слово.
Написать свой класс-обёртку для облегчённой строки в char *. Накладные расходы: ~1—2 слова.
Использовать std::string_view из c++17. Накладные расходы: ~2—3 слова.
Использовать специализированные структуры для словаря, например, префиксное дерево. Накладные расходы: зависит от реализации и данных.

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

БЛОГ НА HUSL

Как получить массив или вектор слов из словаря используя поменьше памяти?

Ответы (2 шт):