Вторничная веревка для Льва Николаича

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

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

Несколько топиков назад мы обсуждали конкатенации строк и прочее ( конкатенация строки в одну переменную ).
И в топике была упомянута такая структура данных как 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) бывают разные: изменяемые, иммутабельные (.net, java), cow. Какую брать за эталон?


Информация к размышлению (в первую очередь - для себя самого):
В дотнете первых версий StringBuilder был реализован как изменяемая строка, а начиная с версии 4.0 он как раз является реализацией верёвки. Так что если кто из дотнетчиков возьмётся, то было бы здорово обе версии померить.

Тут ещё следует учесть, что объекты более 85 кб попадают в LOH (large object heap), следовательно, в старом стрингбилдере большие строки туда и попадали (что не есть хорошо), в новом они будут храниться кусками в куче маленьких объектов. Вот. SOH компактируется, что хорошо для устранения фрагментации и экономного расходования памяти. LOH раньше не компактировался, но с версии .net 4.5 его тоже можно сжимать. Хорошо бы и это учесть в тестах.

Мда, в итоге выходит куча вариантов. Чё-то я очкую... Но я всегда готов дать ЦУ.

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

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

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

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

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

И без бенчмарков по самому принципу построения Rope-строк понятно, что выигрыш может быть только на вставке строки в середину и удалении кусков строки. Тут нужно искать задачу, в которой Rope-строки действительно нужны и дадут преимущество. Я такой задачи не знаю. StringBuilder решает все проблемы со строками, которые мне встречались и по производительности в обычных вариантах использования (добавление строки в конец) заведомо уделает Rope-строки.

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

petalvik
Информация к размышлению (в первую очередь - для себя самого): В дотнете первых версий StringBuilder был реализован как изменяемая строка, а начиная с версии 4.0 он как раз является реализацией верёвки. Так что если кто из дотнетчиков возьмётся, то было бы здорово обе версии померить.

Исходники StringBuilder
Нет там никакой веревки, там связный список из массивов

        internal char[] m_ChunkChars;                // The characters in this block
        internal StringBuilder m_ChunkPrevious;      // Link to the block logically before this block

mayton
Структура экзотична и КМК мало где применяется. И у меня возникла мысль - найти ей применение.

Работа с большими текстами редкая задача, как следствие инструменты под нее тоже.

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

Можно попробовать залить в БД какую-нибудь. SQLite тут вполне подойдет. Там in-memory DB есть.

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

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

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

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