admin
Originali versija iš Ši istorija Pasirodė žurnale „Quanta“.
Kompiuterių mokslininkai dažnai sprendžia abstrakčias problemas, kurias sunku suprasti, tačiau įdomus naujas algoritmas yra svarbus visiems, kuriems priklauso knygos ir bent viena lentyna. Algoritmas nagrinėja tai, kas vadinama bibliotekos rūšiavimo problema (oficialiau, „sąrašo ženklinimo“ problema). Iššūkis yra sugalvoti knygų organizavimo tam tikrą rūšiuotą tvarka, pavyzdžiui, paveiliniu požiūriu, strategiją, kuri sumažina tai, kiek laiko reikia naujos knygos ant lentynos.
Pavyzdžiui, įsivaizduokite, kad jūs laikysite savo knygas suliptas, palikdami tuščią vietą dešinėje nuo lentynos dešinėje. Tada, jei į savo kolekciją pridėsite Isabel Allende knygą, jums gali tekti perkelti kiekvieną knygą ant lentynos, kad būtų vietos. Tai būtų daug laiko reikalaujanti operacija. Ir jei tada gausite Douglaso Adamso knygą, turėsite tai padaryti iš naujo. Geresnis išdėstymas paliktų neužimtas erdves, paskirstytas visoje lentynoje, tačiau kaip tiksliai jos turėtų būti paskirstytos?
Ši problema buvo iškelta 1981 m. Dokumente, ir ji ne tik teikia bibliotekininkams organizacinių patarimų teikimą. Taip yra todėl, kad problema taip pat taikoma failų išdėstymui ant standžiųjų diskų ir duomenų bazėse, kur elementai, kuriuos reikia išdėstyti, galėtų būti milijardai. Neefektyvi sistema reiškia reikšmingą laukimo laiką ir pagrindines skaičiavimo išlaidas. Tyrėjai išrado keletą efektyvių daiktų saugojimo metodų, tačiau jie jau seniai norėjo nustatyti geriausią įmanomą būdą.
Praėjusiais metais atliktame tyrime, kuris buvo pristatytas Kompiuterių mokslo konferencijos Čikagoje fonduose, septynių tyrėjų komanda aprašė būdą, kaip organizuoti daiktus, kurie yra gąsdinantys artimas teoriniam idealui. Naujasis požiūris sujungia šiek tiek žinių apie knygų lentynos praeities turinį su stebėtina atsitiktinumo galia.
„Tai labai svarbi problema“, – sakė Mičigano universiteto kompiuterių mokslininkas Sethas Pettie, nes daugelis duomenų struktūrų, kuriomis mes šiandien pasitikime, saugo informaciją iš eilės. Naująjį kūrinį jis pavadino „nepaprastai įkvėptu (ir) lengvai vienu iš trijų mano mėgstamiausių metų dokumentų“.
Susiaurėjančios ribos
Taigi, kaip galima įvertinti gerai suremontuotą knygų lentyną? Įprastas būdas yra pamatyti, kiek laiko reikia įterpti atskirą daiktą. Natūralu, kad tai priklauso nuo to, kiek daiktų yra visų pirma, vertė paprastai žymima n. Isabel Allende pavyzdyje, kai visos knygos turi judėti, kad būtų galima pritaikyti naują, laikas, kurį reikia, yra proporcingas n. Kuo didesnis nkuo ilgiau tai užtrunka. Tai daro tai „viršutine riba“ problemai: jis niekada neužtruks ilgiau nei proporcingas laiko tarpas n Norėdami pridėti vieną knygą prie lentynos.
1981 m. Straipsnio autoriai, kurie išsprendė šią problemą n. Ir iš tikrųjų jie įrodė, kad žmogus gali padaryti geriau. Jie sukūrė algoritmą, kuriam buvo garantuojama, kad jis pasieks vidutinį įterpimo laiką, proporcingą (log n)2. Šis algoritmas turėjo dvi savybes: jis buvo „deterministinis“, reiškiantis, kad jo sprendimai nepriklausė nuo jokio atsitiktinumo, taip pat buvo „sklandus“, tai reiškia, kad knygos turi būti paskirstytos tolygiai lentynos poskyriuose, kur įterpimai (arba delecijos) yra pagaminti. Autoriai paliko klausimą, ar viršutinę ribą būtų galima dar labiau patobulinti. Daugiau nei keturis dešimtmečius niekas nesugebėjo to padaryti.
Tačiau įsikišusius metus buvo patobulintos apatinės ribos. Nors viršutinė riba nurodo maksimalų įmanomą laiką, reikalingą knygai įterpti, apatinė riba suteikia kuo greitesnį įterpimo laiką. Norėdami rasti galutinį problemos sprendimą, tyrėjai stengiasi sumažinti atotrūkį tarp viršutinės ir apatinės ribos, idealiu atveju, kol jie sutaps. Kai tai atsitiks, algoritmas laikomas optimaliu – ne 3 -ąjį ribotą iš viršaus ir apačioje, nepaliekant vietos tolesniam tobulinimui.
