| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > C/C++: Общие вопросы > расширение строки |
| Автор: fish9370 23.4.2013, 14:32 | ||
в астере (asterisk.org, кто не знает), при формировании строки, при заползании за доступное пространство, используется следующая формула для расширения строки:
где need - это пространство необходимое для хранения строки заданной длины имеется ли математическая база под этой формулой? какие у вас мысли по этому поводу? |
| Автор: bsa 25.4.2013, 12:44 |
| fish9370, для расширения С++ вектора используется формула вида size = size ? size * 2 : 1 Это стандартный метод экспоненциального увеличения. Т.е. чем больше у тебя текущий объем, тем больше резервируется. Причем, тут используется довольно пессимистичный вариант (возможно, для строк он актуален). |
| Автор: baldina 25.4.2013, 13:18 | ||||
обе формулы - частные случаи x = k*x + c, поэтому
делает вобщем то же самое что и
только с большей экономией (и потенциально более частой потребностью расширения) можно взять другие k и c, если есть основания (особенности задачи) |
| Автор: fish9370 25.4.2013, 14:21 | ||
я поинтересовался у разработчиков, это писал некий Kevin, говорят он большой мастер работы с памятью, к сожалению с ним мне поговорить так и не удалось..
это что та самая формула? линейное уравнение? но как я полагаю на нее накладываются определенные ограничения, связанные с выравниванием? |
| Автор: baldina 25.4.2013, 18:51 |
| выравнивание тут непричем (да и не получается оно по этой формуле) думаю большой мастер работы с памятью прикинул некий средний случай, его и реализовал (k=1.25). если строки изменяются чаще, а самих строк не так много, лучше подходит k=2 (как в std::vector). в какой-то реализации std::string я вроде бы видел k=1.5 |
| Автор: fish9370 26.4.2013, 09:35 | ||
1.25 тут тоже не получается, просто некий коэффициент.. да и тяжеловато деление, можно было решить все сдвигами.. одни вопросы.. |
| Автор: baldina 26.4.2013, 10:13 | ||||
компилятор наверняка так и решил))
почему? x+=x/4+c === x=1.25*x+c |
| Автор: fish9370 26.4.2013, 15:40 |
| спасибо всем, baldina особый респект.. |
