Optimalizace kodu pro dct – PHP – Fórum – Programujte.com

Potreboval bych pomoci s optimalizaci kody pro vypocet dct transformace (pouziva to treba jpeg), abych to mohl zkusit aplikovat na cely obrazek, ne jen na 32x32 pixelu. Klasicky jpeg to pouziva na 8x8 pole, coz je dost nuda a s dnesnim vypocetnim vykonem a pameti by mohl pouziva linearni nebo kvadratickou dct na cely soubor. Takovy je plan :)

* Treba strasnou brzdu mi tam dela pocitani absolutni hodnoty pres abs(). To uz jsem nahradil.
* Tez si nejsem jisty, co to bude delat na rychlosti, kdyz misto kosinove tabulky to budu pocitat primo.
* Mno, a potom se mi tak uplne nelibi prace s polem. Neni tam nejaky rychlejsi prvek? Ono to pole v pameti i dost zabira a pak mi tam strasi s prekrocenim limitu pameti.

<?php
ini_set('max_execution_time', 10000);	//10000s
//set_time_limit(10000);   
//ini_set('memory_limit', '256M');

function microtime_float()	//pp 17.3.2014
{
    list($usec, $sec) = explode(" ", microtime());
    return ((float)$usec + (float)$sec);
}
$time = array();
$time[] = microtime_float();



// input
$file = "img/1299576.jpg";
list($width, $height, $type, $attr) = getimagesize($file);
$img  = ImageCreateFromJpeg($file);
imagefilter($img, IMG_FILTER_GRAYSCALE);


    
// prepare tables
//$inp  = array(14,17,49,122,8,56,67,121,18,219,163,88,147,88,195,121);
//$q    = array(16,11,10,16,12,12,14,19,14,13,16,24,14,17,22,29);
//$max = 16;
$maxM = $maxN = 4;
$maxM = $maxN = 16;
$maxM = $maxN = 32;
//$maxM = $maxN = 64;
$maxMN = $maxM * $maxN;
$cosA = array();
$cosB = array();
$qcA  = array();
$qcB  = array();
//$c   = array();
$c_arr = array();
$c_arr[0] = pow(1/$maxM,0.5);
$c_arr[1] = pow(2/$maxM,0.5);
$c_arr[2] = pow(1/$maxN,0.5);
$c_arr[3] = pow(2/$maxN,0.5);
$c_arr[4] = $c_arr[1] * $c_arr[3];
//$c_arr[0] *= $c_arr[4];
//$c_arr[1] *= $c_arr[4];
$cosCM = $cosCN = M_PI / (2 * $maxM);

$cosM = array();
for ($j=0,$ii=0;$j<$maxM;$j++)
	{
	$cosM[$j] = array();
	for ($i=0;$i<$maxN;$i++,$ii++)
		{
		$cosM[$j][$i] = cos($cosCM * (2*$j+1)*$i);
		}
	}
//echo '<pre>';
//print_r($cosM);

// ---
$cosSuma = array();
for ($ii=0;$ii<$maxMN;$ii++)
	{
	$cosSuma[$ii] = 0;
	}
for ($k=0,$kk=0;$k<$maxM;$k++)
	{
	for ($l=0;$l<$maxN;$l++,$kk++)
		{
		for ($i=0,$ii=0;$i<$maxM;$i++)
			{
			for ($j=0;$j<$maxN;$j++,$ii++)
				{
//				$cos = cos($cosCM * (2*$k+1)*$i) * cos($cosCN * (2*$l+1)*$j); //ok
				$cos = $cosM[$k][$i] * $cosM[$l][$j];
//				$cosSuma[$ii] += abs($cos);
				$cosSuma[$ii] += $cos>0 ? $cos : -$cos;
//				$cosSuma[$ii] += $cos;
				}
			}
		}
	}
for ($ii=0;$ii<$maxMN;$ii++)
	{
	$cosSuma[$ii] /= $maxM/4;
	}

$time[] = microtime_float();

// read input
$x = 0;
$y = 0;
$x = 300;
$y = 600;
$inp = array();
for ($i=0,$ii=0;$i<$maxM;$i++)
	{
	for ($j=0;$j<$maxN;$j++,$ii++)
		{
		$inp[$ii] = imagecolorat($img, $x+$i, $y+$j) & 0xFF;	//$r = ($rgb >> 16) & 0xFF; $g = ($rgb >> 8) & 0xFF; $b = $rgb & 0xFF;
//		$inp[$iI] = rand(0,256);
		}
	}

$time[] = microtime_float();


$out = array();
/*
$qcM = 1;
for ($ii=0;$ii<$maxMN;$ii++)
	{
	$out[$ii] = 0;
	}
*/
for ($i=0,$ii=0;$i<$maxM;$i++)
	{
	$c1 = $i==0 ? $c_arr[0] : $c_arr[1];
	for ($j=0;$j<$maxN;$j++,$ii++)
		{
		$c2 = $j==0 ? $c_arr[2] : $c_arr[3];;
//		$qcM = ($c1 * $c2) / $q[$ii];	//ok
		$qcM = ($c1 * $c2) / $cosSuma[$ii];
		$out[$ii] = 0;
		for ($k=0,$kk=0;$k<$maxM;$k++)
			{
			for ($l=0;$l<$maxN;$l++,$kk++)
				{
// ok				$cosM = cos($cosCM * (2*$k+1)*$i) * cos($cosCN * (2*$l+1)*$j);
				$cos = $cosM[$k][$i] * $cosM[$l][$j];
				$out[$ii] += $inp[$kk] * $cos;
				}
			}
		$out[$ii] = round($out[$ii] * $qcM);
		}
	}



// transform 1D back
$inp2 = array();
for ($ii=0;$ii<$maxMN;$ii++)
	{
	$inp2[$ii] = 0;
	}
for ($k=0,$kk=0;$k<$maxM;$k++)
	{
	for ($l=0;$l<$maxN;$l++,$kk++)
		{
		for ($i=0,$ii=0;$i<$maxM;$i++)
			{
			$c1 = $i==0 ? $c_arr[0] : $c_arr[1];
			for ($j=0;$j<$maxN;$j++,$ii++)
				{
				$c2 = $j==0 ? $c_arr[2] : $c_arr[3];
//				$qcM = ($c1 * $c2) * $q[$ii];
				$qcM = ($c1 * $c2) * $cosSuma[$ii];
// ok				$cos = cos($cosCM * (2*$k+1)*$i) * cos($cosCN * (2*$l+1)*$j);
				$cos = $cosM[$k][$i] * $cosM[$l][$j];
				$inp2[$kk] += $out[$ii] * $cos * $qcM;
				}
			}
		}
	}
$stat_diff = array();
$stat_inp=0;
$stat_out=0;
$stat_err=0;
for ($ii=0;$ii<$maxMN;$ii++)
	{
	$inp2[$ii] = round($inp2[$ii]);
//	$inp2[$i] = $inp2[$i] <= 255 ? ($inp2[$i] >= 0 ? $inp2[$i] : 0) : 255;
	$stat_inp += abs($inp[$ii]);
	$stat_out += abs($out[$ii]);
	$stat_err += abs($inp[$ii] - $inp2[$ii]);
//	$stat_diff[$ii] = $inp[$ii] - $inp2[$ii];
//	$stat_err += abs($stat_diff[$ii]);
	}


// print
echo '<table><tr>';
//echo '<td>cosA';
//echo '<pre>'; print_r($cosM); echo '</pre>';
//echo '<td>cosB';
//echo '<pre>'; print_r($cosB); echo '</pre>';
//echo '<td>Q';
//echo '<pre>'; print_r($q);  echo '</pre>';
//echo '<td>C';
//echo '<pre>'; print_r($c); echo '</pre>';
//echo '<td>QC-A';
//echo '<pre>'; print_r($qcA);  echo '</pre>';
//echo '<td>cosSuma';
//echo '<pre>'; print_r($cosSuma);  echo '</pre>';
if ($maxM<=16)
{
echo '<td>INP';
echo '<pre>'; print_r($inp);  echo '</pre>';
echo '<td>OUT';
echo '<pre>'; print_r($out);  echo '</pre>';
echo '<td>INP2';
echo '<pre>'; print_r($inp2); echo '</pre>';
echo '<td>stat_diff';
echo '<pre>'; print_r($stat_diff);  echo '</pre>';
}
echo '</tr></table>';
echo "err = $stat_err / ".($maxMN*256)." (".($stat_err/($maxMN*256)*100)." %) ... abs(D) / (max*256)<br>";
echo "inp = $stat_inp | out = $stat_out ... suma(value)<br>";
//echo "errinp = $stat_err / $stat_inp = ".($stat_err/$stat_inp*100)." % (A / B)";

//output
//header('Content-Type: image/png');
//imagepng($img);
imagedestroy($img);

$time[] = microtime_float();
$t = array();
$t[] = round($time[count($time)-1]-$time[0],3);
for ($i=1;$i<count($time);$i++)
	{
	$t[] = round($time[$i]-$time[$i-1],3);
	}
$t = implode(" | ",$t);
echo '<hr>Cas zpracovani '.$t.' s';

/*
pp q-256:
16	18	23	27	34	34	38	40
18	20	26	30	38	38	42	44
23	26	34	40	50	50	55	58
27	30	40	46	58	58	64	67
34	38	50	58	72	72	80	84
34	38	50	58	72	72	80	84
38	42	55	64	80	80	89	94
40	44	58	67	84	84	94	99
var tabZ=new Array(MMNN);
var x=Math.sqrt(MM/2 * NN/2);
var i,j,k;
for(j=0,k=0;j<NN;j++) {for(i=0;i<MM;i++,k++)
	{tabZ[k] = x/Math.sqrt((2*i+1)*(2*j+1));}}
*/
?>

Ono precijen PHP neni zrovna urcene na tenhle typ uloh :)

Jasne. Ale prijde mi jednodusi zplacat to v necem, co mam, nez si instalovat neco slozite dny a pak zjistim po spusteni kodu, ze to nedela uplne to, co chci. Treba ted pole 64x64 pocita 70s, 32x32 kolem 7s. Coz jsou pomerne neprijatelne casy.

#1 peter
Viděl bych 2 cesty: Přepsat do něčeho vhodnějšího (např. do Fortranu) nebo k tomu použít odpovídající nástroj, např. Matlab nebo Octave.

#3 peter
Obavam se, ze v PHP s tim uz moc nehnes...

Jenze, ja si to chtel promitat primo na obrazku. Nasel jsem kod a rychlejsi cos pomoci polynomu. neni to teda o moc rychlejsi, ale to je mozna tim, ze je to ve funkci....
 Pridal jsem tam sledovani casu a nejvic to brzdi prave pocitani kosinu, ted.
Cas zpracovani (0.583 | 0.372 - cos tabulky | 0.001 - input | 0.074 - do dct | 0.137 - z dct) s
S temi casy z/do dct, s tim se asi moc nehne, ale ten cos mne toci :) Aspon moje php to pocita pomalu. Preci nemuze pole 256 cisel kosinu pocitat tak dlouho.

// http://lab.polygonal.de/?…
function fastCos($x)
{
$x += 4.71238898; // $x += M_PI + pp(M_PI/2);
while ($x > 3.14159265)
	{
    $x -= 6.28318531;
}

if ($x < 0)
{
    $x = 1.27323954 * $x + 0.405284735 * $x * $x;
    if ($x < 0)
        return .225 * ($x *-$x - $x) + $x;
    else
        return .225 * ($x * $x - $x) + $x;
}
else
{
    $x = 1.27323954 * $x - 0.405284735 * $x * $x;
    if ($x < 0)
        return .225 * ($x *-$x - $x) + $x;
    else
        return .225 * ($x * $x - $x) + $x;
}
}

Ha, tak od puvodni verze upoustim. Presel jsem z tabulkove dct na radkovou. Stejne ten program nestiha v php pri vetsim poctu prvku :) Naposledy jsem mel kolem 3000, coz se kvadraticky pak pronasobuje, cili obcas 9.000.000 cyklu s nasobenim float cisel :) No, 70s mam. Tak hold budu muset pracovat s mensim poctem a obrazek rozsekat.
Pri tom velkem poctu musi projit pole o 3000 hodnot a kazdou z nich pronasobit nejakym cislem, vsechno secist a ulozit do vysledne bunky. Coz mu dela desne problemy. Nebo to mam napsane neusporne :)

Php proste praci s poli nema nejak zmaknutou a pocitani mnoha cisel :)

No hlavně PHP je interpretované, v některých operacích je až nekoliktisíckrát pomalejší než nativně běžící jazyky :) .

#7 peter
V PHP se s polem téměř nepracuje, na takové výpočty ani nebylo stavěno.

Ten čas naženeš až počítáním $cosSuma, což je o setsakra víc iterací, než těch "pár" cosinů ;-)

Jinak teda PHP nemá klasické pole (teď už snad jo), je to výrazně pomalejší mapa (navíc ji máš "dvourozměrnou" a plníš ji postupně).

No, ono linearni dct se toho mnoho zjednodusilo. Treba nemusim pocitat sumacos, tam to vychazi 16 pro nultou pozici a 10 a nejake desetinky pro ostatni. Desetinky jsem zanedbal, vysledna chyba se nepatrne zvysila.
Hlavne jsem to mohl testnout na 3000 px.  (snad to bude cele, odmazaval jsem komenty kodu...)

<?php
ini_set('max_execution_time', 10000);    //10000s
//set_time_limit(10000);   
//ini_set('memory_limit', '256M');

function microtime_float()    //pp 17.3.2014
{
    list($usec, $sec) = explode(" ", microtime());
    return ((float)$usec + (float)$sec);
}
$time = array();
$time[] = microtime_float();


function printNonZero(&$arr)
{
$stat = array();
$v = 16;
for ($i=0;$i<$v;$i++)
    {
    $stat[$i] = 0;
    }
$i = 0;
foreach ($arr as $key=>$value)
    {
    if ($value!=0) {echo "[$key] => $value\n"; $i++;}
    $x = abs($value);
    if ($x<$v) {$stat[$x]++;}
    }
if ($i!=0) {echo "Sum $i\n";}
ksort($stat);
echo "Sum abs<$v "; print_r($stat); echo "\n";
}


// input
$file = "img/1299576.jpg";
list($width, $height, $type, $attr) = getimagesize($file);
$img  = ImageCreateFromJpeg($file);
imagefilter($img, IMG_FILTER_GRAYSCALE);

$time[] = microtime_float();
    

// prepare tables
$maxM = 16;
$maxM = 256;
//$maxM = 1024;
//$maxM = 1920-300; //1920x1200 - 300x600
//$maxM = 3000;
$cosA = array();
$cosB = array();
$qcA  = array();
$qcB  = array();
$c0  = pow(1/$maxM,0.5);
$c1  = pow(2/$maxM,0.5);
$cosM = M_PI / ($maxM * 2);
$qcB = null;

$time[] = microtime_float();

// read input
$x = 300;
$y = 600;
$inp = array();
for ($i=0;$i<$maxM;$i++)
    {
    $x++;
    if ($x>=1920) {$x=0; $y++; if ($y>960) break;}
    $inp[$i] = imagecolorat($img, $x, $y) & 0xFF;    //$r = ($rgb >> 16) & 0xFF; $g = ($rgb >> 8) & 0xFF; $b = $rgb & 0xFF;
//    $inp[$i] = rand(0,256);
    }

$time[] = microtime_float();

// transform 1D
$out = array();
$cosSuma = array();
for ($i=0;$i<$maxM;$i++)
    {
    $c = $i==0 ? $c0 : $c1;
$j = 0;
    $cosSuma[$i] = ($i==0 ? 16 : 10) / abs(cos($cosM * (2*$j+1)*$i));
    $out[$i] = 0;
    for ($j=0;$j<$maxM;$j++)
        {
        $out[$i] += $inp[$j] * cos($cosM * (2*$j+1)*$i);
        }
    $out[$i] = round($out[$i] * ($c / $cosSuma[$i]));
    }

$time[] = microtime_float();

// transform 1D back
$inp2 = array();
$stat_diff = array();
$stat_inp=0;
$stat_out=0;
$stat_err=0;
for ($i=0;$i<$maxM;$i++)
    {
    $inp2[$i] = 0;
    for ($j=0;$j<$maxM;$j++)
        {
        $c = $j==0 ? $c0 : $c1;
        $inp2[$i] += $out[$j] * cos($cosM * (2*$i+1)*$j) * $c * $cosSuma[$j];
        }
    $inp2[$i] = round($inp2[$i]);
//    $inp2[$i] = $inp2[$i] <= 255 ? ($inp2[$i] >= 0 ? $inp2[$i] : 0) : 255;
    $stat_inp += $inp[$i]>0 ? $inp[$i] : -$inp[$i];
    $stat_out += $out[$i]>0 ? $out[$i] : -$out[$i];
    $x = $inp[$i] - $inp2[$i];
    $stat_err += $x>0 ? $x : -$x;
    }

$time[] = microtime_float();

// print
echo '<table><tr>';
if ($maxM<=16)
{
echo '<td>INP';
echo '<pre>'; print_r($inp);  echo '</pre>';
echo '<td>OUT';
echo '<pre>'; print_r($out);  echo '</pre>';
echo '<td>INP2';
echo '<pre>'; print_r($inp2); echo '</pre>';
echo '<td>stat_diff';
echo '<pre>'; print_r($stat_diff); echo '</pre>';
}
else
{
echo '<td>OUT';
echo '<pre>'; printNonZero($out); echo '</pre>';
}
echo '</tr></table>';
echo "err = $stat_err / ".($maxM*256)." (".($stat_err/($maxM*256)*100)." %) ... abs(D) / (max*256)<br>";
echo "inp = $stat_inp | out = $stat_out ... suma(value)<br>";
echo "errinp = $stat_err / $stat_inp = ".($stat_err/$stat_inp*100)." % (A / B)";

//output
imagedestroy($img);

$time[] = microtime_float();
$t = array();
$t[] = round($time[count($time)-1]-$time[0],3);
for ($i=1;$i<count($time);$i++)
    {
    $t[] = round($time[$i]-$time[$i-1],3);
    }
$t = implode(" | ",$t);
echo '<hr>Cas zpracovani '.$t.' s';
?>