Back to site
Since 2004, our University project has become the Internet's most widespread web hosting directory. Here we like to talk a lot about web development, networking and server security. It is, after all, our expertise. To make things better we've launched this science section with the free access to educational resources and important scientific material translated to different languages.

U slavu tweak-ovanja: Takmičenje u programiranju po uzoru na wiki

Od Neda Gulleya , The MathWorks, Inc.

Znam nešto što i vi želite da znate. Ali da li ću vam to reći? Zašto bih? Od kakve je to koristi za mene? Internet tehnologija čini online saradnju lakom, ali ljudska priroda se tvrdoglavo odupire promeni. Zašto bih ja sarađivao sa vama? Šta bi me to ubedilo da podelim svoje ideje sa vama, budući da ih vi možete iskoristiti protiv mene? U širem smislu, kako možemo da napravimo sistem koji podstiče ljude da sarađuju, na primer, putem pisanja korisnog koda? Ovo su neka od pitanja koje smo istražili sa novom vrstom open source takmičenja u programiranju.

Takmičenja u programiranju su postala stalna odlika geek kulture. ACM na primer vodi studentsko takmičenje u programiranju koje se toliko proširilo da sad uključuje skoro 4000 timova iz svih krajeva sveta [1]. Takmičenja okupljaju učesnike na jednom mestu ili se mogu odvijati na internetu, ali sva ta takmičenja imaju isti oblik: imate određeni problem i ograničeno vreme da napišete bolji kod od bilo koga drugog. Ovaj tip takmičenja je dobar za određivanje najtalentovanijeg pojedinca između grupe takmičara, ali je to više na akademskom nivou. Šta da postoji takmičenje koje bi preciznije modelovalo način na koji se ideje zapravo kreću? Recimo da jedan čovek da ideju, drugi čovek je može usvojiti i modifikovati čak i dok takmičenje traje. Pobednički ulaz za ovaj tip takmičenja bi bio amalgamirani napor koji ulaže mnogo ljudi, ljudi koji se istovremeno takmiče i sarađuju. Ovaj pristup je više neuredan, organski način na koji se dobar deo softvera, naročito open source softvera, zapravo pravi. Na taj način, open source takmičenje u programiranju bi nam pokazalo kako inovacija zapravo radi u stvarnom svetu. Nekoliko godina smo održavali upravo ovakav tip takmičenja pomoću MATLAB programskog jezika, a rezultati su nam dali fascinantnu kvantitativnu perspektivu u vezi sa dinamikom inovacije i nagradu za kolaborativno programiranje [2]. Vremenom smo posmatrali neverovatnu sličnost između našeg open source takmičenja i web sajtova koji su bazirani na wiki. Wiki je ogoljen alat za upravljenje dokumentima za online saradnju. Veoma jednostavno, to je stranica ili skup stranica koje može modifikovati bilo ko ko ih pregleda. Ovo jednostavno pravilo ima velike posledice. Drastičnim smanjenjem troška učešća, broj učesnika se srazmerno povećava. Na naše iznenađenje, dokumenta napravljena i uređivana na wiki-ju su često ubedljiva, dobro se održavaju i od velike su pomoći. Ogromni projekti su napravljeni kao wiki-ji, od kojih je najfascinantnija Wikipedia, čitava enciklopedija koja se spontano uvećava i kojoj raste vrednost putem saradnje indukovane wiki-jem [3]. Naša takmičenja liče na wiki u tom smislu da svako može da modifikuje bilo koji kod na displeju. Kao i kod wiki-ja, rezultat je plodan susret umova i model za uspešan kolaborativni dizajn.

Kako takmičenje funkcioniše

MATLAB jezik (koga je razvio The MathWorks, Inc.) je optimizovan za crunching brojeva velikom brzinom. Naročito je koristan za brz prototip algoritama. Dugogodišnji korisnici jezika su razvili trikove i tehnike koji trguju brzinom implementacije, brzinom izvođenja, elegancije i kompaktnosti. Mi smo pokrenuli prvo takmičenje pre pet godina u nadi da će to biti zabavan način da se MATLAB korisnici podstaknu da dođu i podele svoje veštine. Uspeh takmičenja nas je ubedio da od njega napravimo redovan događaj. Trudimo se da održimo takmičenje dva puta godišnje u trajanju od oko nedelju dana. Održali smo osam različitih takmičenja od januara 1999. godine. Ova takmičenja se obično svedu na pokušavanje da se reši jedan težak problem optimizacije za što manje vremena. Problem putujućeg trgovca je kanonički primer ovoga: koja je najkraća moguća kružna putanja koju trgovac mora da napravi kroz datu listu gradova? Učesnici moraju da napišu MATLAB kod koji, kada se obiđu svi gradovi, vraća spisak koji sadrži informaciju o tome kojim je putem najlakše obići ove gradove. Oni nikad ne vide naš test paket. Oni jednostavno pošalju svoj najbolji algoritam a kompjuter ih rangira i beleži koliko mu je trebalo vremena da se pokrene. Stoga njihov algoritam sadrži rezultat (proputovana razdaljina koju treba što više smanjiti) i CPU vreme (koje takođe treba smanjiti). Ovo se kombinuje u jedan skor pomoću eksponencijalne kazne za CPU vreme kao što je prikazano ispod.

skor = k1 * razdaljina + k2 * e^(k3 * vreme)

Vrednosti k1, k2 i k3 se moraju naštimovati za svako takmičenje. Ako uopšte ne ograničimo CPU vreme, ulazima može trebati dosta vremena i mogu pokvariti naš sistem. S druge strane ako previše ograničimo CPU vreme, javiće se brzi ali dosadni algoritmi kao rezultat. Problemi se biraju tako da niko nema dovoljno vremena da nađe apsolutno najbolje rešenje. Učesnici moraju da istraže spektar mogućnosti između učinka algoritma i brzine izvođenja. Ovaj oblik takmičenja je važan jer to znači da uvek postoji dovoljno mesta za napredovanje kako takmičarska nedelja odmiče.

Sa tačke gledišta učesnika, takmičenje se sastoji od tri primarne web stranice: trenutno stanje, stranica za pregled kodova iza bilo kog unosa i stranica za nov unos. Kao što je rečeno, neobična odlika ovog takmičenja jeste što takmičari šalju kod koji se odmah skoruje, rangira i postavlja tako da ga svi mogu videti. Zapravo, kao i sa dugmetom "Uredi ovu stranicu" na wiki stranici, takmičenje je specijalno napravljeno da podstakne učesnike da kradu jedni drugima kod. Kao što je prikazano u Figuri 1, ovaj proces vam omogućava da vidite kod za bilo koji unos (obično za vodeći unos), da ga promenite i da ga pošaljete sa svojim imenom na njemu.

How the contest works
Figura 1. Kako takmičenje radi

Recimo da na primer vidite vodeći unos koji sadrži sledeći red.

x = [1 2 3 4 5 6 7 8 9 10];

Kao MATLAB stručnjak znate da red

x = 1:10;

ima isti efekat i da se pokreće mnogo brže. Morate samo da pritisnete dugme "Uredi ovaj unos", napravite promenu i da ga pošaljete u red za ocenjivanje. Uz malo sreće dospećete na prvo mesto.

Primer takmičenja

Pored naših sopstvenih varijanti poznatog problema putujućeg trgovca, evo nekih drugih primera takmičenja koje smo održali.

  • Mapiranje Marsa [1647 unosa] Dato je nekoliko robotizovanih tragača i gruba mapa dela površine Marsa. Koja je optimalna ruta koja će vam pomoći da istražite najveći deo područja za najmanje vremena?
  • Savijanje proteina [2437 unosa] Protein je niz amino kiselina, od kojih je svaka ili hidrofobična ili hidrofilična. Ukoliko imate takav protein, savijte ga u dve dimenzije da biste smanjili udaljenost između hidrofobičnih amino kiselina.
  • Masterum [1138 unosa] Rešite skrivene obojene klinove u opštem Masterum problemu koji može imati bilo koji broj klinova i boja.
  • Molekularno modelovanje [1631 unosa] Data je tabela udaljenosti između različitih parova atoma u molekulu. Rekonstruišite oblik molekula.

Po nalogu postoji 100-150 takmičara iako je ovaj broj teško ustanoviti budući da ljudi ne daju svoja imena uvek. Neki takmičari se odlučuju za slanje jednog ili dva unosa, a drugi šalju desetine ili u nekim slučajevima čak i stotine algoritama poboljšavajući ih vremenom.

Vizuelno prikazivanje rezultata

Kako biste razumeli prirodu takmičenja vrlo je korisno prikazati rezultate vizuelno. Figura 2 prikazuje 977 unosa sa našeg takmičenja Molekularnog modelovanja [4]. Svaka plava tačka je drugačiji unos. Grafički prikazujemo skor svakog unosa (niži skor je bolji) u odnosu na vreme kada je poslat, tako da se horizontalna osa širi tokom nedelju dana. Pobednički unos se definiše kao unos sa najmanjim skorom kada se takmičenje završi. Crvena linija koja se nalazi pri dnu označava najbolji skor u bilo kojoj vremenskoj tački. Budući da je pobednički unos onaj sa najmanjim (najboljim) skorom, linija se polako spušta dok ne sustigne pobednički unos u donjem desnom uglu.


Figura 2. Skor unosa nasuprot vremenu slanja

Tamo gde je crvena linija praktično ravna, doprinos pravljenju koda je takođe mali. Veliki vertikalni padovi su ređi i generalno pokazuju fundamentalni napredak kada je algoritam u pitanju. Vodeća strategija se iznova menja pre nego što je kvalitetno drugačiji pristup u potpunosti zameni. Uzajamno dejstvo ova dva pristupa vodi stepenastom prikazu na grafikonu kao što se to može videti na figuri 2.

Imamo dodatne informacije o ovim unosima koje nisu prikazane u figuri 2: znamo kada je jedan unos nastao od drugog unosa. Stoga, ako unos nazvan npr. "TurboSolver" inspiriše nekog da ga modifikuje i nazove "Sin TurboSolver-a", možemo prikazati vezu između njih linijom. Potomak koji je modifikovan može stvoriti složeno porodično stablo. Sledeća figura 3 prikazuje iste podatke sa takmičenja kao i pre sa linijma koje povezuju sve povezane unose; kako bi bilo što jasnije, naglasili smo jedan klaster povezanih unosa crvenom bojom. Crvene tačke povezane crvenim linijama su unosi koji pripadaju jednoj familiji unosa. Unos koji se nalazi skroz sa leve strane unutar crnog kruga jeste rodonačelnih ove grupe. On se od ostalih prethodnih unosa izdvaja po tome što ga njegov stvaralac nije napravio po uzoru na neki drugi unos koji bi predstavljao njegovog "roditelja". Ovo znači da je algoritam nov, iako je autor možda odlučio da sakrije odakle mu inspiracija. Prateći porodice unosa i modifikacija koda možemo videti kako i kada dolazi do poboljšanja.


Figura 3. Porodica povezanih unosa

Figura 4 prikazuje koliko je linija koda svaki od 90 vodećih unosa takmičenja u Molekularnom modelovanju sadržao. Kako biste stekli utisak koliko koda je sačuvano tokom vremena, svaka linija zelenom bojom prikazuje koliko je linija koda identično linijama prethodnog takmičara koji je vodio. Kod se čuva za vreme takmičenja, a to ide dotle da samo jedna linija pravi razliku između dva unosa. Možete da vidite da dok linija koda teži da bude vremenom sve duža, ona se može i smanjiti kada se nebitni delovi koda odsecaju.


Figura 4. Čuvanje koda u vodećim unosima

Šeme učešća: Tweak-ovi i Leap-ovi

Uopšteno govoreći imate dva izbora ako želite da učestvujete u takmičenju. Možete poslati potpuno nov pristup u nadi da će on predstavljati skok u performansama ili možete modifikovati postojeći program. Mi koristimo reč "tweak" kako bismo opisali proces pravljenja malih modifikacija na tuđi kod. Takmičenje se sastoji od cik-cak kretanja između leap-ova i tweak-ova. Vodeći takmičar se stalno stavlja na probu kako bi mu se našle slabe tačke i kako bi se videle slabosti algoritma. Duge borbe tweak-ova se mogu okončati dramatičnim preokretima u kodu. Kada se takav preokret dogodi on takođe stvara mogućnosti za tweak-ovanje i okuplja znatiželjne takmičare koji će se sad sjatiti oko novog vodećeg takmičara.

Dobra stvar u vezi sa tweak-ovanjem jeste što se značajno smanjuje granica unosa. Ne morate da razumete uključeni algoritam, jedino morate da znate da promenite sporiju liniju koda bržom koja radi istu stvar. Nijedan napredak nije dovoljno premali kako bi se smatrao vrednim doprinosom. Ako prvi primetite da vodeći unos sadrži varijablu koja se nikad ne koristi, možete jednostavno obrisati tu liniju i ponovo poslati fajl sa svojim imenom i bićete (trenutno u najboljem slučaju) prebačeni na prvo mesto. Mnogi ljudi u početku vide tweak-ovanje kao parazitski način, naročito oni kojima su ideje "pokradene" na prvom mestu. Ali tweak-ovanje predstavlja zapravo gorivo koje pokreće čitavo takmičenje. Ono nudi trenutnu nagradu tweak-u - uz ulaganje od samo nekoliko minuta, vaše ime se pojavljuje na vodećem mestu, obasjano slavom. Ova praksa je takođe izazivanje originalnog autora na dvoboj ("Kako se neko usuđuje da tweak-uje moj kod!"). Ako vas neko tweak-uje, želećete to da znate. A takođe možete uložiti trud da se vratite na svoje prvo mesto pomoću tweak-ovanja.

Ova situacija je analogna nekom ko ispravlja greške u spelovanju u Wikipedia članku. Kad shvatite da je vaša mala promena "otišla uživo" i da će je videti čitav svet, to vam može doneti pravo uzbuđenje. Ovaj mali nivo aktivnosti, bilo da je u pitanju tweak-ovanje koda ili provera teksta na wiki stranicama obezbeđuje adiktivnost koja gura ljude da sve više učestvuju. Smatramo da je tweak-ovanje stvar na koju se naši učesnici najčešće žale, ali je to istovremeno i odlika koja ih tera da se još više unose. Naše table za diskusiju su preplavljene pitanjima kao što su:

  • Ko dobija najveće zasluge za dati kod?
  • Ko je najviše doprineo, a ko je "samo tweaker"?
  • Koja je razlika između značajne promene i tweak-a?

Ovaj tip pitanja muči i softverske projekte u stvarnom svetu. Čini se da postoji kulturalna predispozicija da se nađe i glorifikuje (uglavnom mitski) prodor usamljenog genija. Budući da se ovaj model ne poklapa uvek sa stvarnošću, na ova pitanja ne postoji zadovoljavajući odgovor. Na sreću, okvir takmičenja se ponaša kao rastvarač koji smanjuje ovaj tip "ja sam uradio više od tebe" prepucavanja i povećava plodnu saradnju među raznim grupama. Wikiji dele ovo svojstvo. Poznato je da newsgrupe i weblogovi teže da rasplamsaju vatru, dok wiki dokumenta pokušavaju da je ugase [5]. U slučaju našeg takmičenja, prepucavanje se ipak dešava, ali je svima u suštini jasno da se svi zabavljaju. Deo ove uspešne formule jeste činjenica da mi često ne nudimo vredne nagrade takmičarima. Primarna nagrada je socijalne prirode. Ponovo, putem analogije, pretpostavite da su ljudima koji su doprineli Wikipedia sajtu isplaćene velike sume novca na osnovu toga koliko je njihovih reči opstalo u člancima koje su menjali. Možete samo da zamislite zbrku koja bi tada nastala. Preduzeće koje je zasnovano na reputaciji se lako može pokvariti novcem.

Zaključci

Kada prvi put čuju kako Wikipedia sajt funkcioniše ljudi na to obično gledaju sa prezirom i u neverici. On ne može raditi. Kako bi mogao? Slično, MATLAB online takmičenje u programiranju je napravljeno na skoro paradoksalnoj premisi koja glasi: takmičenje može biti kolaborativno. Uprkos svim očekivanjima, ova drama tweak-ova i leap-ova čini MATLAB programiranje zabavnim sportom. Ponovo i ponovo nam takmičari govore koliko im je ovo bilo zabavno. "Ovo je jedna od najadiktivnijih i najkompulsivnijih stvari koje sam probao", naveo je jedan takmičar. "Oprostite mi, tweak-ovao sam....rešio sam da više ne tweak-ujem, ali nisam siguran da mogu da se zaustavim", reče drugi. I ovo: "Kod kuće, iako sam otac troje dece, moj posao je bio rad na takmičenju". Kao i sa wikijima uspeh nastaje iz nagrađenog ega i trenutne gratifikacije koja je nastala usled osećaja učešća u velikoj i smislenoj aktivnosti. Rezultirajući visok nivo učešća stvara atmosferu u kojoj se odvija algoritamska evolucija. Pobednički unos na svakom takmičenju predstavlja isprepletani trud desetina ljudi.

I da se vratimo na naše prvobitno pitanje: zašto bi ja trebalo da sarađujem s tobom? Odgovor je: cenim tvoje mišljenje. Budući da tvoje mišljenje o meni zavisi od vrednosti ideja koje ulažem, radiću vredno kako bi ti dao baš ono što želiš. Dobro okruženje za saradnju kontinuirano i velikodušno nagrađuje deljenje nagrade koja povećava reputaciju. Uspešna saradnja i takmičenje odjekuje popularnošću open source programiranja i wikija, a to će lako naći put u mnoga preduzeća kako kolaborativni dizajn postaje sve učestaliji.





Published (Last edited): 24-02-2013 , source: http://starchamber.com/gulley/pubs/tweaking/tweaking.html