Ищу алгоритм удаления
> и их можно в оперативке сохранить.
В том и дело, что нельзя.
можно, не значит нужно, если надо полностью иметь структуру на диске, то эта сотня байт спокойно помещаются в начало файла с данными, или в любой другой дополнительный файл.
Только С#.
не знаю его библиотеки и шарпом не пользуюсь, но предполагаю, что можно присовокупить соответствующий класс их С++ и средствами шарпа сохранить на диск туда, где ему нужно быть. Остальную логику я вроде рассказал. Если не понятно объяснил, не стесняйтесь, спрашивайте.
Это если вам, что понадобится просто с кем то обсудить, то всегда пож.
спасибо, не, у меня такой задачи сейчас нет, была когда в 90-х диссер писал, и с тех пор особо не менял
там ничего, работает же, и есть доказательство оптимальности при определенных условиях.
С записью проблем проблем нет, пиши всегда в конец. Но блоки нужно удалять, либо вместо малого блока записать более большой, когда при обновлении блока данных стало больше.Удаленные блоки можно записывать в список удаленных, после оттуда выбирать подходящие. Из больших блоков можно делать маленькие, а два маленьких соседних блока объединять в большой.Вот как сделать этот список удаленных блоков лучшим образом? Он же тоже место будет занимать. Удалили 1000 блоков, а после использовали 900. Список остался, но уже не такой большой.
Ну добавлять всегда в конец это не очень хорошо. Вернее хорошо, если скорость добавления важнее других требований. А так в общем случае можно например завести таблицу выделенных блоков где одна запись описывает один блок. И таблицу свободного пространства (дырок), где одна запись это одна дырка, т.е. свободный блок. Они индексируются по длине, чтобы быстро находить блок или дырку нужного размера. При выделении нового блока находится подходящая дырка. При удалении блока надо либо новую дырку добавить либо расширить соседние дырки. Вопрос только как обновлять таблицу размещения и индекс.
как их сделать динамическими?
------
Апдейтить после каждого изменения исходных данных.
это прерогатива пользователя.
-----
Ну так вообще никаких проблем - подтверждает актуализацию или ждет оной. Не твоя же забота.
зависит от данных и их организации
-----
Не понял.
ты хочешь сравнивать не эквивалентные схемы? Так это изначально бессмысленно.
быстрее чем просто прочитать данные?
------
В некоторых случаях - да.
У тебя получается короткий "индекс" из имен файлов, вместо скана всего файла.
нужно их же перенести на другой комп/ в другой каталог.
-------
Зачем?
Написал батник и запустил без окна - все пройдет довольно быстро.
Ну так это и есть проблема, как ее оптимально организовать.
Это именно решение:
1. список дырок в виде записей <смещение, размер>: <1000, 500>, <2000, 200>, <3000, 700>
2. индекс в виде сортировки по размеру: [1, 0, 2]
Так что не вижу где здесь еще что-то можно решать. Вот это "как ее оптимально организовать" вообще ни о чем, поскольку нет критериев оптимальности: оптимизировать чтение, запись, память (на диске или в памяти), конкурентный доступ, распределенное представление или что-то еще.
А проблемы здесь было 2:
- как избежать обновления ссылок на блоки при перемещении блоков -> Ответ: путем введения логических ссылок
- как управлять таблицей размещения -> Ответ: путем сортировки по размеру (и потом двоичного поиска)
Обе проблемы для технического интервью на мидла наверное.
1. выкидываешь - size - всегда распределяешь стандартными блоками 512, 1024, 8096
2. выкидываешь - freeblockref - цепочка свободных блоков, если нужна, ведется отдельно
3. выкидываешь - leftnode - скан всегда рута
4. заменяешь - rightnode - на - nextblock - это где лежит продолжение, если не уместился
делаешь другую структуру (имя/ключ(8.3?), firstblock, size, removed)
работает так
- начальная разметка - пустой список ключей и зануленная таблица блоков
- добавил- сделал запись ключа, заполнил занятые блоки, последний пометил мах(н) FFF?
- удалил -- пометил ключ как удаленный
- очистка - зануляешь цепочку nextblock и удаляешь ключ
Таблицу структур имя/ключ пишешь в обычный блок и расширяешь по мере необходимости.
Таблицу nextblok'ов - размещаешь целиком на максимальный размер набора.
Это грубая эмуляция FAT. Код есть на сайтах эмбедеров.
Так что не вижу где здесь еще что-то можно решать.
Попробую пояснить.
Есть какой-то список дырок, каждый элемент списка имеет свой размер.
Вначале список пустой, затем увеличивается, после может уменьшаться.
Вот процесс увеличения и уменьшения размера списка и интересует.
Даже скорее уменьшение размера списка дырок.
Ответ: путем введения логических ссылок
Еще один уровень для доступа и еще одна таблица перевода логических ссылок в физические?
Вначале список пустой, затем увеличивается, после может уменьшаться.
--------------
Либо резервируется изначально. Где много вставок - чем больше резервируется - тем лучше.
И зачем уменьшаться? Увеличение всегда дорого.
Если будет совсем плохо - см ISAM. Сишных реализаций не знаю.
Либо резервируется изначально.
Ну вот создал я файл, сколько резервировать?
И зачем уменьшаться
Допустим у меня в папочке 10 тыс. файлой, тогда в моем списке будет 10000+1 записи (папочка+файлы)
удаляю я всю папочку, получаю 10т.+1 описаний дырок. Сканирую следующую папочку с 9т. файлов, остается всего 1т. дырок.
Значит теперь структура описания удаленных файлов содержит 9т ненужных записей.
Всё оставлять?