| Форумы
ЧАТ |
Орешник |
|
| Форумы -» | Основная («Начинающим»)/ Базы / 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-30 15:08:00) [21]При вычитании подмножества из множества всегда получается подмножество.
Это можно учесть в коде, чтобы проще находить подмножества.
SergP (2016-05-30 15:01:00) [22]Дерево это как?
Была мысль искать с помощью бинарного поиска, но я посчитал что затраты в подержании массива в отсортированном виде (или в организации поддержке дополнительного массива для индексов) этого не будут стоить.
Sha (2016-05-30 14:21:00) [23]> Правда в процедуре, из которой вызывается эта функция есть поиск по массиву
Наверно, дерево подошло бы больше.
SergP (2016-05-30 12:27:00) [24]
> 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 !
-----------------------------
SergP (2016-05-30 12:24:00) [25]Вот например:
-----------------------------
! 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 11:57:00) [26]
> Sha © (30.05.16 11:52) [24]
>
> Мне кажется, что проще отталкиваться непосредственно от
> условий [17],
Сильно много вариантов при переборе будет, и каждый еще нужно проверить на соответствие исходным данным...
Разве что делать перебор на ограниченном участве поля.
SergP (2016-05-30 11:52:00) [27]
> 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;
Sha (2016-05-30 11:52:00) [28]Мне кажется, что проще отталкиваться непосредственно от условий [17],
т.е. искать ячейки "где мин точно не может быть" перебором,
просто пробуя экономно расположить имеющиеся мины в ячейках.
SergP (2016-05-30 09:45:00) [29]Мда. в [21] я что-то не то сморозил... Почему-то раньше мне казалось что там хватит регистров.
SergP (2016-05-29 20:57:00) [30]
> Вот и хочу найти нечто подобное для x86
Ну разумеется что коды команд мне тут особо не нужны, и время выполнения команды для современных компов - понятие расплывчатое, но какой-то критерий (для того чтобы по ходу написания видеть что это лучше сделать так, ибо по другому оно будет дольше выполняться) нужен обязательно.
Ну и такие вещи, если имеют место то желательно их знать:например команда выполняющая определенные действия, в качестве операндов могут использоваться разные регистры, но когда операндом является определенный регистр, то она имеет укороченный вид и/или быстрее выполняется.
SergP (2016-05-29 20:47:00) [31]
> 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, (типа ММХ и пр.)
ну и т.д.
dmk (2016-05-28 16:15:00) [32]>Вот только где бы по асму информации раздобыть нормальной?
В источнике ;)
http://www.intel.com/content/dam/www/public/us/en/documents/manuals/64-ia-32-architectures-software-developer-instruction-set-reference-manual-325383.pdf
Функции можно сделать переменными. Не поддерживает - используешь одну, поддерживает - другую.
Sha (2016-05-27 22:24:00) [33]Увидел пару опечаток:
SmallMask:=1 shl (j1*6);
...
Result.MSet[i-j]:=Result.MSet[i-j] or 1 shl ((i1-j1)*6+i2-j2);
Может еще что-нибудь найдется. Код не отлаживал.
Sha (2016-05-27 22:17:00) [34]Тупо переписал, чтобы убрать деление и выход за границу параллелепипеда 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 BigMask0 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 SmallMask0 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;
SergP (2016-05-27 17:47:00) [35]
> Sha © (27.05.16 16:46) [16]
>
> Про функцию вроде все более-менее понятно.
> Осталось понять, что нужно в итоге после 25 минут вычислений
> получить.
программа должна на поле 7*7 с 11 минами, при наличии одной или нескольких открытых ячеек:
1. Найти ячейки с минами, которые можно найти. Найти закрытые ячейки, где мин точно не может быть (если таковые существуют), т.е. те, куда можно далее тыкать...
Sha (2016-05-27 16:46:00) [36]Про функцию вроде все более-менее понятно.
Осталось понять, что нужно в итоге после 25 минут вычислений получить.
SergP (2016-05-27 16:31:00) [37]
> Sha © (27.05.16 16:14) [13]
>
> Так какую задачу все-таки решаем?
В смысле "какую"?
Сейчас наиболее узкое место программы - приведенная в сабже функция, в плане времени выполнения...
Вобще-то я старался делать чтобы расчеты были мгновенными, чтобы производить их в процессе модификации исходных данных... И оно почти так и работает, где вычисляется все за доли секунды, но встречаются тяжелые ситуации, когда программа задумывается минут на 20-25. вот это и хочу ускорить...
Или Вы имеете ввиду что нужно сменить всю логику вычислений?
Я уже писал, что опробовал несколько вариантов и в конце-концов мне в голову пришел такой. Больше ничего лучшего в голову не приходило...
Но если у Вас имеется хорошая мысль - то думаю что ее тоже можно рассмотреть.
SergP (2016-05-27 16:21:00) [38]Одна группа может состоять из нескольких вариантов.
группа, в нее входящая также может состоять из нескольких вариантов.
И разница может содержать в себе несколько вариантов.
Например если большая группа может состоять из вариантов:
1+1+1+1, 1+1+2, 1+3, 2+2
а группа в нее входящаяможет содержать варианты:
1+1, 2
то в результате работы функции получим разнцу: 1+1, 2
и кроме того из большой группы убираем вариант 1+3
Ну и в процессе вычислений (при обработке пересечений) могут образовываться группы у которых сумма "достоинств" мин непостоянная... так что группа иногда может содержать довольно много вариантов...
Sha (2016-05-27 16:14:00) [39]Так какую задачу все-таки решаем?
SergP (2016-05-27 16:00:00) [40]
> Sha © (27.05.16 15:26) [11]
>
> > SergP © (27.05.16 15:00) [9]
>
> Почему нельзя вариант кодировать его номером,
> а все эти соответствующие ему количества мин и т.п. хранить
> в таблице?
так вариантов может несколько.
данная функция работает "множествами" вариантов.
| |
Страницы: 