Ausazkotasuna erabiliz, talde batek algoritmo sinple bat sortu du datu fluxu batean objektu ezberdin asko kalkulatzeko.
Imajina ezazu oihan tropikal birjina batera bidaltzen zaituztela basoko bizitzaren errolda egiteko. Animalia bat ikusten duzun bakoitzean, argazki bat ateratzen duzu. Zure argazki digitalak ateratako argazki guztien erregistroa eramango du, baina zuri animalia bakarren kopurua baino ez zaizu interesatzen, oraindik zenbatu ez dituzun guztiak. Zein da zenbaki hori lortzeko modurik onena? «Begi bistako soluzioak eskatzen du orain arte ikusi dituzun animalia guztiak gogoratzea eta animalia berri bakoitza zerrendarekin alderatzea», azaldu du Lance Fortnow Illinoisko Teknologia Institutuko informatikariak. Baina jokatzeko modu adimentsuagoak daude, gaineratu du; izan ere, milaka sarrera badituzu, begi bistako ikuspegia ez da batere erraza.
Okertu egiten da. Zer gertatzen da Facebook bazara eta egunero saioa hasten duten erabiltzaile ezberdinen kopurua zenbatu nahi baduzu, are gehiago, horietako batzuk gailu askotatik eta askotan saioa hasten badute? Orain saio hasiera bakoitza milaka milioiko zerrenda batekin alderatzen ari gara.
Duela gutxiko artikulu batean, zientzialari informatikoek zerrenda luze batean sarrera ezberdinen kopurua alderatzeko modu berri bat deskribatu dute, eta metodo horrek sarrera kopuru txiki bat bakarrik gogoratzea eskatzen du. Algoritmoak elementuak banan-banan gehitzen diren edozein zerrendatarako funtzionatuko du: pentsa diskurtso bateko hitzak, uhal garraiatzaile bateko produktuak edo errepide bateko autoak.
CVM algoritmoa, bere sortzaileengatik hala deitua (Indiako Estatistika Institutuko Sourav Chakraborty , Lincoln-eko Nebraskako Unibertsitateko Vinodchandran Variyam , eta Torontoko Unibertsitateko Kuldeep Meel ), urrats esanguratsua da elementu ezberdinen arazoa deritzona konpontzeko. Zientzialari informatikoek 40 urte baino gehiago daramatzate arazo horrekin borrokan. Elementu fluxu bat efizienteki monitorizatzeko modu bat eskatzen du (horren guztizko kopurua eskura dagoen memoria baino handiagoa izan daiteke), eta, ondoren, elementu bakarren kopurua zenbatestea.
«Algoritmo berria izugarri sinplea eta inplementatzen erraza da», adierazi du Massachusetts-eko (Amherst) Unibertsitateko Andrew McGregor-ek. «Ez nintzateke harrituko [elementu desberdinen] arazoari praktikan aurre egiteko lehenetsitako modua bihurtuko balitz».
Arazoa eta CVM algoritmoak arazoa nola konpontzen duen argitzeko, imajinatu Hamleten audioliburua entzuten ari zarela. Lanak 30.557 hitz ditu. Zenbat dira desberdinak? Hori jakiteko, lana entzun dezakezu (eteteko botoia maiz erabiliz), hitz bakoitza alfabetikoki idatzi koaderno batean eta dagoeneko zure zerrendan dauden hitzak albo batera utzi. Amaierara iristean, zerrendako hitz kopurua baino ez duzu zenbatuko. Ikuspegi horrek funtzionatzen du, baina, gutxi gorabehera, hitz bakarren kopuru bereko memoria kantitate bat eskatzen du.
Datuen transmisioan ohikoak diren egoeretan, milioika elementu egon daitezke jarraipena egiteko. «Agian ez duzu dena biltegiratu nahi», dio Variyamek. Eta horretan eskain dezake CVM algoritmoak modu errazago bat. Trikimailua da, baieztatu zuen, ausazkotasunean konfiantza izatea.
Itzul gaitezen Hamletera, baina oraingoan zure lan memoriak (arbel bat) 100 hitzentzako tokia besterik ez du. Obra hasten denean, entzuten dituzun lehen 100 hitzak idazten dituzu, errepikapenak berriro alde batera utzita. Espazioa beteta dagoenean, sakatu eten eta jaurti txanpon bat hitz bakoitzeko. Aurpegia ateratzen bada, hitza zerrendan geratuko da; gurutzea ateratzen bada, berriz, ezabatu egingo duzu. Aurretiazko txanda horren ostean, 50 bat hitz desberdin geratuko zaizkizu.
Orain aurrera egin taldeak 1. txanda deritzonarekin. Segi Hamlet irakurtzen eta gehitu hitz berriak aurrera egin ahala. Zure zerrendan dagoen hitz bat aurkitzen baduzu, jaurti txanpona berriro. Gurutzea bada, ezabatu hitza; aurpegia bada, hitza zerrendan geratuko da. Jarraitu horrela arbelean 100 hitz izan arte. Ondoren, ezabatu ausaz gutxi gorabehera erdia, 100 txanpon jaurtiketen emaitzaren arabera. Hor amaitzen da 1. txanda.
Ondoren, jarraitu 2. txandarekin. Jarraitu 1. txandan bezalaxe, baina orain zailagoa izango da hitz bat mantentzea. Errepikatutako hitzen bat aurkitzen duzunean, jaurti txanpona berriro. Gurutzea ateratzen bada, ezabatu hitza, lehen bezala. Baina aurpegia ateratzen bada, bigarren aldiz jaurtiko duzu txanpona. Hitza mantenduko duzu soilik aurpegia bigarren aldiz ateratzen bada. Taula bete ondoren, txanda 100 txanpon jaurtiketetan oinarritutako beste garbiketa batekin amaitzen da, gutxi gorabehera hitzen erdia.
Hirugarren txandan, jarraian hiru aurpegi atera beharko dituzu hitza mantentzeko. Laugarren txandan lau aurpegi atera beharko dituzu jarraian. Eta horrela hurrenez hurren.
Azkenik k txandan, Hamleten amaierara iritsiko zara. Ariketaren helburua izan da hitz bakoitzak, egin dituzun ausazko aukeraketen arabera, hor egoteko probabilitate bera izatea: 1/2k. Adibidez, 61 hitz badituzu zerrendan Hamleten amaieran eta prozesuak sei txanda behar izan bazituen, 61 zati probabilitatea egin dezakezu, 1/26, hitz desberdinen kopurua zenbatesteko, eta horrek 3904 hitzeko emaitza ematen du kasu honetan. (Erraza da prozedura horrek nola funtzionatzen duen ikustea: demagun 100 txanponekin hasten zarela, bakoitza banaka jaurtitzen duzula, eta aurpegia ateratzen duten txanponak bakarrik gordetzen dituzula. 50 bat txanponekin amaituko duzu, eta norbaitek zenbaki hori probabilitatearen arabera zatitzen badu, ½, asma dezake hasieran 100 txanpon inguru zeudela).
Variyam eta haren kideek matematikoki frogatu zuten teknikaren zehaztasuna handitu egiten dela memoriaren tamainarekin. Hamletek 3.967 hitz bakar ditu zehazki. (Zenbatu egin zituzten). 100 hitzeko memoria erabili zuten esperimentuetan, bost egikaritzeren ondorengo batez besteko kalkulua 3955 hitzekoa izan zen. 1.000 hitzeko memoriarekin, batez bestekoa 3.964ra igo zen. «Jakina», azaldu du Variyamek «[memoria] hitz guztiak sartzeko bezain handia bada, orduan % 100eko zehaztasuna lor dezakegu».
«Hori oso adibide egokia da adierazteko batzuetan konponbide oso sinpleak daudela, bai eta oso oinarrizko eta ondo aztertutako arazoetarako ere, baina ez direla begi bistakoak eta aurkitu ditzaten zain daudela», baieztatu du Harvardeko Unibertsitateko William Kuszmaul-ek.
Jatorrizko artikulua:
Steve Nadis (2024). Computer Scientists Invent an Efficient New Way to Count, Quanta Magazine, 2024ko maiatzaren 16a. Quanta Magazine aldizkariaren baimenarekin berrinprimatua.