Хакни рутину. Как алгоритмы помогают справляться с беспорядком, не тупить в супермаркете и жить проще - стр. 6
Если бы у нас было гораздо больше носков разных типов и цветов, то ряд непарных оказался бы таким длинным, что нам пришлось бы заново пересматривать всю их последовательность каждый раз, когда мы вытаскиваем из кучи новый. Это трудоемко и долго, особенно если искомый предмет оказывается в самом конце.
В 1953 году математик Ханс Питер Лун, работавший в корпорации «IBM», выдвинул идею, которая положила начало созданию альтернативной структуры, облегчающей потенциальную замедленность, присущую любому комплексному поиску. Эта структура иногда называется ассоциативным массивом, или хеш-таблицей (посыплем еще немного соли на раны старушки Марджи). Хеш-таблица делает то же, что и массив: она сохраняет вещи в коллекции, но использует более строгую последовательность (например, большой черный носок всегда идет после красного носка) для немедленного так называемого поиска за постоянное время.[11]
Он называется непрерывным, потому что не зависит от длины последовательности. Впрочем, это не всегда так. Многие вещи в программном обеспечении, к неудовольствию исследователей и практиков, не подчиняются фундаментальным законам – в отличие от природы. Но здесь мы допускаем, что из-за малого числа несопоставимых носков синапсы Марджи будут возбуждаться быстро и вызывать почти немедленную реакцию.
Как мы увидим позже, непрерывный поиск чаще всего происходит в тех случаях, когда можно смоделировать задание при помощи формулы, которая избавляет от необходимости выполнять его снова и снова, перебирая все существующие позиции.[12] Известно, что формула, используемая с хеш-таблицами, называется хеш-функция. Ее работа – поместить вещь в кучу так, чтобы потом можно было вытащить ее из памяти достаточно быстро.
Но отложим эти соображения в сторону. Суть в том, что подход, который использует одни и те же знания повторно, может быть быстрее, чем тот, который их не использует. Это особенно полезно знать, когда речь идет о выполнении каких-либо повторяющихся операций. Например, вы выбираете в магазине коробку свеч в виде букв для именинного пирога вашей дочери. Или же вы собрались постирать, и вам нужно отделить белое постельное белье от цветного и нижнего. Или вы пытаетесь составить самое длинное слово из определенного набора букв, как в британском телешоу «Каунтдаун».
В каждой из этих ситуаций вы спросите себя: можно ли сделать это задание быстрее, используя память – свою собственную или общечеловеческую? В примере с кучей носков, составляя ряд носков без пары, мы договорились, что у нас не может быть больше пяти их типов. В примере с коробкой свеч мы бы выбрали любые подходящие нам четыре буквы, когда мы натыкаемся на них, а не искали бы отдельно L или U и так далее.