Форум: "Основная";
Текущий архив: 2003.01.20;
Скачать: [xml.tar.bz2];
Внизмножественная выборка из массива собственной базы данных Найти похожие ветки
← →
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.
← →
Игорь Шевченко (2003-01-10 17:35) [21]Login_Andrew (10.01.03 17:17)
Виноват, не прочитал внимательно вопрос. Бинарный поиск не применим вообще, так как тебе надо искать совпадение не всего ключа, а его части, причем, часть может ноходиться не в начале ключа, а в середине или в конце. Тогда - последовательный перебор будет самым быстрым и легким способом.
Про Memory Mapped Files:
win32.hlp - CreateFileMapping, MapViewOfFile
← →
Игорь Шевченко (2003-01-10 17:41) [22]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;
← →
Digitman (2003-01-10 17:48) [23]
> А какое максимальное количество записей может иметь TStringList!
Теоретически - 2147483647. Практически - зависит от наличия своб.ресурсов процесса и системы в целом.
> Где-то я читал, что есть ограничение для него только ~
> 16 000 записей и все
Чушь полная. Теор.органичение лишь макс.значением, которое способна хранить переменная Integer-типа.
Другой вопрос, что никакой программер (думающий головой, а не иным местом) такое бешеное число строк в стринг-листе хранить не додумается.
> А метод Find можно прописать так, чтобы он производил поиск
> по части слова.
Можно. А зачем ? Ты ж сам сказал, что не хочешь грузить НД целиком в память ?
← →
Login_Andrew (2003-01-10 17:48) [24]для Digitman
Как можно практически связать TDataSet с моим типом файла базы данных? Его я указал выше.
← →
Digitman (2003-01-10 17:58) [25]да там чуть ли не все методы - виртуальные либо абстрактные) ... на то и шаблон
читай в хэлпе назначение интересующих тебя методов, перекрывай их в своем наследнике и реализуй то, что ожидает от НД внешний код, вызывающий тот или иной метод твоего объекта-наследника
← →
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
Пожалуйста, приведите конкретный код.
Страницы: 1 вся ветка
Форум: "Основная";
Текущий архив: 2003.01.20;
Скачать: [xml.tar.bz2];
Память: 0.54 MB
Время: 0.011 c