2

задался таким вопросом, поскольку стоит задача быстро заполнить c-строку символами. Проблема в том, что количество символов заранее неизвестно (переписываю токенизатор с js на плюсы, и если например тип токена строка, то ее длина может быть неограниченно большой, сотни и тысячи символов, а может быть очень короткой). Отказался от string:: осознанно, поскольку не хочу тратить время выполнения на выделение памяти. Есть ли какой-нибудь минимально затратный алгоритм заполнения строки неизвестной длины с большим разбросом? Пока вижу только возможность каждый раз инициировать массив char очень большой длины, и молиться чтобы строка туда влезла, но это сильно ударит по производительности, как мне кажется (токенов тысячи)

4
  • Если все строки, которыми будет оперировать программа - читаются из файла, то отобразите файл на память (или прочитайте его в один строковый массив, если нужна конверсия кодировок) и используйте std::string_view, который переиспользует память исходных данных. Освобождение общего куска памяти (или файла) - в конце работы программы, когда пользователей этих строк уже не будет.
    – Chorkov
    22 июл 2022 в 7:27
  • @Chorkov увы, читаются не из файла
    – Mod diller
    22 июл 2022 в 7:46
  • Еще раз посмотрите на std::string. В большинстве современных реализаций, для коротких строк (до 8 символов, обычно) не использую выделение памяти, а хранят строку непосредственно в объекте., вместо указателя.
    – Chorkov
    22 июл 2022 в 7:56
  • 2
    Вы все равно будете выделять память для С-строки, так зачем это делать неудобно и небезопасно? :) Работайте со string и помните Кнута: корень всех зол — в преждевременной оптимизации. Не оптимизируйте то, что не нужно — пока вы не докажете, что вас тормозит именно выделение памяти в string, не пытайтесь ее оптимизировать.
    – Harry
    22 июл 2022 в 9:03

3 ответа 3

4

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

Обращение к символу за константу сразу отметает любые древовидные контейнеры. Если потребовать максимально быстрого доступа к символу, то есть единственный способ хранить строку - в виде непрерывного массива символов. Тогда чтение/запись по индексу - одна ассемблерная инструкция. Кеши процессора оптимизированы для работы с массивами.

Такое хранение требует выделить массив неизвестной заранее длины. Обычный дизайн - 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. У них специально интерфейсы подогнаны под лёгкую замену. Если оба вас не устроят, тогда пишите свой контейнер.

3
  • Спасибо большое, помогло кажется
    – Mod diller
    22 июл 2022 в 8:13
  • std::string в большинстве реализаций хранит символы в одном блоке памяти В стандарте сказано (22.3.2.2), что A specialization of basic_string is a contiguous container, так что те реализации, которые так НЕ делают, не соответствуют стандарту...
    – Harry
    22 июл 2022 в 9:10
  • @Harry, спасибо, поправил. 22 июл 2022 в 9:13
2

Обычно алгоритм состоит в том, чтобы провести анализ с какой частотой какой длины строки попадаются. И выделять память, достаточную, чтобы в неё поместилось условно 80%-90% строк, с которыми работаете. Тогда выделять дополнительную память придется очень редко.
Собственно это стандартный подход при обработке данных неизвестной заранее длины - буфер. Заполняете буфер данными, когда он закончился, делаете что-то с уже обработанными данными (например записываете в файл), либо выделяете ещё один буфер. Продолжаете заполнять буфер дальше.
Непонятна нелюбовь к std::string. Создаете строку, резервируете сразу необходимый размер памяти через reserve() - это ровно то же, что и создать массив (выделить память). В конце-концов string это vector<char>. И дальше работаете. 1 раз массив всё равно создавать придется (выделять память) - поэтому непонятно ваше высказывание "не хочу тратить время выполнения на выделение памяти". Видимо имелось ввиду "не хочу постоянно перевыделять память при заполнении уже выделенной, копировать данные и т.д."?

1
  • Я против гадания на статистике. Это оптимизация ускоряет конкретный тест с конкретным распределением длин строк и замедляет все остальные. А если вы переоценили размер, память кончится намного раньше чем ожидал пользователь. Вполне конкретный баг в отличие от процентов производительности. 22 июл 2022 в 8:08
0

Обычно классы используются для работы со строками. Но всё зависит от набора библиотек которыми вы пользуетесь. Понятно что для слабого микроконтроллера будет одно, для персоналки другое. Если используете COM/ActiveX прийдётся стыковаться с COM.

Варианты оптимизации работы ЦП/памяти:

  1. template шаблонизация позволяет оптимизировать константы, возвращать сразу длинну без вычислений, или создавать переменные для работы на разные диапазоны длинн строк
  2. хеширование позволяет ускорить сравнение (если проверка на равенство)
  3. пулы памяти позволяют оптимизировать обращение в памяти
  4. разбитие строки в памяти на части позволят оптимальнее использовать память, нужно если строки больше мегабайта или какого-то значения.
  5. строки можно выстроить деревом, например бинарным - используя класс для каждой буквы - если нужен быстрый поиск по первым буквам, если нужны словари
  6. Использование 32-64-128битных операций при поиске или копировании строк.

Варианты оптимизации в программер-френдли интерфейс

  1. Использовать char& operator[], что упрощает доступ к "поменять букву"
  2. Использовать implicit и explicit cast, что упрощает передачу строки в известные библиотеки, типы (там char* wchar_t*) и назад (т.е. конструкция a=b будет работать без "лишних" дописок)
  3. Можно добавить операторы + += - * и ряд других если есть идеи как их задействовать для определенных операций с строками.

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.