Проблема с поисом незарезервированых идентификаторов.

← →
Master Kolyan (2004-09-14 15:43) [0]

Причём проблема не такая простая: надо найти минимальный идентификатор(число) если дан массив, в котором каждому номер(идентификатор) а значение допустим true\false - наличие идентификатора. И ещё одно условие - поиск не должен быть пойском как таковым, мне необходима так сказать гигангтская скорость такого процесса.

Мне это нужно для хорошей организации работы программы с памятью компа. Далее написано как я собираюсь работать с памятью на ЖД:

Мне значит необходимо хранить данные в виде кучи фрагментов по 2048 Байт скажем. Создаём файл в который помещаем в произвольном порядке все эти фрагменты, и создаём другой файл с идентификаторами - каждому идентификатору соответствует позиция фрагмента данных в первом файле начиная с начала. Во втором файле хранятся только указатели, там могут быть и пустые указатели - они говорят о том, что фрагмента данных с таким идентификатором нету (идентификатор = позиции указателя во втором файле). Второй файл занимает совсем немного места на ЖД по сравнению с файлом данных. Далее объясняю как работать с фрагментами данных:
1) добавление фрагмента: просто добавляем в конец первого файла 2048 байт. Проблема тут в том, чтобы найти среди этой кучи пустой идентификатор, ну допустим нашли, и повесили на него нужный указатель.
2) удаление: тут проще - зануляем указатель в первом файле, копируем фрагмент данных с конца второго файла на место удаляемого(вот почему размер фрагментов данных одинаковы), изменяем указатель свежеперенесенного фрагмента на указатель затертого(удаленного).
3)чтение: ну тут все просто: смотрим указатель в первом файле и читаем по нему данные из второго файла.
4)запись(изменение): то же самое: смотрим указатель в первом файле и изменяем по нему данные во втором файле.

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

я могу создать массив для хранения освободившихся идентификаторов в порядке возрастания. Но если их будет слишком много? Для того, чтобы добавить освободившийся ID скажем в начало массива прийдётся сдвигать все впереди стоящие байты, чтобы освободить место для этого ID. - это неэффективно

А теперь главный вопрос, как сделать так, чтобы и быстро и правильно и эффективно?

...Пасиб!!!

← →
TUser © (2004-09-14 15:51) [1]

Я не очень точно вник, но для быстрой работы обычно делают деревья (упорядоченные). Там ты быстрой найдешь минимальный незанятый идентификатор, если хранить true/false на всех уровнях иерархии. При изменении флага у какого-либо ид-ра - пройдись вверх по дереву до корня и поставь если требуется соотв. флаги, а при поиске минимального свободного - иди в те ветки, где что-то свободное есть.

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

Короче - см. книги Ахо, Хопкрофх, Ульман и Кнута.

← →
Master Kolyan (2004-09-14 16:05) [2]

Это список доступных мне книг (просто уж покупать так покупать)
1)ВТ Искусство прогр-я в 3тт Т. 2 Получисленные алгоритмы (Кнут Д.Э.) Изд. 3-е
2)ВТ Искусство прогр-я в 3тт Т. 3 Сортировка и поиск (Кнут Д.Э.) Изд. 2-е
3)ВТ Введ. в теорию автоматов,языков и вычислений (Хопкрофт Дж.,Мотвани Р.,Ульман Дж.) Изд. 2-е
4)ВТ Системы баз данных Полный курс (Гарсиа-Молина Г.,Ульман Дж.Д.,Уидом Дж.)
5)ВТ Компиляторы: Принципы,технологии,инструменты (Ахо А.,Сети Р.,Ульман Дж.)
Может есть чего-нибудь знакомое.

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