Комментарии 18
Еще отлично должно подойти декартово дерево по неявному ключу. Immutable из коробки, полностью копировать дерево при вставке/удалении не нужно, а только O(logN) узлов, не будет проблем с undo/redo, легко пишется, все операции за O(logN)*
Возможно кому-нибудь будет полезна старая статья про Gap Buffer - https://habr.com/ru/articles/197650/
Копирование узла при записи подразумевает, что хотя стек undo будет содержать более легковесную версию исходного дерева, новое созданное дерево может увеличить общее потребление памяти намного больше, чем вы могли изначально думать.
ЯННП, может кто-нибудь объяснить, что имелось в виду под "записью" и "копированием узла при записи" и при чём тут потребление памяти, когда речь идёт о быстродействии?
Copy-on-write поведение. По-умолчанию копирования не происходит пока не начинается запись в некоторую позицию. Основная проблема что то самое copy может иногда оказываться не очень быстрым в зависимости от размера нижележащей структуры и соотвественно memory intensive, что может сказываться в том числе и на быстродействии.
Если не ошибаюсь, современная память читается/пишется со скоростью около 20 ГБ/с. Это очень очень много. И возникает вопрос: а чего не брутфорсом-то просто делать, зачем структуру данных отдельную? Это точно не экономия на спичках при стрельбе из пушки по воробьям?
Вам не доводилось редактировать многогигабайтные лог-файлы? Если у Вас лог-файл размером 1 Гб, скорость печати 420 символов в минуту, и Вы печатаете в середине файла, Вам, если совсем "в лоб", нужно будет выделять 7 Гб памяти в секунду (при общем занятом объёме в каждый момент времени 2 Гб: текущая версия и новая). Выглядит не очень практично :) А лог-файл ведь бывает и по 2 Гб. И по 3. А есть ещё всякие множественные курсоры. А это всё ещё нужно и отрендерить. И т.д.
Простите за любопытство, но зачем кому-то может понадобится редактировать лог-файлы? Тем более, печатать в середине. Я просто всегда думал, что лог-файлы редактируются исключительно путём добавления записей в конец.
Ну, я редактировал. Это может быть удобно, когда вам нужно отметить какой-нибудь фрагмент, или удалить нерелевантную часть, или что-нибудь в таком духе. Это не обязательно может быть файл с логами, просто я подумал о логах, т.к. сталкивался с этим.
Иными словами, чтобы облегчить себе чтение лога при разборе какой-то проблемы.
Естественно, если Вы этим занимаетесь на постоянной основе, у Вас, вероятно, будут какие-то специализированные инструменты (я даже для себя делал вспомогательные утилиты для работы с логами нашей компании), но зачастую гораздо проще и быстрее сделать это просто в текстовом редакторе. Но если текстовый редактор будет перевыделять память целиком на каждый символ, так, увы, не получится)
Я обычно применял скриптовые средства, чтобы скопировать интересующую часть лога в отдельный файл, и редактировал её. Редактировать середину километрового лога, ИМХО, совмещение неприятного с бесполезным.
Да, и так я тоже делал. И утилиты свои полноценные писал. И специализированным софтом для работы с логами пользовался. И регулярками лог преобразовывал. И редактировал лог-файл в том числе. Под каждую конкретную задачу – свой инструмент. Ну и под конкретного человека, на самом деле. Что быстрее / эффективнее – то и делаешь. У меня регулярно были случаи (да даже и всё ещё есть, хотя я уже давно не работаю с многогигабайтными логами), когда воспользоваться текстовым редактором для меня проще/быстрее. Отчасти, к слову, в силу того, что даже 10 лет назад на HDD работа с лог-файлом размером в 1-2 Гб не представляла проблем. Благодаря как раз оптимизации, вложенной в текстовые редакторы, включая грамотный выбор структур данных :)
Многогигабайтный лог-файл только с диска займет прочитать минуту. Не говоря уж о записи. И в память не влезет, надо использовать memory-mapped files по любому. Какие уж там структуры данных…
А, Вы про дисковую память? Я думал, Вы про оперативную) 20 Гб/с на consumer grade железе пока для постоянной памяти – много, если не брать всякие там flash RAID-массивы. В лучшем случае раза в 3 медленнее, и то с кучей оговорок. Или всё-таки про RAM?
Ну, тут ведь зависит от того, насколько "в лоб" делать. Я интерпретировал Ваше сообщение так: "Почему вместо каких-то заумных структур данных всё не хранить в одной строке, и перевыделять её при изменении?". По крайней мере, это самое brute force решение, которое пришло мне в голову. Если понял не правильно – мои извинения. Но, в любом случае, да, вот хотя бы в этом случае задачу "с нахрапа" не решить))
Многогигабайтный лог-файл только с диска займет прочитать минуту
На такое я люблю отвечать историей, как я однажды открыл 22Гб файл с XML данными (надо было на структуру глянуть, чтобы спарсить нормально) на двухъядерном компе с 4гб оперативы. ССД тогда в помине не было, но вим прожевал его секунд за 20, в нём легко работал поиск и прочие манипуляции с текстом.
Так что про минуту на чтение Вы явно загнули.
CPU тоже очень-очень быстрый. Но зачем же пессимизировать программу заведомо неподходящим выбором структур данных. Хотя, интересно было бы посмотреть на бенчмарки.
Выбор структур данных для самописного текстового редактора