|
|
Строка 1: |
Строка 1: |
| '''Буферное окно''' ({{lang-en|Gap buffer}}) в [[информатика|информатике]] это [[динамический массив]], который позволяет эффективно производить вставку и удаление элемента в некоторой области. Буферное окно особенно распространено в [[Текстовый редактор|текстовых редакторах]], где большинство изменений текста происходят около позиции [[курсор]]а. Текст хранится в большом буфере в двух смежных сегментах с окном для вставки элементов между ними. Перемещение курсора вызывает копирование текста с одной стороны окна в другую (иногда копирование задерживается до операции изменения текста). Вставка добавляет новый текст в конец первого сегмента. Удаление увеличивает размер окна. | | '''Буферное окно''' в [[информатика|информатике]] это [[динамический массив]], который позволяет эффективно производить вставку и удаление элемента в некоторой области. Буферное окно особенно распространено в [[Текстовый редактор|текстовых редакторах]], где большинство изменений текста происходят около позиции [[курсор]]а. Текст хранится в большом буфере в двух смежных сегментах с окном для вставки элементов между ними. Перемещение курсора вызывает копирование текста с одной стороны окна в другую (иногда копирование задерживается до операции изменения текста). Вставка добавляет новый текст в конец первого сегмента. Удаление увеличивает размер окна. |
|
| |
|
| Текст в буферном окне делится на две символьные строки, которые используют очень мало дополнительной памяти и которые могут быть легко отображены или использованы в поиске, в сравнение с другими структурами данных, к примеру [[Связный список|связанных списков]]. Однако, операции в разных местах файла и те, которые заполняют окно (требуют создания нового окна) могут потребовать копирования большого объёма текста, что особенно неэффективно для больших файлов. | | Текст в буферном окне делится на две символьные строки, которые используют очень мало дополнительной памяти и которые могут быть легко отображены или использованы в поиске, в сравнение с другими структурами данных, к примеру [[Связный список|связанных списков]]. Однако, операции в разных местах файла и те, которые заполняют окно (требуют создания нового окна) могут потребовать копирования большого объёма текста, что особенно неэффективно для больших файлов. |
|
| |
|
| Использование буферного окна основано на предположении, что перекопирование происходит достаточно редко и его стоимость может быть амортизирована более дешевыми операциями. Это делает буферное окно более простой альтернативой {{нп1|Rope|Rope|en|Rope (computer science)}} для использования в текстовых редакторах<ref name="chucarroll">Mark C. Chu-Carroll. «[http://scienceblogs.com/goodmath/2009/02/18/gap-buffers-or-why-bother-with-1/ Gap Buffers, or, Don’t Get Tied Up With Ropes?] {{Wayback|url=http://scienceblogs.com/goodmath/2009/02/18/gap-buffers-or-why-bother-with-1/ |date=20131022105420 }}» ''ScienceBlogs'', 2009-02-18. Accessed 2013-01-30.</ref> таких как [[Emacs]].<ref>{{Cite web|url=https://www.gnu.org/software/emacs/manual/html_node/elisp/Buffer-Gap.html|title=27.13 The Buffer Gap|author=Emacs Lisp|website=|date=|publisher=www.gnu.org|lang=en|accessdate=2020-01-18|archive-date=2019-12-24|archive-url=https://web.archive.org/web/20191224004134/https://www.gnu.org/software/emacs/manual/html_node/elisp/Buffer-Gap.html|deadlink=no}}</ref>
| |
|
| |
| == Пример ==
| |
| Ниже приведено несколько примеров операции над буферным окном. Окно представлено пустым пространством между квадратными скобками. Это представление немного обманчиво: обычно в реализации концы представлены [[Указатель (тип данных)|указателями]] или индексами массива и содержимое окна игнорируется, что позволяет, к примеру, производить удаление лишь установкой указателя без изменения текста в буфере. Это общая практика использования полуоткрытого интервала для указателей окна, то есть указатель начала_окна установлен после последнего символа в первом сегменте и указатель на конец_окна на первый символ во втором сегменте (или, что эквивалентно, указатели установлены на точки «между» символами)
| |
|
| |
| Начальное состояние:
| |
|
| |
| This is the way [ ]out.
| |
|
| |
| Пользователь добавляет некоторый текст:
| |
|
| |
| This is the way the world started [ ]out.
| |
|
| |
| Пользователь перемещает курсор перед started", система перемещает "started " из первого сегмента во второй.
| |
|
| |
| This is the way the world [ ]started out.
| |
|
| |
| Пользователь добавляет текст, заполняющий окно. Система увеличивает окно.
| |
|
| |
| This is the way the world as we know it [ ]started out.
| |
|
| |
| == См. также ==
| |
| * [[Динамический массив]] — частный случай буферного окна, где окно всегда в конце | | * [[Динамический массив]] — частный случай буферного окна, где окно всегда в конце |
| * {{нп1|Zipper|Zipper|en|Zipper (data structure)}} — концептуально обобщение буферного окна
| |
| * [[Связный список]] | | * [[Связный список]] |
| * [[Кольцевой буфер]] | | * [[Кольцевой буфер]] |
| * {{нп1|Rope|Rope|en|Rope (computer science)}}
| |
|
| |
| == Примечания ==
| |
| {{примечания}}
| |
|
| |
| == Ссылки ==
| |
| * [http://www.codeproject.com/KB/recipes/GenericGapBuffer.aspx Overview and implementation in .NET/C#]
| |
| * [http://www.lazyhacker.com/gapbuffer/gapbuffer.htm Brief overview and sample C++ code]
| |
| * [http://www.codeproject.com/KB/recipes/SplitArrayDictionary.aspx Implementation of a cyclic sorted gap buffer in .NET/C#]
| |
| * [http://history.dcs.ed.ac.uk/archive/apps/ecce/hmd/e915.imp.html Use of gap buffer in early editor.] (First written somewhere between 1969 and 1971)
| |
| * [https://web.archive.org/web/20101227201108/http://www.gnu.org/software/emacs/elisp/html_node/Buffer-Gap.html emacs gap buffer info](Emacs gap buffer reference)
| |
| * [http://www.common-lisp.net/project/flexichain/download/StrandhVilleneuveMoore.pdf Text Editing]
| |
|
| |
|
| | ---- |
| [[Категория:Структуры данных]] | | [[Категория:Структуры данных]] |
Буферное окно в информатике это динамический массив, который позволяет эффективно производить вставку и удаление элемента в некоторой области. Буферное окно особенно распространено в текстовых редакторах, где большинство изменений текста происходят около позиции курсора. Текст хранится в большом буфере в двух смежных сегментах с окном для вставки элементов между ними. Перемещение курсора вызывает копирование текста с одной стороны окна в другую (иногда копирование задерживается до операции изменения текста). Вставка добавляет новый текст в конец первого сегмента. Удаление увеличивает размер окна.
Текст в буферном окне делится на две символьные строки, которые используют очень мало дополнительной памяти и которые могут быть легко отображены или использованы в поиске, в сравнение с другими структурами данных, к примеру связанных списков. Однако, операции в разных местах файла и те, которые заполняют окно (требуют создания нового окна) могут потребовать копирования большого объёма текста, что особенно неэффективно для больших файлов.