Форум: "Прочее";
Текущий архив: 2013.03.22;
Скачать: [xml.tar.bz2];
ВнизОптимизировать код Найти похожие ветки
← →
Очень Злой (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]
> Если важнее всего скорость, то упаковку — ффтопку
вобще-то в данном случае что с упаковкой, что без, должно быть вроде как одинаково, но в вариантных записях я один раз просто напоролся на то, что компилятор сделал не так, как я хотел, поэтому теперь страхуюсь на всякий случай...))
← →
RWolf © (2012-12-01 00:48) [18]оба внутренних цикла можно бы и развернуть.
← →
RWolf © (2012-12-01 00:50) [19]заодно от проверки x=y избавляемся.
← →
Очень злой (2012-12-01 00:54) [20]да и Sha "ткнул" меня мордой в то, о чем я сам не подумал, но что должно значительно повысить скорость. так что уже остальные фичи возможно и не понадобятся, и вместо массива hist будет достаточно 14 бит, т.е. укладываемся в word
← →
Sha © (2012-12-01 00:57) [21]> и вместо массива hist будет достаточно 14 бит, т.е. укладываемся в word
все равно надо использовать родные железу 32 бита
← →
картман © (2012-12-01 01:39) [22]
> Sha © (30.11.12 21:35) [6]
шикарно было бы узнать, как ты дошел именно до такого решения. А еще было бы неплохо привести примеры решения задач без использования магии битовой арифметики.
← →
Sha © (2012-12-01 01:50) [23]> картман © (01.12.12 01:39) [22]
> как ты дошел именно до такого решения
Стандартный прием - вынести из цикла все, что можно вычислить снаружи
> было бы неплохо привести примеры решения задач без использования
> магии битовой арифметики
вот тут, например, похожая задача
http://guildalfa.ru/alsha/node/16
← →
Use_R (2012-12-01 01:55) [24]
> картман © (01.12.12 01:39) [22]
>
> шикарно
Истинный. :)
← →
картман © (2012-12-01 02:20) [25]
> Sha © (01.12.12 01:50) [23]
спасибо
Страницы: 1 вся ветка
Форум: "Прочее";
Текущий архив: 2013.03.22;
Скачать: [xml.tar.bz2];
Память: 0.51 MB
Время: 0.085 c