Если это ваш первый визит, рекомендуем почитать справку по форуму. Для размещения своих сообщений необходимо зарегистрироваться. Для просмотра сообщений выберите раздел. |
алгоритм поиска в записях переменной длины |
Философия, технологии, алгоритмы! |
|
Опции темы |
25.05.2006, 12:47 | #1 |
Роман
Сообщений: 429
Регистрация: 04.06.2004
Возраст: 41
Не в сети |
алгоритм поиска в записях переменной длины
Подскажите, а существует алгоритм поиска в базе данных, у которой длина одного поля в каждой записи имеет разную длину. Т.е. длина каждой записи - разная
Нужно для реализации в микроконтроллере, а сама база хранится во флешке, ёмкость которой ограничена. известно количество записей, длина в байтах всей базы, и содержимое поля1 - вводимое юзером. вот база: поле1 - упорядоченные записи фиксированной длины. тип - целое. по нему и осуществляется поиск поле2 - текстовое поле переменной длины. его и нужно найти. длина его для каждой записи известна, и может хранится перед этим полем или в самом начале записи поле3 - целое число (1 байт). его тоже нужно найти. если необходимо, то можно добавить ещё и ID - порядковый номер записи, начиная с 1. ну, естественно, длина записи также известна и может храниться, например, в начале каждой записи. поле1 поле2 поле3 ----- ----- ----- 394000 тексттексттексттекст 1 394043 тексттекст 1 394087 текст 1 450034 тексттексттексттексттексттекст 1 450120 тексттекст 2 634004 текст 2 646445 текст 1 664503 тексттекст 2 673094 тексттексттексттекст 1 684933 текст 2 и т.д. всего записей - порядка 45000. допустим нужно найти запись, у которой первое поле = 394087 как? если что - мой icq 290511085 |
26.05.2006, 09:18 | #3 |
Роман
Сообщений: 429
Регистрация: 04.06.2004
Возраст: 41
Не в сети |
я ж говорю:
Нужно для реализации в микроконтроллере, а сама база хранится во флешке, ёмкость которой ограничена. Т.е. формат у неё собственный. как именно хранятся значения - ещё не определил. Ну например, запись может выглядеть так: 1-е поле: три байта (bcd-кодирование) 2-е поле: первый байт - длина строки, а дальше - сама строка (макс. 60 символов, но обычно - гораздо меньше, т.к. длина переменная 3- поле: один байт да и важно ли это?? мне ведь не листинг нужен, а только общий алгоритм |
26.05.2006, 12:00 | #5 |
Форумец
Сообщений: 578
Регистрация: 16.11.2004
Не в сети |
В том-то и дело, что для записей разной длинны, даже отсортированных, подойдет только метод последовательного поиска. Для быстрого поиска нужна именно одинаковая длинна. В этом случае можно применить методы бинарного поиска и ускоренной сортировки. А почему бы не создать базу такого типа:
поле1 - упорядоченные записи фиксированной длины. тип - целое. по нему и осуществляется поиск поле2 - фиксированной длинны -> ссылка ка текстовое поле (в другой области данных, произвольной длинны) + собственно длинна. поле3 - целое число (1 байт). его тоже нужно найти. Или это поле также в другой области данных. В этом случае размер базы вырастет незначительно, но алгоритмов поиска + сортировки, вставки, удаления и т.д. можно придумать немало. Есть книжица Г.Шилдт Теория и практика C++ там целая глава про связанные списки, бинарные деревья, поиск, вставку и т.д.т.п. |
26.05.2006, 12:08 | #6 |
Форумец
Сообщений: 578
Регистрация: 16.11.2004
Не в сети |
Да, ещё одно дополнение. Насколько я знаю, "настоящие" СУБД не производят поиск непосредственно в данных. Для этого создаются индексные ключи (файлы) которые как раз содержат отсортированную инфу о данных (ключевые поля как поле1)+ ссылки на соответствующие записи в БД. Изменение данных происходит одновременно с изменением инфы во всех активных индексных ключах. Этим занимается сама СУБД. Вот так.
|
29.05.2006, 15:19 | #9 |
Форумец
Сообщений: 340
Регистрация: 25.07.2002
Не в сети |
Но позвольте Zhenka, это ведь тривиальный поиск совпадения строк, и все быстрые алгоритмы аля ДКА и Кнута-Морриса-Прата итд применимы. Тока им память дополнительная нужна... А про индексирование это правильный подход, но поддержание корректности индексов и сама функция индексирования это оч. одельныя тема...
|
30.05.2006, 11:09 | #10 |
Форумец
Сообщений: 578
Регистрация: 16.11.2004
Не в сети |
Да, но искать можно по-разному... Даже простой поиск совпадений, но начатый с середины упорядоченного массива уменьшит время поиска в среднем вдвое, не говоря уже о каких-то крутых алгоритмах. Но чтобы знать её (середину) нужно знать размер записи, поэтому и предлагаю применить ключевые поля известного размера. А на счет памяти не совсем понимаю, если применить алгоритм без рекурсии и запоминания большого количества промежуточных значений, куда она денется ?
|