|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Evgeniy Jirnov 2:5030/1230.13 27 Jan 2003 13:31:18
To : Oleg Khovayko
Subject : Вопросец возник...
--------------------------------------------------------------------------------
25 Янв 03 04:48, Oleg Khovayko -> Evgeniy Jirnov:
>> Что-то я не соображу: бинарный поиск imho применить нельзя.
OK> Hельзя. точно.
А жаль...
>> Hе перебирать же 3000 строк на совпадение с маской по возрастанию?
OK> А придется! :(
OK> Hа самом деле, существуют методы, упрощающие твою задачу.
OK> По списку масок надо строить конечный автомат, который и будет
OK> тебе для каждой строки возвращать список масок, к которым
OK> подходит данная строка.
Hа самом деле можно мою задачу можно упростить, но тогда я получу уменьшение
скорости непонятно на сколько. А суть такова: в данный момент я перебираю 3000
строк и для каждой строки прогоняю 500 масок. Если перебирать 500 масок и для
каждой перебирать 3000 строк, тогда можно сильно упростить задачу: во-первых, у
меня довольно мало масок, где первый символ - "*", во-вторых маски отсортированы
по возрастанию... Hо если сделать так, то я получу ограничение на 16k строк...
>> Причем масок
>> около 500. Получается мне надо перебрать 3000*500=1500000
>> комбинаций? :(
OK> Ага.
OK> Чем реально могу пособить - в свое время я написал эффективную
OK> процедуру сравнения имени файла с маской, которая в худшем случае
OK> производит (A+1)*L операций сравнения, где А - число звездочек в
OK> маске, а L - длина строки-кандидата.
OK> Хочу заметить, что это существенно лучше того, что сейчас применяется
OK> в UNIX-ах. Ибо UNIX shell можно в легкую положить такой
OK> последовательностью команд:
OK> touch aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
OK> ls *a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*a*b
Гхм... У меня процедура сравнения строки с маской производит довольно мало
сравнений и не валится на такой строчке и маске. Вот ее исходный текст:
{ДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДД}
type
TCheckWildcardStack = packed record
Src,
Mask: Byte;
end;
function CheckMask(const Src, Mask: String): Boolean;
var
Stack: array[1..128] of TCheckWildcardStack;
StackPointer,
SrcPosition, MaskPosition,
SrcLength, MaskLength: Byte;
begin
CheckMask:=False;
if (Mask = '') and (Src <> '') then Exit;
MaskLength:=Length(Mask);
SrcLength:=Length(Src);
if Mask[MaskLength] <> '*' then
while (MaskLength > 1) and (SrcLength > 1) do
begin
if (Mask[MaskLength] = '*') or (Mask[MaskLength] = '?') then Break;
if Mask[MaskLength] <> Src[SrcLength] then Exit;
Dec(MaskLength);
Dec(SrcLength);
end;
if Mask[MaskLength] = '*' then
while (Mask[MaskLength - 1] = '*') and (MaskLength > 1) do Dec(MaskLength);
StackPointer:=0;
SrcPosition:=1;
MaskPosition:=1;
while (SrcPosition <= SrcLength) and (MaskPosition <= MaskLength) do
begin
case Mask[MaskPosition] of
'?':
begin
Inc(SrcPosition);
Inc(MaskPosition);
end;
'*':
begin
if (MaskPosition = 1) or (Mask[MaskPosition - 1] <> '*') then
Inc(StackPointer);
Stack[StackPointer].Mask:=MaskPosition;
Inc(MaskPosition);
if MaskPosition <= MaskLength then
if (Mask[MaskPosition] <> '?') and (Mask[MaskPosition] <> '*') then
while (SrcPosition <= Length(Src)) and (Src[SrcPosition] <>
Mask[MaskPosition]) do Inc(SrcPosition);
Stack[StackPointer].Src:=SrcPosition + 1;
end;
else
if Src[SrcPosition] = Mask[MaskPosition] then
begin
Inc(SrcPosition);
Inc(MaskPosition);
end else
begin
if StackPointer = 0 then Exit;
SrcPosition:=Stack[StackPointer].Src;
MaskPosition:=Stack[StackPointer].Mask;
Dec(StackPointer)
end;
end;
while not ((SrcPosition <= SrcLength) xor (MaskPosition > MaskLength)) do
begin
if (MaskPosition >= MaskLength) and (Mask[MaskLength] = '*') then Break;
if StackPointer = 0 then Exit;
SrcPosition:=Stack[StackPointer].Src;
MaskPosition:=Stack[StackPointer].Mask;
Dec(StackPointer)
end;
end;
CheckMask:=True;
end;
{ДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДДД}
Hе знаю правда чья она, но автору огромнейшее спасибо...
С уважением _Evgeniy_
... 83 AB E3 AF A0 EF 20 E2 E0 A0 E2 A0 20 A2 E0 A5 AC A5 AD A8 21
--- np: Enigma - Track 6
* Origin: А вы и ухом не моргнули (2:5030/1230.13)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
