Какая сложность получения чанка и зачем копируются данные в чанках StringBuilder'а в C#?
Разбираюсь со стринг билдером в C#, но не могу понять две вещи:
- Почему в коде его реализации написано, что арифметическая сложность получения чанка - это
O(N*N)илиO(N)? Разве она не должна быть всегдаO(log(N))?O(log(N))на поиск нужного чанка +O(1)на получение по индексу внутри чанка. - О какой операции переноса данных в новый чанк тут идет речь? Зачем переносить данные? Разве при заполнении чанка нельзя то, что не влезло просто положить в новый, который в
2раза больше?
Ответы (1 шт):
Почитал я код. Вроде могу ответить.
Список чанков:
первый <- ... <- предыдущий <- текущий <- следующий <- ... <- последний <-
|у нас есть|нужно найти| ... |начинаем с конца|
Чанки в
StringBuilder- это односвязный список, причём линки есть только от следующего чанка к предыдущему, ну и на конец списка (видимо, для лёгкого удаления элементов с конца списка при необходимости). Поэтому, чтобы итерироваться по чанкам в прямом порядке (а именно такой кусок кода вы разбираете), нужно на каждом шаге итерирования перебирать чанки от последнего к первому в поисках текущего чанка, чтобы таким образом найти следующий к нему чанк, нужный для следующей итерации. Для числа чанков <8 при итерировании используется именно такой перебор списка с конца, и получается общая сложность перебораO(N*N), а вот для большего чем8кол-ва чанков временно (пока не закончится перебор) создаётся вспомогательный массив с индексами чанков, так что сложность получаетсяO(N)(имея индексы не нужно на каждом шаге итерации заново перебирать все чанки, чтобы найти следующий чанк, он берётся просто по индексу из временного массива индексов), но этот подход требует дополнительноO(N)временной памяти.-
Зачем переносить данные? Разве при заполнении чанка нельзя то, что не влезло просто положить в новый, который в 2 раза больше?
А то, что вы кладёте данные в новый чанк - это не перенос данных? Это тоже самое и есть, просто другими словами. Или вы имели в виду, что старый чанк оставить на месте, и только для того, что не влезло, сделать новый чанк, в который положить данные? Видимо, не хотят, чтобы в результате получилось слишком много чанков. Тут вечный трейдофф. Либо мало чанков, но копирование при ресайзе чанка, либо делать много чанков без копирования предыдущего содержимого, но ведь на каждый чанк нужна дополнительная ссылка и чанки дольше потом обходить и дольше всё это копировать, когда наконец настанет ToString(). Поэтому, если я правильно понял, размер чанка стараются держать меньше 8000 (чтобы он не уехал в Large Object Heap), а внутри этого размера чанк растёт, пока может (путём выделения чанка увеличенного размера и копирования туда содержимого). Начиная с начального размера 16.