Студент случайно откри изцяло нов начин за съхранение на данни
Основният проблем на хеш-таблиците има ненадейно решение...
Емил Василев 12:31 | 14.02.2025 33 СподелиНай-четени
КосмосЕмил Василев - 9:35 | 13.02.2025Детектор на дъното на Средиземно море е уловил неутрино с рекордно висока сила – то е с извънгалактически генезис
ТелефониДаниел Десподов - 11:29 | 12.02.2025HyperOS вкарва нова актуализация за фърмуера на батерията – вижте дали вашият Xiaomi дава отговор на изискванията
IT НовиниСветослав Димитров - 12:21 | 12.02.2025Крипто специалист предвижда бърз напредък на криптовалутата Bitcoin до $350 000
Емил Василевhttps://www.kaldata.com/През есента на 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
