HiAsm
HiAsm
Вверх ↑
ФорумыПомощь по пакетуПоиск одинаковых данных в дампе или сравнение двух файлов разного размера ← Ctrl123Ctrl →
Этот топик читают: Гость
Ответов: 8911
Рейтинг: 823
#31: 2020-03-16 22:01:51 ЛС | профиль | цитата
Galkov писал(а):
где используются те самые j и k
Ой, и правда, наверное не сохранил перед тем как выложить. (менял переменные). Когда скачивал/проверял и не заметил Спасибо!
В теле цикла заменить m на j, а n на k.
Выложил https://forum.hiasm.com/getfile/38919
У ТС, как я понял не библиотека отдельных кусочков, которые и ищутся в файле, а просто файлы, в которых может быть совпадение (плагиат)
карма: 19

0
Ответов: 192
Рейтинг: 2
#32: 2020-03-17 17:18:54 ЛС | профиль | цитата
Леонид писал(а):
плагиат

это не плагиат это ключи доступа
карма: 0

0
Ответов: 9906
Рейтинг: 351
#33: 2020-03-22 16:20:42 ЛС | профиль | цитата
Ну вот.......
Нашел я таки время, чтобы детально во всем содеянном разобраться... Сделать для себя некие умозаключения.

1) Сказать нечего: летает из под IC оно гораздо круче, чем чисто в схемной реализации.
Тем не менее, схемная реализация мне кажется вещью очень нужной.
В алгоритме индексации (там делов-то на 4 элемента) смогут разобраться, прочувствовать его - многие наши пользователи...
Таки у нас форум по HiAsm, а не по дельфячему кодингу....
Как бы не всякий, сначала найдет ошибки в коде, а уже потом его запустит.
BTW
Леонид писал(а):
В теле цикла заменить m на j, а n на k
Угу... И в аргументах _hi_OnEvent -- тоже.

Не хватало мне для этого "человеческих" массивов.
Ну так я их сделал. Под названием SimpleArray (там сделано так же, как я делал в матрице - есть опция выбора типа данных ArrayType). И главное, что есть методы doCount (особаченное св-во) и doFillData.
Отсюда предложение к коллегам: протестировать его, на предмет добавления в штатный инструментарий (В плане иконок - никаких претензий на художника/дизайнера у меня не имеется, хотя чего-то я и должен был нарисовать).

2) Чтобы сравнивать хронометражи, мне пришлось немного причесать код Леонид-а, и "пересадить" свой алгоритм в его схему (правда добавил некоторые отладочные выводы). Тестирование проводил на файлах с "белым шумом", которые я получал по такой схеме:
Файлы "белого шума"

Add(MainForm,2953706,42,154)
{
 Height=115
 link(onCreate,2916266:doRandomize,[(242,174)(242,146)])
}
Add(Random,2916266,259,133)
{
 Max=255
 Quality=1
 link(onRandom,6565636:doPut,[])
}
Add(MemoryStream,857626,315,70)
{
 Point(doSize)
}
Add(Button,10718682,42,84)
{
 Left=21
 Top=21
 link(onClick,10004433:doEvent1,[])
}
Add(Edit,1956480,196,21)
{
 Left=112
 Top=21
 Text="17"
 Alignment=1
 DataType=1
 ClearAfterEnter=1
}
Add(Math,1881904,189,84)
{
 OpType=11
 Op1=2
 ResultType=0
 link(onResult,857626:doSize,[])
 link(Op2,2698912:Var2,[])
}
Add(For,15706600,182,133)
{
 IncludeEnd=1
 link(onEvent,2916266:doRandom,[])
 link(onStop,1642205:doStrCatDlm,[(221,146)(221,188)])
 link(End,1881904:Result,[])
}
Add(Hub,10004433,112,84)
{
 OutCount=3
 link(onEvent1,1881904:doOperation,[])
 link(onEvent2,6565636:doPosition,[(305,97)(305,146)])
 link(onEvent3,15706600:doFor,[(172,104)(172,139)])
}
Add(DataToFileEx,6565636,315,126)
{
 Point(doPosition)
 link(Stream,12551088:Var2,[])
}
Add(MT_Add,2427908,364,182)
{
 link(onAdd,12681472:doCopyFromStream,[])
 link(Data,12551088:Var3,[(370,117)])
}
Add(GetDataEx,12551088,315,112)
{
 link(Data,857626:Stream,[])
}
Add(FileStream,12681472,420,168)
{
 Mode=1
 AutoCopy=0
 Point(doCopyFromStream)
}
Add(StrCatDelim,1642205,259,182)
{
 Str1="RND_"
 Str2=".bin"
 Point(Delimiter)
 link(onStrCatDlm,5809954:doExecute,[])
 link(Delimiter,2698912:Var3,[(279,68)])
}
Add(GetDataEx,2698912,196,63)
{
 link(Data,1956480:Text,[])
}
Add(SDialog,5809954,315,182)
{
 FileName=""
 link(onExecute,2427908:doAdd,[])
}
правленный код Леонида

Add(Label,1824696,434,91)
{
 @Hint=#26:А чтобы никто не догадался|
 Width=100
 Height=286
 Align=1
 Caption=""
 AutoSize=1
 AddHint(-59,-23,158,13,@Hint)
}
Add(Button,6300579,42,35)
{
 Left=10
 Top=5
 Width=70
 Caption="Open 2 files"
 link(onClick,908814:doExecute,[])
}
Add(Edit,6253556,287,84)
{
 Left=65
 Top=40
 Width=25
 Text="5"
 DataType=2
}
Add(Label,5760286,287,35)
{
 Left=7
 Top=35
 Width=61
 Height=32
 Caption="Number of\r\nbytes >="
 AutoSize=1
 Alignment=2
}
Add(Button,13033686,42,161)
{
 Left=15
 Top=125
 Caption="Search"
 link(onClick,6984947:doEvent1,[])
}
Add(ODialog,908814,91,35)
{
 Title="Open first file"
 link(onExecute,14252828:doEvent1,[])
}
Add(ODialog,9007154,91,84)
{
 Title="Open second file"
 link(onExecute,4645375:doEvent1,[])
}
Add(Hub,14252828,133,35)
{
 OutCount=3
 link(onEvent1,14151222:doOpen,[])
 link(onEvent2,14151222:doClose,[])
 link(onEvent3,9007154:doExecute,[(158,55)(158,76)(81,76)(81,90)])
}
Add(FileStream,14151222,175,35)
{
 link(onLoad,9951475:doCopy,[])
}
Add(FileStream,6090657,175,84)
{
 link(onLoad,7759878:doCopy,[])
}
Add(Button,5547259,42,217)
{
 Left=15
 Top=202
 Caption="Save"
 link(onClick,9381149:doExecute,[])
}
Add(InlineCode,9739546,231,182)
{
 WorkPoints=#31:doSearchStream=Поиск совпадений|
 EventPoints=#6:onTime|48:onRes=Позиции начала совпадения, разделитель ";"|
 VarPoints=#8:compares|
 DataPoints=#46:Stream1=Данные 1-го файла (нужен MemoryStream)|46:Stream2=Данные 2-го файла (нужен MemoryStream)|35:Num=Количество байтов для сравнения|
 Code=#15:unit HiAsmUnit;|0:|9:interface|0:|29:uses kol,Share,Debug,Windows;|0:|4:type|29:  THiAsmClass = class(TDebug)|11:    private|16:      dbg:int64;|10:    public|45:      onTime,onRes:THI_Event;        //Events|44:      Stream1,Stream2,Num:THI_Event; //Datas|60:      procedure doSearchStream(var _Data:TData; Index:word);|54:      procedure compares(var _Data:TData; Index:word);|6:  end;|0:|14:implementation|0:|37:procedure THiAsmClass.doSearchStream;|20:var Fl1,Fl2:PStream;|18:  Fil1,Fil2:PChar;|40:  Sort1,Sort2:Array of Array of integer;|27:  _Len1,_Len2,_Len:integer;|24:  i,j,k,_Min,_A:integer;|5:begin|78:  _Min:=ReadInteger(_Data,Num,4);    //Минимальное количество совпадающих байт|35:  Fl1 := ReadStream(_data,Stream1);|25:  if Fl1 = nil then Exit;|35:  Fl2 := ReadStream(_data,Stream2);|25:  if Fl2 = nil then Exit;|20:  _Len1 := Fl1.Size;|20:  _Len2 := Fl2.Size;|21:  Fil1 := Fl1.Memory;|21:  Fil2 := Fl2.Memory;|27:  SetLength(Sort1, $10000);|45:  for i:=0 to $FFFF do SetLength(Sort1[i],0);|27:  SetLength(Sort2, $10000);|45:  for i:=0 to $FFFF do SetLength(Sort2[i],0);|106://---Определяем и записываем в массивы положение всех найденных из $10000 возможных двухбайтных комбинаций|30://---Файл первый -- индексация|22:  _hi_OnEvent(onTime);|19:  _Len:=_Len1-_Min;|27:  for i:=0 to _Len do begin|40:    _A:=ord(Fil1[i])*256+ord(Fil1[i+1]);|25:    k:=Length(Sort1[_A]);|30:    SetLength(Sort1[_A], k+1);|20:    Sort1[_A, k]:=i;|6:  end;|30://---Файл второй -- индексация|22:  _hi_OnEvent(onTime);|19:  _Len:=_Len2-_Min;|27:  for i:=0 to _Len do begin|40:    _A:=ord(Fil2[i])*256+ord(Fil2[i+1]);|25:    k:=Length(Sort2[_A]);|30:    SetLength(Sort2[_A], k+1);|20:    Sort2[_A, k]:=i;|6:  end;|98://---Перебираем все двухбайтные совпадения в одноимённых массивах на предмет дальнейших совпадений|22:  _hi_OnEvent(onTime);|11:  dbg := 0;|28:  for i:=0 to $FFFF do begin|55:    if (Length(Sort1[i])>0)and(Length(Sort2[i])>0) then|71:      for j:=0 to high(Sort1[i]) do for k:=0 to high(Sort2[i]) do begin|17:        inc(dbg);|110:        _A:=2;                                                     //Два первых байта совпадают по определению|110:        while ((Sort1[i,j]+_A)<_Len1)and((Sort2[i,k]+_A)<_Len2) do //Проверяем на выход файлов за свои размеры|113:          if Fil1[Sort1[i,j]+_A]=Fil2[Sort2[i,k]+_A] then inc(_A)  //Увеличиваем кол-во совпавших байт на единицу|121:          else break;                                              //Если уже не совпадают - длина совпадений уже найдена|118:        if _A>=_Min then //Если кол-во совпавших байтов не менее установленного - выводим длину и позиции на индикацию|90:          _hi_OnEvent(onRes, int2str(_A)+';'+int2str(Sort1[i,j])+';'+int2str(Sort2[i,k]));|10:      end;|6:  end;|4:end;|0:|31:procedure THiAsmClass.compares;|5:begin|21:  dtReal(_Data, dbg);|4:end;|0:|4:end.|
 link(onTime,5441784:doWork2,[])
 link(onRes,11582479:doAdd,[])
 link(Stream1,9951475:Stream,[])
 link(Stream2,7759878:Stream,[])
 link(Num,6253556:Text,[(251,131)(293,131)])
}
Add(Hub,4645375,133,84)
{
 link(onEvent1,6090657:doOpen,[])
 link(onEvent2,6090657:doClose,[])
}
Add(LED,15486262,434,147)
{
 Left=30
 Top=157
 Height=32
 Shape=1
}
Add(Hub,6984947,126,161)
{
 OutCount=4
 link(onEvent1,15486262:doOn,[])
 link(onEvent2,12086:doStart,[(347,174)(347,181)])
 link(onEvent3,11582479:doClear,[(221,181)(221,202)])
 link(onEvent4,11956262:doStart,[])
}
Add(SDialog,9381149,91,217)
{
 Filter="TXT|*.txt"
 link(onExecute,11582479:doSave,[])
}
Add(Thread,11956262,175,182)
{
 Delay=0
 FastStop=0
 link(onExec,9739546:doSearchStream,[])
 link(onSyncExec,16031966:doData,[(214,195)(214,244)])
}
Add(TimeCounter,12086,357,175)
{
 link(onStop,12961819:doEvent1,[])
}
Add(StrList,11582479,287,189)
{
 Point(doSave)
}
Add(FormatStr,13053289,427,252)
{
 DataCount=6
 Mask="Found %1 (%6) matches in (%2,%3,%4,%5) мs"
 link(onFString,5052926:doWork2,[])
 link(Str1,11582479:Count,[(433,236)(300,236)])
 link(Str2,16099733:Value1,[])
 link(Str3,16099733:Value2,[])
 link(Str4,16099733:Value3,[])
 link(Str5,16099733:Value4,[])
}
Add(StringTable,4173653,357,266)
{
 Left=100
 Width=322
 Height=261
 Align=5
 Columns=#18:Matches length=100|21:Pos in first file=100|22:Pos in second file=100|
 Grid=0
 ColumnClick=1
 Point(onColumnClick)
 Point(doSortDigit)
 link(onColumnClick,4173653:doSortDigit,[(396,279)(396,307)(347,307)(347,293)])
}
Add(ArrayEnum,156378,301,266)
{
 link(onItem,4173653:doAdd,[])
 link(Array,11582479:Array,[])
}
Add(Hub,2244651,273,238)
{
 OutCount=5
 link(onEvent1,5441784:doWork3,[(326,244)])
 link(onEvent2,15486262:doOff,[(396,251)(396,160)])
 link(onEvent3,13053289:doString,[])
 link(onEvent4,4173653:doClear,[(340,265)(340,279)])
 link(onEvent5,156378:doEnum,[])
}
Add(MemoryStream,9951475,231,35)
{
}
Add(MemoryStream,7759878,238,84)
{
}
Add(HubEx,5441784,322,182)
{
 link(onEvent,12086:doStop,[])
}
Add(Hub,12961819,406,182)
{
 link(onEvent1,5052926:doWork1,[(487,188)])
 link(onEvent2,16099733:doValue,[])
}
Add(HubEx,5052926,483,252)
{
 link(onEvent,5996595:doCaption,[])
}
Add(MemFIFO,16099733,434,189)
{
 Count=4
}
Add(MainForm,5996595,504,252)
{
 Width=438
}
Add(DoData,16031966,231,238)
{
 link(onEventData,2244651:doEvent1,[])
 link(Data,9739546:compares,[])
}
Мой код, инжектированный в его схему

Add(Label,1824696,434,105)
{
 @Hint=#26:А чтобы никто не догадался|
 Width=100
 Height=286
 Align=1
 Caption=""
 AutoSize=1
 AddHint(-59,-23,158,13,@Hint)
}
Add(Button,6300579,42,49)
{
 Left=10
 Top=5
 Width=70
 Caption="Open 2 files"
 link(onClick,908814:doExecute,[])
}
Add(Edit,6253556,287,98)
{
 Left=65
 Top=40
 Width=25
 Text="5"
 DataType=2
}
Add(Label,5760286,287,49)
{
 Left=7
 Top=35
 Width=61
 Height=32
 Caption="Number of\r\nbytes >="
 AutoSize=1
 Alignment=2
}
Add(Button,13033686,42,175)
{
 Left=15
 Top=125
 Caption="Search"
 link(onClick,6984947:doEvent1,[])
}
Add(ODialog,908814,91,49)
{
 Title="Open first file"
 link(onExecute,14252828:doEvent1,[])
}
Add(ODialog,9007154,91,98)
{
 Title="Open second file"
 link(onExecute,4645375:doEvent1,[])
}
Add(Hub,14252828,133,49)
{
 OutCount=3
 link(onEvent1,14151222:doOpen,[])
 link(onEvent2,14151222:doClose,[])
 link(onEvent3,9007154:doExecute,[(158,69)(158,90)(81,90)(81,104)])
}
Add(FileStream,14151222,175,49)
{
 link(onLoad,9951475:doCopy,[])
}
Add(FileStream,6090657,175,98)
{
 link(onLoad,7759878:doCopy,[])
}
Add(Button,5547259,42,231)
{
 Left=15
 Top=202
 Caption="Save"
 link(onClick,9381149:doExecute,[])
}
Add(InlineCode,9739546,231,196)
{
 WorkPoints=#31:doSearchStream=Поиск совпадений|
 EventPoints=#6:onTime|48:onRes=Позиции начала совпадения, разделитель ";"|
 VarPoints=#8:compares|
 DataPoints=#46:Stream1=Данные 1-го файла (нужен MemoryStream)|46:Stream2=Данные 2-го файла (нужен MemoryStream)|35:Num=Количество байтов для сравнения|
 Code=#15:unit HiAsmUnit;|0:|9:interface|0:|21:uses kol,Share,Debug;|0:|4:type|29:  THiAsmClass = class(TDebug)|11:    private|38:      Entry:Array[0..$FFFF]of integer;|28:      Tail:Array of integer;|16:      dbg:int64;|10:    public|45:      onTime,onRes:THI_Event;        //Events|44:      Stream1,Stream2,Num:THI_Event; //Datas|60:      procedure doSearchStream(var _Data:TData; Index:word);|54:      procedure compares(var _Data:TData; Index:word);|6:  end;|0:|14:implementation|0:|37:procedure THiAsmClass.doSearchStream;|15:var ST:PStream;|14:  F1,F2:PChar;|41:  _Len1,_Len2,_Len, i, j,_Min,_A:integer;|5:begin|80:  _Min:=ReadInteger(_Data, Num, 4);    //Минимальное количество совпадающих байт|35:  ST := ReadStream(_Data, Stream1);|24:  if ST = nil then Exit;|19:  _Len1 := ST.Size;|18:  F1 := ST.Memory;|35:  ST := ReadStream(_Data, Stream2);|24:  if ST = nil then Exit;|19:  _Len2 := ST.Size;|18:  F2 := ST.Memory;|39:  FillChar(Entry, sizeof(Entry), #$FF);|27:  SetLength(Tail, _Len2-1);|30://---Файл второй -- индексация|22:  _hi_OnEvent(onTime);|19:  _Len:=_Len2-_Min;|33:  for i := _Len downto 0 do begin|37:    _A :=ord(F2[i])*256+ord(F2[i+1]);|25:    Tail[i] := Entry[_A];|18:    Entry[_A] := i|6:  end;|25://---Файл первый -- поиск|22:  _hi_OnEvent(onTime);|21:  _Len := _Len1-_Min;|11:  dbg := 0;|29:  for i := 0 to _Len do begin|44:    j := Entry[ord(F1[i])*256+ord(F1[i+1])];|25:    while j >= 0 do begin|15:      inc(dbg);|90:      _A := 2;                                 //Два первых байта совпадают по определению|82:      while ((i+_A)<_Len1)and((j+_A)<_Len2) do //Проверяем выход за размеры файлов|93:        if F1[i+_A]=F2[j+_A] then inc(_A)      //Увеличиваем кол-во совпавших байт на единицу|101:        else break;                            //Если уже не совпадают - длина совпадений уже найдена|116:      if _A>=_Min then //Если кол-во совпавших байтов не менее установленного - выводим длину и позиции на индикацию|70:        _hi_OnEvent(onRes, int2str(_A)+';'+int2str(i)+';'+int2str(j));|19:      j := Tail[j];|8:    end;|6:  end;|4:end;|0:|31:procedure THiAsmClass.compares;|5:begin|21:  dtReal(_Data, dbg);|4:end;|0:|4:end.|
 link(onTime,5441784:doWork2,[])
 link(onRes,11582479:doAdd,[])
 link(Stream1,9951475:Stream,[])
 link(Stream2,7759878:Stream,[])
 link(Num,6253556:Text,[(251,145)(293,145)])
}
Add(Hub,4645375,133,98)
{
 link(onEvent1,6090657:doOpen,[])
 link(onEvent2,6090657:doClose,[])
}
Add(LED,15486262,434,161)
{
 Left=30
 Top=157
 Height=32
 Shape=1
}
Add(Hub,6984947,126,175)
{
 OutCount=4
 link(onEvent1,15486262:doOn,[])
 link(onEvent2,12086:doStart,[(347,188)(347,195)])
 link(onEvent3,11582479:doClear,[(221,195)(221,216)])
 link(onEvent4,11956262:doStart,[])
}
Add(SDialog,9381149,91,231)
{
 Filter="TXT|*.txt"
 link(onExecute,11582479:doSave,[])
}
Add(Thread,11956262,175,196)
{
 Delay=0
 FastStop=0
 link(onExec,9739546:doSearchStream,[])
 link(onSyncExec,15749816:doData,[(214,209)(214,258)])
}
Add(TimeCounter,12086,357,189)
{
 link(onStop,3828704:doEvent1,[])
}
Add(StrList,11582479,287,203)
{
 Point(doSave)
}
Add(FormatStr,13053289,427,266)
{
 DataCount=5
 Mask="Found %1 (%5) matches in (%2,%3,%4) мs"
 link(onFString,5052926:doWork2,[])
 link(Str1,11582479:Count,[(433,250)(300,250)])
 link(Str2,16099733:Value1,[])
 link(Str3,16099733:Value2,[])
 link(Str4,16099733:Value3,[])
}
Add(StringTable,4173653,357,280)
{
 Left=100
 Width=322
 Height=261
 Align=5
 Columns=#18:Matches length=100|21:Pos in first file=100|22:Pos in second file=100|
 Grid=0
 ColumnClick=1
 Point(doSortDigit)
 Point(onColumnClick)
 link(onColumnClick,4173653:doSortDigit,[(396,293)(396,321)(347,321)(347,307)])
}
Add(ArrayEnum,156378,301,280)
{
 link(onItem,4173653:doAdd,[])
 link(Array,11582479:Array,[])
}
Add(Hub,2244651,273,252)
{
 OutCount=5
 link(onEvent1,5441784:doWork3,[(326,258)])
 link(onEvent2,15486262:doOff,[(396,265)(396,174)])
 link(onEvent3,13053289:doString,[])
 link(onEvent4,4173653:doClear,[(340,279)(340,293)])
 link(onEvent5,156378:doEnum,[])
}
Add(MemoryStream,9951475,231,49)
{
}
Add(MemoryStream,7759878,238,98)
{
}
Add(HubEx,5441784,322,196)
{
 link(onEvent,12086:doStop,[])
}
Add(HubEx,5052926,483,266)
{
 link(onEvent,5996595:doCaption,[])
}
Add(MemFIFO,16099733,434,203)
{
 Count=3
}
Add(MainForm,5996595,504,266)
{
 Width=438
}
Add(Hub,3828704,406,196)
{
 link(onEvent1,5052926:doWork1,[(487,202)])
 link(onEvent2,16099733:doValue,[])
}
Add(DoData,15749816,231,252)
{
 link(onEventData,2244651:doEvent1,[])
 link(Data,9739546:compares,[])
}
Ну будем тестировать, например, на файлах RND_22 (4 метра) и RND_21 (2 метра)...
Что же мы видим:
  a)  Алгоритм Леонид-а работает гораздо быстрее моего (у него ~7сек, против моих ~17сек)
  b)  Индексация у меня проскакивает почти моментально (~20мсек), а у Леонид-а две индексации ~3.5сек.
  c)  Косвенным подтверждением идентичности алгоритмов - количество макроопераций сравнения последовательностей (полное совпадение).
Ну и фактически найденные последовательности (специально сделал сортировку по столбцу, чтобы сравнивать). Кстати говоря, с моими файлами - это ~134 МегаОпа, что отличается от 8 ТераОпов на те самые 4.8 порядка, прогнозируемые ранее. Между прочим, сами операции поиска (все 134 МегаОпа) занимают около 3-х секунд. Что в моем коде, что у Леонид-а (я их комментировал, и сравнивал времена).

Вот я долго думал, почему мой код "тормозит", в сравнении с Леонид-ом. Всю башку себе сломал: как же так... ну все же правильно... ну не может этого быть... и дизасм смотрел - да там 4 элементарные команды проца!
Остановился пока на таком заключении: перебор позиций вхождения в словарь у меня осуществляется лазанием (вообще-то элементарным - j:=Tail[j]) по всему массиву. Который, для RND_21, весит таки 8 метров. А у Леонид-а - эти позиции лежат все подряд в одном массиве. В общем, думаю я себе - процессор с совершенно разной скоростью обращается к памяти при таких раскладах. Опять же: 134 МегаОпа - это вам не кот чихнул.
Других идей пока не возникло... Если кто в теме - поделитесь.

НО, не будем пока петь осанну алгоритму индексации Леонид-а
Постоянная реаллокация массива на предмет добавления одного нового элемента - очень трудозатратная вещь (что видно из его времян индексации). Да и опасная - может и AV закончиться. Собственно, я с этого и начинал: сделал себе StringArray (сначала в IC, а теперь это и SimpleArray позволяет), ну и давай себе добавлять позиции в хвостик через ';'. Ну, быстродействие этого дела - мне сразу не понравилось (схема - это вам не IC). Но, ручки то шаловливые - вот и давай я ему совать все, что под руку попадется. И попался мне под руки libmySQL.dll (кажется, намедни его поминали незлым тихим словом) - закончилось все это AV, после долгих трудов. А попробуйте подсунуть его в схему Леонид-а - у меня, по крайней мере, это закончилось тоже AV.
На самом деле, это реальная проблема, при больших объемах информации.
После этого я напрягся, и вспомнил идею того алгоритма индексации, что у меня сейчас. Не, это не я его придумал, читал где-то... Может и в учебнике каком ни то...
А вот помните мою первую схему в этом посте? Она называется "Тест индексирования словаря"
Так там есть IC с названием "String Accumulator". Думаете мне просто захотелось продемонстрировать свое искусство написания IC?
Вовсе нет. Казалось бы делов: добавить в хвостик строки еще одно число через запятую. Конечно, я начинал с обыкновенного Memory. Но опять же, подсунул ему libmySQL.dll - индексация с сегодняшним алгоритмом прошла махом. А вот уж как начал он для него делать текст.... Он первую строку 20 минут делал (а дальше уже - бегом, секундное дело).
Дело в том, что в этом файле двойных ноликов - как у дурака фантиков. В текстовом представлении нашего хеша, его первая строка -- треть файла занимала.
Вот такая вот проблема... Ищет быстро (и именно из-за способа индексирования), а сама индексация - тормозить может, в плоть до падения при неблагоприятных обстоятельствах.

3) Проанализируем, чего у нас получается.
Когда файл словаря меньше, чем хеш-таблица, то поиск в ней не зависит от размера файла. Типа, какая разница, насколько эта таблица заполнена - на треть, на четверть, или на половину. Получается, что время поиска пропорционально сумме длины словаря (время на его индексацию), и длины файла поиска. Со своим коэффициентом каждая длина, естественно.
А если больше, чем хеш таблица - тогда время поиска пропорционально произведению этих длин, деленному на размер хеш таблицы.
Что мы и имеем в настоящее время.
Мораль такая: надо так устраивать хеш-таблицу, чтобы словарь не переполнял ее ни в коем случае. И это будет как бы самое чики-пуки.

Отсюда возникает мысль: а не замахнуться ли нам на Вильяма на нашего на Шекспира
Индексировать не двумя, а тремя первыми байтами.
Что меняется: массив, который у меня обзывается "Entry to HashList", станет размером 16777216. Это 64 метра в памяти. Это многовато, конечно же... А с другой стороны, кому-то разве жалко ???
В общем, это может выглядеть примерно так:
Трехбайтная индексация

Add(Label,1824696,791,154)
{
 @Hint=#26:А чтобы никто не догадался|
 Width=418
 Height=43
 Align=2
 Caption=""
 AutoSize=1
 AddHint(-68,-34,158,13,@Hint)
}
Add(MainForm,14415943,336,63)
{
 Width=435
 Height=418
 Caption="Поиск в индексированном словаре"
}
Add(Button,2823604,28,42)
{
 Left=14
 Top=14
 Caption="Словарь"
 link(onClick,10410305:doExecute,[])
}
Add(ODialog,10410305,70,42)
{
 link(onExecute,550519:doOpen,[])
}
Add(FileStream,550519,119,42)
{
 link(onLoad,7747773:doEvent1,[])
}
Add(Hub,7747773,168,42)
{
 OutCount=5
 link(onEvent1,16091653:doWork1,[(319,48)])
 link(onEvent2,13093263:doStart,[])
 link(onEvent3,13093263:doStop,[])
 link(onEvent4,3503074:doEnabled,[(200,69)(200,97)(32,97)(32,174)])
 link(onEvent5,550519:doClose,[(193,76)(193,90)(109,90)(109,55)])
}
Add(TimeCounter,13093263,224,49)
{
 link(onStart,9769920:doLoad,[(445,55)(445,167)])
 link(onStop,198127:doStrCatDlm,[])
}
Add(For,3827780,315,182)
{
 IncludeEnd=1
 link(onEvent,180655:doEvent1,[])
 link(End,161234:Var1,[(328,173)(293,173)])
}
Add(Math,16212320,315,350)
{
 OpType=3
 link(onResult,16582522:doOperation,[])
 link(Op1,15696705:Var2,[])
 link(Op2,161234:Var3,[(328,229)])
}
Add(ProgressBar,4002621,511,350)
{
 Top=359
 Width=418
 Align=4
 ProgressColor=-16777203
}
Add(Timer,9718670,231,350)
{
 Interval=100
 Enable=1
 link(onTimer,13110199:doEvent1,[])
}
Add(FileStream,7806628,133,168)
{
 link(onLoad,15415920:doEvent1,[])
}
Add(StrCatDelim,16729616,462,392)
{
 Delimiter=": "
 link(onStrCatDlm,15437502:doText,[])
 link(Str1,2816362:Var2,[])
 link(Str2,11030346:Var2,[])
}
Add(Hub,13110199,280,350)
{
 link(onEvent1,16212320:doOperation,[])
 link(onEvent2,16729616:doStrCatDlm,[(305,363)(305,398)])
}
Add(Label,15437502,511,392)
{
 Left=301
 Top=14
 Width=32
 Height=22
 Font=[MS Sans Serif,10,0,0,1]
 Caption="0000"
}
Add(Button,3503074,42,168)
{
 Left=91
 Top=14
 Width=69
 Enabled=1
 Caption="Поиск в..."
 Point(doEnabled)
 link(onClick,3944805:doExecute,[])
}
Add(ChangeMon,14219118,413,350)
{
 link(onData,4002621:doPosition,[])
}
Add(MultiElementEx,9769920,462,161)
{
 @Hint=#74:Словарь, индексированный по первым трем байтам последовательности символов|
 Name="Hash"
 link(onFirstPos,8703109:doEvent1,[])
 link(onNextPos,9275719:doEvent1,[])
 AddHint(0,-106,174,39,@Hint)
}
BEGIN_SDK
  Add(EditMultiEx,10199030,21,21)
  {
   WorkCount=#34:doLoad=Загрузка+Индексация словаря|102:doHash=Поиск позиций в словаре, соответствующих ключу (три первых байта последовательности, как целое)|32:doStop=Преждевременная остановка|
   EventCount=#64:onFirstPos=Вход в список позиций для ключа, заданного по doHash |60:onNextPos=Последующие позиции для ключа, заданного по doHash|78:onEndList=Сообщение об окончании списка позиций для ключа, заданного по doHash|
   VarCount=#134:VocStream=Загруженный по doLoad словарь, предустановленный (для удобства дальнейших сравнений) сразу после найденных по doHash позиций|88:Pos=Позиция в словаре при активизации выходов onFirstPos и onNextPos (в ответ на doHash)|
   Width=426
   Height=382
   VOffset=287
   HOffset=224
   link(doLoad,2204106:doCopy,[(32,314)(32,118)])
   link(doHash,3991985:doRead,[(39,321)(39,307)])
   link(doStop,4635615:doWork2,[(60,328)(60,363)])
   link(VocStream,13641125:Var3,[(251,187)])
   link(Pos,2630774:Var1,[(258,306)])
  }
  Add(ArrayRW,3123448,294,203)
  {
   link(onRead,314531:doWrite,[])
   link(Array,1903610:Var2,[])
   link(Value,14531255:Var2,[])
  }
  Add(MemoryStream,2204106,49,112)
  {
   link(onCopy,15738292:doOperation,[])
  }
  Add(For,13673247,105,217)
  {
   Step=-1
   InData=0
   link(onEvent,4247253:doEvent1,[])
  }
  Add(Hub,4247253,154,217)
  {
   link(onEvent1,12366427:doWork2,[])
   link(onEvent2,8348129:doGet,[(179,230)(179,209)])
  }
  Add(DataToFileEx,8348129,196,203)
  {
   DataSize=3
   Point(doPosition)
   link(onGet,12097523:doEvent1,[])
   link(Stream,13641125:Var2,[])
  }
  Add(Math,15738292,105,112)
  {
   OpType=1
   Op2=2
   ResultType=0
   link(onResult,7061963:doEvent1,[])
   link(Op1,2204106:Size,[(111,103)(97,103)(97,152)(62,152)])
  }
  Add(ArrayRW,314531,350,196)
  {
   link(Array,13276856:Var2,[])
   link(Index,14531255:Var3,[(363,187)])
  }
  Add(Hub,12097523,266,203)
  {
   link(onEvent1,3123448:doRead,[])
   link(onEvent2,3123448:doWrite,[])
  }
  Add(GetDataEx,14531255,308,182)
  {
   Angle=3
   link(Data,13673247:Position,[(258,187)(258,257)(111,257)])
  }
  Add(Hub,7061963,154,112)
  {
   OutCount=3
   link(onEvent1,12237287:doData,[])
   link(onEvent2,3054796:doCount,[])
   link(onEvent3,6037519:doOperation,[(179,132)(179,202)(46,202)(46,223)])
  }
  Add(GetDataEx,1903610,294,154)
  {
   link(Data,10262139:Array,[])
  }
  Add(If_else,2046476,119,301)
  {
   Type=4
   Op2=Integer(0)
   link(onTrue,14186977:doEvent1,[])
  }
  Add(Repeat,1024522,210,322)
  {
   link(onRepeat,11909561:doRead,[])
  }
  Add(ArrayRW,11909561,266,322)
  {
   link(onRead,15153304:doCompare,[])
   link(Array,13276856:Var3,[(272,166)])
   link(Index,2630774:Var2,[])
  }
  Add(GetDataEx,13276856,350,161)
  {
   link(Data,3054796:Array,[])
  }
  Add(If_else,15153304,322,322)
  {
   Type=4
   Op2=Integer(0)
   link(onTrue,3557159:doEvent1,[])
   link(onFalse,4635615:doWork1,[(361,335)(361,363)])
  }
  Add(Memory,9048510,273,259)
  {
   link(onData,7181297:doOperation,[])
  }
  Add(Hub,3557159,371,322)
  {
   link(onEvent1,16340614:doWork3,[(396,328)(396,300)(256,300)])
   link(onEvent2,10199030:onNextPos,[(403,335)(403,321)])
  }
  Add(HubEx,16340614,252,259)
  {
   link(onEvent,9048510:doValue,[])
  }
  Add(GetDataEx,2630774,273,301)
  {
   link(Data,9048510:Value,[])
  }
  Add(Math,6037519,56,217)
  {
   OpType=1
   Op2=1
   ResultType=0
   link(onResult,13673247:doFor,[])
  }
  Add(ArrayRW,3991985,70,301)
  {
   link(onRead,2046476:doCompare,[])
   link(Array,1903610:Var1,[(76,159)])
  }
  Add(Hub,14186977,168,301)
  {
   OutCount=4
   link(onEvent1,16340614:doWork2,[(200,307)(200,265)])
   link(onEvent2,10199030:onFirstPos,[])
   link(onEvent3,1024522:doRepeat,[(200,321)(200,328)])
   link(onEvent4,10199030:onEndList,[(193,328)(193,370)(410,370)(410,328)])
  }
  Add(GetDataEx,13641125,196,182)
  {
   Angle=3
   link(Data,2204106:Stream,[(55,187)])
  }
  Add(Math,7181297,322,259)
  {
   Op2=3
   ResultType=0
   link(onResult,12366427:doWork3,[(361,265)(361,251)(186,251)])
  }
  Add(HubEx,12366427,182,217)
  {
   link(onEvent,8348129:doPosition,[])
  }
  Add(HubEx,4635615,196,357)
  {
   Angle=3
   link(onEvent,1024522:doStop,[(200,335)])
  }
  Add(DoData,12237287,189,112)
  {
   Data=Integer(-1)
   link(onEventData,10262139:doFillData,[])
   AddHint(0,-30,24,13,Data)
  }
  Add(SimpleArray,3054796,350,112)
  {
   @Hint=#16:Tail of HashList|
   Point(doCount)
   AddHint(-12,-30,88,13,@Hint)
  }
  Add(SimpleArray,10262139,294,112)
  {
   @Hint=#17:Entry to HashList|
   Count=16777216
   AddHint(-66,-30,95,13,@Hint)
  }
END_SDK
Add(Hub,9275719,511,168)
{
 OutCount=3
 link(onEvent1,12827354:doWork2,[(541,174)(541,125)])
 link(onEvent2,3779604:doData,[(543,181)(543,216)])
 link(onEvent3,598827:doWork2,[(536,188)(536,265)])
}
Add(Hub,8703109,553,161)
{
 OutCount=3
 link(onEvent1,12827354:doWork3,[(578,167)])
 link(onEvent2,9787654:doValue,[])
 link(onEvent3,598827:doWork1,[(578,181)])
}
Add(Application,6093389,595,119)
{
 Wait=1
 Point(onTerminate)
 link(onTerminate,9129885:doWork3,[(634,125)(634,111)])
}
Add(Hub,11711312,273,147)
{
 link(onEvent1,9769920:doStop,[(438,153)(438,181)])
 link(onEvent2,3827780:doStop,[(298,160)(298,195)])
}
Add(Button,15189132,42,105)
{
 Left=252
 Top=14
 Width=34
 Caption="Стоп"
 link(onClick,9129885:doWork2,[])
}
Add(StrCatDelim,198127,273,56)
{
 Str1="Время загрузки/индексации "
 Str2=" мсек"
 link(onStrCatDlm,16091653:doWork2,[])
}
Add(HubEx,9129885,252,105)
{
 Angle=1
 link(onEvent,11711312:doEvent1,[(256,153)])
}
Add(ODialog,3944805,84,168)
{
 link(onExecute,7806628:doOpen,[])
}
Add(MemoryStream,7170827,245,182)
{
 link(onCopy,3827780:doFor,[])
}
Add(DataToFileEx,4127981,399,168)
{
 DataSize=3
 Point(doPosition)
 link(onGet,9769920:doHash,[])
 link(Stream,6157586:Var2,[])
}
Add(Hub,180655,364,182)
{
 link(onEvent1,4127981:doPosition,[])
 link(onEvent2,4127981:doGet,[(389,195)(389,174)])
}
Add(Hub,15415920,182,168)
{
 OutCount=5
 link(onEvent1,14010202:doClear,[(228,174)(228,335)])
 link(onEvent2,9718670:doTimer,[(221,181)(221,356)])
 link(onEvent3,7170827:doCopy,[])
 link(onEvent4,9718670:doStop,[(214,195)(214,363)])
 link(onEvent5,7806628:doClose,[(207,202)(207,216)(123,216)(123,181)])
}
Add(Math,16582522,364,350)
{
 OpType=2
 Op2=100
 ResultType=0
 link(onResult,14219118:doData,[])
}
Add(HubEx,12827354,574,119)
{
 link(onEvent,6093389:doProcessMessages,[])
}
Add(Memory,9787654,595,168)
{
 Point(Data)
 link(Data,4978821:Position,[(601,159)(636,159)(636,236)(748,236)])
}
Add(DataToFileEx,4978821,735,196)
{
 Point(Position)
 Point(doPosition)
 link(Stream,16410524:Var2,[])
}
Add(DoData,3779604,595,210)
{
 link(onEventData,4978821:doPosition,[])
 link(Data,9787654:Value,[])
}
Add(GetDataEx,6157586,399,140)
{
 Angle=3
 link(Data,7170827:Stream,[(356,145)(356,222)(251,222)])
}
Add(Repeat,13622019,637,266)
{
 link(onRepeat,1662931:doGet,[])
}
Add(DataToFileEx,1662931,686,266)
{
 Point(onRdError)
 Point(Position)
 link(onGet,11436920:doCompare,[])
 link(Stream,9769920:VocStream,[(692,250)(468,250)])
 link(onRdError,15482775:doWork1,[(725,279)])
}
Add(If_else,11436920,735,266)
{
 link(onTrue,16690597:doNext,[(774,272)(774,251)])
 link(onFalse,15482775:doWork2,[(774,279)(774,307)])
 link(Op1,4978821:Data,[])
}
Add(HubEx,15482775,721,301)
{
 Angle=2
 link(onEvent,13622019:doStop,[(627,307)(627,279)])
}
Add(CounterEx,16690597,791,245)
{
 Min=3
 Max=1000000000
 Default=3
 Point(doReset)
}
Add(Hub,1010477,595,259)
{
 OutCount=3
 link(onEvent1,16690597:doReset,[(620,265)(620,258)])
 link(onEvent2,13622019:doRepeat,[])
 link(onEvent3,204999:doCompare,[(620,279)(620,349)])
}
Add(HubEx,598827,574,259)
{
 link(onEvent,1010477:doEvent1,[])
}
Add(If_else,204999,791,343)
{
 Type=4
 link(onTrue,6477243:doHEX,[])
 link(Op1,11624451:Var2,[])
 link(Op2,3089555:Value,[(804,285)(839,285)])
}
Add(Edit,15507716,791,196)
{
 Left=182
 Top=14
 Width=57
 Hint="Минимальная длина для вывода в таблицу"
 Text="5"
 Alignment=1
 DataType=1
 link(onChange,3089555:doValue,[])
}
Add(StringTable,14010202,1029,322)
{
 Top=43
 Width=418
 Height=316
 Align=5
 Font=[Lucida Console,8,0,0,204]
 Columns=#14:Поз.Образца=90|14:Поз.Словаря=90|8:Длина=60|17:Найденный HEX=158|
 ColumnClick=1
 Point(doSelect)
 Point(doEnsureVisible)
 Point(doSortDigit)
 Point(onColumnClick)
 link(onColumnClick,14010202:doSortDigit,[(1068,335)(1068,384)(1019,384)(1019,363)])
}
Add(FormatStr,8234335,889,343)
{
 DataCount=4
 Mask="%1;%2;%3;%4"
 link(onFString,8212874:doEvent1,[])
 link(Str1,13703200:Var3,[(895,327)])
 link(Str2,11030346:Var3,[(902,320)])
 link(Str3,7121260:Var3,[(909,313)])
}
Add(GetDataEx,15696705,315,322)
{
 link(Data,3827780:Position,[])
}
Add(GetDataEx,161234,287,224)
{
 Angle=3
 link(Data,7170827:Size,[(258,229)])
}
Add(HubEx,16091653,315,56)
{
 Angle=1
 link(onEvent,14415943:doCaption,[(319,69)])
}
Add(Hub,8212874,938,343)
{
 link(onEvent1,14010202:doAdd,[(963,349)(963,328)])
 link(onEvent2,12094826:doOperation,[])
}
Add(Math,12094826,966,350)
{
 OpType=1
 Op2=1
 ResultType=0
 link(onResult,14010202:doEnsureVisible,[])
 link(Op1,14010202:Count,[(972,341)(1007,341)(1007,376)(1035,376)])
}
Add(GetDataEx,2816362,462,322)
{
 Angle=3
 link(Data,15696705:Var3,[])
}
Add(GetDataEx,11624451,791,308)
{
 link(Data,16690597:Count,[])
}
Add(Memory,3089555,833,196)
{
 Default=Integer(5)
}
Add(MultiElementEx,6477243,840,343)
{
 @Hint=#65:Вывод HEX-строкой фрагмента файла (с позиции Pos и длиной Length)|
 Name="Hex"
 link(Stream,16410524:Var3,[(846,145)])
 link(Pos,13703200:Var2,[])
 link(Length,7121260:Var2,[])
 link(onResult,8234335:doString,[])
 AddHint(-87,38,197,26,@Hint)
}
BEGIN_SDK
  Add(EditMultiEx,7064033,21,21)
  {
   WorkCount=#43:doHEX=Преобразование фрагмента в HEX-строку|0:|
   EventCount=#29:onResult=HEX-строка на выходе|
   DataCount=#61:Stream=Поток, фрагмент из которого преобразуется в HEX-строку|21:Pos=Позиция фрагмента|22:Length=Длина фрагмента|
   Width=272
   Height=151
   VOffset=98
   HOffset=112
   link(doHEX,4501688:doEvent1,[])
  }
  Add(MemoryStream,13175504,182,49)
  {
  }
  Add(StreamConvertor,1590622,238,119)
  {
   link(onResult,7064033:onResult,[])
   link(Data,16026769:Var3,[(244,96)])
  }
  Add(StreamCopy,11268055,182,119)
  {
   link(onCopy,1590622:doConvert,[])
   link(Dest,16026769:Var2,[])
   link(Source,7216814:Var3,[(195,103)])
   link(Count,7064033:Length,[(202,33)(153,33)])
  }
  Add(Hub,4501688,42,119)
  {
   OutCount=3
   link(onEvent1,13175504:doClear,[(67,125)(67,62)])
   link(onEvent2,14523250:doData,[])
   link(onEvent3,11268055:doCopy,[(172,139)(172,125)])
  }
  Add(DataToFileEx,14984113,133,112)
  {
   Point(doPosition)
   link(Stream,7216814:Var2,[])
  }
  Add(DoData,14523250,84,126)
  {
   link(onEventData,14984113:doPosition,[])
   link(Data,7064033:Pos,[(90,33)(146,33)])
  }
  Add(GetDataEx,7216814,133,98)
  {
   link(Data,7064033:Stream,[])
  }
  Add(GetDataEx,16026769,182,91)
  {
   link(Data,13175504:Stream,[])
  }
END_SDK
Add(GetDataEx,13703200,847,322)
{
 Angle=3
 link(Data,2816362:Var3,[])
}
Add(GetDataEx,16410524,735,140)
{
 Angle=3
 link(Data,6157586:Var3,[])
}
Add(GetDataEx,7121260,854,308)
{
 Angle=3
 link(Data,11624451:Var3,[])
}
Add(GetDataEx,11030346,469,315)
{
 link(Data,9769920:Pos,[])
}

--- Добавлено в 2020-03-22 16:29:29

Вот он, не побоюсь этого слова - SimpleArray

Редактировалось 10 раз(а), последний 2020-03-26 17:32:59
карма: 9

0
файлы: 1SimpleArray.rar [2.7KB] [409]
Ответов: 8911
Рейтинг: 823
#34: 2020-03-22 17:57:24 ЛС | профиль | цитата
Galkov, я и начинал с трёхбайтной индексации, только 50/50 программка вылетала без предупреждения
Не имея достаточных знаний, решил, что не хватает заказываемой при запуске памяти и перешёл на двухбайтную индексацию
карма: 19

0
Ответов: 9906
Рейтинг: 351
#35: 2020-03-23 16:11:37 ЛС | профиль | цитата
Все мы чего то не имеем в достаточном количестве...........
Данный форум может являться полигоном для набора некоторого опыта, который на следующем этапе будет являться уже и знанием.
Если им правильно пользоваться.

А по факту - вещь удивительная. Начинали с неких ТераОпов, даже дискутировали о названии сего дикого числа.
А кончили, при сравнении RND_20 и RND_19 (1М сравниваем с 512К) -- 32-мя КилоОпами за 0.18 сек.
SearchMatches.png
В такой схеме:
Мой код, переделанный под 3-байтную индексацию, и ранее инжектированный в схему Леонида

Add(Label,1824696,427,91)
{
 @Hint=#26:А чтобы никто не догадался|
 Width=100
 Height=286
 Align=1
 Caption=""
 AutoSize=1
 AddHint(-59,-23,158,13,@Hint)
}
Add(Button,6300579,35,35)
{
 Left=10
 Top=5
 Width=70
 Caption="Open 2 files"
 link(onClick,908814:doExecute,[])
}
Add(Edit,6253556,280,84)
{
 Left=65
 Top=40
 Width=25
 Text="5"
 DataType=2
}
Add(Label,5760286,280,35)
{
 Left=7
 Top=35
 Width=61
 Height=32
 Caption="Number of\r\nbytes >="
 AutoSize=1
 Alignment=2
}
Add(Button,13033686,35,161)
{
 Left=15
 Top=125
 Caption="Search"
 link(onClick,6984947:doEvent1,[])
}
Add(ODialog,908814,84,35)
{
 Title="Open first file"
 link(onExecute,14252828:doEvent1,[])
}
Add(ODialog,9007154,84,84)
{
 Title="Open second file"
 link(onExecute,4645375:doEvent1,[])
}
Add(Hub,14252828,126,35)
{
 OutCount=3
 link(onEvent1,14151222:doOpen,[])
 link(onEvent2,14151222:doClose,[])
 link(onEvent3,9007154:doExecute,[(151,55)(151,76)(74,76)(74,90)])
}
Add(FileStream,14151222,168,35)
{
 link(onLoad,9951475:doCopy,[])
}
Add(FileStream,6090657,168,84)
{
 link(onLoad,7759878:doCopy,[])
}
Add(Button,5547259,35,217)
{
 Left=15
 Top=202
 Caption="Save"
 link(onClick,9381149:doExecute,[])
}
Add(InlineCode,9739546,224,182)
{
 WorkPoints=#31:doSearchStream=Поиск совпадений|
 EventPoints=#6:onTime|48:onRes=Позиции начала совпадения, разделитель ";"|
 VarPoints=#8:compares|
 DataPoints=#46:Stream1=Данные 1-го файла (нужен MemoryStream)|46:Stream2=Данные 2-го файла (нужен MemoryStream)|35:Num=Количество байтов для сравнения|
 Code=#15:unit HiAsmUnit;|0:|9:interface|0:|21:uses kol,Share,Debug;|0:|4:type|29:  THiAsmClass = class(TDebug)|11:    private|34:      Entry,Tail:Array of integer;|16:      dbg:int64;|10:    public|45:      onTime,onRes:THI_Event;        //Events|44:      Stream1,Stream2,Num:THI_Event; //Datas|25:      constructor Create;|60:      procedure doSearchStream(var _Data:TData; Index:word);|54:      procedure compares(var _Data:TData; Index:word);|6:  end;|0:|14:implementation|0:|31:constructor THiAsmClass.Create;|5:begin|12:  inherited;|29:  SetLength(Entry, $1000000);|4:end;|0:|37:procedure THiAsmClass.doSearchStream;|15:var ST:PStream;|14:  F1,F2:PChar;|43:  _Len1,_Len2,_Len, i, j,k,_Min,_A:integer;|11:  s:string;|5:begin|35:  ST := ReadStream(_Data, Stream1);|24:  if ST = nil then Exit;|19:  _Len1 := ST.Size;|18:  F1 := ST.Memory;|35:  ST := ReadStream(_Data, Stream2);|24:  if ST = nil then Exit;|19:  _Len2 := ST.Size;|18:  F2 := ST.Memory;|82:  _Min := ReadInteger(_Data, Num, 4);    //Минимальное количество совпадающих байт|29:  if _Min < 3 then _Min := 3;|59:  FillChar(Entry[0], sizeof(Entry[0])*Length(Entry), #$FF);|27:  SetLength(Tail, _Len2-2);|30://---Файл второй -- индексация|22:  _hi_OnEvent(onTime);|21:  _Len:=_Len2 - _Min;|33:  for i := _Len downto 0 do begin|61:    _A :=ord(F2[i])shl 16 + ord(F2[i+1])shl 8 + ord(F2[i+2]);|25:    Tail[i] := Entry[_A];|18:    Entry[_A] := i|6:  end;|25://---Файл первый -- поиск|22:  _hi_OnEvent(onTime);|23:  _Len := _Len1 - _Min;|11:  dbg := 0;|29:  for i := 0 to _Len do begin|68:    j := Entry[ord(F1[i])shl 16 + ord(F1[i+1])shl 8 + ord(F1[i+2])];|25:    while j >= 0 do begin|16:      inc(dbg); |90:      _A := 3;                                 //Три первых байта совпадают по определению|82:      while ((i+_A)<_Len1)and((j+_A)<_Len2) do //Проверяем выход за размеры файлов|93:        if F1[i+_A]=F2[j+_A] then inc(_A)      //Увеличиваем кол-во совпавших байт на единицу|101:        else break;                            //Если уже не совпадают - длина совпадений уже найдена|105:      if _A>=_Min then begin //Если не менее установленного, выводим длину, позиции, и HEX - на индикацию|60:        s := int2str(_A)+';'+int2str(i)+';'+int2str(j)+';'; |63:        for k := 0 to _A-1 do s := s + int2hex(ord(F1[i+k]),2);|30:        _hi_OnEvent(onRes, s);|10:      end;|19:      j := Tail[j];|8:    end;|6:  end;|4:end;|0:|31:procedure THiAsmClass.compares;|5:begin|21:  dtReal(_Data, dbg);|4:end;|0:|4:end.|
 link(onTime,5441784:doWork2,[])
 link(onRes,11582479:doAdd,[])
 link(Stream1,9951475:Stream,[])
 link(Stream2,7759878:Stream,[])
 link(Num,6253556:Text,[(244,131)(286,131)])
}
Add(Hub,4645375,126,84)
{
 link(onEvent1,6090657:doOpen,[])
 link(onEvent2,6090657:doClose,[])
}
Add(LED,15486262,427,147)
{
 Left=30
 Top=157
 Height=32
 Shape=1
}
Add(Hub,6984947,119,161)
{
 OutCount=4
 link(onEvent1,15486262:doOn,[])
 link(onEvent2,12086:doStart,[(340,174)(340,181)])
 link(onEvent3,11582479:doClear,[(214,181)(214,202)])
 link(onEvent4,11956262:doStart,[])
}
Add(SDialog,9381149,84,217)
{
 Filter="TXT|*.txt"
 link(onExecute,11582479:doSave,[])
}
Add(Thread,11956262,168,182)
{
 Delay=0
 FastStop=0
 link(onExec,9739546:doSearchStream,[])
 link(onSyncExec,15749816:doData,[(207,195)(207,244)])
}
Add(TimeCounter,12086,350,175)
{
 link(onStop,3828704:doEvent1,[])
}
Add(StrList,11582479,280,189)
{
 Point(doSave)
}
Add(FormatStr,13053289,420,252)
{
 DataCount=5
 Mask="Found %1 (%5) matches in (%2,%3,%4) мs"
 link(onFString,5052926:doWork2,[])
 link(Str1,11582479:Count,[(426,236)(293,236)])
 link(Str2,16099733:Value1,[])
 link(Str3,16099733:Value2,[])
 link(Str4,16099733:Value3,[])
}
Add(StringTable,4173653,350,266)
{
 Left=100
 Width=322
 Height=261
 Align=5
 Font=[Lucida Console,8,0,0,0]
 Columns=#18:Matches length=100|21:Pos in first file=100|22:Pos in second file=100|18:Matches in HEX=200|
 Grid=0
 ColumnClick=1
 Point(doSortDigit)
 Point(onColumnClick)
 link(onColumnClick,4173653:doSortDigit,[(389,279)(389,307)(340,307)(340,293)])
}
Add(ArrayEnum,156378,294,266)
{
 link(onItem,4173653:doAdd,[])
 link(Array,11582479:Array,[])
}
Add(Hub,2244651,266,238)
{
 OutCount=5
 link(onEvent1,5441784:doWork3,[(319,244)])
 link(onEvent2,15486262:doOff,[(389,251)(389,160)])
 link(onEvent3,13053289:doString,[])
 link(onEvent4,4173653:doClear,[(333,265)(333,279)])
 link(onEvent5,156378:doEnum,[])
}
Add(MemoryStream,9951475,224,35)
{
}
Add(MemoryStream,7759878,231,84)
{
}
Add(HubEx,5441784,315,182)
{
 link(onEvent,12086:doStop,[])
}
Add(HubEx,5052926,476,252)
{
 link(onEvent,5996595:doCaption,[])
}
Add(MemFIFO,16099733,427,189)
{
 Count=3
}
Add(MainForm,5996595,497,252)
{
 Width=438
}
Add(Hub,3828704,399,182)
{
 link(onEvent1,5052926:doWork1,[(480,188)])
 link(onEvent2,16099733:doValue,[])
}
Add(DoData,15749816,224,238)
{
 link(onEventData,2244651:doEvent1,[])
 link(Data,9739546:compares,[])
}

Такое не часто случается, однако.

Редактировалось 8 раз(а), последний 2020-03-26 17:31:05
карма: 9

1
Голосовали:zhorik5
Ответов: 8911
Рейтинг: 823
#36: 2020-03-23 20:51:45 ЛС | профиль | цитата
Galkov, запустил, ну очень быстро! Посмотрел, заодно поучился спасибо!
карма: 19

0
Ответов: 192
Рейтинг: 2
#37: 2020-03-24 14:28:06 ЛС | профиль | цитата
Galkov писал(а):
В такой схеме:

надо компонент малость исправить описание точек


карма: 0

0
Ответов: 9906
Рейтинг: 351
#38: 2020-03-24 15:52:40 ЛС | профиль | цитата
Ну да... В трех схемах - исправил.
карма: 9

0
Ответов: 192
Рейтинг: 2
#39: 2020-03-24 16:17:09 ЛС | профиль | цитата
А вообще очень интересное решение, с помощью данной реализации даже не нужно делать сдвиги. На мой взгляд это пока идеальный принцип поиска.

Редактировалось 1 раз(а), последний 2020-03-25 10:08:27
карма: 0

0
Ответов: 9906
Рейтинг: 351
#40: 2020-03-25 15:24:53 ЛС | профиль | цитата
Добавил вывод HEX-найденного в таблицу в две схемы с 3-байтной индексацией (мне показалось, что была такая заявка).
Одна - совсем без IC (моя предпоследняя, с SimpleArray)
Вторая с IC (последняя).

Кстати, а чего это народ отмалчивается... Было конкретное предложение о добавлении элемента.
Tad у нас профессиональный тестер (если мне не изменяет память). А nesco - профессиональный добавлятель.
Есть и еще очень не тривиальные коллеги. А молчат...
Че к чему

Редактировалось 7 раз(а), последний 2020-03-26 17:30:07
карма: 9

0
Ответов: 5227
Рейтинг: 587
#41: 2020-03-25 16:50:16 ЛС | профиль | цитата
Galkov писал(а):
Кстати, а чего это народ отмалчивается...

Вот и тут отмалчивались https://forum.hiasm.com/topic/65383
Чего удивительного...
Galkov писал(а):
А nesco - профессиональный добавлятель

Да ужжжжж
карма: 4
Мой форум - http://hiasm.bbtalk.me/ схемы, компоненты...
0
Ответов: 192
Рейтинг: 2
#42: 2020-03-31 13:33:09 ЛС | профиль | цитата
Galkov писал(а):
Было конкретное предложение о добавлении элемента.

Я за, штука нужная не каждый в коде понимает!
Galkov писал(а):
Tad
вообще давно не видел его. Надеюсь все хорошо у него.

Редактировалось 1 раз(а), последний 2020-03-31 13:35:29
карма: 0

0
42
ФорумыПомощь по пакетуПоиск одинаковых данных в дампе или сравнение двух файлов разного размера ← Ctrl123Ctrl →
Сообщение
...
Прикрепленные файлы
(файлы не залиты)
HiAsm Studio 2003 - 2024
Пользовательское соглашение | support@hiasm.com
Яндекс.Метрика