Вопросец возник...

From

Evgeniy Jirnov (2:5030/1230.13)

To

Oleg Khovayko ()

Date

2003-01-27T12:31:18Z

Area

RU.ALGORITHMS

Мир твоему дому, Oleg.


25 Янв 03 04:48, Oleg Khovayko -> Evgeniy Jirnov:

 >> Что-то я не соображу: бинарный поиск imho применить нельзя.
 OK> Нельзя. точно.

А жаль...

 >> Не перебирать же 3000 строк на совпадение с маской по возрастанию?
 OK> А придется! :(
 OK> На самом деле, существуют методы, упрощающие твою задачу.
 OK> По списку масок надо строить конечный автомат, который и будет
 OK> тебе для каждой строки возвращать список масок, к которым
 OK> подходит данная строка.

На самом деле можно мою задачу можно упростить, но тогда я получу уменьшение скорости непонятно на сколько. А суть такова: в данный момент я перебираю 3000 строк и для каждой строки прогоняю 500 масок. Если перебирать 500 масок и для каждой перебирать 3000 строк, тогда можно сильно упростить задачу: во-первых, у меня довольно мало масок, где первый символ - "*", во-вторых маски отсортированы по возрастанию... Но если сделать так, то я получу ограничение на 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;
{────────────────────────────────────────────────────────────────────────────}

Не знаю правда чья она, но автору огромнейшее спасибо...

С уважением _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)