ту би континуед

Тут у меня в rss-ленте недавно прошло нечто, что связано с предыдущим постом. Оказывается, некоторые устраивают "атаки" на знании хеш-фукнции. Так как часть софта открыта, то генерируется набор с равными хешами. Соответственно, добавление всего набора будет за квадрат.

В ruby типа даже реализацию словарей пофиксили. Только у некоторых приложения стали падать, так как они заложились на порядок добавления в словарь. foreach-итератор выдает не в том порядке, в котором элементы были добавлены. Можно ли вообще полагаться на порядок добавления в контейнер? Сложный философский вопрос... В интерфейсе/контракте это сложно описать. Документация/спецификация гарантий мало дает, это ж просто текст.

Не знаю ситуации насчет анти-qsort. В том же .нет антиКуСорт очевидным образом применим, там вообще выбирается средний элемент (и в куче других платформ, не только .нет).  Оказывается, что если выбирать случайный разделяющий элемент, то все равно все плохо. Пытались выжать из этого спортивную задачку, через 15 минут пришли к выводу, что это уже халява. Что-то с этой идеи выжали, получилась средняя динамика за 4-ую (или 6?).

Вообще, атаки на алгоритмику по определению прикольны. Это вам не sql-injection пихать. Тут (увы, избитая фраза, но) думать надо. Причем в любой(!) маломальской области надо думать. И хеши, и сортировка, и регекспы и etc...

Не так страшны падающие самолеты, как софт написанный для самолетов.

Магия

Когда я писал диплом, то в исходниках по 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.

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

Вызга монос

Есть несколько классических задачек на рекурсивную логику.

Загадано число N (N >= 2). Одному человеку сообщается N + 1, другому N - 1. Между ними происходит следующий диалог:

- Я не знаю, что это за число.
- Я не знаю, что это за число.
...
- Я не знаю, что это за число.
- Я знаю, что это за число.

В зависимости от вариации задачи, люди (не)?знают, что им сообщили (N + 1 или N - 1).
Длина диалога внезапно равна N (+-1). Надо моделировать на малых числах и курить. А то, если N велико, трудно понять, что же нам дает не знание собеседника.

Следующая задача примерно такая же. Загадано два числа, одному сообщается сумма чисел, другому - произведение. Такой же диалог. Тут надо еще побольше шевелить мозгом, удары об стену идут вне зачета.

Эта задача была на полуфинале где-то в 2003/2004. На тренировке мы до нее не дошли, другой халявы было предостаточно.

А есть еще класс задач с шапочками, где какой-либо злодей надел на (пусть) гномов шапочки двух цветов, причем известно что есть оба цвета. Все гномы видят цвет всех, кроме себя. Им нужно к 22:37 определить, какой же у них цвет шапочки. Иначе смерть, ипотека, жена_трое_детей.

"Помоги веселым гномикам сделать это..." Там обычно, одетые, например, в красные шапки, должны сделать шаг вперед. Пусть у нас будут красные и черные.

Тут если два гнома, то тривиально. Три - одноходовка. На четырех уже надо подумать. Но здесь и далее меня выносит: если первые две задачки были дискретными, то здесь же есть какой-то скрытый элемент динамики. Даже для трех: пусть гном (я) видит у соседей два других цвета. Тогда из того, что одетый в черное стоит на месте, следует я тоже в черном. Если бы другой гном в черном видел бы на мне красный, и на другом красный, то он бы догадался, что на нем черный (ибо по условию обязательно есть оба цвета). И вот оба черных дошли до правильной мысли и должны сделать шаг.

Здесь заложена какая-то скрытая дискретность, раз он не пошел на предыдущей секунде (или другая отсечка), значит у него не хватает информации. Это, кстати, довольно круто, что недостаток информации дает какую новую для меня. Но как человеку немного более близкому к информатике, тут сильно глючит: успеют ли они за единицу времени провести логический вывод для следующего шага? Там как-то страшно (в смысле сильно не понятно как) растет дерево разбора... Непонятно, как синхронизироваться. Чистая математика и логика как-то вообще не рассматривают вопросы об эффективности и производительности, что печалит.

ЗЫ. Бывают какие-то моменты времени, что мне кажется, что я эти задачки понимаю. Как любят говорить математики, множество меры 0 (про время). В остальные моменты времени я думаю так: "блин, тут же все просто должно быть, я ж это понимал." Сидишь и гошешь челову, при условии что весь вызг монесен.