Оптимизировать код

← →
Очень Злой (2012-11-30 20:26) [0]

Есть кусок кода, так наваял на глаз пока:

for i:=low(hist) to high(hist) do hist[i]:=false; for i:=0 to xcount-1 do begin z:=0; for x:=1 to 4 do for y:=1 to 4 do if a[i][x]=a[p][y] then if x=y then inc(z,6) else inc(z); hist[z]:=true; end; n:=0; for i:=low(hist) to high(hist) do if hist[i] then inc(n); v:=n/xcount;

чуствую что его можно оптимизировать с точки зрения времени выполнения, но не могу придумать пока как.
в данном коде:
a:array of string[4];
тип остальных переменных видно по смыслу.
значение переменных xcount, p устанавливается до этого участка кода.
в конце интересует лишь значение v
в массиве a хранятся последовательности из 4-х неповторяющихся цифр от 0 до 9

размерность массива hist - должна быть достаточной для хранения значений со всеми возможными индексами (а их может быть 14, но действительная размерность больше потому как там есть неиспользуемые значения)

тип элементов массива a не обязательно должен быть string[4]. можно использовать любые извращения, вплоть до хранения нужной информации в каком-нить зашифрованном виде, если это поможет уменьшить время выполнения указанной части кода, все равно эти значения можно вычислить один раз в начале.

можно ли как-то это оптимизировать с точки зрения времени выполнения? так как это самая внутренняя часть большого кол-ва вложенных циклов?

← →
Sha © (2012-11-30 20:47) [1]

> for i:=0 to xcount-1 do

каково типичное значение xcount?

> if x=y then inc(z,6) else inc(z);

почему 6? вроде 5 достаточно?

← →
Rouse_ © (2012-11-30 20:48) [2]

Если критично, то переписать на асме, убрав таким образом лишние накладные расходы при обращении к массивам.
Первую строчку можно заменить через FillChar()
Плюс тут у тебя еще переменная Р участвует, не понятно что означающая...

← →
Игорь Шевченко © (2012-11-30 20:50) [3]

> можно ли как-то это оптимизировать с точки зрения времени
> выполнения?

зачем ? Это самый критичный кусок кода или просто руки чешутся ?

← →
брат Птибурдукова (2012-11-30 21:24) [4]

> if a[i][x]=a[p][y] then

p=?

← →
картман © (2012-11-30 21:33) [5]

for x:=1 to 4 do
for y:=1 to 4 do
if a[i][x]=a[p][y] then
if x=y then inc(z,6) else inc(z);

один фор лишний, коль if x=y then?

← →
Sha © (2012-11-30 21:35) [6]

var table: array[0..9999] of byte; function Sha(a: pInteger; xcount: integer): double; var hist, n: integer; begin; hist:=0; while xcount>0 do begin; hist:=hist or 1 shl table[a^]; dec(xcount); inc(a); end; n:=0; while hist<>0 do begin; inc(n); hist:=hist and (hist-1); end; Result:=n/xcount; end;

← →
Очень злой (2012-11-30 23:26) [7]

> зачем ? Это самый критичный кусок кода или просто руки чешутся
> ?

да.

> Плюс тут у тебя еще переменная Р участвует, не понятно что
> означающая...

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

> каково типичное значение xcount?

ориентировочно от единиц до 3-4 сотен

но, этот кусок кода еще крутится в нескольких внешних циклах, суммарное кол-во итераций по отношению к данному куску кода ориентировочно исчисляется десятками миллионов - сотнями миллиардов ... сейчас точно не скажу...

← →
брат Птибурдукова (2012-11-30 23:31) [8]

> for x:=1 to 4 do for y:=1 to 4 do if a[i][x]=a[p][y]
> then
Чё-то оно мне как-то сильно напоминает MMX/SSE...

← →
Очень Злой (2012-12-01 00:06) [9]

> Первую строчку можно заменить через FillChar()

ну я думал массив hist заменить на запись, что-то типа:
hist = packed record case boolean of true: (arr:packed array[0..15] of byte;); false: (iv1,iv2:int64;); end;

тогда очистка масива свелась бы к:

iv1=0; iv2=0;

но размерность массива была бы 16, что хоть и достаточно для хранения данных (там максимум их 14 штук), но усложняет вычисление индекса.

> Sha © (30.11.12 21:35) [6]

не совсем понял. ладно завтра разберусь, но:

> var
> table: array[0..9999] of byte;

как в типе byte предполагается хранить 4 числа от 0 до 9 ? даже с учетом того что они не совпадают, все равно получается 10*9*8*7=5040 вариантов... (кстати порядок следования чисел важен). я размышлял над использованием чего-нить другого вместо string[4], думал над word, но там вроде потребуется много битовых операций вместо циклов:

> for x:=1 to 4 do
> for y:=1 to 4 do
> if a[i][x]=a[p][y] then
> if x=y then inc(z,6) else inc(z);

> картман © (30.11.12 21:33) [5]
>
> for x:=1 to 4 do
> for y:=1 to 4 do
> if a[i][x]=a[p][y] then
> if x=y then inc(z,6) else inc(z);
>
> один фор лишний, коль if x=y then?

ну кусочек кода можно поднять по циклам на 1 уровень выше, но будет ли от этого лучше?

← →
Sha © (2012-12-01 00:24) [10]

> Очень Злой (01.12.12 00:06) [9]
> как в типе byte предполагается хранить 4 числа от 0 до 9 ?

В таблице хранятся предварительно вычисленные значения z в диапазоне 0..24
(или меньше, если без дыр) для a[i] и a[p], где i=0..9999, p-фиксированное.

← →
Джон Буль (2012-12-01 00:25) [11]

Use short boolean scheme, Luke:
if (a[i][x] = a[p][y]) and (x = y) then inc(z,6) else inc(z);

← →
Очень злой (2012-12-01 00:30) [12]

> В таблице хранятся предварительно вычисленные значения z
> в диапазоне 0..24
> (или меньше, если без дыр) для a[i] и a[p], где i=0..9999,
> p-фиксированное.

Ага. Понял... отличная мысль. а я как-то не додумался до этого.

← →
Sha © (2012-12-01 00:30) [13]

> Джон Буль (01.12.12 00:25) [11]

не тот буль

← →
Очень злой (2012-12-01 00:32) [14]

> Джон Буль (01.12.12 00:25) [11]
>
> Use short boolean scheme, Luke:
> if (a[i][x] = a[p][y]) and (x = y) then inc(z,6) else inc(z);
>

неа...

если a[i][x] <> a[p][y] то ничего не нужно делать...

← →
Очень злой (2012-12-01 00:34) [15]

> Джон Буль (01.12.12 00:25) [11]
>
> Use short boolean scheme, Luke:
> if (a[i][x] = a[p][y]) and (x = y) then inc(z,6) else inc(z);
>

так then сработает правильно, а else нет, ибо в моем варианте оно относится к внутреннему if

← →
брат Птибурдукова (2012-12-01 00:38) [16]

> hist = packed record
Если важнее всего скорость, то упаковку — ффтопку

← →
Очень злой (2012-12-01 00:47) [17]

> Если важнее всего скорость, то упаковку — ффтопку

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

оба внутренних цикла можно бы и развернуть.

заодно от проверки x=y избавляемся.

← →
Очень злой (2012-12-01 00:54) [20]

да и Sha "ткнул" меня мордой в то, о чем я сам не подумал, но что должно значительно повысить скорость. так что уже остальные фичи возможно и не понадобятся, и вместо массива hist будет достаточно 14 бит, т.е. укладываемся в word

> и вместо массива hist будет достаточно 14 бит, т.е. укладываемся в word

все равно надо использовать родные железу 32 бита

> Sha © (30.11.12 21:35) [6]

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

> картман © (01.12.12 01:39) [22]
> как ты дошел именно до такого решения

Стандартный прием - вынести из цикла все, что можно вычислить снаружи

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

вот тут, например, похожая задача

http://guildalfa.ru/alsha/node/16

← →
Use_R (2012-12-01 01:55) [24]

Оптимизировать код Найти похожие ветки