Danas mi je na Twitteru iskočilo nekoliko cvrkuta sledećeg sadržaja
I scored 94% in #c on @Codility!
I scored 100% in #csharp on @Codility!
I’ve got Golden Certificate Delta 2011 on @Codility!
Programski jezici, testiranje znanja, “code” u nazivu? Sasvim dovoljno da rasplamsa moju radoznalost…
Kao prvo, šta je Codility? Bez prevelikog udubljivanja u tematiku sajta i vršljanja po njemu, jasno se vidi da je ideja autora bila da iskombinuje sajt za zapošljavanje (npr. Freelancer.com) sa sajtom za vežbanje algoritama (odličan primer za ovo drugo bi bio domaći Z-Trening).
Codility saves time of software talent recruiters by filtering out job candidates who cannot write correct programs.
Codility administers short programming tests and checks whether solutions are rock solid.
Naime, da bi se poslodavcima olakšao proces selekcije, ovaj sajt pred zainteresovane programere stavlja određene algoritamske zadatke koje oni moraju rešiti za ograničeno vreme da bi pokazali svoje (neophodno) znanje. Naravno, ceo proces je automatizovan, pa se tako rešenja testiraju na predefinisanom skupu test primera. Veoma zanimljiva ideja, ali i nezgodna, jer poslodavac procenu kandidata (odnosno nekih njegovih kvalifikacija) prepušta računaru — setimo se problema koje je Skynet napravio.
Jedna od stvari koje Codility nudi jeste besplatno testiranje za nekoliko algoritamskih problema. S obzirom da je najosnovnija pretplata 40€ mesečno, ova opcija je veoma bitna da bi privukli nove mušterije. Zbog toga oni nude neku vrstu sertifikacije koja zapravo nema pravu vrednost, ali predstavlja zanimljivu vežbu.
Odlučio sam da se oprobam, pa sam dobio sledeći zadatak (uprošćena verzija, ali sa istom poentom):
Dat je niz od N brojeva (N <= 20.000) iz intervala [1, 100]. Potrebno je svakom broju dodeliti znak + ili - tako da apsolutna vrednost sume svih elemenata bude što manja moguća. Potrebno je da program vrati tu najmanju moguću sumu.
Moje rešenja problema bilo je sledeće:
int abs(int x)
{
return (x < 0) ? -x : x;
}
int min_abs_sum ( int A[], int n )
{
int *count = (int*)calloc(105, sizeof(int));
int i;
for (i = 0; i < n; i++)
count[abs(A[i])]++;
int suma = 0;
for (i = 100; i >= 0; i--)
while (count[i]-- > 0)
suma = abs(suma-i);
return suma;
}
Najobičnije greedy rešenje koje redom uzima brojeve počevši od najvećeg (koristi se counting sort), pa ih oduzima od trenutne sume da bismo se što više približili nuli. Ovakvi algoritmi su dosta efikasni, jer u svakoj iteraciji uzimaju trenutno najbolje rešenje, ali su zbog toga često i netačni. Međutim, ispostavilo se da je ovo tačno, pošto je prošlo sve test primere. Dobio sam svoj sertifikat i u detaljima se moglo videti da rešenje zaista jeste brzo i da radi besprekorno.
Iako je na njihovom sajtu sve prošlo u redu, nisam mogao da se otmem utisku da ovakvo rešenje nije optimalno, kao kada bismo rešavali problem vraćanja kusura greedy algoritmom. Sat vremena kasnije se ispostavilo da sam u pravu (odnosno da nisam, s obzirom da mi je algoritam netačan): ukoliko je ulaz niz {3, 3, 3, 4, 5} rešenje je 0 (5+4-3-3-3), dok je moj algoritam vraćao 2 (-5+4+3-3+3).
I ovde dolazimo da važnosti testiranja. Ljudi iz Codilityja su osmislili zadatak i test primere, ali nisu uspeli da pokriju sve slučajeve, pa čak ni kad su ovako jednostavni. Generalna praksa kod smišljanja test primera za algoritamske probleme je da više ljudi reši problem na različite tačne i netačne načine (i neefikasne, ukoliko postoji vremensko ograničenje), pa da se osmisli skup ulaznih podataka koji će samo optimalan algoritam u potpunosti pravilno rešavati. Kako ovo osnovno načelo nije poštovano, ova greška je uspela da se provuče. Nisam aktivni korisnik ovog sajta, pa ne mogu da kažem da li su ozbiljnije pristupili ostalim zadacima, ali je pomalo neozbiljno da preview koji treba da privuče korisnike ne radi ispravno. Srećom, ne ignorišu mailove, pa su veoma brzo izmenili test primere nakon što sam im skrenuo pažnju na ovu grešku.
Budimo realni — bagovi su neizbežna stvar. Međutim, to nikako nije razlog da se faza testiranja u potpunosti preskoči, odnosno “prepusti” korisnicima. Testiranje softvera je zadatak na koji ljudi često gledaju sa nipodaštavanjem, a on je zapravo podjednako važan kao i sâm razvoj softvera. Šta više, od testera se očekuje da razumeju kôd programa i njegovo funkcionisanje da bi mogli uspešno da predvide bagove, pa bi oni neretko mogli da zamene mesta sa programerima i naprave podjednako dobru aplikaciju. Možda i bolju.
Bitno je da ljudi sa ovakvim znanjem testiraju softver, jer samo oni mogu da uoče bagove koji bi prouzrokovali loše rezultate koji običnom korisniku izgledaju validno. Iako su neki programi komplikovaniji/zahtevniji od drugih (npr. softver banke), svaki klijent ima pravo da naručeni program radi najbolje moguće, pa je zato testiranje uvek važno i apsolutno neophodno.