Конференция "Начинающим" » Посоветуйте библиотеку для Delphi
 
  • kilkennycat © (13.04.18 21:38) [20]

    > Redmond  


    > TFileStream это не библиотека..

    автор хочет библиотеку.


    > Верное? Весь файл?

    Да. Простое, но не оптимальное, об оптимизации далее говорил.
    Например, вариант "читаем блоками на 1024 байт и ищем подстроку "Hello my little world"",  можно реализовывать как чтение всего файла, но без загрузки в память. Читаем каждый 21-ый байт (с юникодом, разумеется, иначе), проверяем его на вхождение в массив байтов [H,e,l,o, ,m,y,i,t,w,r,d]. Если оно есть, мы легко получаем область вероятного нахождения сей подстроки, размером всего в 41 байт.
    Чтобы найти все вероятные области вхождения подстроки, нам требуется прочитать данных в 21 раз меньше, чем объем файла.
    Разумеется, это не прямое руководство к действию, во многих случаях это будет неоптимально,  и не является единственным (и даже законченным для этого случая) решением.
  • kilkennycat © (13.04.18 21:40) [21]
    Чет я как-то заумил. невыспался. но, думаю, мысля понятна ))
  • Игорь Шевченко © (14.04.18 11:11) [22]
    MMF наше все - просто и незатратно.
  • SergP © (14.04.18 12:45) [23]

    > Зачем два блока? Всё равно заранее не определить понадобится
    > ли второй, а всегда читать по два будет накладным. хотя.
    > .. Может зависеть от задачи, надо обмозговать.


    Ну 2 блока ИМХО нужно иметь в памяти потому что концовка искомой строки может оказаться не в том блоке что и начало.  Но читать по 2 блока я и не предлагал, это буфер размером на 2 блока должен быть, чтобы когда поиск в очередном блоке закончен, и мы переходим к следующему блоку, на место уже "прочесаного" блока грузился очередной. Т.е. просмотрели первый блок, переходим ко второму, и сразу на место первого блока грузится третий. Просмотрели второй блок, переходим к третьему, а на место второго грузится четвертый и т.д.

    т.е. что-то типа этого (в файле filename ищется подстрока s и возвращается  позиция первого вложения если найдена, или -1 если такое не найдено:
    Написано абы как, под влиянием значительного кол-ва пива, но на работоспособность проверено. Исключительно в целях объяснения мысли, указаной в  SergP ©   (12.04.18 17:12) [13].  Для практического применения следует дорабатывать напильником.

    ...
    var
     buffer:array[0..8191] of byte;
    ...
    function SearchFirst(filename,s:string):integer;
    var
     d:integer;
     f:file;
     pos:integer;
     i:integer;
     fsize:integer;
     flag:boolean;
    begin
     AssignFile(f,filename);
     Reset(f,1);
     fsize:=filesize(f);
     reset(f,4096);
     blockread(f,buffer[0],1,d);
     for result:=0 to fsize-length(s) do
     begin
       if result and 4095 = 0 then blockread(f,buffer[result and 4096 xor 4096],1,d);
       pos:=result and 8191;
       if buffer[pos]=ord(s[1]) then
       begin
         flag:=true;
         for i:=2 to length(s) do
         begin
           pos:=(pos+1) and 8191;
           if buffer[pos]<>ord(s[i]) then
           begin
             flag:=false;
             break;
           end;
         end;
         if flag then
         begin
           CloseFile(f);
           Exit;
         end;
       end;
     end;
     result:=-1;
     CloseFile(f);
    end;
    ...
  • Игорь Шевченко © (14.04.18 14:26) [24]
    SergP ©   (14.04.18 12:45) [23]

    Почитал бы ты МакКоннелла...
  • SergP © (14.04.18 15:09) [25]

    > Игорь Шевченко ©   (14.04.18 14:26) [24]
    >
    > SergP ©   (14.04.18 12:45) [23]
    >
    > Почитал бы ты МакКоннелла...


    Никогда не читал его.  С чего именно советуете начать?
  • Игорь Шевченко © (14.04.18 15:31) [26]
    SergP ©   (14.04.18 15:09) [25]


    > С чего именно советуете начать?


    "Совершенный код"
    https://www.ozon.ru/context/detail/id/138437220/
  • SergP © (20.04.18 00:14) [27]

    > Игорь Шевченко ©   (14.04.18 14:26) [24]
    >
    > SergP ©   (14.04.18 12:45) [23]
    >
    > Почитал бы ты МакКоннелла...


    Нашел, скачал. Правда не было времени читать все. Пока только бегло переглянул. Но не совсем понял что именно Вам не понравилось в [23]. Я и не писал что то код для непосредственного использования. Просто хотел показать как я вижу возможность использования примитивного алгоритма поиска в файле, при условии его поблочного чтения...

    А что касается алгоритма и пр. то вот ради интереса решил проверить как будет работать КМП (Алгоритм Кнута — Морриса — Пратта)
    плюс

    > Игорь Шевченко ©   (14.04.18 11:11) [22]
    >
    > MMF наше все - просто и незатратно.


    function SearchFirstKMP(const filename,substring:string):integer;
    var
     hfile,hmap:THandle;
     fSizeL,fSizeH:dword;
     pData:pointer;
     P:array of word;
     i,j:integer;
     SubstSize:integer;
     ch:Char;
    begin
     Result:=-2;
     hfile:=CreateFile(pansichar(filename),GENERIC_READ,FILE_SHARE_READ,nil,OPEN_EXIS TING, 0,FILE_FLAG_SEQUENTIAL_SCAN);
     if hfile<>INVALID_HANDLE_VALUE then
     begin;
       fSizeL:=GetFileSize(hFile, @fSizeH);
      {
      // С файлами размером более 2 Гб заморачиваться не будем. игнорируем
       if (fsizeH<>0) or (fSizeL and $80000000 > 0) then
       begin
         FileClose(hfile);
         result:=-3;
         Exit;
       end;
      }
       hmap:=CreateFileMapping(hFile,nil,PAGE_READONLY,fSizeH,fSizeL,nil);
       if hMap <> 0 then
       begin
         pData:=MapViewOfFile(hmap,FILE_MAP_READ,0,0,0);
         if pData<>nil then
         begin
           // КМП - подготовка
           SubstSize:=length(substring);
           SetLength(P, SubstSize+1);
           P[1]:=0;
           j:=0;
           for i:=2 to SubstSize do
           begin
             while (j>0) and (Substring[j+1] <> Substring[i]) do j:=P[j];
             if Substring[j+1] = Substring[i] then inc(j);
             P[i]:=j;
           end;
           //КМП - поиск
           j := 0;
           result:=-1;
           for i:=0 to fsizeL-1 do
           begin
             ch:=pchar(pointer(cardinal(pData)+i))^;
             while (j>0) and (SubString[j+1]<>ch) do j:= P[j];
             if Substring[j+1] = ch then inc(j);
             if j = SubstSize then
             begin
               result := i-SubstSize+1;
               break;
             end;
           end;
           UnmapViewOfFile(pData);
         end;
         CloseHandle(hmap);
       end;
       FileClose(hfile);
     end;
    end;


    Возможно тестовый пример оказался неудачным, но время выполнения получилось почти такое же как и в [23], по крайней мере не меньше, а даже и чуть больше.
 
Конференция "Начинающим" » Посоветуйте библиотеку для Delphi
Есть новые Нет новых   [91044   +18][b:0.001][p:0.001]