Студент случайно откри изцяло нов начин за съхранение на данни

През есента на 2021 година студентът от университета Рутгерс Андрю Крапивин попада на научната статия „Tiny Pointers“ (Малки указатели), която по-късно променя живота му. По онова време начинаещият учен само бе зърнал публикацията, но две години по-късно, когато решил да я проучи подробно „просто за забавление“, тя преобърнала един от основните принципи на компютърната наука.

Докато изучавал статията, Крапивин се замислил как да направи указателите още по-компактни, така че да заемат по-малко памет. Тези елементи играят важна роля в работата на компютъра: те са като пътни знаци, които насочват системата към мястото, където се съхраняват данните. Колкото по-малко място заема всеки „знак“, толкова по-ефективно се използва паметта.

Създаването на по-компактни пътни знаци обаче изисквало нов начин за организиране на информацията, към която водят. Студентът се обърнал към хеш-таблиците, един от основните методи за съхранение на данни в компютърните системи. Хеш-таблицата работи като интелигентно съдържание: тя не само съхранява определени материали, но и позволява светкавично да се намери подходящият елемент, да се изтрие или да се добави нов.

В процеса на експериментите Крапивин случайно изобретява нов тип хеш-таблица. Нейната уникалност се състояла в това, че тя намирала правилните елементи много по-бързо от съществуващите варианти, като за намирането им били необходими по-малко стъпки.

Мартин Фарах-Колтън, един от авторите на оригиналната статия за „Малките указатели“ и бивш учител на Крапивин първоначално се отнася скептично към откритието. Хеш-таблиците се изучават от началото на 50-те години на миналия век и се считат за една от най-изследваните структури в компютърните науки. Предложеното подобрение изглеждало твърде значително за толкова изучена област. За да провери идеята на ученика, той се обърнал към колегата си Уилям Кушмаул от университета Карнеги-Мелън.

Реакцията на Кушмаул изумила всички: оказало се, че Крапивин не просто е подобрил хеш-таблицата, а е опровергал научно предположение, в което се е вярвало в продължение на 40 години.

През 1985 година известният компютърен учен Андрю Яо, бъдещ носител на наградата „Тюринг“ издига хипотеза за граничната скорост на хеш-таблиците от определен тип. В своята статия Яо твърди, че най-ефективният начин за търсене в хеш-таблица е случайното търсене на позиции: системата проверява клетките в случаен ред, докато намери желания елемент или свободно място. Според неговата теория времето за търсене неизбежно нараства със запълването на таблицата. Ако изразим запълването чрез параметъра x (където x=100 означава, че таблицата е запълнена на 99%, а x=1000 означава, че е запълнена на 99,9%), то в най-лошия случай ще трябва да проверим брой клетки, пропорционален на x.

От друга страна, студентът, който работи върху усъвършенстването на „Малките указатели“ разработва принципно нов начин за организиране на данни.

Вместо произволно търсене неговият метод използвал специален алгоритъм, който определял оптималните позиции за поставяне и търсене на елементи. Така дори в най-сложните случаи, когато таблицата била почти пълна, времето за операции било пропорционално на (log x)², което означава много по-бавно нарастване в сравнение с линейната зависимост в метода на Яо.

Тоест, когато таблицата е пълна на 99,9% (x=1000), класическият метод ще трябва да провери около 1000 елемента в най-лошия случай. Новият алгоритъм ще се справи със същата задача за около 100 операции. Тази разлика става все по-значителна с увеличаването на пълнотата на таблицата, но основната изненада предстои. В същата статия от 1985 година Яо изследва средното време за намиране на елементи в хеш-таблици, като използва така наречения „алчен“ алгоритъм. Този подход изисква поставяне на новите елементи на първата свободна позиция, все едно че запълвате аудитория стриктно по ред, започвайки от първия ред. Яо доказва, че в такива таблици средното време за търсене не може да бъде по-малко от log x.

Авторите на новата статия решават да проверят дали това ограничение се отнася за хеш-таблици с други алгоритми за разполагане на данни. Те създали версия, в която елементите били разпределени по по-сложни правила и получили изненадващ резултат: средното време за търсене било постоянно – то изобщо не зависело от заетостта на таблицата.

„Този резултат беше изненада дори за нас. Нямахме представа, че времето за търсене може да остане постоянно, независимо от заетостта. Това откритие можеше да ни се изплъзне за още 40 години. То ни принуждава да погледнем на възможностите на хеш-таблиците по съвсем нов начин“.

казват Фарах-Колтън и Сефер Асади

Въпреки, че откритието все още няма пряко практическо приложение, неговото значение за компютърните науки не може да бъде подценено.

„Дълбокото разбиране на основните структури от данни е изключително важно. Никога не можем да предвидим как едно теоретично откритие ще се превърне в практически резултат. Тъй като хеш-таблиците вече се използват навсякъде – от търсачките до базите данни, всяко подобрение може да има далечни последици.“

отбеляза Алекс Конуей от Cornell Tech