[6. Ход коня] [Оглавление] [8. Звезды и судьбы]
Как компьютер сам рассказал мне о хешировании
После "хода коня" мне захотелось узнать, что можно сделать, чтобы компьютер быстрее работал. Я решил выяснить скорость его работы. Еще со времен программируемого калькулятора МК-61 я помнил о том, что все команды исполняются за разное количество времени. Для себя я это открыл, поднося к калькулятору обыкновенный приемник, настроенный на средние волны. Каждая из команд, исполняемых калькулятором, отзывалась характерным "пиликом" в динамике приемника. Я даже научился писать программы, при исполнения которых звучала та или иная мелодия, и даже отослал письмо в журнал "Наука и Жизнь" с целью поведать миру об этой своей идее, в котором привел подробное ее описание. Оказалось, правда, что не я один занимался этим вопросом, и, спустя пару месяцев, статья, под которой стояло чужое имя, уже была опубликована. Дело в том, что от момента получения письма до момента его публикации проходило около четырех месяцев, потому меня кто-то опередил на целых два месяца. Правда, господин Пухначев, ведущий рубрику в журнале, написал мне благодарное письмо, которое затем помогло мне поступить на факультет Кибернетики МИФИ (ныне Московский Инженерно-Физический Институт (Технический Университет)).
Итак, я написал простейшую программу на Фокале, которая в цикле заполняла массив чисел и после присвоения каждому из элементов определенной константы, издавала "бип". Я с удивлением заметил, что частота издаваемых "бипов" все время уменьшается, становится довольно низкой (медленное "биканье") при числах, близких по кратности к 512, а затем опять, скачком, резко возрастает до первоначальной, но после опять замедляется. Обнаружив такой парадокс, я стал думать, почему происходит подобное?
Это было в конце 9 класса. Литературы по интерпретатору Фокал не было. Я знал, что выделение памяти происходит динамически, во время работы программы, и понял, что сначала проверяется свободна ли ячейка памяти А. Если она не свободна, проверяется ячейка А+1, потом А+2, потом А+3... Причем, выделение памяти происходит 512 байтными блоками. Проверки А, А+1, А+2 и приводят к тому, что скорость заполнения ячеек уменьшается, так как каждое следующее присваивание вызывает вначале проверку ячеек памяти А, А+1, А+2, А+3, ... на то, что они свободны. А так как хеш-функция (я узнал это слово только в институте) выделения памяти оперирует 512 байтными блоками, то каждый 512 элемент выделяется хеш-функцией практически мгновенно.
Таким образом, сам компьютер впервые рассказал мне о том, что такое хеширование. Впоследствии в институте было очень интересно слушать лекции господина Панферова о различных типах хеш-функций и методах их применения.
[6. Ход коня] [Оглавление] [8. Звезды и судьбы]