Optimalizace kodu pro dct – PHP – Fórum – Programujte.com
 x   TIP: Přetáhni ikonu na hlavní panel pro připnutí webu
Reklama
Reklama

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

 

Hledá se programátor! Plat 1 800 € + bonusy (firma Boxmol.com)
peter
~ Anonymní uživatel
2528 příspěvků
6. 1. 2015   #1
-
0
-

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));}}
*/
?>
Nahlásit jako SPAM
IP: 2001:718:2601:1f7:14ed:95...–
Reklama
Reklama
Satik0
Stálý člen
6. 1. 2015   #2
-
0
-

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

Nahlásit jako SPAM
IP: 86.49.188.–
peter
~ Anonymní uživatel
2528 příspěvků
6. 1. 2015   #3
-
0
-

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.

Nahlásit jako SPAM
IP: 2001:718:2601:1f7:14ed:95...–
Kit+11
Guru
6. 1. 2015   #4
-
0
-

#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.

Nahlásit jako SPAM
IP: 147.229.242.–
Komentáře označují místa, kde programátor udělal chybu nebo něco nedodělal.
Satik0
Stálý člen
6. 1. 2015   #5
-
0
-

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

Nahlásit jako SPAM
IP: 86.49.188.–
peter
~ Anonymní uživatel
2528 příspěvků
6. 1. 2015   #6
-
0
-

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;
}
}
Nahlásit jako SPAM
IP: 2001:718:2601:1f7:14ed:95...–
peter
~ Anonymní uživatel
2528 příspěvků
7. 1. 2015   #7
-
0
-

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 :)

Nahlásit jako SPAM
IP: 2001:718:2601:1f7:51b3:f6...–
Satik0
Stálý člen
7. 1. 2015   #8
-
0
-

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

Nahlásit jako SPAM
IP: 86.49.188.–
Kit+11
Guru
7. 1. 2015   #9
-
0
-

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

Nahlásit jako SPAM
IP: 147.229.242.–
Komentáře označují místa, kde programátor udělal chybu nebo něco nedodělal.
q
~ Anonymní uživatel
219 příspěvků
7. 1. 2015   #10
-
0
-

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ě).

Nahlásit jako SPAM
IP: 213.211.51.–
peter
~ Anonymní uživatel
2528 příspěvků
8. 1. 2015   #11
-
0
-

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';
?>

Nahlásit jako SPAM
IP: 2001:718:2601:1f7:f513:4f...–
Zjistit počet nových příspěvků

Přidej příspěvek

Toto téma je starší jak čtvrt roku – přidej svůj příspěvek jen tehdy, máš-li k tématu opravdu co říct!

Ano, opravdu chci reagovat → zobrazí formulář pro přidání příspěvku

×Vložení zdrojáku

×Vložení obrázku

Vložit URL obrázku Vybrat obrázek na disku
Vlož URL adresu obrázku:
Klikni a vyber obrázek z počítače:

×Vložení videa

Aktuálně jsou podporována videa ze serverů YouTube, Vimeo a Dailymotion.
×
 
Podporujeme Gravatara.
Zadej URL adresu Avatara (40 x 40 px) nebo emailovou adresu pro použití Gravatara.
Email nikam neukládáme, po získání Gravatara je zahozen.
-
Pravidla pro psaní příspěvků, používej diakritiku. ENTER pro nový odstavec, SHIFT + ENTER pro nový řádek.
Sledovat nové příspěvky (pouze pro přihlášené)
Sleduj vlákno a v případě přidání nového příspěvku o tom budeš vědět mezi prvními.
Reaguješ na příspěvek:

Uživatelé prohlížející si toto vlákno

Uživatelé on-line: 0 registrovaných, 48 hostů

Podobná vlákna

Optimalizace pro IE — založil Gadael

Funkce pro přepínání kódu — založil Thermopolis

 

Hostujeme u Českého hostingu       ISSN 1801-1586       ⇡ Nahoru Webtea.cz logo © 20032016 Programujte.com
Zasadilo a pěstuje Webtea.cz, šéfredaktor Lukáš Churý