Старый 25.05.2006, 12:47   #1   
Роман
 
Аватар для timex
 
Сообщений: 429
Регистрация: 04.06.2004
Возраст: 41

timex вне форума Не в сети
алгоритм поиска в записях переменной длины

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

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

известно количество записей, длина в байтах всей базы, и содержимое поля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
  Ответить с цитированием
Старый 25.05.2006, 13:44   #2   
форумец
 
Аватар для DimmaN
 
Сообщений: 1,604
Регистрация: 22.01.2004
Возраст: 24

DimmaN вне форума Не в сети
Что еще за база данных? Формат ее какой? Может это вообще CSV? Короче, как хранятся все эти значения?
  Ответить с цитированием
Старый 26.05.2006, 09:18   #3   
Роман
 
Аватар для timex
 
Сообщений: 429
Регистрация: 04.06.2004
Возраст: 41

timex вне форума Не в сети
я ж говорю:

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

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

1-е поле: три байта (bcd-кодирование)
2-е поле: первый байт - длина строки, а дальше - сама строка (макс. 60 символов, но обычно - гораздо меньше, т.к. длина переменная
3- поле: один байт



да и важно ли это?? мне ведь не листинг нужен, а только общий алгоритм
  Ответить с цитированием
Старый 26.05.2006, 11:09   #4   
Форумец
 
Аватар для MadFish
 
Сообщений: 340
Регистрация: 25.07.2002

MadFish вне форума Не в сети
Алгоритмов поиска море. Выбор зависит от главного критерия. Что важно? Размер кода(доп. памяти)или быстродействие? Если в микроконтроллере то наверное память. Тогда тупой брутфорс.
  Ответить с цитированием
Старый 26.05.2006, 12:00   #5   
Форумец
 
Аватар для Zhenka
 
Сообщений: 578
Регистрация: 16.11.2004

Zhenka вне форума Не в сети
В том-то и дело, что для записей разной длинны, даже отсортированных, подойдет только метод последовательного поиска. Для быстрого поиска нужна именно одинаковая длинна. В этом случае можно применить методы бинарного поиска и ускоренной сортировки. А почему бы не создать базу такого типа:
поле1 - упорядоченные записи фиксированной длины. тип - целое. по нему и осуществляется поиск
поле2 - фиксированной длинны -> ссылка ка текстовое поле (в другой области данных, произвольной длинны) + собственно длинна.
поле3 - целое число (1 байт). его тоже нужно найти. Или это поле также в другой области данных.
В этом случае размер базы вырастет незначительно, но алгоритмов поиска + сортировки, вставки, удаления и т.д. можно придумать немало. Есть книжица Г.Шилдт Теория и практика C++ там целая глава про связанные списки, бинарные деревья, поиск, вставку и т.д.т.п.
  Ответить с цитированием
Старый 26.05.2006, 12:08   #6   
Форумец
 
Аватар для Zhenka
 
Сообщений: 578
Регистрация: 16.11.2004

Zhenka вне форума Не в сети
Да, ещё одно дополнение. Насколько я знаю, "настоящие" СУБД не производят поиск непосредственно в данных. Для этого создаются индексные ключи (файлы) которые как раз содержат отсортированную инфу о данных (ключевые поля как поле1)+ ссылки на соответствующие записи в БД. Изменение данных происходит одновременно с изменением инфы во всех активных индексных ключах. Этим занимается сама СУБД. Вот так.
  Ответить с цитированием
Старый 26.05.2006, 12:15   #7   
Роман
 
Аватар для timex
 
Сообщений: 429
Регистрация: 04.06.2004
Возраст: 41

timex вне форума Не в сети
Zhenka, блин, а идея со ссылками хорошая! надо будет обдумать её!

а изменения базы будут происходить где-то снаружи. внутри флехи она read-only.
  Ответить с цитированием
Старый 26.05.2006, 12:16   #8   
Форумец
 
Аватар для Zhenka
 
Сообщений: 578
Регистрация: 16.11.2004

Zhenka вне форума Не в сети
Тем более, если снаружи. Программа создания данных усложнится, но писать-то ее один раз... А для юзера, все это будет совершенно незаметно. Успехов.
  Ответить с цитированием
Старый 29.05.2006, 15:19   #9   
Форумец
 
Аватар для MadFish
 
Сообщений: 340
Регистрация: 25.07.2002

MadFish вне форума Не в сети
Но позвольте Zhenka, это ведь тривиальный поиск совпадения строк, и все быстрые алгоритмы аля ДКА и Кнута-Морриса-Прата итд применимы. Тока им память дополнительная нужна... А про индексирование это правильный подход, но поддержание корректности индексов и сама функция индексирования это оч. одельныя тема...
  Ответить с цитированием
Старый 30.05.2006, 11:09   #10   
Форумец
 
Аватар для Zhenka
 
Сообщений: 578
Регистрация: 16.11.2004

Zhenka вне форума Не в сети
Да, но искать можно по-разному... Даже простой поиск совпадений, но начатый с середины упорядоченного массива уменьшит время поиска в среднем вдвое, не говоря уже о каких-то крутых алгоритмах. Но чтобы знать её (середину) нужно знать размер записи, поэтому и предлагаю применить ключевые поля известного размера. А на счет памяти не совсем понимаю, если применить алгоритм без рекурсии и запоминания большого количества промежуточных значений, куда она денется ?
  Ответить с цитированием
Поиск в теме: 


Опции темы

Быстрый переход:

  Ваши права в разделе
Вы не можете создавать новые темы
Вы не можете отвечать в темах
Вы не можете прикреплять вложения
Вы не можете редактировать свои сообщения
BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.


Powered by vBulletin® Version 3.8.7
Copyright ©2000 - 2024, Jelsoft Enterprises Ltd. Перевод: zCarot
Support by DrIQ & Netwind