Вспомнил проблемку которую давно решил, но совершенно не помню как.

Что имеем?

Некий файл, хранилище данных, данные туда записываются поблочно, типа 100, 200, 500 байт. Этих блоков может быть дофига, миллионы и больше.

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

С записью проблем проблем нет, пиши всегда в конец. Но блоки нужно удалять, либо вместо малого блока записать более большой, когда при обновлении блока данных стало больше.

Удаленные блоки можно записывать в список удаленных, после оттуда выбирать подходящие. Из больших блоков можно делать маленькие, а два маленьких соседних блока объединять в большой.

Вот как сделать этот список удаленных блоков лучшим образом? Он же тоже место будет занимать.

Удалили 1000 блоков, а после использовали 900. Список остался, но уже не такой большой.

для добавлений....

Вот как сделать этот список удаленных блоков лучшим образом? Он же тоже место будет занимать.

И что?

Раз вы решили управление файлами вынести на более высокий уровень прикладного кода, то и создавайте на этом уровне что-то вроде файловой таблицы. Только вместо файлов в ней будут ваши блоки.

А почему, собственно, пишете в один файл, вместо того, чтобы по файлу на блок?

решили управление файлами вынести на более высокий уровень

Это не управление файлами - это скорее dynamic storage

А почему, собственно, пишете в один файл, вместо того, чтобы по файлу на блок?

Миллионы файлов в каталоге?

Стандартно - блоки помечаются - удаленные. Никуда не перемещаются.

После изменения статуса - перестраиваются индексы.

Когда наступает "Ой, звиздец" - проводится ужимание с физическим удалением.

Основной вопрос - нахрен? - блобы вполне подходят.

Миллионы файлов в каталоге?

-----

Для компа - почти пофиг. Просто не лезь туда гуем...

это классическая задача аллокаторов памяти. В каждый блок в начале записываете структурку, которая связана соседями линейным двухсвязанным списком (чтобы детектировать, что соседний блок удалили и надо объединить свободное пространство), а в каждый удаленный - дополнительно пишем структуру динамически балансируемого дерева, в котором все отсортировано по размеру этого свободного пространства.

При запросе на новый блок в за логарифмическое время находите первый блок по размеру, который удовлетворяет (или если нет, то пишем в конец).

При удалении пользуемся линейным списком чтобы понять соседа и, если сосед пустой, объединяем (еще два реквеста в бинарное дерево).

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

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

Стандартно - блоки помечаются - удаленные.

Ну пометил, а как искать? не лазить же по всему файлу.

проводится ужимание

каким образом? Позицию "занятых" блоков менять нельзя, разве что системные блоки, которые еще можно контролировать как то.

блобы вполне подходят

В базе? нет, никакой прослойки, быстродействие резко упадет думаю.

Вот как раз проблема перед глазами. Была отличная прога каталогизатор файлов с бинарным сохранением данных.

Сделали новую и решили пользовать SQLite. Пользоваться прогой невозможно стало и медленней и размеры сохранённых данных увеличились

Просто не лезь туда гуем...

А быстродействие, а перенос?

а в каждый удаленный - дополнительно пишем структуру динамически балансируемого дерева,

Ну так как проблема как раз в этом дереве. На каждый удаленный блок пишется дополнительная структура. Блок взяли а что делать со структурой?

Миллионы файлов в каталоге?

-----

Для компа - почти пофиг. Просто не лезь туда гуем...

А если ещё и отдельное место на диске с запасом выделить под это дело, чтобы фрагментация не влияла... А ещё и нормальные SSD использовать с хорошими буферами...

а как искать?

-------

по индексу перестроенному после изменения

менять нельзя

------

Можно. Разумеется с коррекцией ссылок.

Можно подумать над чем-то похожим на FAT (FAT16,FAT32,FAT64)

быстродействие резко упадет думаю

-----

Не-а...

Пока ты добъешься такого же - последняя весна закончится

невозможно стало

-----

Кури доку на sqlite.Я об нем ничего не знаю

Что Я знаю на 100% - нормальный сервер БД с большим объемом данных работает быстрее самописок.

С единственным исключением - когда данные статичны и денормализованны - самописка будет быстрее. Но! Статичных данных у нас не бывает.

А быстродействие, а перенос?

------

нормально - просто работаешь на чуть более низком уровне

Про - понос - не понял.

Блок взяли а что делать со структурой?

-------

Читай доки на FAT.

с хорошими буферами...

-------

просто не пользуй то что берет с диска ненужное.

а как искать? ------- по индексу перестроенному после изменения

Так как раз в дополнительных данных и проблема, как их сделать динамическими?

Можно. Разумеется с коррекцией ссылок.

Ссылки менять не могу - это прерогатива пользователя.

Не-а...Пока ты добъешься такого же - последняя весна закончится

очень сомневаюсь

нормальный сервер БД с большим объемом данных работает быстрее самописок

многое зависит от данных и их организации

нормально - просто работаешь на чуть более низком уровне

найти файл, открыть файл, прочитать данные - быстрее чем просто прочитать данные?

Есть вот у меня миллионы файлов в одном каталоге, нужно их же перенести на другой комп/ в другой каталог.

Ну так как проблема как раз в этом дереве. На каждый удаленный блок пишется дополнительная структура. Блок взяли а что делать со структурой?

проблемы-то нет. Каждая структура (или класс, если на С++) листка этого бинарного дерева сидит в блоке со свободной памятью - вы же ее удалить не можете, так как после нее есть блок с занятой памятью. Очевидно, если блок был в конце файла, то лучше его просто удалить и из бинарного дерева и из файла. А вот головка, или корень этого бинарного дерева - это несколько десятков байт, и их можно в оперативке сохранить.

Самописный код бинарного дерева

380 725 7945 bintree.c
83 191 1942 bintree.h
463 916 9887 итого

меньше 500 строк сишника, в современном С++ есть соответствующий класс, и не надо велосипед выдумывать. Предполагаю, что в других языках и бинарное дерево, и двухсвязанные списки тоже в стандартных библиотеках имеются. Весь код такого аллокатора:

380 725 7945 bintree.c
83 191 1942 bintree.h
112 216 2158 decmem.c
463 969 11349 dmem.c
93 267 3159 dmem.h
336 592 5963 memc.c
62 170 1358 memc.h
292 1127 7883 memf.f
303 639 6732 quemem.c
2124 4896 48489 итого

у меня в свое время получился слегка больше двух тысяч строк и в 90-х я это примерно за месяц запрограммировал и радовался. Как я говорю, сейчас все это решается стандартными средствами С++, поэтому код дарить не буду, но рассказать-объяснить постараюсь. Если хотите, или так будет проще, могу войсом, тогда в личке телефонами обменяться надо будет.

и их можно в оперативке сохранить.

В том и дело, что нельзя.

Открыл прогу, добавил данных, ушел.

Открыл прогу удалил данные, ушел.

Открыл прогу, добавил данных, ушел.

и в 90-х я это

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

Сейчас что подобное хочется, но детали забылись.

поэтому код дарить не буду

Да код и не нужен, спасибо. Главное идея, а уж реализовать дело вторичное.

Относительно телефона нет проблем, но эта не та проблема, на которую нужно еще тратить ваше время. Это если вам, что понадобится просто с кем то обсудить, то всегда пож.

Ну и Си с плюсами я уже давно не пользую. Только С#.

Стандартная и очень частая задача. Ну например ссылки в Яве, DNS (именя в IP адреса) и т.п.

Решается путем введения двух идентификаторв: физического представления блока (смещение) и его логического представления (ссылка на блок), а также отображения между ними. Используется только логические ссылки. Физическое представление только в реализации.

BlockRef // Логический идентификатор, напрмер, int

BlockOffset // Физическое расположение например смещение в файле

interface Storage
  BlockRef alloc(size int)
  delete(BlockRef)

  resize(new_size int)

  byte[] read(BlockRef)
  write(BlockRef, byte[])

class FileStorage implements Storage
  File file // Здесь все храним
  Map block_allocation<BlockRef, BlockOffset> // Фактически таблица размещения это главная структура (тоже интерфейс)

  gc() // Запускаем периодически для сборки мусора, уплотнения и пр. оптимизаций

Главное это как отображать логические ссылки в физическое расположение. В простейшем случае это map. Но в реальности думаю есть миллионы разных способов для разных применений. Как говорится "зависит от контекста". Ну например можно хранить во многих файлах или большие блоки отдельно от маленьких или реализовать очередь запросов в случае конкурентного доступа и т.п. Надо конечно заниматься подсчетом использования ссылок, но это все просто для простых применений, а для сложных можно постепенно улучшать, поскольку интерфейс определен.

> и их можно в оперативке сохранить.

В том и дело, что нельзя.

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

Только С#.

не знаю его библиотеки и шарпом не пользуюсь, но предполагаю, что можно присовокупить соответствующий класс их С++ и средствами шарпа сохранить на диск туда, где ему нужно быть. Остальную логику я вроде рассказал. Если не понятно объяснил, не стесняйтесь, спрашивайте.

Это если вам, что понадобится просто с кем то обсудить, то всегда пож.

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

С записью проблем проблем нет, пиши всегда в конец. Но блоки нужно удалять, либо вместо малого блока записать более большой, когда при обновлении блока данных стало больше.Удаленные блоки можно записывать в список удаленных, после оттуда выбирать подходящие. Из больших блоков можно делать маленькие, а два маленьких соседних блока объединять в большой.Вот как сделать этот список удаленных блоков лучшим образом? Он же тоже место будет занимать. Удалили 1000 блоков, а после использовали 900. Список остался, но уже не такой большой.

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

как их сделать динамическими?

------

Апдейтить после каждого изменения исходных данных.

это прерогатива пользователя.

-----

Ну так вообще никаких проблем - подтверждает актуализацию или ждет оной. Не твоя же забота.

зависит от данных и их организации

-----

Не понял.

ты хочешь сравнивать не эквивалентные схемы? Так это изначально бессмысленно.

быстрее чем просто прочитать данные?

------

В некоторых случаях - да.

У тебя получается короткий "индекс" из имен файлов, вместо скана всего файла.

нужно их же перенести на другой комп/ в другой каталог.

-------

Зачем?

Написал батник и запустил без окна - все пройдет довольно быстро.

то эта сотня байт

Каким образом? Вот минимальное Node всего на один удаленный блок

int Size

long FreeBlockRef

long LeftNode

long RightNode

и средствами шарпа сохранить на диск туда, где ему нужно быть

Да, всё тоже самое что и в С++

И таблицу свободного пространства (дырок), где одна запись это одна дырка, т.е. свободный блок

Ну так это и есть проблема, как ее оптимально организовать.

Написал батник и запустил без окно

Виндузятники так не делают

вместо скана всего файла

кто сказал такую глупость?

Ну так это и есть проблема, как ее оптимально организовать.

Это именно решение:

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. Код есть на сайтах эмбедеров.

Так что не вижу где здесь еще что-то можно решать.

Попробую пояснить.

Есть какой-то список дырок, каждый элемент списка имеет свой размер.

Вначале список пустой, затем увеличивается, после может уменьшаться.

Вот процесс увеличения и уменьшения размера списка и интересует.

Даже скорее уменьшение размера списка дырок.

Ответ: путем введения логических ссылок

Еще один уровень для доступа и еще одна таблица перевода логических ссылок в физические?

кто сказал такую глупость?

------------

таки - ты Индексы же строить отказываешься.

Таблицу nextblok'ов - размещаешь целиком на максимальный размер набора.

А не знаю я максимального размера набора

выкидываешь - size - всегда распределяешь стандартными блоками 512, 1024, 8096

ну так всё равно нужно знать размер: 1,2,3.

таки - ты Индексы же строить отказываешься.

воображение у вас батенька большое

Вначале список пустой, затем увеличивается, после может уменьшаться.

--------------

Либо резервируется изначально. Где много вставок - чем больше резервируется - тем лучше.

И зачем уменьшаться? Увеличение всегда дорого.

Если будет совсем плохо - см ISAM. Сишных реализаций не знаю.

А не знаю я максимального размера набора

------

Размер диска или квота.

ну так всё равно нужно знать размер

------

Ну так он всегда один - какой выберешь - такой и будет.

Либо резервируется изначально.

Ну вот создал я файл, сколько резервировать?

И зачем уменьшаться

Допустим у меня в папочке 10 тыс. файлой, тогда в моем списке будет 10000+1 записи (папочка+файлы)

удаляю я всю папочку, получаю 10т.+1 описаний дырок. Сканирую следующую папочку с 9т. файлов, остается всего 1т. дырок.

Значит теперь структура описания удаленных файлов содержит 9т ненужных записей.

Всё оставлять?

Ну так он всегда один - какой выберешь - такой и будет

Один размер для 4 байт и 1000?

Читай доки на FAT.

https://droopy.narod.ru/FAT.htm

см. Потери на остатках кластеров.

Ну вот создал я файл, сколько резервировать?

------

размер диска/квоты делишь на размер выбранного блока => получаешь возможное количество блоков

смотришь сколько байт нужно чтобы поместился номер последнего блока

резервируешь: количество блоков * количество байт для номера

И, кстати, будет не вредно сразу прописать весь файлик мусором - чтоб место физически выделилось.

Один размер для 4 байт и 1000?

------

именно так.

для 4 байт один блок

для 1000 - 1 или 2 или 4 - по размеру блока

Читай доки на FAT.

----------

Мне то зачем? Я и так знаю.

При побайтвом мапинге будет другая проблема - фрагментированность - единственный записанный байт залочит всю систему.

1. Все полезные алгоритмы нужно хранить на флешки/CD/внешнем диске.

2. Даже Microsoft не смогла сделать толком нормальную утилиту по дефрагментации диска, она купила её помойму у Symantec. Когда удаляются файлы, там помечается каким-то флагом что файл удалён, и при этом остаются дырки, а при дефрагметации диска пустые места (дырки) заполняются данными. Дефрагментация это долгий процесс.

3. В файловой системе блоки (сектора) фиксировоной длины, помойму 1 блок (сектор) = 512 байт.

4. Не понял задачу, но как-то так:

#include <iostream>
#include <cstdlib>
#include <cstring>
using namespace std;
// Копирует блок в общую память
void copy_block(char *buf, char *data, int pos) {
    memcpy(buf+pos, data, strlen(data));
}
// Удаляет блок из общей памяти
void delete_block(char *buf, int pos, int len) {
    memset(buf+pos, '\0', len);
}
int main(int argc, char** argv) {
    char *buf; // Общая память
    char block1[] = "Hello "; // блок содержащий слово Hello
    char block2[] = "Igor"; // блок содержащий слово Igor
    char block3[] = "Ann";// блок содержащий слово Ann
    buf = (char *)malloc(65535); // Резервируем память 65К
    memset(buf, '\0', 65535); // Инициализируем память
    copy_block(buf, block1, 0); // Копируем в 0 ячейку памяти Hello
    copy_block(buf, block2, strlen(block1)); // Копируем в 5 ячейку памяти Igor
    cout << buf << endl; // Выводим на экран Hello Igor
    delete_block(buf, strlen(block1), strlen(block2)); // Удаляем в 5 ячейки памяти 3 байта
    cout << buf << endl; // Выводим на экран Hello
    copy_block(buf, block3, strlen(block1));// Копируем в 5 ячейку памяти Ann
    cout << buf << endl; // Выводим на экран Hello Ann
    free(buf); // Освобождаем зарервированную память
    return 0;
}

А с блоками можно сделать примерно так:

    struct BLOCK_1 {
        long next_offset;
        char buf[5];
    };

    struct BLOCK_2 {
        long next_offset;
        char buf[10];
    };

    struct BLOCK_3 {
        long next_offset;
        char buf[15];
    };
        
    BLOCK_1 block_1;
    BLOCK_2 block_2;
    BLOCK_3 block_3;
    
    block_1.next_offset = 5;
    strcpy(block_1.buf, "Igor");
    block_2.next_offset = 5 + 10;
    strcpy(block_2.buf, "Ann");
    block_3.next_offset = 5 + 10 + 15;
    strcpy(block_3.buf, "Mustermann");

P.S.:Извиняюсь если ответил не так, что-то последние три дня плохо соображаю, две ночи плохо спал.

Если я кому-то отвечаю, это не значит что я ему симпатизирую, каждый остаётся при своём мнении Meine Die Formel der Liebe

Один размер для 4 байт и 1000?------именно так.

Мне то зачем? Я и так знаю.

Исправил, это была "ссылка" на твой запрос

buf = (char *)malloc(65535); // Резервируем память 65К

Это сразу не годится

Структура записи должна быть типа такой, хотя ссылка на следующий блок совершенно не нужна

struct BLOCK {
        long next_offset;
        char buf[];
    };

Все полезные алгоритмы нужно хранить на флешки/CD/внешнем диске.

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

получаю 10т.+1 описаний дырок.

------

Просто затираешь в таблице блоков освободившиеся блоки.

В том числе и блоки под папкой.

Единственный неудаляемый блок - корневой

-----------------

Значит вопрос фрагментации не решался.

Когда удаляются файлы, там помечается каким-то флагом что файл удалён, и при этом остаются дырки, а при дефрагметации диска пустые места (дырки) заполняются данными.

А зачем физически удалять данные, если достаточно пометить их как свободные для перезаписи?

Дефрагментация это долгий процесс.

Вместо вредной и медленной дефрагментации лучше скопировать всё на другой пустой диск, а потом на первом всё удалить. Теперь можно при необходимости повторить процесс, но в обратном направлении.

Чтобы фрагментация меньше доставляла проблем, нужно придерживаться примерно такого же правила, как для RAM - память должна использовать не более, чем на 2/3 от доступной. В идеале не более, чем на половину. Если используется больше, нужно докупить памяти. Оперативка, кстати, тоже страдает от фрагментации, хотя и в меньшей степени из-за своей скорости. Но ещё она страдает вдобавок и от свопа.

Просто затираешь в таблице блоков освободившиеся блоки.

А как это повлияет на размер файла? Или как я туда смогу что то записать из данных?

Значит вопрос фрагментации не решался.

Всё отлично решалось. И блоки были, только не фиксированной длины, а просто кратные степени 2ки.

Но пока ничего не навеяло на путь решения. Уже на этапе удаления блока, два соседних удалённых блока объединялись и в таблицу удаленных записывался только этот объединённый блок.

А как это повлияет на размер файла?

-------

А должно?

Или как я туда смогу что то записать из данных?

------

Находишь в таблице блоков пустой (000) блок и пишешь туда. Что не вошло - пишешь в следующий пустой.

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

не фиксированной длины, а просто кратные степени 2ки.

------

голову примени - либо фрагментация, либо фиксированный размер блока. Другого просто нет. Даже не комбинируется.

У винды, кстати, память управляется блоками фиксированной длины и под это дело уходит хренова куча памяти.

два соседних удалённых блока объединялись

-----

У тебя квота Х.

Ты пишешь последовательно (Х/2-2), (4). (Х/2-2) - полный.

Освобождаешь оба (Х/2-2).

Теперь тебе надо писать ровно (Х/2) - все, приплыли.

Если не приплыли, то как-то без блоков переменой длины.

А как это повлияет на размер файла?-------А должно?

конечно, зачем мне лишний мусор в файле

Находишь в таблице блоков пустой

Речь как то и идет о таблице пустых блоков мне нужно утилизовать записи которые уже не используются.

Что не вошло - пишешь в следующий пустой

Концепт другой, блок заполняется полностью.

либо фрагментация, либо фиксированный размер блока. Другого просто нет

Ага, конечно нет. Когда сам же и делал. И речь о 100% дефрагментации не идёт.

Теперь тебе надо писать ровно (Х/2) - все, приплыли.

Мысля у вас какая то странная.

вот один свободный блок на 16 байт, вот рядышком еще один на 16. Объединяем и получаем блок на 32 байта.

Где проблема, то?

зачем мне лишний мусор в файле

------

Чтобы повех него писать новую инфу.

Или т при удалении файла прописываешь занимаемое им место поперемено 0/1?

о таблице пустых блоков

------

А нету такой. За ненадобностью.

мне нужно утилизовать записи

-----

Ну так объявляешь блоки свободными и все.

Концепт другой,

------

Выше написано во что упрешься.

Где проблема, то?

-----

Выше очень подробно писано. Там где об (Х/2-2)

Чтобы поверх него писать новую инфу.

ну так и я о том же.

о таблице пустых блоков
------А нету такой. За ненадобностью.

И как же ты будешь дырки отслеживать?

Ну так объявляешь блоки свободными и все.

Для этого удаленные блоки данных и записываются в таблицу свободных блоков.

Выше написано во что упрешься.

расскажи лучше IBM, что процессор может быть только одноядерным

Выше очень подробно писано. Там где об (Х/2-2)

Вижу только какую-то билиберду

Что за (Х/2-2)? х=10, 5-2=3 - не может быть блок равен 3

Можно начать с более простой проблемы.

Если размер выделяемых блоков кратен степени 2, то как быстрее всего найти два удалённых смежных блока?

Если все удаленные блоки хранятся в каком то списке.

И как же ты будет дырки отслеживать?

-------

Может все же доки на FAT почитаешь?

Может все же доки на FAT почитаешь?

Так ссылку уже давал раньше - не годится эта фигня, там размер блока фиксированный

в таблицу свободных блоков.

------=

В таблицу блоков пишется:

000 - блок свободен для записи

FFF - блок последний в цепочке использованных блоков (первый - указан рядом с именем/ключем)

любое другое - номер следующего использованного этой записью блока

не может быть блок равен 3

---------

Всего лишь Х у тебя неправильный....

В таблицу блоков пишется:

так разве в этом проблема? Проблема в организации этой самой таблицы.

любое другое - номер следующего использованного этой записью блока

так это уже будет таблица использованных блоков, которая как раз и не требуется

Всего лишь Х у тебя неправильный....

ну напиши правильный...

как быстрее всего найти два удалённых смежных блока?

-------

Никак.

Потому как

- если блоки фиксированной длинны, то без разницы смежные они или нет

- если блоки переменной длины - в момент освобождения должны склеиваться

если блоки переменной длины - в момент освобождения должны склеиваться

Вот бери клей

0..15

120..127

так это уже будет таблица использованных блоков

----------------

Это таки таблица где свободные блоки помечены 000 и порядковый номер(индекс в массиве) однозначно определяет смещение от общей выбранной точки до начала блока.

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

Вот бери клей

--------

А откуда взято что они смежные?

Ну да пустяки - китайца с ножницами и клеем - посадишь - будет клеить...

А откуда взято что они смежные?

Из твоего определения - "если блоки переменной длины - в момент освобождения должны склеиваться"

Это таки таблица где свободные блоки помечены 000

И нафига мне такая громадная таблица для всех используемых блоков?

Из твоего определения -

-----------

В моем определении сказано - если - смежные - там где кончается один - начинается другой.

Как по твоим цифрькам определить смежность? А то у меня одна из возможностей определить смежность как нахождение на следующей плоскости того же цилиндра да еще с фиксированным сдвигом.

А две твои таблицы - по свободным и по занятым - при том же объеме будут меньше?

В моем определении сказано - если - смежные - там где кончается один - начинается другой.

А ты случаем не забыл это определение написать?

А то у меня одна из возможностей определить смежность как нахождение на следующей плоскости того же цилиндра да еще с фиксированным сдвигом.

Ну да, если пустую бутылку от столичной обвернуть hex дампом файла, то возможно что то похожее и получится.

А две твои таблицы - по свободным и по занятым

Откуда взялось две таблицы? Нужно только одна со свободными блоками.

если пустую бутылку

------

А если полную?

Цилиндром со времен ЕС ЭВМ называлось все находящееся по головками в текущем положении.

Ну да, чистые софтовики этого не знают - все столичной меряют... а по гермашке - ужО выпитой...

Цилиндром со времен ЕС ЭВМ называлось все находящееся по головками в текущем положении.

Ну так тонко и намекаю, что до такого определения цилиндра можно дойти только по ужО выпитой и не раз.

Но похоже все идеи по делу уже закончились. Ну ладно, будет пока неоптимальное решение.

Нужно только одна со свободными блоками.

-------

как обычно - либо полная информация и нормальные решения.

либо частичная и решение частное (а-ля как нибудь)

Но похоже все идеи по делу уже закончились.

----------

задачу полностью определи - может что-то добавится.

либо полная информация и нормальные решения.

У меня такое чувство что ты забрался в раковину и никак не хочешь оттуда вылезти

Только какие то постулаты. Либо только фиксированные блоки либо только таблица обо всех блоках.

Ну вот пишу я миллион записей и ничего не удаляю, на кой мне информация о занятых блоках?

Тем более, что решение было и достаточно простое, раз не запомнилось. Но всё вертелось вокруг того, что размер блоков был кратен степени двойки.

задачу полностью определи

да не знаю что еще добавить, вроде уже всё написано.

Ну вот маленькая часть:

Есть список блоков в файле длина которых кратна степени двойки, соответственно есть начало блока Х и его длина L.

Появляется некий новый блок из того же файла с началом блока Х1 и длиной L1.

Если Х1+L1 = Х или Х+L = Х1, то блоки смежные и их можно объединить.

Ограничения: список блоков находится на диске (в памяти может не поместится), список блоков отсортирован по длине блоков.

Хочется иметь красивый алгоритм поиска смежных блоков. Что помню - это был побочный эффект организации списка блоков.

вроде уже всё написано

-------

Рамазано по постам, что-то учитывается, что опущено.

надо собрать в кучку

Надо обосновать отказ от предложенных вариантов.

Появляется некий новый блок из того же файла

-=-----

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

То, что Ты сам,Я или кто-то еще имеет какое-то свое понимание - не важно - опиши детали.

Х1+L1 = Х или Х+L = Х1

-------

Ну так у тебя написно - проверить текущий (Х1) на "смежность" с предыдущим и следующим.

список блоков отсортирован по длине блоков.

-------

Ну и как ты собираешься искать предыдущий и следующий?

Либо сортировка по Х, либо пороход по списку с выбором пары

побочный эффект организации списка

------

Списка или массива представления списка?

В первом случае у тебя только гарантия сортировки по длине, без информации об положении элементов списка.

Во втором у тебя список остается как был, но элементы можно физически упорядочить по возрастанию Х.

Его выбрали произвольно, с перекрытием других блоков? Его дописали? Начало? средина? Конец? Перехлест имевшихся блоков?

Перехлёст и перекрытие блоков абсолютно невозможно. В блоках же какая то инфа записана.

Да и вообще какая разница откуда он появляется? Если так интересно - его удалили.

не важно - опиши детали.

появляется проблема - нужно ли описывать, что земля не стоит на трёх китах?

Ну так у тебя написано

сам же просишь опиши детали, вот это и важные детали, а то опять цилиндр приплетёшь.

Ну и как ты собираешься искать предыдущий и следующий?

ну это и есть задачка....

Либо А, либо Б

Так не бывает, вполне может быть и С. Так это это чисто твое персональное мнение.

Например, считаем минимальный размер блока 16 байт, тогда все блоки в списке можно представить в двоичном виде

0  0  1  0  0  1  1   1   0    0   1    1000
0,16,32,48,64,80,96,112,128, 144,160, 176 -> адрес

Здесь 3 блока длиной 16,48 и 32 байта, по адресам 32, 80, 160

Тоже самое но без пробелов

001001110011000

добавляем теперь блок в 32 байта, по адресу 48

001111110011000

сразу видно, что с адреса 32 появился большой блок в 6*16=96 байт

физически упорядочить по возрастанию Х.

Всё информация записана в файле, создать что то разумное еще можно, но вторичная сортировка никак невозможна.

это и есть задачка

------

Не-е, это не задачка - у тебя просто нет этой информации

минимальный размер блока 16 байт

-------

256 - не хочешь из-за большой таблицы.

Здесь 3 блока длиной ... добавляем теперь блок в 32 байта, по адресу 48

------

У тебя выше блок определен как 16 байт.

32 байта блоке быть не может - используй другой термин. Пусть будет - сегмент - добавил сегмент из двух блоков.

Что у тебя должно получится в списке? Таблицу ( не список ) занятых/свободных блоков Я вижу.

Остаются три 4 ранее определенных сегмента?

Или их надо конвертирвать в два? В смысле - три - слипаются?

Сегмент удаляется целиком или произвольными блоками?

вторичная сортировка никак невозможна

-------

Тогда что ты понимаешь под тем что список отсортирован?

Физически упорядоченные узлы (нах тогда список?) или логически упорядоченные ( т.е. 9 ссылается на 5 потому что 5 - описывает следующий по размеру сегмент)

Это Я к тому, что логические связки могут быть по размеру, а физический порядок - по номерам начального блока. Изменение одного не меняет второго.

В блоках же какая то инфа записана.

------

Ну мне же это не мешает что-то прописать поверх... Потому и уточняю поведение системы.

У тебя выше блок определен как 16 байт.

определен только минимальный размер блока

В смысле - три - слипаются?

А что это не естественно? Три смежных свободных сегмента можно смело пустить в дело как один.

Сегмент удаляется целиком или произвольными блоками?

Сегмент или нужен или не нужен. Но у меня есть только блоки переменной длины.

Тогда что ты понимаешь под тем что список отсортирован? (по размеру блока)

Я могу достаточно быстро найти блок зная его размер.

Любой другой поиск не предусмотрен либо может организовываться простым перебором всех элементов.

Это Я к тому, что логические связки могут быть по размеру, а физический порядок - по номерам начального блока

Ну это уже два типа сортировки одних и тех же элементов. Которая осуществляется по мере расширения списка, а не некими дополнительными проходами.

определен только минимальный размер блока

-------

Ну следующий будет 18 байт....

А что это не естественно?

--------

нет.

Три смежных свободных сегмента можно смело пустить в дело как один.

------

Вот тут ты сам себе противоречишь - либо они слипаются, либо остаются отдельными.

Ты говоришь - слипаются, но в то же время у тебя как то имеются смежные не слипшиеся.

Доопределяй.

Но у меня есть только блоки переменной длины.

-------

Т.е. имется 16 байт переменной длины.

может организовываться простым перебором всех элементов.

----------

Ну это Я тебе давно сказал - либо организация, либо перебор.

Ну это уже два типа сортировки одних и тех же элементов.

-------

Аааа... ты необходимости пересортировки боишься.

Зря. Тебе предлагается один список удовлетворяющий обоим критериям одновременно.

Ну следующий будет 18 байт....

не может быть в принципе, следующий 32.

Вот тут ты сам себе противоречишь - либо они слипаются, либо остаются отдельными.

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

У занятых блоков нет операции слияния. Только свободные имеют такое право.

Т.е. имется 16 байт переменной длины.

блоки могут быть переменной длины, 16 байт - абсолютно минимальный размер блока.

ты необходимости пересортировки боишься.

лишнее время, элемент должен вставляется в список сразу на правильную позицию.

Тебе предлагается один список удовлетворяющий обоим критериям одновременно.

где?

У занятых блоков нет операции слияния.

--------

добавляем теперь блок в 32 байта, по адресу 48

001111110011000

сразу видно, что с адреса 32 появился большой блок в 6*16=96 байт

Что-то меня слегка глючит...

элемент должен вставляется в список сразу на правильную позицию.

-------

А что тебе мешет это делать?

где?

------------

#92

Что-то меня слегка глючит...

видимо вторую строку не заметил, с начальными адресами. Самый обычный map

0  0  1  0  0  1  1   1   0    0   1
0,16,32,48,64,80,96,112,128, 144,160, 176 -> адрес

#92

ссылка была бы лучше

"Это Я к тому, что логические связки могут быть по размеру, а физический порядок - по номерам начального блока. "

И как ты собираешься это делать на диске?

И как ты собираешься это делать на диске?

------

Какая разница где?

Ну будет вместо [] fseek()... проблем то...

вместо [] fseek()

Это означает еще какая то структура дополнительно. И динамический массив не так просто сделать, опять упираемся в проблему как отдавать ненужные блоки.