задался таким вопросом, поскольку стоит задача быстро заполнить c-строку символами. Проблема в том, что количество символов заранее неизвестно (переписываю токенизатор с js на плюсы, и если например тип токена строка, то ее длина может быть неограниченно большой, сотни и тысячи символов, а может быть очень короткой). Отказался от string:: осознанно, поскольку не хочу тратить время выполнения на выделение памяти. Есть ли какой-нибудь минимально затратный алгоритм заполнения строки неизвестной длины с большим разбросом? Пока вижу только возможность каждый раз инициировать массив char очень большой длины, и молиться чтобы строка туда влезла, но это сильно ударит по производительности, как мне кажется (токенов тысячи)
3 ответа
Нужен контейнер для хранения заранее неизвестного количества символов. Такой что символы можно добавлять без больших накладных расходов, есть быстрое обращение к любому символу за постоянное время.
Обращение к символу за константу сразу отметает любые древовидные контейнеры. Если потребовать максимально быстрого доступа к символу, то есть единственный способ хранить строку - в виде непрерывного массива символов. Тогда чтение/запись по индексу - одна ассемблерная инструкция. Кеши процессора оптимизированы для работы с массивами.
Такое хранение требует выделить массив неизвестной заранее длины. Обычный дизайн - array
, capacity
, size
. capacity
- текущая емкость контейнера, size
- число элементов в контейнере. Добавление символа увеличивает size
. Когда size
уперся в capacity
контейнер выделяет новый массив (обычно в два раза большего размера (capacity * 2
)), копирует данные, стирает старый массив. Увеличение размера в два раза позволяет сохранить линейную производительность при наполнении массива. Грубо говоря, если бы вы знали размер заранее, то заполнили бы контейнер за единицу времени, если размер заранее не известен, то та же работа будет выполнена за две единицы времени в дизайне array
, capacity
, size
.
Не известный заранее размер обходится в двукратное замедление при заполнении контейнера. Обращение к контейнеру происходит на максимальной возможной скорости.
Небольшое замедление при заполнении обычно не проблема. Большая проблема - фрагментация памяти при выделениях массивов большего размера. Нормально это способ работает пока длина строки не превосходит трети объёма памяти.
Если вас устраивают эти ограничения (половина скорости при заполнении, треть доступной памяти, максимальная скорость при обращении, данные в непрерывном куске памяти), то std::vector
к вашим услугам. Или сделайте ваш аналог - это не сложно.
Описанные ограничения присущи любому контейнеру, который хранит данные в непрерывном куске памяти.
Если отказаться от непрерывности, то можно выделять память небольшими фрагментами одинакового размера и хранить массив указателей на эти фрагменты. Так как мы не освобождаем память при увеличении объёма, то фрагментации не будет. Размер фрагмента подбирается так чтобы накладные расходы по памяти были не большие. Скорость заполнения будет не хуже чем у вектора. Недостаток - доступ к символу по индексу требует двух обращений к памяти - одно в массив фрагментов, второе в сам фрагмент. Такое обращение будет примерно в два раза медленнее чем обращение к элементу вектора.
Если вас устраивают эти ограничения (быстрое заполнение, половина скорости при обращении, почти полное использование памяти, данные не в непрерывном куске памяти), то std::deque
к вашим услугам. Или сделайте ваш аналог - это не сложно. :)
P.S. std::string
начиная с C++ 11 хранит символы в одном блоке памяти - ведёт себя как std::vector
.
P.P.S. Ещё раз: недостатки и преимущества вектора/строки определяются только требованием хранения данных в непрерывной памяти. Если от него отказаться, появляются новые возможности. Дек - одна из них.
P.P.P.S. Начните с std::vector
, если не устроит, переключитесь на std::deque
. У них специально интерфейсы подогнаны под лёгкую замену. Если оба вас не устроят, тогда пишите свой контейнер.
-
-
std::string в большинстве реализаций хранит символы в одном блоке памяти В стандарте сказано (22.3.2.2), что A specialization of basic_string is a contiguous container, так что те реализации, которые так НЕ делают, не соответствуют стандарту...– Harry22 июл 2022 в 9:10
-
Обычно алгоритм состоит в том, чтобы провести анализ с какой частотой какой длины строки попадаются. И выделять память, достаточную, чтобы в неё поместилось условно 80%-90% строк, с которыми работаете. Тогда выделять дополнительную память придется очень редко.
Собственно это стандартный подход при обработке данных неизвестной заранее длины - буфер. Заполняете буфер данными, когда он закончился, делаете что-то с уже обработанными данными (например записываете в файл), либо выделяете ещё один буфер. Продолжаете заполнять буфер дальше.
Непонятна нелюбовь к std::string
. Создаете строку, резервируете сразу необходимый размер памяти через reserve()
- это ровно то же, что и создать массив (выделить память). В конце-концов string
это vector<char>
. И дальше работаете. 1 раз массив всё равно создавать придется (выделять память) - поэтому непонятно ваше высказывание "не хочу тратить время выполнения на выделение памяти". Видимо имелось ввиду "не хочу постоянно перевыделять память при заполнении уже выделенной, копировать данные и т.д."?
-
Я против гадания на статистике. Это оптимизация ускоряет конкретный тест с конкретным распределением длин строк и замедляет все остальные. А если вы переоценили размер, память кончится намного раньше чем ожидал пользователь. Вполне конкретный баг в отличие от процентов производительности. 22 июл 2022 в 8:08
Обычно классы используются для работы со строками. Но всё зависит от набора библиотек которыми вы пользуетесь. Понятно что для слабого микроконтроллера будет одно, для персоналки другое. Если используете COM/ActiveX прийдётся стыковаться с COM.
Варианты оптимизации работы ЦП/памяти:
- template шаблонизация позволяет оптимизировать константы, возвращать сразу длинну без вычислений, или создавать переменные для работы на разные диапазоны длинн строк
- хеширование позволяет ускорить сравнение (если проверка на равенство)
- пулы памяти позволяют оптимизировать обращение в памяти
- разбитие строки в памяти на части позволят оптимальнее использовать память, нужно если строки больше мегабайта или какого-то значения.
- строки можно выстроить деревом, например бинарным - используя класс для каждой буквы - если нужен быстрый поиск по первым буквам, если нужны словари
- Использование 32-64-128битных операций при поиске или копировании строк.
Варианты оптимизации в программер-френдли интерфейс
- Использовать char& operator[], что упрощает доступ к "поменять букву"
- Использовать implicit и explicit cast, что упрощает передачу строки в известные библиотеки, типы (там char* wchar_t*) и назад (т.е. конструкция a=b будет работать без "лишних" дописок)
- Можно добавить операторы + += - * и ряд других если есть идеи как их задействовать для определенных операций с строками.
string
и помните Кнута: корень всех зол — в преждевременной оптимизации. Не оптимизируйте то, что не нужно — пока вы не докажете, что вас тормозит именно выделение памяти вstring
, не пытайтесь ее оптимизировать.