Обновление динамических данных на диске
Всем привет.
Задача: записать в файл динамические данные. Спустя какое-то время обновить их.
Пересборка файла не годится. Превращение динамических данных в статические невозможна.
Как?
Текущее решение:
Статическую часть выделяю в отдельный файл. Динамические (по их числу, благо всего две) - в другие.
Запись знает о своём смещении в файле и о смещениях динамических данных (что нам помогает только при чтении, так как ограничение по длине никто не отменял).
При обновлении, я переписываю "по месту" статическую часть, изменяя ссылки на динамическую - динамическую пишу в конце файла. Образуется мусор. Программа-обработчик при первом обращении к этим файлам их пересобирает, удаляя неиспользованный мусор.
Родившееся в процессе написания этого поста решение: писать динамические данные в старое место, при этом, если длины не хватает, добавлять в конец смещение на продолжение, продолжать в конце файла. Чтение будет затруднено постоянными прыжками из одного места в другой, но при пересборке опять же все это приводится к человеческому виду.
Есть какие-нибудь ещё предложения, советы?
Задача: записать в файл динамические данные. Спустя какое-то время обновить их.
Пересборка файла не годится. Превращение динамических данных в статические невозможна.
Как?
Текущее решение:
Статическую часть выделяю в отдельный файл. Динамические (по их числу, благо всего две) - в другие.
Запись знает о своём смещении в файле и о смещениях динамических данных (что нам помогает только при чтении, так как ограничение по длине никто не отменял).
При обновлении, я переписываю "по месту" статическую часть, изменяя ссылки на динамическую - динамическую пишу в конце файла. Образуется мусор. Программа-обработчик при первом обращении к этим файлам их пересобирает, удаляя неиспользованный мусор.
Родившееся в процессе написания этого поста решение: писать динамические данные в старое место, при этом, если длины не хватает, добавлять в конец смещение на продолжение, продолжать в конце файла. Чтение будет затруднено постоянными прыжками из одного места в другой, но при пересборке опять же все это приводится к человеческому виду.
Есть какие-нибудь ещё предложения, советы?
Если данные текстовые, можно записывать их в xml. Если двоичные, писать данные, разбивая на блоки фиксированной длины и дополняя до нужной длины нулевыми байтами.
Цитата: ellor!
Если данные текстовые, можно записывать их в xml. Если двоичные, писать данные, разбивая на блоки фиксированной длины и дополняя до нужной длины нулевыми байтами.
Файл должен сбрасываться на диск после каждого изменения - XML не годится.
Данные могут быть произвольной длины. Даже если взять среднюю, мы получим порядка 50% лишнего объема. Не вариант. Да и вообще превращение динамических данных в статические - практика порочная.
(Не годятся также любые манипуляции в памяти процесса навроде построения каких угодно деревьев, etc. по той же причине - каждое изменение сразу же записывается на диск, чтобы избежать потери данных в случае отключения света, BSoD'а и прочих нехороший вещей)
Я не вполне понял вопрос.
Нужно уточнить понятия статических и динамических данных и допустимые операции с ними.
Например: "Данные - это массив записей фиксированного размера. Возможные операции - изменение элемента с заданным номером. Для динамических данных также есть операции вставки/удаления записи"
Также желательно более формализовано написать, чего вы хотите добиться от формата хранения этих данных. Например "при операции добавления элемента в середину динамической части данных должно перезаписываться не более 1% содержимого файла..."
А так остается только гадать, что именно вам нужно. Могу предположить, что нужно что-то похожее на алгоритмы хранения файлов на диске, где каждый файл может разбиваться на кусочки и храниться в разных местах. http://cs.mipt.ru/docs/courses/osstud/12/ch12.htm
Нужно уточнить понятия статических и динамических данных и допустимые операции с ними.
Например: "Данные - это массив записей фиксированного размера. Возможные операции - изменение элемента с заданным номером. Для динамических данных также есть операции вставки/удаления записи"
Также желательно более формализовано написать, чего вы хотите добиться от формата хранения этих данных. Например "при операции добавления элемента в середину динамической части данных должно перезаписываться не более 1% содержимого файла..."
А так остается только гадать, что именно вам нужно. Могу предположить, что нужно что-то похожее на алгоритмы хранения файлов на диске, где каждый файл может разбиваться на кусочки и храниться в разных местах. http://cs.mipt.ru/docs/courses/osstud/12/ch12.htm
Цитата: P*t*
Я не вполне понял вопрос.
Нужно уточнить понятия статических и динамических данных и допустимые операции с ними.
Например: "Данные - это массив записей фиксированного размера. Возможные операции - изменение элемента с заданным номером. Для динамических данных также есть операции вставки/удаления записи"
Также желательно более формализовано написать, чего вы хотите добиться от формата хранения этих данных. Например "при операции добавления элемента в середину динамической части данных должно перезаписываться не более 1% содержимого файла..."
А так остается только гадать, что именно вам нужно. Могу предположить, что нужно что-то похожее на алгоритмы хранения файлов на диске, где каждый файл может разбиваться на кусочки и храниться в разных местах. http://cs.mipt.ru/docs/courses/osstud/12/ch12.htm
Нужно уточнить понятия статических и динамических данных и допустимые операции с ними.
Например: "Данные - это массив записей фиксированного размера. Возможные операции - изменение элемента с заданным номером. Для динамических данных также есть операции вставки/удаления записи"
Также желательно более формализовано написать, чего вы хотите добиться от формата хранения этих данных. Например "при операции добавления элемента в середину динамической части данных должно перезаписываться не более 1% содержимого файла..."
А так остается только гадать, что именно вам нужно. Могу предположить, что нужно что-то похожее на алгоритмы хранения файлов на диске, где каждый файл может разбиваться на кусочки и храниться в разных местах. http://cs.mipt.ru/docs/courses/osstud/12/ch12.htm
Статические данные - данные фиксированного размера.
Динамические данные - данные произвольного размера.
Нужно: уметь изменять динамические данные без их дублирования или разрезания\склейки файла.
Да, вы совершенно верно поняли задачу. Изначально хотел назвать тему "Виртуальная файловая система или как нашинковать файл". Но тут знакомые Сишники развели руками и я решил, что готовых решений нет и придётся разрабатывать алгоритм, структуры, и всё это реализоваывать и отлаживать долгие месяцы (время критично). Если ваша ссылка имеет какое-либо отношение к этому - спасибо, почитаю. Может быть, это именно то, что я искал.
---
Ага, собственно до необходимости реализации файловой системы я сам дошел. :) Но вот писать это, пока, времени нет. Но как-нибудь непременно займусь, если не найду готовых решений.
Тогда могу предложить такой алгоритм (осторожно - алгоритм сложный, а описание очень сжатое):
Данные хранятся в блоках по N записей. Внутри блока записи упорядочены, но сами блоки могут храниться в файле в произвольном порядке. Также в файле есть индекс блоков, где указано, в каком порядке блоки лежат. Для большей производительности индекс можно прямо в файле хранить в виде дерева поиска.
При удалении записи в блоке остается пустое место. Если блок становится пустым, он удаляется из индекса и попадает в список свободных блоков. Если два соседних блока оказываются полупустыми, то все записи перекидываются в один, а второй уничтожается.
При добавлении записи (если добавлять требуется в полный блок) вставляется новый блок из списка свободных.
Из за того, что блоки могут полупустыми, возникает проблема поиска записи с нужным номером - нужно определить в каком блоке она лежит. Для решения этой проблемы придется хранить массив размеров блоков и при поиске i-й записи идти по нему, суммируя все элементы пока сумма не достигнет i. Возможно суммирование можно будет ускорить, использовав дерево Фенвика.
Доля мусора будет не больше половины в худшем случае (если чередуются полные блоки и блоки с одной записью).
Если есть всего S записей, а размер блока N, то порядок времени выполнения одной операции будет:
для относительно простой реализации - O(S/N + N)
для сложной реализации с деревом поиска, деревом Фенвика и прочими извращениями - O(log(S/N) + N)
Данные хранятся в блоках по N записей. Внутри блока записи упорядочены, но сами блоки могут храниться в файле в произвольном порядке. Также в файле есть индекс блоков, где указано, в каком порядке блоки лежат. Для большей производительности индекс можно прямо в файле хранить в виде дерева поиска.
При удалении записи в блоке остается пустое место. Если блок становится пустым, он удаляется из индекса и попадает в список свободных блоков. Если два соседних блока оказываются полупустыми, то все записи перекидываются в один, а второй уничтожается.
При добавлении записи (если добавлять требуется в полный блок) вставляется новый блок из списка свободных.
Из за того, что блоки могут полупустыми, возникает проблема поиска записи с нужным номером - нужно определить в каком блоке она лежит. Для решения этой проблемы придется хранить массив размеров блоков и при поиске i-й записи идти по нему, суммируя все элементы пока сумма не достигнет i. Возможно суммирование можно будет ускорить, использовав дерево Фенвика.
Доля мусора будет не больше половины в худшем случае (если чередуются полные блоки и блоки с одной записью).
Если есть всего S записей, а размер блока N, то порядок времени выполнения одной операции будет:
для относительно простой реализации - O(S/N + N)
для сложной реализации с деревом поиска, деревом Фенвика и прочими извращениями - O(log(S/N) + N)
Цитата: P*t*
Тогда могу предложить такой алгоритм (осторожно - алгоритм сложный, а описание очень сжатое):
Данные хранятся в блоках по N записей. Внутри блока записи упорядочены, но сами блоки могут храниться в файле в произвольном порядке. Также в файле есть индекс блоков, где указано, в каком порядке блоки лежат. Для большей производительности индекс можно прямо в файле хранить в виде дерева поиска.
При удалении записи в блоке остается пустое место. Если блок становится пустым, он удаляется из индекса и попадает в список свободных блоков. Если два соседних блока оказываются полупустыми, то все записи перекидываются в один, а второй уничтожается.
При добавлении записи (если добавлять требуется в полный блок) вставляется новый блок из списка свободных.
Из за того, что блоки могут полупустыми, возникает проблема поиска записи с нужным номером - нужно определить в каком блоке она лежит. Для решения этой проблемы придется хранить массив размеров блоков и при поиске i-й записи идти по нему, суммируя все элементы пока сумма не достигнет i. Возможно суммирование можно будет ускорить, использовав дерево Фенвика.
Доля мусора будет не больше половины в худшем случае (если чередуются полные блоки и блоки с одной записью).
Если есть всего S записей, а размер блока N, то порядок времени выполнения одной операции будет:
для относительно простой реализации - O(S/N + N)
для сложной реализации с деревом поиска, деревом Фенвика и прочими извращениями - O(log(S/N) + N)
Данные хранятся в блоках по N записей. Внутри блока записи упорядочены, но сами блоки могут храниться в файле в произвольном порядке. Также в файле есть индекс блоков, где указано, в каком порядке блоки лежат. Для большей производительности индекс можно прямо в файле хранить в виде дерева поиска.
При удалении записи в блоке остается пустое место. Если блок становится пустым, он удаляется из индекса и попадает в список свободных блоков. Если два соседних блока оказываются полупустыми, то все записи перекидываются в один, а второй уничтожается.
При добавлении записи (если добавлять требуется в полный блок) вставляется новый блок из списка свободных.
Из за того, что блоки могут полупустыми, возникает проблема поиска записи с нужным номером - нужно определить в каком блоке она лежит. Для решения этой проблемы придется хранить массив размеров блоков и при поиске i-й записи идти по нему, суммируя все элементы пока сумма не достигнет i. Возможно суммирование можно будет ускорить, использовав дерево Фенвика.
Доля мусора будет не больше половины в худшем случае (если чередуются полные блоки и блоки с одной записью).
Если есть всего S записей, а размер блока N, то порядок времени выполнения одной операции будет:
для относительно простой реализации - O(S/N + N)
для сложной реализации с деревом поиска, деревом Фенвика и прочими извращениями - O(log(S/N) + N)
О! Интересно и в принципе выполнимо. Спасибо, возьму на заметку. Возможно, так и сделаю.