Алгоритмы файловых операций - Программирование

/7y3uK · 24.12.2004, 16:04

Всем привет - у меня вопрос, который может перерости в обсуждение.
Сразу скажу, что не хотелось бы привязывать данную тему к конкретному языку, т.к. принципы работы с файлами ИМХО схожи.

Имеется: поток, который может создавать/открывать, записывать/читать из/в файл. Работаем в Винде 32 битной, под файловой
системой NTFS. ASM приветствуется, если можно как-то его применить в контексте использования с языками высокого уровня.

Безусловно просто реализовать: запись в конец файла, чтение, замена информации на другую в рамках фиксированного количества байт.

Сложное: удаление из файла фиксированного числа байт (для больших файлов в частности), вставка в файл, замена с увеличением или уменьшением размера.

Возьмем для этого такой пример файла, размером 24 байта:
Hex код:
CE 02 02 02 D1 F2 F0 EE F7 Ea E0 00 00 00 00 32 34 38 33 32 31 38 39 00
ASCII код:
O...Строчка....24832189.

А теперь представим, что файл весит мегабайт эдак 100-500 и надо удалить из файла, допустим первые 4 байта, заменить строку "Строчка"
на строку "Длинная строчка", ну вставить куда-нить че-нить и тд.

Hex0gen · 24.12.2004, 16:30

/7y3uK
%) Насколько я тебя понял, тебе интересна работа с файлами большого размера.

Простые операции реализуются тривиально с помощью функций WinAPI. Операции удаления (вставки) определенного числа байт из середины (в середину) файла являются не стандартными. Тебе нужны не алгоритмы файловых операций, а алгоритмы работы со списками.

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

/7y3uK · 24.12.2004, 21:04

Стоп, стоп, стоп... я понимаю, что вырезка и вставка - не стандартные операции, но это самое нужное и интересное... интересно какие бывают подходы. Пишут же люди движки баз данных, следовательно есть масса различных подходов к этому вопросу, различающихся по скоростным характеристикам. Вот если взять, к примеру, Hex редактор под названием WinHex и создать там файл размером 100 метров, заполнить его случайными числами, сохранить, перезапустить прогу, открыть файл и потом выбрать в середине файла или в начале какой-либо сегмент и удалить его - скорость удаления "из середины" там достаточно большая, хотя ИМХО и зависит от железа, но ведь работает...
Суть моего вопроса придумать, подсказать, подсмотреть алгоритм.... вобщем запостить здесь ваши мысли и будет вам в репутацию всем хорошо

Hex0gen · 24.12.2004, 22:12

Ок, давай поразмыслим.
Требуется написать редактор больших файлов: должен включать обычные "текстовые" операции: вставка, изменение и удаление данных в произвольном месте, быстрая навигация по содержимому.

Предлагаю следующий подход:

Файл при работе с программой не изменяется вообще!!! Сохраняются только те изменения, которые внес пользователь. Изменения вносятся в файл только при нажатии на кнопку Save (или при выходе из программы).
Поэтому наша программа разбивается на две части:

1. Виртуальный просмоторщик и редактор данных файла (virtual-editor). Данный компонент будет сохранять только те изменения, которые мы внесли в файл. Но должен делать вид, что вносит изменения в файл!!! Поэтому я назвал его виртуальным (все изменения хранятся в памяти).

2. Часть, совершающая физическое редактирование файла (commiter). Этот компонент уже корежит данные на диске.

/7y3uK · 24.12.2004, 23:32

Отсюда вытекают два подхода, т.к. не могу с тобой не согласиться

)

1) Как сделать быстрое удаление в виртуальном отображателе - тут можно воспользоваться различными компонентами и методами высокоуровневых языков программирования для репрезентативного отображения информации в текстовом виде - тут проблем мало, т.к. редаткторов текстовой информации масса...

2) Каким способом сделать физическое редактирование?

Предлагаю рассмотреть плюсы и минусы вот такого варианта:
Делается резервная копия файла для откатки, при выборе удяляемого/изменяемого блока пользователем - фиксируется смещение от начала файла до начала изменяемого блока и смещение конца блока... далее создается новый файл, куда копируется содержимое исходного файла до первого адреса, потом копируется измененный контент, далее дописывается оствавшееся содержимое со второй метки....
Такой подход товольно ресурсоемок, но на вскидку более простого варианта продумать не могу

Crazy_kettle · 25.12.2004, 00:40

to /7y3uK

В базе данных скорее всего при удалении вставке не всегда, ИМХО, происходит изменение размера файла. Это говорит о том, ИМХО, что не вся часть файла используется. И с помощью этого можно ускорить быполнение операций (например, при удаления записи, она реально не удаляется, а перестраиваются ссылки, при вставке дописывать одну запись в конец, или образовавшуюся пустоту).

Что насчёт реализации удаления оптимальным образом, то скорее всего лучше сохранить послеудаляемый участок файла в памяти, скопировать его на новое место (с момента удаления), а потом обрезать файл (ИМХО, отерация "обрезки" файла или изменения размера) стандартная. Один минус при нажатии резет или при отключении питания получим мусор. Можно осуществлять и побуферное копирования (не весь остаток файла сохранять, а только 1024 байта, например (потом, после копирования первой порции буфер обновлять)). Но первый вариант, ИМХО, побыстрее будет, исклячая очень больших файлов, когда Винде пришодится "свопится".
Для вставки использовать похожий подход.

Лучше, ИМХО, навскидку ничего не придумаю. Ести очень интересуют алгоритмы, то можно выбрать какой-нибудь Open Source проект, где явно эта операция реализована и посмотреть в исходники как разработчики умудрились это сделать. Понимаю геморно, но если очень хочется ...

P.s. думаю эти функции не стандартные оттого, что не существует эффективной их реализации в данной файловой системе.

ЕЖ · 25.12.2004, 01:08

Цитата:

Сообщение от /7y3uK

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

Расскажу тебе на примере MS SQL Server. Он не меняет размер БД с добавлением/удалением каждой записи. При создании БД задается её размер и шаг приращения в %. Сам файл БД содержит в себе собственную "файловую систему", если можно так сказать. Есть соответственно движок, который отвечает за эту работу с этой системой. Эта система состоит из достаточно не хитрых связанных сегментов, аналогов секторов реальных файловых систем. Частенько при записи в них данных эти сегменты не заполняются плотно, а лишь частично. Существует там и фрагментация. У MSSQL очень мошьная аналитическая система анализа запросов и построения плана их исполнения. Система может просчитывать ожидаемые объемы поступления данных. В нужный моменты файл БД растет на заданный %. Предварительная оценка этого % одна из важных задач администрирования производительности сиквела.

Но это я рассказал в двух словах. Если интересует, где-то у меня было значительно более подробное описание...

/7y3uK · 26.12.2004, 02:50

ЕЖ
Если есть более подробная инфа на русском - буду признателен

ЕЖ · 27.12.2004, 13:03

/7y3uK
Могу тебе выслать файлик architec.chm (790k) из MS SQL Server Books Online. Там всё подробно расписано с рисунками и схемами. Правда на английском, но лично мне всё понятно. На русском у меня есть всё почти один в один в книге, но её ещё сканировать надо, выкладывать...

/7y3uK · 27.12.2004, 17:27

Это ИМХО... думаю, скачают все кому интересно, поэтому если есть время и желание, то можно и отсканированный вариант

) Но и за аглицкую версию в репутацию пропишу

)

ЕЖ · 27.12.2004, 18:03

/7y3uK
Ну поскольку ты мыло не оставил... Официально свободная для доступа документация по MSSQL ищется в Google за две секунды, вот хотя бы:
http://mirror.aarnet.edu.au/pub/micr...0/common/Help/

Тебе нужны 2 файла:
- architec.chm
- architec.chi

По сабжу смотри в .chm разделы: Database Architecture > Physical Database Architecture > Space Allocation and Reuse, но перед этим всё-таки стоит прочитать всё с начала раздела Database Architecture.

P.S. Сканировать реально некогда.

24.12.2004, 16:04	# 1
/7y3uK Advanced Member Регистрация: 09.03.2004 Адрес: толстозадая Москва Сообщения: 498	Алгоритмы файловых операций Всем привет - у меня вопрос, который может перерости в обсуждение. Сразу скажу, что не хотелось бы привязывать данную тему к конкретному языку, т.к. принципы работы с файлами ИМХО схожи. Имеется: поток, который может создавать/открывать, записывать/читать из/в файл. Работаем в Винде 32 битной, под файловой системой NTFS. ASM приветствуется, если можно как-то его применить в контексте использования с языками высокого уровня. Безусловно просто реализовать: запись в конец файла, чтение, замена информации на другую в рамках фиксированного количества байт. Сложное: удаление из файла фиксированного числа байт (для больших файлов в частности), вставка в файл, замена с увеличением или уменьшением размера. Возьмем для этого такой пример файла, размером 24 байта: Hex код: CE 02 02 02 D1 F2 F0 EE F7 Ea E0 00 00 00 00 32 34 38 33 32 31 38 39 00 ASCII код: O...Строчка....24832189. А теперь представим, что файл весит мегабайт эдак 100-500 и надо удалить из файла, допустим первые 4 байта, заменить строку "Строчка" на строку "Длинная строчка", ну вставить куда-нить че-нить и тд.

25.12.2004, 00:40	# 6
Crazy_kettle Junior Member Регистрация: 13.05.2004 Сообщения: 128	to /7y3uK В базе данных скорее всего при удалении вставке не всегда, ИМХО, происходит изменение размера файла. Это говорит о том, ИМХО, что не вся часть файла используется. И с помощью этого можно ускорить быполнение операций (например, при удаления записи, она реально не удаляется, а перестраиваются ссылки, при вставке дописывать одну запись в конец, или образовавшуюся пустоту). Что насчёт реализации удаления оптимальным образом, то скорее всего лучше сохранить послеудаляемый участок файла в памяти, скопировать его на новое место (с момента удаления), а потом обрезать файл (ИМХО, отерация "обрезки" файла или изменения размера) стандартная. Один минус при нажатии резет или при отключении питания получим мусор. Можно осуществлять и побуферное копирования (не весь остаток файла сохранять, а только 1024 байта, например (потом, после копирования первой порции буфер обновлять)). Но первый вариант, ИМХО, побыстрее будет, исклячая очень больших файлов, когда Винде пришодится "свопится". Для вставки использовать похожий подход. Лучше, ИМХО, навскидку ничего не придумаю. Ести очень интересуют алгоритмы, то можно выбрать какой-нибудь Open Source проект, где явно эта операция реализована и посмотреть в исходники как разработчики умудрились это сделать. Понимаю геморно, но если очень хочется ... P.s. думаю эти функции не стандартные оттого, что не существует эффективной их реализации в данной файловой системе. Последний раз редактировалось Crazy_kettle; 25.12.2004 в 01:14.

24.12.2004, 16:30	# 2
Hex0gen Newbie Регистрация: 24.09.2004 Сообщения: 42	/7y3uK %) Насколько я тебя понял, тебе интересна работа с файлами большого размера. Простые операции реализуются тривиально с помощью функций WinAPI. Операции удаления (вставки) определенного числа байт из середины (в середину) файла являются не стандартными. Тебе нужны не алгоритмы файловых операций, а алгоритмы работы со списками. Могу предложить следующие варианты: 1. Один большой файл режешь на кучу маленьких (причем размеры этих файлов могут быть различными). При этом получишь выигрышь при вставке/удалении (так как удалить или вставить в маленький файл проще, чем в большой). Но получаешь проигрышь при выполнении комманды seek. 1. Пишешь свою файловую систему, в которой функции вставки в середину файла является стандартной операцией %)

24.12.2004, 21:04	# 3
/7y3uK Advanced Member Регистрация: 09.03.2004 Адрес: толстозадая Москва Сообщения: 498	Стоп, стоп, стоп... я понимаю, что вырезка и вставка - не стандартные операции, но это самое нужное и интересное... интересно какие бывают подходы. Пишут же люди движки баз данных, следовательно есть масса различных подходов к этому вопросу, различающихся по скоростным характеристикам. Вот если взять, к примеру, Hex редактор под названием WinHex и создать там файл размером 100 метров, заполнить его случайными числами, сохранить, перезапустить прогу, открыть файл и потом выбрать в середине файла или в начале какой-либо сегмент и удалить его - скорость удаления "из середины" там достаточно большая, хотя ИМХО и зависит от железа, но ведь работает... Суть моего вопроса придумать, подсказать, подсмотреть алгоритм.... вобщем запостить здесь ваши мысли и будет вам в репутацию всем хорошо

24.12.2004, 22:12	# 4
Hex0gen Newbie Регистрация: 24.09.2004 Сообщения: 42	Ок, давай поразмыслим. Требуется написать редактор больших файлов: должен включать обычные "текстовые" операции: вставка, изменение и удаление данных в произвольном месте, быстрая навигация по содержимому. Предлагаю следующий подход: Файл при работе с программой не изменяется вообще!!! Сохраняются только те изменения, которые внес пользователь. Изменения вносятся в файл только при нажатии на кнопку Save (или при выходе из программы). Поэтому наша программа разбивается на две части: 1. Виртуальный просмоторщик и редактор данных файла (virtual-editor). Данный компонент будет сохранять только те изменения, которые мы внесли в файл. Но должен делать вид, что вносит изменения в файл!!! Поэтому я назвал его виртуальным (все изменения хранятся в памяти). 2. Часть, совершающая физическое редактирование файла (commiter). Этот компонент уже корежит данные на диске.

24.12.2004, 23:32	# 5
/7y3uK Advanced Member Регистрация: 09.03.2004 Адрес: толстозадая Москва Сообщения: 498	Отсюда вытекают два подхода, т.к. не могу с тобой не согласиться ) 1) Как сделать быстрое удаление в виртуальном отображателе - тут можно воспользоваться различными компонентами и методами высокоуровневых языков программирования для репрезентативного отображения информации в текстовом виде - тут проблем мало, т.к. редаткторов текстовой информации масса... 2) Каким способом сделать физическое редактирование? Предлагаю рассмотреть плюсы и минусы вот такого варианта: Делается резервная копия файла для откатки, при выборе удяляемого/изменяемого блока пользователем - фиксируется смещение от начала файла до начала изменяемого блока и смещение конца блока... далее создается новый файл, куда копируется содержимое исходного файла до первого адреса, потом копируется измененный контент, далее дописывается оствавшееся содержимое со второй метки.... Такой подход товольно ресурсоемок, но на вскидку более простого варианта продумать не могу

26.12.2004, 02:50	# 8
/7y3uK Advanced Member Регистрация: 09.03.2004 Адрес: толстозадая Москва Сообщения: 498	ЕЖ Если есть более подробная инфа на русском - буду признателен

27.12.2004, 13:03	# 9
ЕЖ ::VIP:: Регистрация: 19.03.2004 Сообщения: 1 329	/7y3uK Могу тебе выслать файлик architec.chm (790k) из MS SQL Server Books Online. Там всё подробно расписано с рисунками и схемами. Правда на английском, но лично мне всё понятно. На русском у меня есть всё почти один в один в книге, но её ещё сканировать надо, выкладывать...

27.12.2004, 17:27	# 10
/7y3uK Advanced Member Регистрация: 09.03.2004 Адрес: толстозадая Москва Сообщения: 498	Это ИМХО... думаю, скачают все кому интересно, поэтому если есть время и желание, то можно и отсканированный вариант ) Но и за аглицкую версию в репутацию пропишу )

27.12.2004, 18:03	# 11
ЕЖ ::VIP:: Регистрация: 19.03.2004 Сообщения: 1 329	/7y3uK Ну поскольку ты мыло не оставил... Официально свободная для доступа документация по MSSQL ищется в Google за две секунды, вот хотя бы: http://mirror.aarnet.edu.au/pub/micr...0/common/Help/ Тебе нужны 2 файла: - architec.chm - architec.chi По сабжу смотри в .chm разделы: Database Architecture > Physical Database Architecture > Space Allocation and Reuse, но перед этим всё-таки стоит прочитать всё с начала раздела Database Architecture. P.S. Сканировать реально некогда.

Опции темы
Версия для печати Отправить на email