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

← →
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 ! -----------------------------

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

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

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

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

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

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

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

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

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

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

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

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

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

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

)))

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

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

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

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

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