Uparivanje čarapa – na pravi način

Submitted by Бранислава Шандрих on 11/04/2015 - 00:34

carape

Verovatno vam se makar jednom mesečno događa da uparujete svoje čarape i u očaju razmišljate o primeni neke efikasne strategije koja bi vam skratila vreme provedeno u izvršavanju ovog nezanimljivog, a opet neminovnog zadatka. Kako se na čarape obično i ne misli preterano, broj pari je mali, većinu parova i nije moguće formirati (Fenomen nestanka druge čarape. Možda tema za sledeći broj!) – i vreme prođe, a na optimizaciju se zaboravi. Do sledećeg uparivanja.

Standardni algoritam koje znaju i naše bake je sledeći:

1.            Iz gomile od 2n čarapa izabere se jedna nasumično

2.            Ista gomila se pomno pretraži i pronalazi se parnjak

3.            Algoritam se ponavlja nad gomilom od 2(n – 1) čarapa

Pravi programersko-matematički um rekao bi da može i bolje.

Postavimo problem na sledeći način: Neka je data gomila od n pari čarapa, odnosno, neka čarapa ima 2n i svaka ima tačno jedan parnjak. Pretpostavka je da n nije jako veliki broj (čak i da ste neprikosnoveni čistunac i menjate čarape na dnevnoj bazi, a perete veš jednom mesečno). Postavlje se pitanje – kako utrošiti najmanje vremena na uparivanje?

 

Evo nekih rešenja koja nude stručnjaci.

A. Formiranje klasa ekvivalencije

Rešenje predlaže sledeći sled koraka:

1. Kreirati gomilice čarapa na osnovu boje (gruba podela – crvene karirane čarape, kao i crvene čarape na pruge nalaze se u istoj gomili)

2. Odabrati metriku – na primer, na osnovu šare, te razvrstati čarape unutar gomile. Ovo je trenutak u kom se rastaju karirane i prugaste čarape.

3. U okviru dobijenih podgomila rekurzivno ponoviti postupak, sve dok se ne dobiju toliko mali skupovi čarapa da ih je jednostavno vizuelno obraditi!

 

A1. Paralelizacija

Ideja je paralelizovati prethodno opisani postupak, odnosno angažovati više ljudi za ovaj posao. Doduše, i ovaj postupak košta: sudaranje šaka, međusobno dogovaranje... Optimizacija bi eventualno bila da se, na početku, svakoj osobi dodeli tačno jedna gomilica. Na taj način se izbegavaju navedeni problemi paralelizacije. Na kraju je neophodno samo spojiti sve gomile, a to je postupak logaritamske složenosti: O(log(broj osoba * broj gomilica po osobi)), u slučaju da se i za spajanje primeni optimalan algoritam.

 

B. Čarape na vidiku

Ovaj metod nudi jednostavno rešenje:

1. Rasprostreti 2n čarapa po nekoj velikoj površini (na primer krevetu ili tepihu)

2. Pogledom prelaziti po gomili sve dok se ne uoči par

3. Izbaciti uparene čarape iz gomile

4. Ponoviti postupak nad 2n – 2 čarapa

Iako jednostavna, ova strategija ipak ne nudi mnogo bolje rešenje u odnosu na ono intuitivno, te ćemo analizirati i ostale metode.

 

C. Staro dobro sortiranje

Slučaj 1: Sve čarape su identičnog izgleda i veličine.

Iako nam ovaj slučaj daje najbolju (konstantnu) vremensku složenost, složićemo se da ipak nije čest u praksi.

Slučaj 2: Čarape je moguće kategorizovati

Pretpostavka je da se čarape mogu na neki način klasifikovati: na osnovu vlasništva (poznato je da čarape pripadaju dvema osobama), boje (čarape možemo kategorizovati kao plave, crvene, crne itd.), veličine (na primer, neke su 38 a neke 43), materijala itd.

Tada se primeni tzv. Radix sort algoritam, koji deli ulazni skup podataka na klase ekvivalencije. Ono što ovaj algoritam čini optimalnim jeste to što se u sledećem koraku ne primenjuje isti postupak rekurzivno na svaku od gomila, već opet na početnu gomilu – ali sa drugim kriterijumom particionisanja.

Jedan konkretan primer: razbiju se čarape na dve klase ekvivalencije – Njene (X) i Njegove (Y) čarape. Klase se ne čuvaju, već se gomila opet vraća u početno stanje, ali u novom redosledu (klasa X pa klasa Y). Neka je sledeći kriterijum boja. Predefinišemo sada 7 klasa: crvene, plave, crne, bele, žute, smeđe i zelene. Sve čarape iz klase X stavljamo u adekvatne gomilice, a onda sve to ponovimo i za klasu Y. Vratimo čarape u početno stanje ali u novom redosledu (sve crvene iz klase X, pa sve crvene iz klase Y itd).

Radix sort algoritam ima veoma povoljnu složenost, O(nlogn), što ga čini zgodnim kandidatom za najoptimalniji algoritam sortiranja čarapa.

 

D. Igra pamćenja

U prvom algoritmu navedenom na listi, osoba uzme jednu čarapu, a potom pretražuje pogledom gomilu dok joj ne nađe par. Verovatnoća da se postigne uparivanje je mala, u ovom slučaju 1 : (2n – 1), i opada s povećanjem broja čarapa. Ideja je da se uvećaju šanse time što bi se umesto jedne – uzelo pet čarapa, a zatim upamtila njihova svojstva (boja, šare, oblik itd).

Zašto baš pet? Navodno, čovek može da formira dobro pamćenje za 5 do 7 elemenata u svojoj radnoj memoriji. Da ne bi bilo gubljenja vremena na sam postupak memorisanja osobina, smatraćemo peticu optimalnom brojkom. Postupak je:

1. Uzeti jednu iz gomile od 2n – 5 čarapa

2. Uporediti šare izabrane čarape sa ostalih pet izdvojenih. Ako dve formiraju par, eliminisati ih. Inače, posmatrati novi skup od 5 + 1 čarapa.

3. Nastaviti postupak.

Daljim izvlačenjem će svakako biti više od pet izdvojenih čarapa, čime, istina, opadaju performanse rada, ali se takođe povećava verovatnoća da će izvučena čarapa imati par u izdvojenoj gomili. Ispostavlja se da, u praksi, ne treba više od 3 do 5 izvlačenja čarapa, što i ovaj algoritam čini dobrim kandidatom.

 

E. Prednosti terena

Sledeći algoritam je veoma jednostavan, ali ipak prostorno i vremenski složeniji od prethodnog. Podrazumeva da osoba koja uparuje čarape ima dovoljno prostora, kao i u algoritmu (B), da može da ih iole pregledno rasprostre oko sebe.

1. Izvuče se jedna čarapa i spusti na pregledno mesto, fizički blizu

2. Izvuče se još jedna čarapa. Ako je par sa već izvučenom čarapom, spariti ih i eliminisati. Inače, spustiti i nju.

3. Ponavljati postupak dok se ne upare sve čarape.

I ovaj algoritam, dakle, ima kvadratnu složenost.

 

F. I za kraj, najbolji među najboljima

Konačno, algoritam asimptotske složenosti O(1), koji zahteva malo predanalize ,glasi:

1. Napraviti procenu potrebnog broja čarapa do kraja životnog veka (ili makar dok se ne penzionišete i preselite u toplije krajeve gde vam čarape neće ni biti potrebne. Pod pretpostavkom da je čitalac mlad, može se umesto trenutka penzionisanja posmatrati vreme potrebno da se najzad patentiraju roboti za sortiranje čarapa, kada ceo problem postaje irelevantan). Uzmite u obzir omiljenu šaru, boju, dužinu... Ovo je bitan korak, jer će sve čarape biti identične radi maksimalne uštede resursa.

2. Pronaći jeftinu dostavu (na primer, kamion za selidbe), koja bi vam poručene čarape dostavila na kućnu adresu (radi najbolje uštede vremena!).

3. Poručiti čarape!

4. Reciklirati stare čarape (na primer, koristiti ih kao sirovinu za pokretanje gorepomenutih robota)

Prednosti ovog algoritma su što je prvenstveno najjeftiniji, u finansijskom, ali i u vremenskom smislu. Možda inicijalno deluje kao veliko ulaganje, ali na višegodišnjem nivou je itekako isplativo. Sitna izmena je da se, eventualno, čarape iznova poručuju na određeni vremenski period (na primer, na godinu dana), što utiče na uvećanje vremenskih i novčanih troškova. Takođe, tu je i prostorna složenost (problem čuvanja čarapa predviđenih za ceo životni vek u sobi u Studenjaku), ali ko je snalažljiviji od studenata?

 

Za kraj, rešenje koje sažima, a verovatno i obesmišljuje sva navedena: bacajte već smotane čarape u mašinu! Dobro će se oprati i već će biti uparene!

 

Referenca:

Stack Overflow

 

 

Napomena: 
Nijedan deo teksta ne sme biti reprodukovan bez prethodnog odobrenja autora ili redakcije portala. Nećemo objavljivati uvredljive, nepristojne i netolerantne komentare.
Podeli: