Tip of the day: granice intervala

U pretpretprošlom postu kao jednu od točaka spomenuo sam “neelegantno baratanje donjim i gornjim granicama intervala” kao jednu od početničkih mana u kodiranju. Koje je onda elegantno baratanje?

Uz oznake L i R za lijevu i desnu granicu (left i right), najbolje je brojevima L i R označiti interval {L, L+1, …, R-1}; dakle, interval [L, R> kojemu je donja granica uključena, a gornja isključena. Ta asimetrija može se isprva učiniti neelegantnom, ali ona nam zapravo pojednostavljuje život:

  • Veličina intervala jednostavno je R – L. (Kad bi obje granice bile uključene, bila bi R – L + 1.)
  • Intervali se na ovaj način lako i prirodno nadovezuju: [A, B> + [B, C> = [A, C>. Ovo je korisno u mnogim “podijeli pa vladaj” pristupima gdje se interval dijeli na dva manja, primjerice u tournament stablu: [L, R> dijelimo na [L, mid> + [mid, R>.
  • Na ovaj način možemo pokriti i slučaj kad je interval prazan: L = R.

Druge prednosti koje mi nisu pale na pamet slobodno dopišite u komentare. Jedan od rijetkih slučajeva gdje koristim drugačiji princip (interval [L, R] kojemu su obje granice uključene) jest binarno pretraživanje, iako mnogi i ondje koriste gornji princip.

Princip “donja uključena, gornja isključena” koriste standardni oblici for petlje u većini programskih jezika: sjetite se kako radi range u Pythonu ili najčešća petlja for (i=0; i < n; ++i) u jeziku C. Sve je to povezano i s činjenicom da su nizovi uglavnom indeksirani od nule, tako da se niz duljine N nalazi na indeksima iz intervala [0, N>. Kraj je isključen: u C++u ćete znati da ste došli do kraja STL containera (vector, string, set, map…) kada naiđete na s.end(), primjerice u petlji: for (it = s.begin(); it != s.end(); ++it) ili u provjeri if s.find(element) == s.end() kao znak da element nije pronađen.

Zašto sve ide od nule? Mnogo je razloga, čak i matematičkih. Brojevi koje možete zapisati s K binarnih znamenaka čine interval [0, 2K >. Ostatci modulo N su 0, 1, …, N-1. Koristite li hash tablicu s modulom N, jasno je da su upravo to indeksi koji vam trebaju. Ili, ako se po nizu krećete ciklički, kad povećate indeks za proizvoljan korak, dovoljno ga je modati s N da dobijete pravi indeks (N -> 0, N+1 -> 1, N+2 -> 2, …). Općenito se formule pojednostavljuju: pogledajte npr. odgovore na https://www.quora.com/Why-do-array-indexes-start-with-0-zero-in-many-programming-languages.

Komentiraj

Popunite niže tražene podatke ili kliknite na neku od ikona za prijavu:

WordPress.com Logo

Ovaj komentar pišete koristeći vaš WordPress.com račun. Odjava /  Izmijeni )

Google photo

Ovaj komentar pišete koristeći vaš Google račun. Odjava /  Izmijeni )

Twitter picture

Ovaj komentar pišete koristeći vaš Twitter račun. Odjava /  Izmijeni )

Facebook slika

Ovaj komentar pišete koristeći vaš Facebook račun. Odjava /  Izmijeni )

Spajanje na %s