Можно ли ускорить функцию?

← →
SergP © (2016-05-26 19:16) [0]

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

... 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
но это даже если и даст какое-то ускорение, то уж очень мизерное.
Подскажите, что еще тут можно оптимизировать?

← →
Sha © (2016-05-26 21:59) [1]

лучше было бы описать задачу в терминах реального мира
вместо описания своего решения задачи

← →
SergP © (2016-05-27 10:46) [2]

> Sha © (26.05.16 21:59) [1]
>
> лучше было бы описать задачу в терминах реального мира
> вместо описания своего решения задачи

Хм. Вы считаете, что это описание непонятное или думаете что возможности для ускорения следует искать не только в этой функции, а и во всей логике вычислений?
Если второе, то я уже пробовал несколько разных вариантов, которые приходили в голову, например для группы хранить не множество возможных вариантов, а максимальные и минимальные количества "сущностей" разных типов. Но тогда точность расчетов страдает. А она имеет приоритет даже перед временем выполнения.

← →
SergP © (2016-05-27 12:57) [3]

Глянул на скомпилированный код функции. Такое ощущение что переписавши все на ассемблере можно ускорить довольно значительно...
Вот только подъизучить ассемблер придется... Хотя и невооруженным взглядом видны некоторые нерациональные вещи

← →
Jeer © (2016-05-27 13:39) [4]

См. [1]

← →
dmk © (2016-05-27 14:09) [5]

Все сделать в регистрах на ассемблере. Основная проблема всех этих вычислений в постоянной записи в память. Ускорение может быть в несколько раз.
Если работа с масками, то SIMD тут вне конкуренции. Asm + ssse3 + pshufb + 128 бит.

← →
SergP © (2016-05-27 14:41) [6]

> Jeer © (27.05.16 13:39) [4]
>
> См. [1]

Ну если это что-то изменит...
Вобщем есть в винде такая игра "Сапер". Это все знают.
существует несколько модифицированный сапер. Там мины 3-х видов (одинарная, двойная и тройная).
Так я пишу программу-помощник для такой игры.

Допустим мы ткнули в угол и получили 3,в углу она распространяется на три ячейки, значит возможные варианты 3, 2+1, 1+1+1
вот в моей программе каждый вариант кодируется соответствующим битом в массиве из 3-х integer: тройная мина в группе это (0,1,0), двойная с одинарной (0,0,128), три одинарных мины (0,0,8).
Т.е. для данной группы все возможные варианты кодируются (0,1,136)
далее ищем группы которые входят в другие, находим разность, также данная функция используется для расчета возможных вариантов в группе, которая является пересечением двух других.
Вот используя такие вещи, нужно вычислить расположение мин и пустых ячеек (разумеется насколько это возможно)

← →
Sha © (2016-05-27 14:51) [7]

> SergP © (27.05.16 10:46) [2]

И первое, и второе.

Например, вот это я не понял:
>Например (1,0,0) означает что в группе имеются 2 штуки A
>(0,0,1) означает что группа пустая
>(2,128,16384) означает что группа может состоять из 2А+С, либо A+B+C, либо 2*B+2*C

Возможно, потому что не представляю, какая исходная задача за всем этим кроется.
Поэтому хотелось бы увидеть условия задачи.
Опять же: одна голова хорошо...

← →
SergP © (2016-05-27 14:53) [8]

> dmk © (27.05.16 14:09) [5]
>
> Все сделать в регистрах на ассемблере. Основная проблема
> всех этих вычислений в постоянной записи в память. Ускорение
> может быть в несколько раз.
> Если работа с масками, то SIMD тут вне конкуренции. Asm
> + ssse3 + pshufb + 128 бит.

Ну пока думаю переделать на Asm. остальное вроде не всеми процессорами поддерживается. Например даже такая штука, как:
((i2-j2) div 6)+((i2-j2) mod 6)
уж очень заумно скомпилировалась. 2 раза idiv используется, число 6 два раза загружается в 32-разрядный регистр и куча всякой ненужной фигни, хотя это можно написать проще:

нахождение разности и
mov cl,6;
div cl;
add al,ah;

Вот только где бы по асму информации раздобыть нормальной? Ну и по асму в Дельфи тоже...

← →
SergP © (2016-05-27 15:00) [9]

> Sha © (27.05.16 14:51) [7]
>
> > SergP © (27.05.16 10:46) [2]
>
> И первое, и второе.
>
> Например, вот это я не понял:
> >Например (1,0,0) означает что в группе имеются 2 штуки
> A
> >(0,0,1) означает что группа пустая
> >(2,128,16384) означает что группа может состоять из 2А+С,
> либо A+B+C, либо 2*B+2*C

число мин в игре: тройных - 2 штуки, двойных 4 штуки, одинарных 5 штук.
Соответственно получается 90 вариантов. (3*5*6)
Каждый из вариантов кодируется битом номер 30*ко-во тройных + 6* кол-во двойных + кол-во одинарных +1
Но для удобства в этом 96-битном числе (3 интежера) используется по 30 младших бит с каждого 32-битного интежера.

← →
SergP © (2016-05-27 15:03) [10]

О. еще, оказывается правильнее писать не
(SmallSource.MSet[j] and SmallMask)=SmallMask
а
(SmallSource.MSet[j] and SmallMask)<>0

так на одну команду cmp меньше получается...

← →
Sha © (2016-05-27 15:26) [11]

> SergP © (27.05.16 15:00) [9]

Почему нельзя вариант кодировать его номером,
а все эти соответствующие ему количества мин и т.п. хранить в таблице?

← →
SergP © (2016-05-27 16:00) [12]

> Sha © (27.05.16 15:26) [11]
>
> > SergP © (27.05.16 15:00) [9]
>
> Почему нельзя вариант кодировать его номером,
> а все эти соответствующие ему количества мин и т.п. хранить
> в таблице?

так вариантов может несколько.
данная функция работает "множествами" вариантов.

← →
Sha © (2016-05-27 16:14) [13]

Так какую задачу все-таки решаем?

← →
SergP © (2016-05-27 16:21) [14]

Одна группа может состоять из нескольких вариантов.
группа, в нее входящая также может состоять из нескольких вариантов.
И разница может содержать в себе несколько вариантов.

Например если большая группа может состоять из вариантов:
1+1+1+1, 1+1+2, 1+3, 2+2
а группа в нее входящаяможет содержать варианты:
1+1, 2
то в результате работы функции получим разнцу: 1+1, 2
и кроме того из большой группы убираем вариант 1+3

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

← →
SergP © (2016-05-27 16:31) [15]

> Sha © (27.05.16 16:14) [13]
>
> Так какую задачу все-таки решаем?

В смысле "какую"?
Сейчас наиболее узкое место программы - приведенная в сабже функция, в плане времени выполнения...
Вобще-то я старался делать чтобы расчеты были мгновенными, чтобы производить их в процессе модификации исходных данных... И оно почти так и работает, где вычисляется все за доли секунды, но встречаются тяжелые ситуации, когда программа задумывается минут на 20-25. вот это и хочу ускорить...

Или Вы имеете ввиду что нужно сменить всю логику вычислений?
Я уже писал, что опробовал несколько вариантов и в конце-концов мне в голову пришел такой. Больше ничего лучшего в голову не приходило...
Но если у Вас имеется хорошая мысль - то думаю что ее тоже можно рассмотреть.

← →
Sha © (2016-05-27 16:46) [16]

Про функцию вроде все более-менее понятно.
Осталось понять, что нужно в итоге после 25 минут вычислений получить.

← →
SergP © (2016-05-27 17:47) [17]

> Sha © (27.05.16 16:46) [16]
>
> Про функцию вроде все более-менее понятно.
> Осталось понять, что нужно в итоге после 25 минут вычислений
> получить.

программа должна на поле 7*7 с 11 минами, при наличии одной или нескольких открытых ячеек:
1. Найти ячейки с минами, которые можно найти. Найти закрытые ячейки, где мин точно не может быть (если таковые существуют), т.е. те, куда можно далее тыкать...

← →
Sha © (2016-05-27 22:17) [18]

Тупо переписал, чтобы убрать деление и выход за границу параллелепипеда 3х5х6.
Но не думаю, что будет заметное ускорение.
type TMSet = packed array[0..2] of integer; TWork = packed record Field: int64; Cells: integer; MSet: TMset; Probe: Extended; end; function GetEntrance(var BigSource, SmallSource: Twork): Twork; var i, i1, i2, j, j1, j2, k, cells, BigMask, SmallMask: integer; BigPermit, SmallPermit: TMset; 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; Result.Cells:=BigSource.Cells-SmallSource.Cells; // êîëè÷åñòâî ÿ÷ååê â ðàçíîñòíîé ãðóïïå for i:=0 to 2 do begin; BigMask:=1; for i1:=0 to 4 do begin; for i2:=0 to 5 do begin; if BigSource.MSet[i] and BigMask<>0 then for j:=0 to i do begin; for j1:=0 to i1 do begin; cells:=SmallSource.Cells-j-j1; if cells>i2 then cells:=i2; SmallMask:=1 shl (j1*5); for j2:=0 to cells do begin; if SmallSource.MSet[j] and SmallMask<>0 then begin; BigPermit[i]:=BigPermit[i] or BigMask; SmallPermit[j]:=SmallPermit[j] or SmallMask; Result.MSet[i-j]:=Result.MSet[i-j] or 1 shl ((i1-j1)*5+i2-j2); end; SmallMask:=SmallMask+SmallMask; end; end; end; BigMask:=BigMask+BigMask; end; 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;

← →
Sha © (2016-05-27 22:24) [19]

Увидел пару опечаток: SmallMask:=1 shl (j1*6); ... Result.MSet[i-j]:=Result.MSet[i-j] or 1 shl ((i1-j1)*6+i2-j2);

Может еще что-нибудь найдется. Код не отлаживал.

← →
dmk © (2016-05-28 16:15) [20]

>Вот только где бы по асму информации раздобыть нормальной?
В источнике ;)
http://www.intel.com/content/dam/www/public/us/en/documents/manuals/64-ia-32-architectures-software-developer-instruction-set-reference-manual-325383.pdf

Функции можно сделать переменными. Не поддерживает - используешь одну, поддерживает - другую.

← →
SergP © (2016-05-29 20:47) [21]

> Sha © (27.05.16 22:17) [18]

Завтра попробую, сейчас Дельфи под рукой нет.
Хотя что-то склоняюсь к тому чтобы переписать функцию на ассемблере.

Пока грубо оно мне видится так: 5 регистров используем как указатели на BigSource, SmallSource, BigPermit, SmallPermit, Result.
Один регистр для всех четырех счетчиков цикла, по байту на каждый. 2 байта из 4 нам всегда доступны, а когда понадобятся другие то можно повертеть регистр с помощью ROR, ROL, BSWAP
Переменные BigMask, SmallMask вообще упразднить,вместо них использовать BTC, BTS
2 оставшихся регистра вроде должно хватить для вычислений и хранения промежуточных данных.
Кстати, мысль с использованием не 4, а 6 циклов тож постараюсь проработать.
Хотя есть вопрос: насколько медленно выполнение DIV ? В частности, если его использовать для деления на 8-разрядное число.

> dmk © (28.05.16 16:15) [20]
>
> >Вот только где бы по асму информации раздобыть нормальной?
>
> В источнике ;)

Конечно, лучше было бы на русском языке. Хотя в инете и на русском языке находил много чего. Но оно все не такое, что быстро запоминается...
Например, лет 25 назад, когда я интересовался ассемблером 8080 и Z80, тоже литература разная была. Одной можно было пользоваться, вроде все в ней есть, но как-то не то. А однажды попалась такая, что несколько раз прочитавши я уже знал на память все команды, все допустимые наборы операндов для каждой команды, время выполнения каждой команды в тактах в зависимости от операндов, флагов и пр, и даже запомнил коды многих команд, хотя и не ставил перед собой такой цели. (что тоже оказалось полезным, ибо позволяло видеть что делается в каком-нить участке программы, взглянувши на ее шестнадцатеричный дамп).
Вот и хочу найти нечто подобное для x86

Ну и по встроенному ассемблеру в Дельфи тоже есть вопросы:
Например передача параметров и возвращение результатов функций,
использование переменных (т.е. памяти где можно хранить промежуточные данные).
Какие расширения доступны в ассемблере в Дельфи 7, (типа ММХ и пр.)
ну и т.д.

← →
SergP © (2016-05-29 20:57) [22]

> Вот и хочу найти нечто подобное для x86

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

← →
SergP © (2016-05-30 09:45) [23]

Мда. в [21] я что-то не то сморозил... Почему-то раньше мне казалось что там хватит регистров.

← →
Sha © (2016-05-30 11:52) [24]

Мне кажется, что проще отталкиваться непосредственно от условий [17],
т.е. искать ячейки "где мин точно не может быть" перебором,
просто пробуя экономно расположить имеющиеся мины в ячейках.

← →
SergP © (2016-05-30 11:52) [25]

> Sha © (27.05.16 22:24) [19]

Проверил. Правда не стал добавлять в запись поле cells, а сделал вычисление его по прежнему методу SmallCells:=bitcount(SmallSource.field).count; дабы пока не менять остальной код. Т.е. в таком виде:
function GetEntranceSha(var BigSource, SmallSource: Twork): Twork; var i, i1, i2, j, j1, j2, cells, Smallcells, BigMask, SmallMask: integer; BigPermit, SmallPermit: TMset; 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; SmallCells:=bitcount(SmallSource.field).count; for i:=0 to 2 do begin; BigMask:=1; for i1:=0 to 4 do begin; for i2:=0 to 5 do begin; if BigSource.MSet[i] and BigMask<>0 then for j:=0 to i do begin; for j1:=0 to i1 do begin; cells:=SmallCells-j-j1; if cells>i2 then cells:=i2; SmallMask:=1 shl (j1*6); for j2:=0 to cells do begin; if SmallSource.MSet[j] and SmallMask<>0 then begin; BigPermit[i]:=BigPermit[i] or BigMask; SmallPermit[j]:=SmallPermit[j] or SmallMask; Result.MSet[i-j]:=Result.MSet[i-j] or 1 shl ((i1-j1)*6+i2-j2); end; SmallMask:=SmallMask+SmallMask; end; end; end; BigMask:=BigMask+BigMask; end; 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;

Вроде работает правильно.

Вобщем при обработке не особо тяжелого примера, но такого, где все-таки приходится ждать заметное время, получилось что с моим первоначальным вариантом расчет идет 44 секудны, с твоим 34 секунды...

Правда в процедуре, из которой вызывается эта функция есть поиск по массиву, из-за которого процент ускорения при обработке данных программой несколько ниже чем реальное ускорение сабжевой функции.
var workarr:packed array of TWork; ... // Обработка вложений // Разность двух групп добавляется в конец массива // Если аналогичная группа уже имеется в массиве, то она корректируется procedure Entrance(Start:integer); var i,j,t,z:integer; EntSec:Twork; flag:boolean; begin Application.ProcessMessages; t:=Workcount-1; for i:=0 to t do begin for j:=start to t do if (i<>j) and ((workarr[i].field and workarr[j].field) = workarr[i].field) and (workarr[i].field<>0) then // i входит в j begin EntSec:=GetEntrance(workarr[j], workarr[i]); flag:=true; for z:=0 to workcount-1 do // if (z<>i) and (z<>j) then if workarr[z].field=EntSec.field then begin workarr[z].MSet[0]:=workarr[z].MSet[0] and EntSec.MSet[0]; workarr[z].MSet[1]:=workarr[z].MSet[1] and EntSec.MSet[1]; workarr[z].MSet[2]:=workarr[z].MSet[2] and EntSec.MSet[2]; flag:=false; break; end; if flag then begin workarr[Workcount]:=EntSec; incworkcount; end; end; end; end;

← →
SergP © (2016-05-30 11:57) [26]

> Sha © (30.05.16 11:52) [24]
>
> Мне кажется, что проще отталкиваться непосредственно от
> условий [17],

Сильно много вариантов при переборе будет, и каждый еще нужно проверить на соответствие исходным данным...
Разве что делать перебор на ограниченном участве поля.

← →
SergP © (2016-05-30 12:24) [27]

Вот например:
----------------------------- ! 2 ! ! ! ! M1! 1 ! 0 ! ----------------------------- ! ! ! ! ! 3 ! 1 ! 0 ! ----------------------------- ! ! ! ! ! 4 ! 0 ! 0 ! ----------------------------- ! 2 ! ! ! ! 5 ! 5 ! 3 ! ----------------------------- ! ! ! ! ! M2! ! ! ----------------------------- ! ! ! ! ! ! 6 ! 3 ! ----------------------------- ! ! ! ! 4 ! ! 2 ! 0 ! -----------------------------

Кроме двух мин (одинарной и двойной) больше ничего не найдено. Тыкаем в нижний левый угол. там 1

----------------------------- ! 2 ! ! # ! # ! M1! 1 ! 0 ! ----------------------------- ! ! ! # ! M1! 3 ! 1 ! 0 ! ----------------------------- ! ! ! # ! M1! 4 ! 0 ! 0 ! ----------------------------- ! 2 ! ! # ! M2! 5 ! 5 ! 3 ! ----------------------------- ! ! ! # ! # ! M2! # ! M3! ----------------------------- ! ! ! ! ! ! 6 ! 3 ! ----------------------------- ! 1 ! ! ! 4 ! ! 2 ! 0 ! -----------------------------

и программа за доли секунды (для нее это довольно легкий вариант) находит еще 4 мины и 8 ячеек где мин не может быть...
А вот сколько нужно вычислений произвести чтобы это найти перебором? Что-то мне такое не кажется реальным.

← →
SergP © (2016-05-30 12:27) [28]

> SergP © (30.05.16 12:24) [27]

Ошибся пока рисовал поля.. Вот так оно было:
----------------------------- ! 2 ! ! ! ! M1! 1 ! 0 ! ----------------------------- ! ! ! ! ! 3 ! 1 ! 0 ! ----------------------------- ! ! ! ! ! 4 ! 0 ! 0 ! ----------------------------- ! 2 ! ! ! ! 5 ! 5 ! 3 ! ----------------------------- ! ! ! ! ! M2! ! ! ----------------------------- ! ! ! ! ! ! 6 ! 3 ! ----------------------------- ! ! ! ! 4 ! ! 1 ! 0 ! -----------------------------

----------------------------- ! 2 ! ! # ! # ! M1! 1 ! 0 ! ----------------------------- ! ! ! # ! M1! 3 ! 1 ! 0 ! ----------------------------- ! ! ! # ! M1! 4 ! 0 ! 0 ! ----------------------------- ! 2 ! ! # ! M2! 5 ! 5 ! 3 ! ----------------------------- ! ! ! # ! # ! M2! # ! M3! ----------------------------- ! ! ! ! ! ! 6 ! 3 ! ----------------------------- ! 1 ! ! ! 4 ! ! 1 ! 0 ! -----------------------------

← →
Sha © (2016-05-30 14:21) [29]

> Правда в процедуре, из которой вызывается эта функция есть поиск по массиву

Наверно, дерево подошло бы больше.

← →
SergP © (2016-05-30 15:01) [30]

Дерево это как?
Была мысль искать с помощью бинарного поиска, но я посчитал что затраты в подержании массива в отсортированном виде (или в организации поддержке дополнительного массива для индексов) этого не будут стоить.

← →
Sha © (2016-05-30 15:08) [31]

При вычитании подмножества из множества всегда получается подмножество.
Это можно учесть в коде, чтобы проще находить подмножества.

← →
SergP © (2016-05-30 18:20) [32]

На данный момент выделил и переписал в отдельную функцию поиск по массиву на ассемблере (Тут Rouse_ подсказал http://delphimaster.net/view/15-1464608311/)
В результате учитывая вышеизложенное и также плюс Sha © (27.05.16 22:17) [18]
вместе оно дало уже ощутимый прирост.
На примере придуманному от балды, первоначальный код давал время расчетов 44 секунды, а с учетом обоих модификаций кода уже 20 секунд.
т.е. более чем в 2 раза.
И это я еще не пытался переписывать сабжевую функцию на ассемблере...

← →
SergP © (2016-05-30 18:34) [33]

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

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

← →
Sha © (2016-05-30 19:54) [34]

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

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

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

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

← →
Sha © (2016-05-30 20:09) [35]

Еще, вероятно проверки перед циклами вроде
if BigSource.MSet[i]<>0 then for i1:=0 to 4 do begin;
дадут небольшое ускорение

← →
SergP © (2016-05-31 18:41) [36]

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

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

)))

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Почти переписал все на ассемблере, значительно изменивши (счетчиков циклов там уже нет, осталось только 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"

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

call Exception.Create call @RaiseExcept

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

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

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

raise Exception.Create("Error GetEntrance");

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

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

В результате получилась такая функция: (не знаю насколько сама функция теперь быстрее работает чем вариант 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;
Теоретически возможности для дальнейшей оптимизации должны иметься. Например более правильно использовать регистры, может где можно добиться спаривания. Хотя думаю что на этом можно и остановиться.

А. ну там еще табличные данные есть
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));

Можно ли ускорить функцию? Найти похожие ветки