четверг, 22 марта 2012 г.

Магия

Когда я писал диплом, то в исходниках по yacc/lex (Pascal version) увидел, что внутри написан самопальный dictionary/hash_table, и стоит константа const int someThing = 997. И комментарий, что это должно быть обязательно простое число. Это в таблице имен, чтобы все имена переменных как-то хранить. Очевидно, типа, по этому модулю мы берем остаток от хеш-функции. Поржал. Ладно, думаю, хорошая шутка, надо запомнить.

Через год я вышел на работу. Понятно, что еще слаб во всяких технологиях/предметной_области/методологиях, но вижу в коде, что в словаре хранится отображение из числа в объект (int -> someObject). На самом деле должен быть мап из части объекта в целый объект, но качестве ключа выбрано именно число, хеш. Количество объектов порядка 10^5. Опросил человек 5, все как очной ставке - говорят под копирку: "Типа int он большой, 4 млрд., объектов мало, вероятность что что-то совпадет маленькая, смотри как тут хеш-функция круто ресшарпером написана. Все тип-топ". Понимаю, что ржать бесполезно, не поймут. Попробовал со стороны "парадокса близнецов", не получилось. Пришлось написать тест и показать, что на стольких объектах хеши совпадут. Поверили. Провел минимальный экскурс в теорию про хеши.

Проходит еще 3-4 года, и теперь зачем-то залез во внутренности dictionary. Как оно работает и так понятно, но сейчас углубился до resize. Есть internal class System.Collections.HashHelpers, в котором есть кучка прикольных методов. Там даже есть

internal static readonly int[] primes = new int[72]

А если посмотреть на resize у ConcurrentDictionary, то там еще большая магия. Рекомендую.

В принципе, понятно откуда ноги растут. Я в детстве тоже так думал, что если это поле то это круче. Но сейчас не понимаю - зачем это все. Если у нас все равномерно распределено, то пофиг по какому модулю это все брать, не будет ничего такого что "из того что модуль простой, то будет меньше коллизий". С таким же успехом можно использовать любую другую магию.

Я пожалуй не буду писать про все остальные мои вопросы в базовых структурах данных и библиотеках. "Жираф большой - ему видней", а у меня куча вопрос. Откуда почти может следовать, что вероятно я не жираф. Но это как-то не строго.

Тут как обычно философский вопрос: насколько надо понимать вещи, которые ты используешь? Например, мы обычно просто едим, даже не представляя весь процесс пищеварения. Я слабо представляю, что просходит на уровне железа, да еще и в параллельном коде. Видимо, мне это пока не надо. Высокоуровнево и 1-2 уровнем пониже как то цельно в голове уложено. Отсюда правило: если вы что-то используете, то надо как минимум понимать на 1 уровень ниже. Если что-то создаете, то минимум на 2.

Никакой магии нет, надо копать глубже.

Комментариев нет: