Привет друзья.

Илья. Белый Сов. Дима-Т. Зяма. Вася. Саша Планетарный. Руслан. Жук-ботан и другие мемберы.

Несколько топиков назад мы обсуждали конкатенации строк и прочее ( конкатенация строки в одну переменную ).
И в топике была упомянута такая структура данных как rope (веревка) https://en.wikipedia.org/wiki/Rope_(data_structure)

Структура экзотична и КМК мало где применяется. И у меня возникла мысль - найти ей применение.
Попробовать поработать с крупным текстом и сравнить с обычными строковыми сущностями которые юзаем каждый день.
За примером решил далеко не ходить и взять Войну и Мир одного печально известного бородача.
Почему именно это? Ну... ее легко скачать. http://az.lib.ru/t/tolstoj_lew_nikolaewich/
И весь роман можно оптимально уложить в "Rope" для дальнейших экспериментов.

Далее. Как всегда - бенчмарк. Нам нужна реализация Rope. И собственно задание
применимо к текстовому файлу Войны и Мира.

1. I/O. Загрузка . Собсно надо загрузить текст в эту структуру и померять скорость (символов/сек).
2. Расчеты . Посчитать количество слов. И среднюю длину слова. Посчитать количество уникальных слов.
3. Трансформации . Здесь нам интересно заменить все немецкие и французские и прочие иностранные слова
на русские. (Иду на хитрость и считаю что dictionary уже у нас есть). Ну и время соотв. посчитать.
4. Транспортные расходы и КПД. . Здесь надо посчитать как дорого нам обходится веревка. В сравнении с тем
если-бы мы весь роман хранили в одной строке TString, CString, std::string ... varchar. e.t.c.
5. Поисковые возможности. . Нужно уметь находить нужное слово. И при этом возвращать номер строки и позицию.

Рад буду слышать ваши мысли и замечания.

P.S. Вопросы всяких там html и кодировок я оставляю за кадром.
Они не особо интересны в данном топике и я надеюсь что они не станут
блокером в нашем обсуждении.

Поскольку алгоритм Rope не выставляет требований к самим строкам - то берите
какой удобно.

Я вот еще забыл упомянуть по какому принципу резать текстовый файл:
- по словам
- по строкам ограниченным переводом строки

Первый вариант удобен тем что даёт статистику узлов (nodes) веревки близкую
к словам и удобен для текстового поиска.

Второй вариант более экономный с точки зрения узлов. И строки более крупные.
не будем мельчить на всяких там междометиях и предлогах.

Вообще надо всё-таки ввести в алгоритм параметр:
- минимальная длина строки в node
- стратегия балансировки (тут надо подумать).

Перевод с иностранных языков.

Выше по ссылкам я предлагал не реализацию стринг билдера а ленивый алгоритм конкатенации

Leonid Kudryavtsevнафига козе баян?
Мне очень приятно что вы как и я - большой любитель фольклора. Пословиц.. поговорок и прочее.
И мы с вами можем часами перебрасываться шутками-прибаутками и прочими частушками.

Но поскольку форум у нас - технический то я ограничусь тем что скажу что я иногда
люблю "пошатать вселенскую энтропию". И о каких-то там профитах или монетизациях
я в этот момент не думаю. Просто мне нравится сам процесс.

Уж поверьте на проектах этого полно да и тошнит от прагматизма коллег...

Смотря через какое место делать
Если сделать все в один проход, обычных строк вполне хватит
Если сделать все через ж....пу, то одной веревки мало, нужно еще и мыло

Ну... смотрите. О каких проходах идет речь? Откуда текстовый редактор знает
что пользователь собирается делать с текстом?

Я понимаю что мой поток мозгового сознания часто шокирует читателя и ввергает
его в изумление. Но я надеюсь что вы поймете мой интерес.

Dima TОбщий размер быстро вычисляется.
Нет. Общий размер не вычисляется. Он - платформозависим. Есть просто некая грубая
оценка, основанная опять-же на эксперименте. Загрузили 5 мегабайт Войны и Мира
и спрогнозировали прирост на все сочинения Джека Лондона e.t.c.

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

Плохие алгоритмы поиска - просто брутфорсят массив. Нам они - не интересы.

ИМХО Для текстовых редакторов разве что подойдет такая структура. Обычно надо просто объединить несколько строк "ааа" + "ббб" + "ввв" ... Для таких операций структура стринг билдера лучше подходит.
Неверно. Стринг билдер никак не является основой для тестовых редакторов.

В крайнем случае linked-list из строк или более сложная структура но никак не стринг-билдер.

И вообще в контексте обсуждения Rope, я считаю StringBuilder если не контр-примером
то по крайней мере неким антогонизмом или мёртвой формой Rope. Впрочем я готов
признать что он будет нужен но буду настаивать на замене его на Stream<Char>

Dima TЯ картинку в вики смотрел, там в корне дерева размер. Да и для доступа по индексу элемента он нужен. Так что быстро, т.е. быстрее получения размера строки с нулем на конце.

Дим! Я имел в виду не размер строки. Я и так его знаю из текстового файла.

Я имею в виду размер структуры данных "Rope".

Ну вот. У нас уже есть оценка. В 300% от исходного размера строки.

Хотя я-бы ввел искусственный регулятор. Я-бы просто задал 150% как коэффициент
загруженности и склеивал бы соседние nodes до тех пор пока это соотношение
не было бы достигнуто. Мдя.

Ну дай бох. Только не забывай что деревья иногда имеют чудовищный оверхед (10, 100, 1000 крат)
на листовых вершинах. Даже при том что листья не несут полезной нагрузки а просто созданы
как заглушки для NULL-s.