Problema implementării unui lookup table pare uneori simplă. În cazul în care se implementează ca un array indexat, iar obținerea unei valori se face prin metoda dă-mi valoarea Y de la cheia X, atunci problemele de performanță nu intervin.

M-am lovit de altă bubă, și anume implementarea unui lookup table simplu bazat pe căutare liniară construit pe baza unui pre-fetch. Ideea este simplu de implementat, și deși procesul respectiv nu rulează prea des, numărul valorilor distincte complică problema destul de mult. Într-un lookup table de 70.000 – 80.000 valori căutarea unui număr mai mare de valori durează peste jumătate de oră (nu știu exact, am oprit benchmark-ul după 30 minute) cu procesorul (sau un core) la ~100% load, pe când restul operațiilor se execută în secunde. Cam multicel pentru o căutare ce ar trebui să returneze TRUE / FALSE. Faptul că numărul de căutări este mai mare decât lookup table-ul în sine mai bate un cui în coșciugul metodei de mai sus. Se mai adaugă și faptul că deși în teorie valorie ar trebui să fie unice, datele din pre-fetch nu sunt neapărat validate în acest sens.

Pre-fetch – pseudo implementare

$haystack = array();
while($value = get_data())
{
	$haystack[] = $value;
}

Ideea este simplă. Stiva $haystack va conține toate valorile, inclusiv cele duplicat. Mă rog, pre-fetch-ul implementează ideea de “stivă” pentru că auto-indexarea cu [] are aceeași funcționalitate ca și array_push(), dar câștigă puțin la viteza de inserare a datelor. Durează câteva secunde, nu este o operație foarte complexă. De aici începe greul.

Căutare – implementare uzuală

Există tentația de a face căutarea pe baza lui in_array() sau array_search(). Ambele sunt aproximativ la fel de rapide (in_array() este cu maxim 1% mai lentă). Problema principală este căutarea liniară, fără indexare.

Dau chiar exemplele din codul meu de benchmark:

	public function bench_in_array($needle)
	{
		return in_array($needle, $this->haystack);
	}
 
	public function bench_array_search($needle)
	{
		if (array_search($needle, $this->haystack) === FALSE)
			return FALSE;
		return TRUE;
	}

Căutare – soluția optimă

Ambele soluții anterioare sunt aproximativ la fel de rapide, dar aproximativ la fel de lente. Interesul este dacă există o valoare. Duplicatele doar încurcă.

$haystack = array_flip($haystack);

Inversează valoarea cu cheile dintr-un array. Valorile duplicat dispar din moment ce un array (mă rog, devine ordered map) nu poate avea chei duplicat. Se pot aplica alte două metode distincte. Dau din nou exemplu din codul meu de benchmark:

	public function bench_array_flip_isset($needle)
	{
		return isset($this->flipped_haystack[$needle]);
	}
 
	public function bench_array_flip_array_key_exists($needle)
	{
		return array_key_exists($needle, $this->flipped_haystack);
	}

Pentru o listă de $needle scurtă (1% din $haystack, valori 100% valide), sunt aproximativ echivalente. Pentru un input 50% valid de dimensiunea $haystack, array_key_exists() este cu aproximativ 80% – 100% mai lent. Dar acum urmează partea frumoasă: căutarea se face indexat. Metoda este de cel puțin 2000 ori mai rapidă decât căutarea cu in_array() / array_search(). Adică în mod uzual căutarea de mai devreme de peste jumatate de oră durează aproximativ sub 3 secunde cu isset() și sub 5 secunde cu array_key_search(). Metodă testată pe un lookup table de 100.000 valori ce mi-a cam ucis browserul. Chrome a crăpat, Firefox a încărcat output-ul de la Codebench în vreo 3.5 GiB RAM. Atașez și imagini ce stau dovadă atrocității de mai devreme.

Adesea m-am lovit de problema sanitizarii variabilelor care provin din input, si nu zic asta facand referire la PHP, ci la programare in general. Din moment ce am avut boala sa studiez catusi de cat bazele securitatii, mi-a ramas in cap un principiu foarte bine formulat: “all user input is evil!”. Adevarat grait. Deci am inceput sa gandesc aplicatiile dupa metoda user proof. In primul rand cand testez ceva nou, nu testez dupa cum ar trebui sa fie utilizata aplicatia in mod corect, ci cum NU ar trebui sa fie folosita, si ce sa se intample in acele cazuri. In primul rand pentru ca o aplicatie nu este o chestie democratica unde userul face ce vrea el si adesea face prost. Deasemenea intervine si cealata extrema. Unde nu este prostie – este viclenie – deci se poate trezi cate un h4x0r de asta cu mai mult timp liber la dispozitie sa te caute la oo (a se citi: securizare).

Problema ID-urilor numerice in PHP desi este una destul de banala, rezolvarea este multipla. De-alungul timpului am testat mai multe chestii, dar doar recent am ajuns la o forma finala care sa ma multumeasca deplin. De ce ID-uri numerice? Pentru ca este foarte usor de lucrat cu ele cand se interactioneaza cu o baza de date. Orice tabela care trebuie sa stocheze in mod unic niste chestii, are o cheie primara. Pana acum cea mai desteapta chestie in materie de chei primare este cheia intreaga care se seteaza cu auto-increment – ceea ce asigura complet unicitatea datelor. Recomandarea ar fi ca auto incrementul sa inceapa de la 0 (chestia asta o sa se lege de ce o sa zic mai jos). Bonus ar fi faptul ca fiecare tabela de acest gen ar trebui sa aiba cheia primara indexata pentru a reduce considerabil timpul de cautare al ei.

Adesea aceste chei primare din baza de date sunt trimise prin intermediul requesturilor de tip GET, deci se vor regasi in componenta URL-ului. Problema se pune atunci cand pe langa acel ID numeric, utilizatorul (in mod intentionat) introduce si altceva pe langa acel ID. Treaba poate sa se imputa de la XSS (Cross Site Scripting) – atunci cand acea cheie se regaseste in pagina, sau la atacuri de tip SQL injection (mai grav).

Desi exista functii native in suportul de MySQL pentru PHP, acestea sunt destul de triste la ID-uri numerice, deci am preferat propria metoda:

function clean_id($id)
{
$id=preg_replace("@[^0-9]@", "", $id);
if (empty($id))
	$id=0;
return $id;
}

Chestia asta de mai sus face vreo doua chestii … prima este aceea ca da strip la tot inputul care nu e numeric. A doua verifica ce a mai ramas, iar daca are valoarea 0 (orice 0 din PHP), atunci returneaza un 0 numeric. Este important acest zero numeric … ziceam ceva mai sus de el … acest zero numeric are grija ca interogarea sa nu dea de o chestie gen <<WHERE id=”>> si sa bubuie o eroare de SQL (care in anumite cazuri … ar putea la randul ei sa divulge alte chestii).

Actualizare:

Datorita observatiei lui AgLiAn am ajuns la concluzia ca functia mea initiala nu rezolva o problema: interger overflow, chestie ce mai departe se traduce in interpretarea ca float de catre PHP – si de unde pot aparea alte probleme. Si pentru ca am mentionat pe undeva mai sus de auto-increment (si acest obicei nu o sa se transforme peste noapte pana la proba contrara ce demonstreaza un obicei prost), functia clean_id(); devine:

function clean_id($id)
{
return abs(intval($id));
}