Проблема с реализацией «веревки» структура данных в переполнении стека
Я пытаюсь сделать веревка структура данных. Это тип двоичного дерева, то есть рекурсивная структура данных.
Назначение веревки состоит в том, что расщепление и конкатенация должны быть быстро, что значит Вы избегаете копировать целые веревки.
Так, например, пользователь должен иметь возможность сказать rope1 + rope2 и ожидать результата в ~ логарифмическом времени.
Однако это представляет проблему:
Если веревка модифицирована, ее родители также изменяются косвенно.
Потому что моя цель состоит в том, чтобы сделать rope вставная замена для stringэто не приемлемо.
Мое решение этого: всякий раз, когда есть любой вид изменений в ropeЯ бы создал новый узел, с небольшим изменением, оставляя старые без изменений.
В теории, я думаю, что это будет работать довольно хорошо.
На практике, однако, это включает в себя распределение кучи для (почти?) каждой модификации из строк.
Даже односимвольное изменение приведет к созданию нового объекта кучи, который не только сам по себе медленный, но и значительно уменьшает локальность памяти, что очень негативно влияет на производительность.
Как мне решить эту проблему?
Решение
Традиционный подход — копирование при записи: для этого вам необходимо пересчитать каждый выделенный узел.
Если измененный узел имеет refcount 1 (никто больше не ссылается на него), вам не нужно дублировать его.
Практическая проблема с этим полезно разделять мутирование от немутирующих операций:
char& rope::operator[] (std::string::pos)
может мутировать ссылочный символ, но нет тривиального способа принудительного выбора перегрузки const, когда он на самом деле не будет. Это означает, что вы должны либо предположить, что произойдет мутация, и, возможно, вызвать ненужную копию, либо вернуть вместо этого некоторый прокси, который перегружает преобразование и назначение символов.
Этот подход был опробован для ранних реализаций std::string (где строка эквивалентна одноузловой веревке) iirc и выпала из фаворита; частично из-за проблемы мутации, а частично из-за того, что COW и требуемый пересчет становятся все более дорогостоящими, если вам приходится беспокоиться о многопоточности.
Как вы говорите, у веревки есть дополнительная проблема, если ваш узел содержит два независимых типа состояния: свою собственную строку и ссылки на свои дочерние узлы (поскольку это приводит к тому, что ссылочные мутации refcount / child распространяются вверх по дереву).
Если вместо этого символы хранятся только в конечных узлах, и вы делаете полный Копируя неконечные узлы (поэтому каждая веревка имеет свою собственную «структуру каталогов»), вы все равно избегаете копировать символы, и пересчитанное общее состояние намного проще.
Получается ли полученная логарифмическая конкатенация, которую вы хотите? Возможно нет:
- Вы должны скопировать все неконечные узлы (и добавить новый корень), и число их — это число логов.
- Вы также должны увеличивать пересчет листьев, хотя, линейный
Будь то выглядит Время, близкое к линейному или логарифмическому, зависит от относительной стоимости приращения подсчета по сравнению с копированием дерева каталогов.
Без этого вы получаете быстрые объединения, но произвольный доступ к символам может (непредсказуемо) выродиться в логарифмическое время, если им придется распространять операцию COW вверх по дереву.
Я предполагаю, что если это подходит вашему варианту использования, вы могли бы реализовать конкатенации перемещений: это, возможно, добавило бы постоянное время, и вы все равно избежали бы дополнительной сложности COW.
Другие решения
На практике, однако, это включает выделение кучи для (почти?) Каждой модификации строк.
Если вы хотите избежать частых проблем с производительностью выделения кучи, то я бы предложил использовать для вашего класса пул памяти, который выделяет кусок памяти и должен запрашивать новое выделение из ОС только после его заполнения, что должно происходить довольно редко. , Затем вы можете оптимизировать доступ к пулу памяти для выделения небольших типов данных, таких как char, так далее.
У Андрея Александреску отличный пример распределителя памяти в виде маленьких блоков в книге «Современный дизайн C ++».