Top.Mail.Ru
Мастера DELPHI, Delphi programming community Титульная страница Поиск, карта сайта Написать письмо 
| Новости | Поиск | FAQ | Статьи | Книги | Новости VCL |
| Форумы ЧАТ | Орешник | KOL и MCK |
Форумы -» Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / RSDN.ORG

« предыдущая ветвь | форум | следующая ветвь »

Можно ли ускорить функцию? [D7, XP]


Страницы:   1 2 3

SergP ©   (2016-05-26 19:16:00) 

Написал функцию:


...
type TMSet = packed array[0..2] of integer;

type TWork=packed record
  field:int64;
  MSet:TMset;
  Probe:Extended;
  end;
...

function GetEntrance(var BigSource,SmallSource: Twork):Twork;
var
 i,i2,j,j2,k,cells:byte;
 BigPermit,SmallPermit:TMset;
 BigMask,SmallMask:integer;
begin
 for i:=0 to 2 do
 begin
   BigPermit[i]:=0;
   SmallPermit[i]:=0;
   result.MSet[i]:=0;
 end;
 Result.field:=BigSource.field xor SmallSource.field;
 cells:=bitcount(Result.field).count; // количество ячеек в разностной группе
 for i:=0 to 2 do
 begin
   BigMask:=1;
   for i2:=0 to 29 do
   begin
     if (BigSource.MSet[i] and BigMask) = BigMask then for j:=0 to i do
     begin
       SmallMask:=1;
       for j2:=0 to i2 do
       begin
         if ((SmallSource.MSet[j] and SmallMask)=SmallMask) and ((i2 mod 6) >= (j2 mod 6)) and (i-j+((i2-j2) div 6)+((i2-j2) mod 6)<=cells)   then
         begin
           k:=i-j;
           BigPermit[i]:=BigPermit[i] or BigMask;
           SmallPermit[j]:=SmallPermit[j] or SmallMask;
           Result.MSet[k]:=Result.MSet[k] or (1 shl (i2-j2));
         end;
         SmallMask:=SmallMask shl 1;
       end;
     end;
     BigMask:=BigMask shl 1;
   end;
 end;
 BigSource.MSet:=BigPermit;
 SmallSource.MSet:=SmallPermit;
 if ((Bigsource.MSet[0] or Bigsource.MSet[1] or Bigsource.MSet[2])=0)
   or ((Smallsource.MSet[0] or SmallSource.MSet[1] or SmallSource.MSet[2])=0)
   or ((Result.MSet[0] or Result.MSet[1] or Result.MSet[2])=0) then raise Exception.Create('Error GetEntrance');
end;


Если нужно описание что делает функция, то суть такова:
У нас имеются 3 разновидности неких сущностей, назовем их A, B, С
Их количество ограничено. Сущностей типа A может быть от 0 до 2, B - от 0 до 4, C - от 0 до 5
Имеются некие ячейки. В ячейке может быть размещена либо одна из сущностей, либо ячейка может быть пустой.
Несколько ячеек назовем группой.
Имеются 2 группы, назовем большая и маленькая. маленькая является частью большой.
TMset, т.е. (mset[2],mset[1],mset[0]) описывает множество комбинаций сушностей и пустых ячеек в группе, всего для этого нужно 90 бит
у меня используются 3 числа типа integer, у каждого из которых используется по 30 бит.
Например (1,0,0) означает что в группе имеются 2 штуки A
(0,0,1) означает что группа пустая
(2,128,16384) означает что группа может состоять из 2А+С, либо A+B+C, либо 2*B+2*C
и т.д.
Суть думаю ясна.
Нужно найти множество комбинаций сушностей для новой группы, которая равна разности большой и маленькой групп,
с корректированием исходных данных (отбросить заведомо неприемлимые комбинации в исходных данных)
Если в результате образуется (0,0,0) в любой из групп (большой, маленькой, разностной), то генерируем исключение,
ибо это означает на ошибку в исходных данных, и далее продолжать вычисления безсмысленно.

В процессе расчетов функция вызывается сотни тысяч раз, возможно и более миллиона. Хотелось бы, чтобы она работала побыстрее.
Оформить это все в виде таблицы понятно, что нереально.
Использовать какие-то промежуточные таблицы реальных размеров - пока не могу придумать как.
Пока думал внутренний цикл поменять например с
for j2:=0 to i2 do
на
for j2:=i2 downto 0 do
но это даже если и даст какое-то ускорение, то уж очень мизерное.
Подскажите, что еще тут можно оптимизировать?

SergP   (2016-06-22 15:49:00) [1]

А. ну там еще табличные данные есть
const
GentArr:packed array[0..29,0..15] of integer=(
(0,0,0,0,$00000001,$00000043,$000010C7,$000431CF,$010C73DF,$031CF7FF,$073DFFFF,$ 0F7FFFFF,$1FFFFFFF,$3FFFFFFF,$3FFFFFFF,$3FFFFFFF),
(0,0,0,0,$00000002,$00000086,$0000218E,$0008639E,$0218E7BE,$0639EFBE,$0E7BEFBE,$ 1EFBEFBE,$3EFBEFBE,$3EFBEFBE,$3EFBEFBE,$3EFBEFBE),
(0,0,0,0,$00000004,$0000010C,$0000431C,$0010C73C,$0431CF3C,$0C73CF3C,$1CF3CF3C,$ 3CF3CF3C,$3CF3CF3C,$3CF3CF3C,$3CF3CF3C,$3CF3CF3C),
(0,0,0,0,$00000008,$00000218,$00008638,$00218E38,$08638E38,$18E38E38,$38E38E38,$ 38E38E38,$38E38E38,$38E38E38,$38E38E38,$38E38E38),
(0,0,0,0,$00000010,$00000430,$00010C30,$00430C30,$10C30C30,$30C30C30,$30C30C30,$ 30C30C30,$30C30C30,$30C30C30,$30C30C30,$30C30C30),
(0,0,0,0,$00000020,$00000820,$00020820,$00820820,$20820820,$20820820,$20820820,$ 20820820,$20820820,$20820820,$20820820,$20820820),
(0,0,0,0,$00000040,$000010C0,$000431C0,$010C73C0,$031CF7C0,$073DFFC0,$0F7FFFC0,$ 1FFFFFC0,$3FFFFFC0,$3FFFFFC0,$3FFFFFC0,$3FFFFFC0),
(0,0,0,0,$00000080,$00002180,$00086380,$0218E780,$0639EF80,$0E7BEF80,$1EFBEF80,$ 3EFBEF80,$3EFBEF80,$3EFBEF80,$3EFBEF80,$3EFBEF80),
(0,0,0,0,$00000100,$00004300,$0010C700,$0431CF00,$0C73CF00,$1CF3CF00,$3CF3CF00,$ 3CF3CF00,$3CF3CF00,$3CF3CF00,$3CF3CF00,$3CF3CF00),
(0,0,0,0,$00000200,$00008600,$00218E00,$08638E00,$18E38E00,$38E38E00,$38E38E00,$ 38E38E00,$38E38E00,$38E38E00,$38E38E00,$38E38E00),
(0,0,0,0,$00000400,$00010C00,$00430C00,$10C30C00,$30C30C00,$30C30C00,$30C30C00,$ 30C30C00,$30C30C00,$30C30C00,$30C30C00,$30C30C00),
(0,0,0,0,$00000800,$00020800,$00820800,$20820800,$20820800,$20820800,$20820800,$ 20820800,$20820800,$20820800,$20820800,$20820800),
(0,0,0,0,$00001000,$00043000,$010C7000,$031CF000,$073DF000,$0F7FF000,$1FFFF000,$ 3FFFF000,$3FFFF000,$3FFFF000,$3FFFF000,$3FFFF000),
(0,0,0,0,$00002000,$00086000,$0218E000,$0639E000,$0E7BE000,$1EFBE000,$3EFBE000,$ 3EFBE000,$3EFBE000,$3EFBE000,$3EFBE000,$3EFBE000),
(0,0,0,0,$00004000,$0010C000,$0431C000,$0C73C000,$1CF3C000,$3CF3C000,$3CF3C000,$ 3CF3C000,$3CF3C000,$3CF3C000,$3CF3C000,$3CF3C000),
(0,0,0,0,$00008000,$00218000,$08638000,$18E38000,$38E38000,$38E38000,$38E38000,$ 38E38000,$38E38000,$38E38000,$38E38000,$38E38000),
(0,0,0,0,$00010000,$00430000,$10C30000,$30C30000,$30C30000,$30C30000,$30C30000,$ 30C30000,$30C30000,$30C30000,$30C30000,$30C30000),
(0,0,0,0,$00020000,$00820000,$20820000,$20820000,$20820000,$20820000,$20820000,$ 20820000,$20820000,$20820000,$20820000,$20820000),
(0,0,0,0,$00040000,$010C0000,$031C0000,$073C0000,$0F7C0000,$1FFC0000,$3FFC0000,$ 3FFC0000,$3FFC0000,$3FFC0000,$3FFC0000,$3FFC0000),
(0,0,0,0,$00080000,$02180000,$06380000,$0E780000,$1EF80000,$3EF80000,$3EF80000,$ 3EF80000,$3EF80000,$3EF80000,$3EF80000,$3EF80000),
(0,0,0,0,$00100000,$04300000,$0C700000,$1CF00000,$3CF00000,$3CF00000,$3CF00000,$ 3CF00000,$3CF00000,$3CF00000,$3CF00000,$3CF00000),
(0,0,0,0,$00200000,$08600000,$18E00000,$38E00000,$38E00000,$38E00000,$38E00000,$ 38E00000,$38E00000,$38E00000,$38E00000,$38E00000),
(0,0,0,0,$00400000,$10C00000,$30C00000,$30C00000,$30C00000,$30C00000,$30C00000,$ 30C00000,$30C00000,$30C00000,$30C00000,$30C00000),
(0,0,0,0,$00800000,$20800000,$20800000,$20800000,$20800000,$20800000,$20800000,$ 20800000,$20800000,$20800000,$20800000,$20800000),
(0,0,0,0,$01000000,$03000000,$07000000,$0F000000,$1F000000,$3F000000,$3F000000,$ 3F000000,$3F000000,$3F000000,$3F000000,$3F000000),
(0,0,0,0,$02000000,$06000000,$0E000000,$1E000000,$3E000000,$3E000000,$3E000000,$ 3E000000,$3E000000,$3E000000,$3E000000,$3E000000),
(0,0,0,0,$04000000,$0C000000,$1C000000,$3C000000,$3C000000,$3C000000,$3C000000,$ 3C000000,$3C000000,$3C000000,$3C000000,$3C000000),
(0,0,0,0,$08000000,$18000000,$38000000,$38000000,$38000000,$38000000,$38000000,$ 38000000,$38000000,$38000000,$38000000,$38000000),
(0,0,0,0,$10000000,$30000000,$30000000,$30000000,$30000000,$30000000,$30000000,$ 30000000,$30000000,$30000000,$30000000,$30000000),
(0,0,0,0,$20000000,$20000000,$20000000,$20000000,$20000000,$20000000,$20000000,$ 20000000,$20000000,$20000000,$20000000,$20000000));

SergP   (2016-06-22 15:48:00) [2]

И то правда... Как-то сразу не подумал об этом.

В результате получилась такая функция: (не знаю насколько сама функция теперь быстрее работает чем вариант Sha, но вся программа тестовый пример посчитала за 1м 44с вместо 4м 42с)

function GetEntrance(var BigSource, SmallSource: Twork): Twork;
 procedure ErrorRaiseException;
 begin
   raise Exception.Create('Error GetEntrance');
 end;
asm
         push ebx
         push esi
         push edi
         push ebp

         xor  ebp,ebp
         mov  ebx,[edx]
         xor  ebx,[eax]
         mov  [ecx],ebx
         jz   @nobit0
@cntbit0: lea  esi,[ebx-1]
         inc  ebp
         and  ebx,esi
         jnz  @cntbit0
@nobit0:  mov  ebx,[edx+$04]
         xor  ebx,[eax+$04]
         mov  [ecx+$04],ebx
         jz   @nobit1
@cntbit1: lea  esi,[ebx-1]
         inc  ebp
         and  ebx,esi
         jnz  @cntbit1
@nobit1:

         lea  edi,[ecx+$08]
         lea  esi,[edx+$08]
         mov  edx,[eax+$10]
         push edx
         mov  edx,[eax+$0C]
         push edx
         mov  edx,[eax+$08]
         push edx
         xor  edx,edx
         push edx
         push edx
         push edx
         push eax
         mov  [ecx+$08],edx
         mov  [ecx+$0C],edx
         mov  [ecx+$10],edx

         mov eax,ebp
         cmp  eax,11  // êîë-âî ÿ÷ååê áîëåå 11 âëèÿåò òàê æå êàê 11
         js  @next
         mov  eax,11
@next:    add  eax,4

         xchg edx,[esi]
@bgns0a:  bsf  ecx,edx
         jz  @ns0ex
@bgns0b:  btr  edx,ecx
         lea  ebp,[ecx*8]
         lea  ebp,[eax+ebp*2]
         lea  ebp,[ebp*4+GentArr]
@_ns0b0:  mov  ebx,[ebp]
         and  ebx,[esp+$10]
         jz   @ns0b1
         bts  [esi],ecx
         or   [esp+$04],ebx
         shr  ebx,cl
         or   [edi],ebx
@ns0b1:   mov  ebx,[ebp-$04]
         and  ebx,[esp+$14]
         jz   @ns0b2
         bts  [esi],ecx
         or   [esp+$08],ebx
         shr  ebx,cl
         or   [edi+$04],ebx
@ns0b2:   mov  ebx,[ebp-$08]
         and  ebx,[esp+$18]
         jz   @bgns0a
         bts  [esi],ecx
         or   [esp+$0C],ebx
         shr  ebx,cl
         or   [edi+$08],ebx
         bsf  ecx,edx
         jnz   @bgns0b

@ns0ex:   xor  edx,edx
         xchg edx,[esi+$04]
@bgns1a:  bsf  ecx,edx
         jz  @ns1ex
@bgns1b:  btr  edx,ecx
         lea  ebp,[ecx*8]
         lea  ebp,[eax+ebp*2]
         lea  ebp,[ebp*4+GentArr]
@_ns1b1:  mov  ebx,[ebp]
         and  ebx,[esp+$14]
         jz   @ns1b2
         bts  [esi+$04],ecx
         or   [esp+$08],ebx
         shr  ebx,cl
         or   [edi],ebx
@ns1b2:   mov  ebx,[ebp-$04]
         and  ebx,[esp+$18]
         jz   @bgns1a
         bts  [esi+$04],ecx
         or   [esp+$0C],ebx
         shr  ebx,cl
         or   [edi+$04],ebx
         bsf  ecx,edx
         jnz   @bgns1b

@ns1ex:   xor  edx,edx
         xchg edx,[esi+$08]
@bgns2a:  bsf  ecx,edx
         jz  @ns2ex
@bgns2b:  btr  edx,ecx
         lea  ebp,[ecx*8]
         lea  ebp,[eax+ebp*2]
         lea  ebp,[ebp*4+GentArr]
@_ns2b2:  mov  ebx,[ebp]
         and  ebx,[esp+$18]
         jz   @bgns2a
         bts  [esi+$08],ecx
         or   [esp+$0C],ebx
         shr  ebx,cl
         or   [edi],ebx
         bsf  ecx,edx
         jnz   @bgns2b
@ns2ex:
         pop  eax
         pop  edx
         mov  [eax+$08],edx
         pop  edx
         mov  [eax+$0C],edx
         pop  edx
         mov  [eax+$10],edx
         add  esp,12    // пропускаем 3 числа засунутые в стек, которые нам уже не нужны
         mov  eax,[edi]
         or   eax,[edi+$04]
         or   eax,[edi+$08]
         jnz  @noraise
         call ErrorRaiseException
@noraise: pop  ebp
         pop  edi
         pop  esi
         pop  ebx          
end;
Теоретически возможности для дальнейшей оптимизации должны иметься. Например более правильно использовать регистры, может где можно добиться спаривания. Хотя думаю что на этом можно и остановиться.

Rouse_   (2016-06-21 19:34:00) [3]

да сделай отдельную процедуру куда напиши

raise Exception.Create('Error GetEntrance');

и вызывай ее - че мучаться то?

SergP   (2016-06-21 18:48:00) [4]

а как быть с этим?

> :00461C6D A1146E4000              mov eax, dword ptr [00406E14]

Rouse_   (2016-06-21 11:44:00) [5]

call Exception.Create
call @RaiseExcept

SergP   (2016-06-21 08:31:00) [6]

Почти переписал все на ассемблере, значительно изменивши (счетчиков циклов там уже нет, осталось только 3 последовательных (не вложенных) цикла где не используются счетчики, ну и удалось задействовать табличные данные для удобства и ускорения (размером 2 кб). Не тестировал еще, так как находясь в больнице заниматься этим проблематично, в основном думать приходится используя тетрадь и ручку.
Только вот возник вопрос: Как вот эту часть там оформить?
 ... raise Exception.Create('Error GetEntrance');
?

В дизасемблированном виде оно выглядит так (без строки: "Error GetEntrance")

:00461C66 B98C1C4600              mov ecx, 00461C8C
:00461C6B B201                    mov dl, 01
:00461C6D A1146E4000              mov eax, dword ptr [00406E14]
:00461C72 E82D98FAFF              call 0040B4A4
:00461C77 E8741CFAFF              call 004038F0


Первая строчка это собственно загрузка адреса строки "Error GetEntrance"

что означают вторая и третяя строчки. А также где мне взять адреса єтих двух подпрограмм?

SergP   (2016-06-01 19:00:00) [7]


> SergP ©   (01.06.16 18:56) [44]
>
> Вот думаю, может попробовать представить это все в виде
> системы линейных уравнений, и решать по принципу метода
> Гаусса?...


Хотя так тоже свои проблемы будут. Например как учесть то условие, что количество переменных уравнения имеющих значение 3 может быть не более двух, 2 не более четырех и 1 не более пяти?

SergP   (2016-06-01 18:56:00) [8]

Вот думаю, может попробовать представить это все в виде системы линейных уравнений, и решать по принципу метода Гаусса?...

Rouse_   (2016-06-01 14:41:00) [9]

угу, вечерком гляну

SergP   (2016-06-01 14:32:00) [10]


> Rouse_ ©   (31.05.16 20:55) [40]
>
> Эммм... дык там же вообще практически на коленке пишется
> без извращений с оптимизацией...
>
> Выложи исходники, где там у тебя 2 часа думает и ТЗ само.
>


отправил на мыло, которое тут на сайте указано.

SergP   (2016-05-31 22:25:00) [11]


> Rouse_ ©   (31.05.16 20:55) [40]
>
> Эммм... дык там же вообще практически на коленке пишется
> без извращений с оптимизацией...
>


Хм. ты так уверен?


> Выложи исходники, где там у тебя 2 часа думает и ТЗ само.


На домашнем компе щас нет Дельфи. А исходники нужно еще привести в более-менее нормальный вид, и снабдить нормальными коментариями, ибо разобраться будет трудно. Завтра приведу в более-менее пригодный вид и выложу, желательно на мыло. просто довольно большой, 1.5 тысячи строк. Да еще и тестовые примеры нужно прицепить...

А насчет 2 часов - уже конечно во много раз быстрее, но тем не менее памяти жрет порядочно. Пока бывали ситуации когда по 60 мб под массивы сжирало.

ЗЫ Я поначалу думал что просто будет, перепробовал несколько вариантов представления данных, но остановился на последнем.
Когда писал программу для обычного сапера - то там все расчеты производились моментально, в процессе модификации исходных данных, т.е. даже не нужна была отдельная кнопка для запуска расчета, даже при тех данных, когда найденная в интернете подобная программа для обычного сапера, (которая в большинстве случаев тоже довольно быстро все просчитывала) была мной поставлена в тупик одним из вариантов исходных данных, когда она сказала что ждать конца расчетов осталось около 72 тыс. часов, т.е. около 9 лет.

Rouse_   (2016-05-31 20:55:00) [12]

Эммм... дык там же вообще практически на коленке пишется без извращений с оптимизацией...

Выложи исходники, где там у тебя 2 часа думает и ТЗ само.

SergP   (2016-05-31 20:30:00) [13]

Т.е. для обычного сапера там все намного проще было. давно написал. А это для такого себе "хитрого" сапера, с минами разного калибра...

SergP   (2016-05-31 20:29:00) [14]


> Rouse_ ©   (31.05.16 18:57) [37]
>
> Ты в итоге чего пишешь то?
> ИИ для сапера?


типа того...

Rouse_   (2016-05-31 18:57:00) [15]

Ты в итоге чего пишешь то?
ИИ для сапера?

SergP   (2016-05-31 18:41:00) [16]

М-да. Попался сложный пример, над которым программа думала около 2-х часов.

Вот только что прилепил бинарный поиск по массиву:
Если найдено такое значение, то производятся операции как и раньше (т.е. модификация имеющейся записи), если не найдено, то новая запись вставляется в массив так, чтобы массив поддерживался в отсортированном по возрастанию виде по полю field (int64), со сдвигом хвоста массива с помощью move.
Думал что это мало что даст из-за сдвигов.
Но протестил на том же примере, на котором программа работала более 2-х часов, и теперь она это посчитала на глаз где-то за минуты 1,5-2

)))

Sha   (2016-05-30 20:09:00) [17]

Еще, вероятно проверки перед циклами вроде

   if BigSource.MSet[i]<>0 then for i1:=0 to 4 do begin;

дадут небольшое ускорение

Sha   (2016-05-30 19:54:00) [18]

> переписал в отдельную функцию поиск по массиву на ассемблере

хорошо увидеть результат, вдруг там еще что осталось )

> даже не имею понятия как ускорить поиск

Я имел в виду, что, например, в потомке можно хранить индекс родительского множества.
В этом случае два вложенных цикла (по родителям и потомкам с проверкой на родство)
сведутся в один цикл по потомкам с известным родителем.

SergP   (2016-05-30 18:34:00) [19]


> Sha ©   (30.05.16 15:08) [31]
>
> При вычитании подмножества из множества всегда получается
> подмножество.
> Это можно учесть в коде, чтобы проще находить подмножества.
>


так поиск идет все равно по полю field. в некотором роде это тоже множество. Но это множество ячеек группы, а не мин
Честно говоря, даже не имею понятия как ускорить поиск, учитывая Ваше высказывания. Даже не представляю себе, что Вы имели ввиду.

SergP   (2016-05-30 18:20:00) [20]

На данный момент выделил и переписал в отдельную функцию поиск по массиву на ассемблере (Тут Rouse_ подсказал http://www.delphimaster.ru/cgi-bin/forum.pl?id=1464608311&n=3)
В результате учитывая вышеизложенное и также плюс Sha ©   (27.05.16 22:17) [18]
вместе оно дало уже ощутимый прирост.
На примере придуманному от балды, первоначальный код давал время расчетов 44 секунды, а с учетом обоих модификаций кода уже 20 секунд.
т.е. более чем в 2 раза.
И это я еще не пытался переписывать сабжевую функцию на ассемблере...

Страницы:   1 2 3

Наверх

Титульная страница Поиск, карта сайта Написать письмо