Ovaj novi algoritam za sortiranje knjiga ili datoteka blizu je savršenstva

Izvorna verzija od ova priča pojavio se u Magazin Quanta.

Računarski znanstvenici često se bave apstraktnim problemima koje je teško shvatiti, ali uzbudljiv novi algoritam važan je svima koji posjeduju knjige i barem jednu policu. Algoritam govori o nečemu što se naziva problem sortiranja biblioteke (formalnije, problem “Popis označavanja”). Izazov je osmisliti strategiju za organiziranje knjiga u nekakvom sortiranom redoslijedu – na primjer, alfabetski – koja minimizira koliko vremena treba da se nova knjiga postavi na policu.

Zamislite, na primjer, da vaše knjige držite zajedno, ostavljajući prazan prostor na krajnjem desnom desnom polici. Zatim, ako dodate knjigu Isabel Allende u svoju kolekciju, možda ćete morati premjestiti svaku knjigu na polici kako biste je napravili mjesta. To bi bila dugotrajna operacija. A ako dobijete knjigu Douglasa Adamsa, morat ćete to učiniti iznova. Bolji aranžman ostavio bi nezauzete prostore raspoređene na cijeloj polici – ali kako bi se, točno, trebali distribuirati?

Ovaj je problem uveden u Rad iz 1981. godinei to nadilazi jednostavno pružanje knjižničarka organizacijskim smjernicama. To je zato što se problem odnosi i na raspored datoteka na tvrdim diskovima i u bazama podataka, gdje bi stavke koje treba dogovoriti mogle brojati u milijardama. Neučinkovit sustav znači značajna vremena čekanja i velike računske troškove. Istraživači su izmislili neke učinkovite metode za pohranjivanje predmeta, ali dugo su željeli odrediti najbolji mogući način.

Prošle godine, u studija To je predstavljeno na Konferenciji zaklade informatike u Chicagu, tim od sedam istraživača opisao je način organiziranja predmeta koji se približavaju teorijskom idealu. Novi pristup kombinira malo znanja o prošlim sadržajima na polici s iznenađujućem snagom slučajnosti.

“To je vrlo važan problem”, rekao je Seth Pettieračunalni znanstvenik sa Sveučilišta u Michiganu, jer mnoge strukture podataka na koje se danas oslanjamo pohranjuju informacije uzastopno. Novo djelo nazvao je “izuzetno nadahnutim [and] Jednostavno jedan od moja tri prva omiljena rada u godini. “

Sužavanje granica

Pa kako se mjeri dobro razvrstana polica za knjige? Uobičajeni je način vidjeti koliko vremena treba za umetanje pojedinog predmeta. Naravno, to ovisi o tome koliko predmeta ima na prvom mjestu, vrijednost koja se obično označava n. U primjeru Isabel Allende, kada se sve knjige moraju preseliti kako bi se smjestile novo, vrijeme koje je potrebno je proporcionalno n. Veći je nšto duže treba. To čini “gornju granicu” problema: nikad neće potrajati duže od vremena proporcionalnog n Da biste dodali jednu knjigu na policu.

Autori rada iz 1981. koji su pokrenuli ovaj problem željeli su znati je li moguće dizajnirati algoritam s prosječnim vremenom umetanja mnogo manje od n. I doista, dokazali su da se može bolje. Stvorili su algoritam koji je zajamčeno da će postići prosječno vrijeme umetanja proporcionalno (zapisnik n)². Ovaj je algoritam imao dva svojstva: bio je “deterministički”, što znači da njegove odluke nisu ovisile o bilo kakvoj slučajnosti, a također je bila “glatka”, što znači da se knjige moraju ravnomjerno širiti u pododjeljke police na kojima je umetanje (ili brisanja) su napravljeni. Autori su ostavili otvoreno pitanje može li se gornja granica još više poboljšati. Više od četiri desetljeća nitko to nije uspio učiniti.

Međutim, intervencijske godine su vidjele poboljšanja donje granice. Dok gornja granica određuje maksimalno moguće vrijeme potrebno za umetanje knjige, donja granica daje najbrže moguće vrijeme umetanja. Da bi pronašli konačno rješenje problema, istraživači nastoje suziti jaz između gornje i donje granice, idealno dok se ne poklapaju. Kad se to dogodi, algoritam se smatra optimalnim – neeksorično ograničen odozgo i ispod, ne ostavljajući mjesta za daljnje pročišćavanje.