| Форумы
ЧАТ |
Орешник |
|
| Форумы -» | Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / RSDN.ORG |
|
| ||
|
|
Новости |
Поиск |
FAQ |
Статьи |
Книги |
Новости VCL
| | Форумы ЧАТ |
Орешник |
|
| |||
| |||
| |||
« предыдущая ветвь | форум | следующая ветвь »
Можно ли ускорить функцию? [D7, XP]
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
но это даже если и даст какое-то ускорение, то уж очень мизерное.
Подскажите, что еще тут можно оптимизировать?
Sha (2016-05-27 15:26:00) [41]> SergP © (27.05.16 15:00) [9]
Почему нельзя вариант кодировать его номером,
а все эти соответствующие ему количества мин и т.п. хранить в таблице?
SergP (2016-05-27 15:03:00) [42]О. еще, оказывается правильнее писать не
(SmallSource.MSet[j] and SmallMask)=SmallMask
а
(SmallSource.MSet[j] and SmallMask)<>0
так на одну команду cmp меньше получается...
SergP (2016-05-27 15:00:00) [43]
> 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 14:53:00) [44]
> 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;
Вот только где бы по асму информации раздобыть нормальной? Ну и по асму в Дельфи тоже...
Sha (2016-05-27 14:51:00) [45]> 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:41:00) [46]
> 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)
далее ищем группы которые входят в другие, находим разность, также данная функция используется для расчета возможных вариантов в группе, которая является пересечением двух других.
Вот используя такие вещи, нужно вычислить расположение мин и пустых ячеек (разумеется насколько это возможно)
dmk (2016-05-27 14:09:00) [47]Все сделать в регистрах на ассемблере. Основная проблема всех этих вычислений в постоянной записи в память. Ускорение может быть в несколько раз.
Если работа с масками, то SIMD тут вне конкуренции. Asm + ssse3 + pshufb + 128 бит.
Jeer (2016-05-27 13:39:00) [48]См. [1]
SergP (2016-05-27 12:57:00) [49]Глянул на скомпилированный код функции. Такое ощущение что переписавши все на ассемблере можно ускорить довольно значительно...
Вот только подъизучить ассемблер придется... Хотя и невооруженным взглядом видны некоторые нерациональные вещи
SergP (2016-05-27 10:46:00) [50]
> Sha © (26.05.16 21:59) [1]
>
> лучше было бы описать задачу в терминах реального мира
> вместо описания своего решения задачи
Хм. Вы считаете, что это описание непонятное или думаете что возможности для ускорения следует искать не только в этой функции, а и во всей логике вычислений?
Если второе, то я уже пробовал несколько разных вариантов, которые приходили в голову, например для группы хранить не множество возможных вариантов, а максимальные и минимальные количества "сущностей" разных типов. Но тогда точность расчетов страдает. А она имеет приоритет даже перед временем выполнения.
Sha (2016-05-26 21:59:00) [51]лучше было бы описать задачу в терминах реального мира
вместо описания своего решения задачи
| |
Страницы: 