U a Rad iz 1985.računalni znanstvenik Andrew Yaokoji bi nastavio osvojiti nagradu Am Turing, tvrdio je da je među hash tablicama s određenim nizom svojstava najbolji način pronalaska pojedinog elementa ili praznog mjesta samo proći kroz potencijalne spotove nasumično – pristup poznat kao jednolično sondiranje. Također je izjavio da, u najgorem scenariju, gdje tražite zadnje preostalo otvoreno mjesto, nikad ne možete bolje od toga x. Već 40 godina većina računalnih znanstvenika pretpostavila je da je Yao -ova pretpostavka istinita.
Krapivina nije zadržana konvencionalnom mudrošću iz jednostavnog razloga što ga nije svjestan. “To sam učinio bez da sam znao za Yao -ovu pretpostavku”, rekao je. Njegova istraživanja s sitnim pokazivačima dovela su do nove vrste hash tablice – ona koja se nije oslanjala na jednolično sondiranje. A za ovu novu hash tablicu, vrijeme potrebno za upiti i umetanje najgorih slučajeva proporcionalno je (zapisnik x)2—Far brže od x. Taj je rezultat izravno protivio Yao -ovoj pretpostavci. Farach-Colton i Kuszmaul pomogli su Krapivinu da to pokaže (zapisnik x)2 je optimalna, nenadmašna granica za popularnu klasu hash tablica koju je Yao pisao.
“Ovaj je rezultat lijep po tome što se bavi i rješava takav klasični problem”, rekao je Momak Blelloch Carnegie Mellon.
“Nije samo da su se opovrgli [Yao’s conjecture]također su pronašli najbolji mogući odgovor na njegovo pitanje “, rekao je Sepehr Assadi Sveučilišta u Waterlou. “Mogli smo proći još 40 godina prije nego što smo znali pravi odgovor.”
Osim što je odbacio Yao -ovu pretpostavku, novi rad sadrži i ono što mnogi smatraju još zapanjujućim rezultatom. To se odnosi na povezanu, iako malo drugačiju situaciju: Yao je 1985. izgledao samo u najgorim slučajevima za upiti, već i u prosječnom vremenu koje je uzeto u svim mogućim upitima. Dokazao je da hash tablice s određenim svojstvima – uključujući one koje su označene “pohlepnim”, što znači da se novi elementi moraju smjestiti na prvo raspoloživo mjesto – ne bi mogli postići prosječno vrijeme bolje od dnevnika x.
Farach-Colton, Krapivin i Kuszmaul željeli su vidjeti i je li se ta ista granica primijenila i na tablice hash-a. Pokazali su da to nije dajući kontraexample, ne-pohlepnu tablicu hash-a s prosječnim vremenom upita koje je puno, puno bolje od zapisnika x. U stvari, to ne ovisi x uopće. “Dobivate broj”, rekao je Farach-Colton, “nešto što je samo konstanta i ne ovisi o tome koliko je tablica hash-a.” Činjenica da možete postići stalno prosječno vrijeme upita, bez obzira na puninu hash tablice, bila je potpuno neočekivana – čak i samim autorima.
Rezultati tima možda neće dovesti do neposrednih prijava, ali to nije sve što je važno, rekao je Conway. „Važno je bolje razumjeti ove vrste struktura podataka. Ne znate kada će ovakav rezultat otključati nešto što vam omogućuje bolje u praksi. “
Originalna priča ponovljena s dopuštenjem iz Magazin Quantaurednička neovisna publikacija Fondacija Simons Čija je misija poboljšati javno razumijevanje znanosti pokrivanjem razvoja istraživanja i trendova iz matematike i fizičkih i životnih znanosti.
