множественная выборка из массива собственной базы данных

← →
Login_Andrew (2003-01-10 13:13) [0]

Есть собственная база данных, с использованием типизированного файла.
Я столкнулся с весьма непростой задачей, которая состоит в том, чтобы сделать выборку по базе данных всех записей, соответствующую заданному вначале критерию, прямо внутри файла!
Например, база данных (типизированный файл типа 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 подобный способ и долог и не весьма эффективен.
Желательно практический пример.

← →
neXt © (2003-01-10 13:27) [1]

Чтобы рещать такие задачи, нужно изменить способ хранения. Идеально, это SQL-совместимая БД (или файл к которому можно былобы обращаться как к БД), тогда более эффективное решение возможно.

← →
neXt © (2003-01-10 13:30) [2]

Можно ещё разместить данные в XML формате и тогда можно будет применять к ним операции множественной выборки XSLT, это полегче чем SQL-БД, но всётки изврат. Но просто текст лопатить кроме как циклом не выйдет.

← →
Anatoly Podgoretsky © (2003-01-10 13:38) [3]

Может у тебя цикл не оптимальный?

← →
Digitman © (2003-01-10 14:09) [4]

Напиши своего наследника TDataSet.
Для выборки по нужным тебе критериям пользуй обычные Filter/Filtered-св-ва либо обрабатывай должным образом событие OnFilterRecord()

← →
Login_Andrew (2003-01-10 15:12) [5]

Anatoly Podgoretsky
А что значит - цикл не оптимальный?
Вы можете привести пример оптимального цикла?
Вы можете набросать хотя бы простенький пример подобного решения или дать ссылку...

neXt и для Digitman
У меня собственная база данных с использованием типизированного файла и она более чем меня устраивает. В ней я применяю бинарный поиск, который в данном примере не подходит, так как дает лишь одно значение.
Может Вы можете подсказать реальный пример хеширования или иного метода?

← →
Anatoly Podgoretsky © (2003-01-10 15:17) [6]

Login_Andrew (10.01.03 15:12)
Откуда я знаю как он у тебя реализован, ты же не приводишь его.
Если не брать в расчет создание специализированного TDataSet, то проще всего загнать в TStringList, если конечно ты точно привел формат твоего файла.

Ты зочешь получить какой то квалифицированный совет и в тоже время не приводишь достаточно информации.

← →
Digitman © (2003-01-10 15:33) [7]

> собственная база данных с использованием типизированного
> файла и она более чем меня устраивает

Да на здоровье ! Никто ж не требует от тебя отказаться от собственного контейнерного формата.

> В ней я применяю бинарный поиск, который в данном примере
> не подходит, так как дает лишь одно значение.

Опять же - ничто не мешает тебе реализовать систему индексации и быстрый поиск/фильтрацию по ключу в индексе. Ведь в тех же TTable/TClientDataSet реализовано это !

Ну, не нравится тебе идея с собств.наследником TDataSet - воспользуйся готовым TClientDataSet. Он позволяет "на ходу" строить произвольные, достаточно эффективные индексы в памяти и содержит станд.методы фильтрации/сортировки/доступа к НД с использованием этих индексов. Все, что от тебя потребуется - загрузить НД из твоего файла через св-во Data, построить нужные индексы и установитьь фильтр (EditKey/SetKey/SetRange и т.п.).
Зато ты получишь полную совместимость со станд. VCL-контролами, требующими в кач-ве источника данных объект-наследник TDataSet

← →
Login_Andrew (2003-01-10 15:39) [8]

Anatoly Podgoretsky
Какая точная информация необходима?
Нет проблем.

← →
Anatoly Podgoretsky © (2003-01-10 15:53) [9]

Сообственно мне - никакой

← →
Login_Andrew (2003-01-10 15:53) [10]

type
TWordsRec = record
word: string[20];
end;
.................
var
Formmain: TFormmain;
mF: file of TWordsRec;
mr: TWordsRec;
....................

процедура поиска
var word, 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;

← →
Login_Andrew (2003-01-10 15:55) [11]

Anatoly Podgoretsky
Извините, если мой ответ показался Вам не корректным.

← →
Login_Andrew (2003-01-10 16:07) [12]

для Digitman
А все таки, если отойти от Вашей идеи что-то наподобие алгоритмов бинарного поиска(без привязки к BDE, TDataSet или подобному), но применительно к данной задаче, Вы не могли бы посоветовать?
Мне в интернете попадались статьи о хешировании, но только статьи и ни единого практического примера, как это реально прописать в Delphi. Насколько я мог понять из этих статей там как-то можно реализовать множественную выборку из базы данных.

← →
Anatoly Podgoretsky © (2003-01-10 16:26) [13]

По крайней мере лисшнее присваивание и копирование cpt:= mr.word; это и так строка
Кроие того правильнее весь файл сразу одним махом загнать в память и уже по нему вести поиск, это всего лишь 210 000 байт.
Это не все возмоэности по оптимизации, например добавлять в strList можно по другому. Да и время на сортировку его тратится не малое.
Возможно и в функции сравнения тоже не оптимальные алгоритмы

Не зря говорять основной источник повышения производительности это алгоритмы

← →
Игорь Шевченко © (2003-01-10 16:28) [14]

Login_Andrew (10.01.03 16:07)

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

Hint: рекомендую использовать Memory Mapped File, если файл только для чтения.

← →
Dms (2003-01-10 16:28) [15]

если интересно, то купи том Д Кнута "Сортировка и поиск" из серии "Искусство программирования", там рассмотрена проблема множественной выборки (кстати, по-моему, хеширование в этом случае необязательно)

← →
Digitman © (2003-01-10 16:38) [16]

> Вашей идеи что-то наподобие алгоритмов бинарного поиска(без
> привязки к BDE, TDataSet или подобному), но применительно
> к данной задаче, Вы не могли бы посоветовать

Бинарный поиск - это вообще-то не моя идея, а твоя)
И BDE здесь ни при чем совершенно - класс TDataSet знать ничего не знает ни о каких BDE, это по сути - некий унифицированный шаблон "драйвера" для унифицированного управления неким абстрактным набором данных, конкретная контейнерная реализация которого м.б. любой, в т.ч. и структурированный файл.

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

Индексы же - своего рода тоже "словари", но их преимущество именно в БД неоспоримо : индексы как минимум хранят инф-цию о физ.местоположении записей, считав однократно индекс в память ты сможешь оч.быстро переместиться к нужной записи в файле, выполнив "точный" seek() на нее. Или не выполнять ненужного перемещения вообще, если индекс не удовлетворяет условиям поиска/фильтрации записи

← →
Digitman © (2003-01-10 16:45) [17]

Или , если файл уже сортирован по ключу, ищи методом половинного деления. За образец возьми реализацию TStringList.Find()

← →
Login_Andrew (2003-01-10 17:17) [18]

для Digitman
Я и имел ввиду, что бинарный поиск применен у меня.
Видимо, написал не совсем понятно.
Так все таки, нужен еще какой-либо "драйвер" (или еще что-либо сопутствующее) для TDataSet при переносе БД, допустим на другой компьтер?
Записи уже действительно отсортированы на этапе их записи в файл базы данных.
Можно ли подробнее о Memory Mapped File? Файл действительно только для чтения в конкретном случае.
Вы могли привести практический пример предлагаемого Вами кода.

для Игоря Шевченко
Не понял Вашей идеи.
Я пробовал нечто подобное, но ничего путного не получил, после первого найденного слова далее просто идет перебор записей друг за другом, как буд-то и нет бинарного поиска.
Вы можете привести пример Вашего совета.

← →
Digitman © (2003-01-10 17:26) [19]

> Так все таки, нужен еще какой-либо "драйвер" (или еще что-либо
> сопутствующее) для TDataSet при переносе БД, допустим на
> другой компьтер?

Абсолютно никакого)
Еще раз повторюсь - реализовав идею с наследником TDataSet ты получаешь отличную возможность использовать в кач-ве виз/невиз объектов НД-менеджмента любые компоненты/контролы, "понимающие" что такое есть класс TDataSet

> Можно ли подробнее о Memory Mapped File?

Это не моя идея. Это - к Игорю.

← →
Login_Andrew (2003-01-10 17:33) [20]

для Digitman дополнение

А какое максимальное количество записей может иметь TStringList!
Где-то я читал, что есть ограничение для него только ~ 16 000 записей и все, а как же тогда быть с остальными до ~ 50 000?
А метод Find можно прописать так, чтобы он производил поиск по части слова.

Anatoly Podgoretsky

А как можно по другому добавлять в strList.

Login_Andrew (10.01.03 17:17)

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

Про Memory Mapped Files:
win32.hlp - CreateFileMapping, MapViewOfFile

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;

> А какое максимальное количество записей может иметь TStringList!

Теоретически - 2147483647. Практически - зависит от наличия своб.ресурсов процесса и системы в целом.

> Где-то я читал, что есть ограничение для него только ~
> 16 000 записей и все

Чушь полная. Теор.органичение лишь макс.значением, которое способна хранить переменная Integer-типа.
Другой вопрос, что никакой программер (думающий головой, а не иным местом) такое бешеное число строк в стринг-листе хранить не додумается.

> А метод Find можно прописать так, чтобы он производил поиск
> по части слова.

Можно. А зачем ? Ты ж сам сказал, что не хочешь грузить НД целиком в память ?

← →
Login_Andrew (2003-01-10 17:48) [24]

для Digitman
Как можно практически связать TDataSet с моим типом файла базы данных? Его я указал выше.

да там чуть ли не все методы - виртуальные либо абстрактные) ... на то и шаблон

читай в хэлпе назначение интересующих тебя методов, перекрывай их в своем наследнике и реализуй то, что ожидает от НД внешний код, вызывающий тот или иной метод твоего объекта-наследника

← →
Login_Andrew (2003-01-10 17:59) [26]

Извините для всех!

Советов очень много, но реально, может кто-либо связать мой конкретный случай со своим видением проблемы и привести конкретный пример кода?
Еще раз привожу рассматриваемый фрагмент (подкорректированный):

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;

← →
Login_Andrew (2003-01-10 18:52) [27]

для Digitman

А как можно загрузить НД из моего файла через св-во Data
Пожалуйста, приведите конкретный код.

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