Внутренний текстовый редактор текстового редактора: оптимальный размер блока?

Question

Кажется очевидным, что при реализации текстового редактора общего назначения (например, я имею в виду, например, что он не должен обрабатывать огромные файлы (более 100-200 МБ (чего еще много, и больше как крайний пример «общего случая»)), невозможно просто сохранить текст в одном непрерывном длинном буфере, потому что производительность будет всасывать вставки/удаления.

Хотя существует ряд способов все это связано с тем, что вы должны разделить текст на куски, и поэтому мой вопрос: учитывая сегодняшнюю мощность компьютера, каков будет оптимальный размер блока? Каков фактический размер текстового буфера, который является практически начинает становиться слишком большим для хранения в простом непрерывном буфере? Насколько быстрыми являются современные компьютеры при перемещении больших кусков байтов? (Для наглядности давайте просто скажем, что щелевые буферы не могут быть использованы, каждый кусок будет простой непрерывный массив.)

Answer 1

Типичная потребительская система может достигать от 10 до 30 ГБ/с сырой памяти в памяти DDR3. Это своего рода базовое число.

Из моего опыта я думаю, что можно с уверенностью предположить, что на Java не возникнет проблемы с достижением около 100 МБ операций с памятью в секунду (C++, вероятно, может делать в 4-8 раз больше). Из этого, казалось бы, с размером буфера 64 КБ вы могли бы перейти к чему-то вроде 2^10 операций в секунду, и все равно все будет в порядке.

Answer 2

В Eclipse почти все редакторы реализованы с использованием GapTextStore, поэтому они полагаются только на один буфер с одним gab.

Интересная часть JaveDoc для GapTextStore состояний:

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

Производительность: изменения стиля ввода выполняются в постоянное время, если не требуется перераспределение. Как правило, изменение, которое не вызывает перераспределения, приведет к не более чем одной операции с аррасикой длиной около d, где d - расстояние от предыдущего изменения. Пусть a (x) - алгоритмическая производительность операции arraycopy длины x, тогда такое изменение затем выполняется в O (a (x)), get (int, length) выполняет в O (a (length)), get (int) в O (1).

Как часто массив требует перераспределения, управляется параметрами конструктора.

Answer 3

Вы должны прочитать на data structure known as a "rope" (например, веревка - вид тяжеловесной струны). Оригинал SGI STL had them, а также строки, и пока они не попали в стандартную библиотеку C++, Gnu has them as an extension.

Обратите внимание на то, что размер «куска» не отображается как таковой в реализации (notes), что гораздо больше касается ленивых, функциональных действий.