stl — C ++ Как лучше всего читать словарь из текстового файла и хранить его в отсортированном контейнере
Как лучше всего читать словарь из текстового файла и хранить его в отсортированном контейнере. У меня проблема с производительностью при вставке слов в контейнер. Так вот мой код.
std::set<std::string> m_words;
std::stringstream ss(textStr);
std::string buf;
while (ss >> buf)
{
m_words.insert(m_words.end(), buf);
}
Файл словаря представляет собой файл английского словаря с 130000 строками.
Есть ли что-то еще, чтобы оптимизировать производительность.
Решение
Вместо добавления отсортированных значений в std :: set, вы можете поместить строки в std :: vector или std :: deque (Примечание: не используйте std :: deque для msvc (2013) — это не лучше, чем стандартный список
У std :: set должна быть хорошая производительность при поиске правильной точки вставки, если он учитывает подсказку «в конце». Однако std :: set выделяет узлы для каждого элемента в отдельности.
Имея последовательность данных, вы можете выполнить бинарный поиск (std :: lower_bound) по этим данным.
Смотрите также:
- Бинарный поиск:
Где я могу получить "полезным" C ++ бинарный алгоритм поиска? - MSVC deque:
профилирование: deque составляет 23% моего времени выполнения
Замечания:
Имея C ++ 11, вы можете рассмотреть vector :: Reserve (огромный_amount) и vector :: shrink_to fit ()
Другие решения
Я предполагаю использовать vectorПоскольку непрерывное хранилище хорошо для производительности, зарезервируйте ожидаемое количество записей заранее, воспользуйтесь семантикой перемещения и отсортируйте вектор только в конце файла:
std::vector<std::string> m_words;
m_words.reserve(10000);
std::string buf;
while (ss >> buf)
{
m_words.push_back(std::move(buf));
buf.clear();
}
std::sort(m_words.begin(), m_words.end());
(Вы также можете проверить размер файла на этапе предварительной обработки, чтобы получить лучший совет вместо фиксированного)
Из-за перемещения буфер должен быть сброшен в пустое состояние.
Если не указано иное, все стандартные библиотечные функции, которые принимают
rvalue ссылочных параметров (таких как std :: vector :: push_back)
гарантированно оставить аргумент move-from действительным, но не указанным
государство. То есть только функции без предварительных условий, такие как
оператор присваивания, может использоваться на объекте после его перемещения в
стандартный контейнер библиотеки (cppreference)