Category Archives: Programare

Categorie dedicata subiectului programare … in ce limbaj imi vine mie pe chelie

Lookup Table în PHP

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.

Parole aleatoare în Linux, “extended ASCII”

Deși în teorie problema din titlu este una rezolvată, în practică de multe ori mi-am dorit o parolă de o complexitate mai mare față de ce-mi oferă majoritatea uneltelor ce nu ies din standard ASCII. Prin metoda subsemnatului, se ia următoarea funcție și se trântește în .bashrc:

function urandompass()
{
cat /dev/urandom | tr -dc '[\41-\176\241-\254\256-\376]' | fold -w $1 | head -n 1
}

Apelul este cretin de simplu: urandompass 12 va genera o parolă de 12 caractere. Sau cheie, am zis-o și pe asta. Funcția poate fi folosită pentru a genera chei pentru un “block cipher”.

Cu toate acestea, pentru cei cu terminalul setat pe UTF-8, caracterele dincolo de range-ul celui de-al 7-lea bit (aka cele ce intră în extended ASCII) nu vor fi printate corect. Teoria spune faptul că UTF-8 este compatibil doar cu setul ASCII, ăla standard. În prealabil este nevoie să se seteze terminalul pe un char encoding single-byte ce implementează vreo formă de extended ASCII gen ISO-8859-x, unde x = 1 este Western, x = 2 = Central European, etc. Personal prefer Western. Pentru cei cu Gnome Terminal, “Terminal » Set Character Encoding » Add or Remove …” dacă e pentru prima dată, dacă nu, atunci ar trebui să poată fi ales din meniu un encoding diferit de cel implicit. Buba este faptul că Gnome Terminal are memorie destul de proastă deci va da reset la UTF-8 dacă terminalul este închis sau se execută reset, deci operația trebuie repetată înainte de a genera orice parolă / cheie.

Acum urmează partea pentru obsedații de detalii aka cei după chipul și asemănarea subsemnatului. “Limitarea” la extended ASCII, ce oricum oferă o complexitate mai bună decât majoritatea generatoarelor, provine de fapt din tr. Un info coreutils ‘tr invocation’ în shell specifică destul de clar: “Currently `tr’ fully supports only single-byte characters.”, deci suportă multi-byte din jumătatea lui cinci. Pentru amatorii de detalii, acele range-uri din funcția mea au fost documentate, oarecum, în prealabil.

În DEC:

33-126
161-172
174-254

În OCT:

41-176
241-254
256-376

Evident, cu ochiul liber se poate vedea că tr primește octal, precum zice manualul. Pentru a le determina am încercat cu encoding ISO-8859-1 și ISO-8859-2 o aplicație ce printează tot range-ul single-byte (mă rog, fără ultimul caracter).

Pentru PHP-iști:

for ($i = 0; $i < 256; $i++)
{
echo $i.': '.chr($i)."\n";
}

Iar pentru snobii cu C, avem alternativă 😀 :

#include 
 
int main()
{
        for (int i = 0; i < 256; i++)
        {
                printf("%d: %c\n", i, i);
        }
        return 0;
}

gcc -std=c99 -o chars chars.c

Inițial m-am inspirtat dintr-o versiune *sh de pe linuxquestions.org, dar arată cretin, nu dau paste la așa ceva. Mă cam strânge octalul de dinți. O versiune rescrisă pentru DEC junkies:

#!/bin/bash
 
chr()
{
	printf \\$(printf '%03o' $1)
}
 
i=0
while [ $i -lt 256 ]; do
	echo "$i: `chr $i`"
	let "i++"
done

Pentru cei ce preferă alte encoding-uri single-byte, dacă range-urile de mai sus nu sunt potrivite, atunci se poate rula oricând vreo aplicație de mai sus pentru a face un test de char printing.

Pentru cei ce nu s-au născut cu “DEC to OCT converter” în cap, așa ca subsemnatul, Calculator din Gnome (gcalctool) are și un mod Programming (Ctrl+P).

Căi UNIX corecte în PHP

Se dă următoarea problemă, aparent mai simplă decât zice titlul: să se determine dacă o cale de tip UNIX este corectă. Buba este faptul că această cale poate să fie către un fișier ce nu există, spre exemplu o cale de UNIX socket ce va fi creat într-un director ce va conține un pool de socket-uri. Deci funcțiile la nivel de filesystem nu vor ajuta, cel puțin nu în primă fază. În cazul  în care există vreo încercare de intuiție a scopului, da, scriu server scripting și în PHP. *sh este prea limitat pentru anumite chestii mai avansate, sau are nevoie de prea mult “boilerplate code”, pe când în Perl nu sunt încă fluent. Pentru cei ce au pierdut știrile de la ora 5, PHP nu mai este de mult un limbaj strict “web oriented”, funcționează bine merci și pentru “general purpose”.

Să revin la problema inițială. Practic se pot identifica două probleme: a) validarea unei căi inexistente – deci apelăm la regex; b) validarea directorului – deși fișierul poate să nu existe în timpul execuției de validare, directorul e musai să fie acolo. De regulă aplicațiile care creează câte un UNIX socket nu verifică aceasta și vor eșua să pornească.

Rezumat, codul arată cam așa:

$validate = preg_match('/^(\/[^\0]*?\/?)[^\0\/]+$/', $path, $matches);
if (empty($validate) === TRUE OR is_dir($matches[1]) !== TRUE OR is_dir($matches[0]) !== FALSE)
{
	// handle error here
}

Acum, discuție pe marginea textului. Acest regex satisface direct ambele probleme. Prima, este fix problema de validare. Se ține cont doar de căi absolute – acesta fiind contextul în care operez. Cu toate acestea, soluția se poate adapta ușor pentru căi relative.

Singurul capturing group din expresie preia întreaga cale, mai puțin numele fișierului. A fost făcută să funcționeze inclusiv pentru root (/). Calea capturată trebuie să fie către un director, pe când calea întreagă trebuie să nu fie un director.

Teoria căilor este simplă. O cale UNIX poate să conțină orice caracter, mai puțin nul, iar / este folosit pe post de separator de directoare, deci este rezervat acestui scop. Căile de tip //var///www//// sunt valide. Exemplul anterior va duce în //var/www unde // în general (Linux, BSD) este tot una cu /. Nu am lucrat pe sisteme unde // să fie distinct față de /, deci nu am considerat că este nevoie să tratez cazul prin expresia de mai sus.

Dragă programatorule, dacă îți vine a copy-paste, fă refactor!

M-am săturat de cod prost scris ca de mere pădurețe. Nu mă refer la cod nefuncțional sau cu bug-uri. Mă refer la metodologia copy-paste la care se apelează intensiv din când în când. După care apucă-te și modifică ceva pentru a adăuga chestii noi. M-am săturat de gândire non-DRY datorită căreia apuc să modific în 5 locuri și 3 fișiere pentru a pune o chestie amărâtă care să arate la fel peste tot. În concluzie, pe lângă defularea de mai sus, m-am hotărât să mai dau niște idei.

Pe alocuri plângerile mele au avut succes. Acum două zile colegii de echipă mă ascultau în timp ce modificam niște chestii, iar involuntar am zis: iar de aici copiez dincolo … touche: “Ce-ai zis mă? Să copiezi?”. Exact ce ziceam mai sus … câteodată și mie îmi vine greu să nu scriu cod prost. Dar eforturile susținute = evoluție. În concluzie am luat linia aceea lungă (un apel înlănțuit de proceduri) și am pus-o într-o nouă metodă.

În concluzie vreo câteva idei, departe de a oferi o imagine completă:

  • dacă îți vine să faci copy-paste, fie ele și 3 linii de cod sau una lungă, înseamnă ca ai nevoie de un mic refactor.
  • o arhitectură bună, modulară, a aplicației, DRY (și preferabil KISS) compliant, duce la o mentenanță mai ușoară. Pentru a modifica ceva nu este nevoie să cauți toate instanțele aceleiași bucăți de cod.
  • dacă acea parte de ‘unknown’ umbrește puterea de a-ți crea arhitectura înainte de a o implementa, atunci orice model repetitiv din cod stă bine într-o metodă separată.
  • caută să înțelegi framework-ul pe care îl folosești. De exemplu în dezvoltarea web folosind MVC, nu prea are ce căuta într-un controller o chestie ce ar sta bine într-un helper/bibliotecă, pentru că atunci când este nevoie să fie apelată bucata respectivă din alt controller, fără refactor, o să fie trist. Desigur, excepție fac acele controllere moștenite, dar și acolo este o linie fină între ce se poate moșteni și ce ar trebui să fie apelabil global.
  • refactor, OOP, clase, interfețe, ‘design pattern’ (exemplu: singleton) ar trebui să nu fie doar cuvinte într-un vocabular de specialitate.