| Форумы
ЧАТ |
Орешник |
|
| Форумы -» | Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / RSDN.ORG |
|
| ||
|
|
Новости |
Поиск |
FAQ |
Статьи |
Книги |
Новости VCL
| | Форумы ЧАТ |
Орешник |
|
| |||
| |||
| |||
« предыдущая ветвь | форум | следующая ветвь »
множественная выборка из массива собственной базы данных [D6, WinXP]
Login_Andrew © (2003-01-10 13:13:00)Есть собственная база данных, с использованием типизированного файла.
Я столкнулся с весьма непростой задачей, которая состоит в том, чтобы сделать выборку по базе данных всех записей, соответствующую заданному вначале критерию, прямо внутри файла!
Например, база данных (типизированный файл типа record) с записями "aa"(№0), ...."abing"(№256), "btri"(№257),..... "cting"(№4567), "ctt"(№4568), ....."ddd"(№7000), "dding"(№7001), ....."ddss"(№20045), "hhh"(20046), ......"hhhhing"(№40567)....... и т.д. ....№-ная запись(№50000).
Критерий выборки - выбрать все записи, которые включают такие части слова, как "ing" или "dd" или "dding", например сделать выборку для слова "adding".
Конечным результатом должен быть неповторяющийся список, который бы включал записи с ключевыми словами "abing", "cting", "ddd", "dding", "ddss", как выборка для слова "adding".
Простая выборка, применяя последовательный цикл, например, for do или while do, дает результат, но при общем числе записей в базе данных ~ 50 000 подобный способ и долог и не весьма эффективен.
Желательно практический пример.
Login_Andrew (2003-01-10 18:52:00) [1]для Digitman
А как можно загрузить НД из моего файла через св-во Data
Пожалуйста, приведите конкретный код.
Login_Andrew (2003-01-10 17:59:00) [2]Извините для всех!
Советов очень много, но реально, может кто-либо связать мой конкретный случай со своим видением проблемы и привести конкретный пример кода?
Еще раз привожу рассматриваемый фрагмент (подкорректированный):
type
TWordsRec = record
word: string[20];
.... - поле дополнительной записи
end;
.................
var
Formmain: TFormmain;
mF: file of TWordsRec;
mr: TWordsRec;
FilePath: string; - путь к файлу базы данных
count: integer; - число записей в базе данных (~ 50 000)
....................
процедура, в которой организован поиск
var word: string;
strList: TStringList;
nd: integer;
begin
AssignFile(mF, FilePath+ "database.dat");
Reset(mF);
strList:= TStringList.Create;
try
strList.Sorted:= true;
strList.Duplicates:= dupIgnore;
for nd:= 0 to count- 1 do
begin
Seek(mF, nd);
BlockRead(mF, mr, 1);
if сравнение поля word записи mr.word с эталоном then strList.Add(mr.word);
(если хотя бы часть слова входит в состав эталонного слова, то занести ее во временный список)
end;
ListBox1.Items.Assign(strList); - основной итоговый список, полученных слов!
finally
strList.Free;
end;
CloseFile(mF);
end;
Digitman (2003-01-10 17:58:00) [3]да там чуть ли не все методы - виртуальные либо абстрактные) ... на то и шаблон
читай в хэлпе назначение интересующих тебя методов, перекрывай их в своем наследнике и реализуй то, что ожидает от НД внешний код, вызывающий тот или иной метод твоего объекта-наследника
Login_Andrew (2003-01-10 17:48:00) [4]для Digitman
Как можно практически связать TDataSet с моим типом файла базы данных? Его я указал выше.
Digitman (2003-01-10 17:48:00) [5]
> А какое максимальное количество записей может иметь TStringList!
Теоретически - 2147483647. Практически - зависит от наличия своб.ресурсов процесса и системы в целом.
> Где-то я читал, что есть ограничение для него только ~
> 16 000 записей и все
Чушь полная. Теор.органичение лишь макс.значением, которое способна хранить переменная Integer-типа.
Другой вопрос, что никакой программер (думающий головой, а не иным местом) такое бешеное число строк в стринг-листе хранить не додумается.
> А метод Find можно прописать так, чтобы он производил поиск
> по части слова.
Можно. А зачем ? Ты ж сам сказал, что не хочешь грузить НД целиком в память ?
Игорь Шевченко (2003-01-10 17:41:00) [6]Login_Andrew (10.01.03 17:17)
Пример:
function THSFileProcessor.ReadFile(AName: String): Boolean;
var
Dummy : DWORD;
FhMappedFile : Integer;
begin
Result := false;
FhFile := CreateFile (PChar(AName), GENERIC_READ,
FILE_SHARE_READ OR FILE_SHARE_WRITE,
nil, OPEN_EXISTING, 0, 0);
if (FhFile = Integer(INVALID_HANDLE_VALUE)) then
Exit;
FBufLen := GetFileSize(FhFile, @Dummy);
FActionCount := 1; { Необходимо закрыть файл }
FhMappedFile := CreateFileMapping (FhFile, nil, PAGE_READONLY, 0, 0, nil );
if (FhMappedFile = 0) then
Exit;
FBuffer := MapViewOfFile (FhMappedFile, FILE_MAP_READ, 0, 0, 0 );
CloseHandle (FhMappedFile);
if ( FBuffer = nil ) then
Exit;
FActionCount := 2; { Необходимо удалить проекцию файла в память }
Result := true;
end;
После этого, переменная FBuffer содержит адрес памяти, в которой находится содержимое твоего файла. Полностью. При этом, сам файл в память читается системой только по мере необходимости.
А найти и перебрать в памяти требуемые ключи, я полагаю, труда не составит.
procedure THSFileProcessor.ClearOldMapping;
begin
if FActionCount = 2 then begin
UnmapViewOfFile (FBuffer);
Dec(FActionCount);
end;
if FActionCount = 1 then
CloseHandle (FhFile);
end;
и часть класса:
{ Поддержка проекции файла в память }
FBuffer: Pointer;
FhFile : Integer;
FActionCount : Integer;
Игорь Шевченко (2003-01-10 17:35:00) [7]Login_Andrew (10.01.03 17:17)
Виноват, не прочитал внимательно вопрос. Бинарный поиск не применим вообще, так как тебе надо искать совпадение не всего ключа, а его части, причем, часть может ноходиться не в начале ключа, а в середине или в конце. Тогда - последовательный перебор будет самым быстрым и легким способом.
Про Memory Mapped Files:
win32.hlp - CreateFileMapping, MapViewOfFile
Login_Andrew (2003-01-10 17:33:00) [8]для Digitman дополнение
А какое максимальное количество записей может иметь TStringList!
Где-то я читал, что есть ограничение для него только ~ 16 000 записей и все, а как же тогда быть с остальными до ~ 50 000?
А метод Find можно прописать так, чтобы он производил поиск по части слова.
Anatoly Podgoretsky
А как можно по другому добавлять в strList.
Digitman (2003-01-10 17:26:00) [9]
> Так все таки, нужен еще какой-либо "драйвер" (или еще что-либо
> сопутствующее) для TDataSet при переносе БД, допустим на
> другой компьтер?
Абсолютно никакого)
Еще раз повторюсь - реализовав идею с наследником TDataSet ты получаешь отличную возможность использовать в кач-ве виз/невиз объектов НД-менеджмента любые компоненты/контролы, "понимающие" что такое есть класс TDataSet
> Можно ли подробнее о Memory Mapped File?
Это не моя идея. Это - к Игорю.
Login_Andrew (2003-01-10 17:17:00) [10]для Digitman
Я и имел ввиду, что бинарный поиск применен у меня.
Видимо, написал не совсем понятно.
Так все таки, нужен еще какой-либо "драйвер" (или еще что-либо сопутствующее) для TDataSet при переносе БД, допустим на другой компьтер?
Записи уже действительно отсортированы на этапе их записи в файл базы данных.
Можно ли подробнее о Memory Mapped File? Файл действительно только для чтения в конкретном случае.
Вы могли привести практический пример предлагаемого Вами кода.
для Игоря Шевченко
Не понял Вашей идеи.
Я пробовал нечто подобное, но ничего путного не получил, после первого найденного слова далее просто идет перебор записей друг за другом, как буд-то и нет бинарного поиска.
Вы можете привести пример Вашего совета.
Digitman (2003-01-10 16:45:00) [11]Или , если файл уже сортирован по ключу, ищи методом половинного деления. За образец возьми реализацию TStringList.Find()
Digitman (2003-01-10 16:38:00) [12]
> Вашей идеи что-то наподобие алгоритмов бинарного поиска(без
> привязки к BDE, TDataSet или подобному), но применительно
> к данной задаче, Вы не могли бы посоветовать
Бинарный поиск - это вообще-то не моя идея, а твоя)
И BDE здесь ни при чем совершенно - класс TDataSet знать ничего не знает ни о каких BDE, это по сути - некий унифицированный шаблон "драйвера" для унифицированного управления неким абстрактным набором данных, конкретная контейнерная реализация которого м.б. любой, в т.ч. и структурированный файл.
Я вообще не советую пытаться реализовать в таком вот контексте бин.поиск и хэширование. Ибо ничего путного из этой затеи не выйдет - где-то нужно будет хранить словарь, а это повлечет за собой изменение/усложнение структуры твоего файла. И разрастаться он у тебя будет жутко после генерации/обновления словаря всякий раз при модификации записей, и "тормоза" будут еще больше.
Индексы же - своего рода тоже "словари", но их преимущество именно в БД неоспоримо : индексы как минимум хранят инф-цию о физ.местоположении записей, считав однократно индекс в память ты сможешь оч.быстро переместиться к нужной записи в файле, выполнив "точный" seek() на нее. Или не выполнять ненужного перемещения вообще, если индекс не удовлетворяет условиям поиска/фильтрации записи
Игорь Шевченко (2003-01-10 16:28:00) [13]Login_Andrew (10.01.03 16:07)
Даже с хешем это будет не очень удобно, так как подобрать оптимальную хэш функцию будет не очень-то легко. Но: если ты пользуешься двоичным поиском, значит, файл отсортирован. Тогда найди двоичным поиском первую нужную запись, пройди назад, до тех пор, пока значение ключа будет совпадать, и иди вперед, до смены ключа, выбирая записи - вот и множественная выборка.
Hint: рекомендую использовать Memory Mapped File, если файл только для чтения.
Dms (2003-01-10 16:28:00) [14]если интересно, то купи том Д Кнута "Сортировка и поиск" из серии "Искусство программирования", там рассмотрена проблема множественной выборки (кстати, по-моему, хеширование в этом случае необязательно)
Anatoly Podgoretsky (2003-01-10 16:26:00) [15]По крайней мере лисшнее присваивание и копирование cpt:= mr.word; это и так строка
Кроие того правильнее весь файл сразу одним махом загнать в память и уже по нему вести поиск, это всего лишь 210 000 байт.
Это не все возмоэности по оптимизации, например добавлять в strList можно по другому. Да и время на сортировку его тратится не малое.
Возможно и в функции сравнения тоже не оптимальные алгоритмы
Не зря говорять основной источник повышения производительности это алгоритмы
Login_Andrew (2003-01-10 16:07:00) [16]для Digitman
А все таки, если отойти от Вашей идеи что-то наподобие алгоритмов бинарного поиска(без привязки к BDE, TDataSet или подобному), но применительно к данной задаче, Вы не могли бы посоветовать?
Мне в интернете попадались статьи о хешировании, но только статьи и ни единого практического примера, как это реально прописать в Delphi. Насколько я мог понять из этих статей там как-то можно реализовать множественную выборку из базы данных.
Login_Andrew (2003-01-10 15:55:00) [17]Anatoly Podgoretsky
Извините, если мой ответ показался Вам не корректным.
Login_Andrew (2003-01-10 15:53:00) [18]type
TWordsRec = record
word: string[20];
end;
.................
var
Formmain: TFormmain;
mF: file of TWordsRec;
mr: TWordsRec;
....................
процедура поиска
varword, cpt: string;
strList: TStringList;
nd: integer;
begin
AssignFile(mF, FilePath+ "database.dat");
Reset(mF);
strList:= TStringList.Create;
try
strList.Sorted:= true;
strList.Duplicates:= dupIgnore;
for nd:= 0 to count- 1 do
begin
Seek(mF, nd);
BlockRead(mF, mr, 1);
cpt:= mr.word;
if сравнение cpt с эталоном then strList.Add(cpt);
end;
ListBox1.Items.Assign(strList);
finally
strList.Free;
end;
CloseFile(mF);
end;
Anatoly Podgoretsky (2003-01-10 15:53:00) [19]Сообственно мне - никакой
Login_Andrew (2003-01-10 15:39:00) [20]Anatoly Podgoretsky
Какая точная информация необходима?
Нет проблем.
| |
Страницы: 