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

как организовать быстрый поиск в бинарном файле, размеченом как файловая система.
я использую для обозначения записей строки - имена, имитируя файловую систему.
сейчас я просто гоняю финукции по файловым спискам и сравниваю строки названия.
всё работает но я задаюсь вопросом.
зачем каждый раз при поиске сравнивать искомую строку-имя
с почти что постоянными записями в файле.
например я ищё вложенную таблицу word2,
она находится в корне но до неё от корня ещё нескролько таблиц.
имена у которых такиеже лаконичные и подчиняются правилам.
может быть есть какой то другой способ быстрого поиска.
я не хочу изобретать велик.
я вот думаю может вычислять отпечаток начала строки, например первые 10 - 15 символов.
отпечаток хранить в виде double числа в заголовке записи, (заговолоко записи и имя хранятся отдельно)
затем при поиске вычислять отпечаток для искомого и искать сначала по нему
а затем принимать решение сравнивать ли строки (при этом считывая их выделяя память и удаляя).
помоему это должно несколько ускорить поиск.
так как сокращает расходы на выделение памяти и операции сравнивания n символов.
(чур моя идея)
может быть чтото подобное уже сделано и можно поглядеть?
где можно почитать про кеширование в современных os и СУБД.
спасибо

Добавлено 21.12.05, 18:59
и ещё мне интересно, почему в этом форуме нет css.
там ведь 8 килобай стилей идёт.
ведь даже не реклама а просто левый текст который даже моя опера ни как не закеширует.

Хотя бы интерфейсы предоставили. А если представить вашу ФС через стандартные контейнеры STL, так задача вообще упрощается

Ну уж очень много инфы... Если речь идёт о поиске в бинарном файле структурированном под ФС файле, то в заголовке этого файла, должна быть таблица адресов, всех элементов бинарного массива, поиск нужно делать в ней а, не в самом файле.
Например:
Имя элемента, начальная позиция в бинарии, размер элемента. Вот и всё.
Быстренько грузишь в память заголовок, и работаешь с ним. Или просто ищёшь по заголовку.

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

Добавлено 21.12.05, 20:45
MaIron

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

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

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

Цитата katariona @ 21.12.05, 18:49

принимать решение сравнивать ли строки (при этом считывая их выделяя память и удаляя)

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

Цитата katariona @ 21.12.05, 20:24

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

Берешь первые 4 символа и рассматриваешь их как 32-разрядное целое. Совпало с первыми 4 символами искомого - сравниваешь остаток, не совпало - переходишь к следующему элементу.

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

Цитата

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

Сделай ее не на STL.

1. на STL она сделана не мной, и видимо STL выбрана для скорости реализации и контроля алгоритмов.
2. ограничения на размер имени пока нет, иногда и само имя служит информационным полем.
3. а что за автоматические переменные? это не котороые сами выделяют память и удаляют?
4. trainer я об этом и говорила, только брать четыре символа и представлять их как лонг число не выгодно,
потому что симоволов в лонг число можно засунуть больше, потому используется 2 ограниченных диапазона символов (смотри выше).
можно в лонг засунуть штук 5 или 6, вот и нужен алгоритм сжатия.
5. почему будут тормозить операции чтения с диска?
читаться то будут столько сколько нужно. узлы 40-40 байт и имена(+ сами данные если они подходят) между чтениям переходы по файлу.
не должно быть сильной разницы между 10 метрами и 1000 метрами.
только линейная разница зависящая от количества информационных объектов, а не от их размера.
6. когда размер файла достигнет гига я надеюсь переташить её на физический уровень диска и заказать оптимизацию готовых алгоритмов на асме.
7. хочу обсуждать другие варианты, хочу понять стоит ли развивать эту идею, или воспользоваться готовым, хочу перенять чужой опыт.

и css ещё не приделали.

Сообщение отредактировано: katariona - 22.12.05, 06:34

Цитата katariona @ 22.12.05, 06:21

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

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

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

Конечно меня можно критиковать, но вариант с файлом отформатированным под ФС это однозначно не лучший вариант, уже лишь по тому что это медленный вариант.
А вариант с перебором внутри файла это вообще глупость ! Представляете нам надо взять элемент который стоит в конце гигабайтной последовательность, нам нужно считать последовательно весе записи файла, пока не будет найдено совпадение ! Это ужас ! А если например произойдёт повреждение при записи данных файл. То всё слетит !

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

Представляете у меня два жёстких диска общей ёмкостью 0,5Тб и около 20 000 000 фрагментированных файлов, мне нужно открыть файл 19 999 999. Для этого по методике katariona мне придётся считать из разных мест диска 19 999 998 заголовков файла сравнить каждый с критерием и вывести нужный файл.
На этом комп просто повиснет.

Если по стандартной методике с заголовком: Условия те же но все данные о элементах храниться в файле смещений размером в 20 мегабайт. Загружаем файл в память < 0,1 сек. И ищем нужный элемент < 2 сек. Всё очень быстро надёжно и красиво. Даже если этот файл утерян, разрушен. То методом вашего любимого поиска обходом, создаём новую таблицу смещений в соответствии с реальной структурой данных.

во-первых, если это важно, это не комерческий проект и не заказ. просто совместный проект по интересу.
во-вторых не имеет значения с файлом, памятью или диском происходят действия.
сейчас просто делаем тестовый вариант с последующим переносом на разные архитектуры.
другими словами делаем логический уровень фс надстроенный над простым бинарным файлом.
мы хотим универсально сделать.
где можно там в файле система будет хранить данные, где можно прямо с диском работать там с диском, а где и с потоками или памятью.
система и так получится ресурсоёмкой, а тут ещё переборы символов в строках.
тут просто нужно отделиться от памяти, дисков и тд и преставить последовательности строк, среди которых надо найти нужную.
в предложении MaIron опять присутствует на первом месте перебор строк. только всё теперь лежит в памяти памяти. а если данных много а памяти чуть чуть. если речь идёт о хранении таблицы в памяти во время работы программы то это нам не подходит - это ограничение.
на http://www.INTUIT.ru я нашла статью о архитектуре ФС.
там описываются 2 алгоритма поиска файлов. первый простой перебор, второй использование хеш-таблиц и даётся
ссылка на третий способ аналогичный поиску в СУБД. мой способо упрошённый аналог с хеш таблицами.
только исключается его недостатоки. хеш не будет считать для всего имени а только для части.
и это будет не хеш отпечаток строки, который будет уникальным.
и мой поиск будет предисловием для простого поиска.
в общем то всё теперь понятно.
я думаю, что надо будет предусмотреть возможность использования таблиц заголовков,
для этого будет достаточно переписать алгоритм дефрагментации, и после неё в начале файла будет вся таблица.
и в-третьих, я не видела такого каталога в котором храниться 20 000 000 файлов.
и думаю не увижу. для этого есть вложенные директории. и любая фс помоему призадумается при обработке такого количества данных.
кстати насколько мне известно в некоторых ФС есть ограничения на количество файлов.

Цитата katariona @ 22.12.05, 06:21

trainer я об этом и говорила, только брать четыре символа и представлять их как лонг число не выгодно

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

Цитата katariona @ 22.12.05, 06:21

почему будут тормозить операции чтения с диска?
читаться то будут столько сколько нужно. узлы 40-40 байт и имена(+ сами данные если они подходят) между чтениям переходы по файлу

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

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

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

Сообщение отредактировано: katariona - 22.12.05, 11:20

Цитата katariona @ 22.12.05, 11:09

опять же говорю что нет ни какого диска

"когда размер файла дойдёт до гига и более", диск появится. Хотя бы в виде swap-файла.

Цитата katariona @ 22.12.05, 11:09

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

А зачем обратимый? Ты собираешься из результата хеш-функции восстанавливать имя? А зачем? И куда уж легче - сравнить два 16- или 32-битовых числа?
Чем больше байт загонишь в хеш, тем более точным получится индекс(при правильной функции) - меньше строк сравнивать придется.