Подросток опровергает легендарное предположение 40-летней давности.

Описание: Слушайте сотни научно-популярных документальных фильмов о Тьюринге бесплатно. Скачайте приложение по ссылкам:
iOS: https://apps.apple.com/in/app/the-tur...
Android: https://play.google.com/store/apps/de...
или слушайте на https://theturingapp.com

ВРЕМЕННЫЕ МЕТКИ:
00:00 - Введение
02:09 - Что такое хеш-функция?

07:37 - Образование и работа Эндрю
18:34 - Как его работа меняет будущее

Узнайте, как Эндрю Крапивин опроверг легендарную 40-летнюю гипотезу в теоретической информатике, касающуюся хеш-таблиц. В этом видео мы исследуем математику «эластичного хеширования» и то, как оно разрушает скоростные ограничения, установленные лауреатом премии Тьюринга Эндрю Яо.

На протяжении десятилетий считалось, что «предел скорости» структур данных неизменен. Хэш-таблицы — это «картотеки» интернета, обеспечивающие работу всего, от записей в базах данных до паролей веб-браузеров. Однако компьютерные специалисты долгое время полагали, что по мере приближения этих таблиц к 99% заполненности производительность неизбежно рухнет — явление, известное как «проблема переполненной парковки».

В 1985 году Эндрю Яо кодифицировал это убеждение, предположив, что любая «жадная» стратегия размещения данных зависит от линейной вероятности: если только 1 из 1000 ячеек пуста, вам придется проверить 1000 ячеек, чтобы найти одну. Это создавало вынужденный выбор: у вас могла быть быстрая хэш-таблица или полная, но никогда не обе сразу.

Эндрю Крапивин, 21-летний студент Ратгерского университета, даже не знал о существовании этой знаменитой гипотезы. Работая над побочным проектом по сжатию памяти, он понял, что традиционные методы терпят неудачу, потому что они «жадные» — они всегда занимают первое свободное место, что создает огромные «пробки» данных. Решение Крапивина, эластичное хеширование, блестяще противоречит интуиции.

Вместо того чтобы занимать первое свободное место, алгоритм намеренно пропускает пустые пространства, создавая «зазоры». Эти стратегические промежутки предотвращают слияние кластеров данных, поддерживая работу системы с той же скоростью и эффективностью, что и почти пустая структура — даже при 99,99% загрузке.
Это открытие — не просто математическая диковинка; оно имеет огромное значение для будущего периферийного ИИ и эффективности баз данных.

Изучайте науку как никогда раньше — доступно, захватывающе и полно впечатляющих моментов. Подпитывайте свое любопытство сотнями бесплатных, тщательно отобранных аудиопередач по STEM-тематике.

Авторы:
Институт теории вычислений Саймонса
Кафедра электротехники и информатики Калифорнийского университета в Беркли
Университет Рутгерса