Category: юмор

Category was added automatically. Read all entries about "юмор".

with Cat The Cat

Мой любимый анекдот про дешевизну индийских ученых и программистов.

Один индийский ученый, имя которого я запамятовал, изобрёл замечательный способ улучшения соединений в кластерах. Вместо соединения в кольцо, где требуется всего 1 сетевой контроллер и logN контроллеров для гиперкуба, он предложил соединять машины в стиле распределенной хэш-таблицы. Вот, примерно, вот как здесь: http://www.freedomlayer.org/articles/dht_intro.html

Типа, делаем 2 контроллера и получаем ускорение передачи сообщений в два раза.

Идея похожа, детали отличаются.

Так вот, когда один мой знакомый обратился к нему с предложением побеседовать, сей индийский ученый потребовал (не попросил! потребовал!) $50 000 (пятьдесят тысяч долларов) только за возможность поужинать за предварительной беседой.

(прочитав последнее эссе Поля Грема)
with Cat The Cat

Про силовые тренировки...

...я пока завершу, ибо осталась совмещённая тренировка Лу Симмонса, а я в ней разобрался на уровне любителя.

Поэтому вот задачка:
+------------------------------+
|..............................|
|..............................|
|..............................|
|.........A.B.C ...............|
|........*******...............|
|..............................|
|..............................|
|*********...******************|
|..............................|
|..............................|
|.......*******................|
|........a.b.c.................|
|..............................|
+------------------------------+
Одинаковые буквы разного регистра - начала или концы путей путей. Всё, что не пробелы или точки - препятствия. Промежуток посередине шириной ровно 3.

Прикол в том, что пуская A* по одиночке, мы не можем гарантировать нахождения путей для всех начальных и конечных точек. Пусти A->a, проблемы будут у B->b и C->c. Надо пускать как-то одновременно, а тут возникает вопрос - а кого первым пускать-то на каждом очередном шаге?

Вот об этом и был мой вопрос в прошлом посте.
with Cat The Cat

Анекдот.

antilamer поместил у себя в посте ссылку про решение многих задач на графах с помощью матричных операций.

Хочу по этому поводу рассказать анекдот из опыта моих коллег.

Мы занимаемся моделированием цифровых схем и для его ускорения желательно отрезать от схемы всё лишнее - не нужные вычисления, повторяющиеся вычисления и тому подобное. Мой молодой коллега, когда я объяснил ему задачу и сказал, что это типичная графовая задача, воодушевился, откопал лекции и написал алгоритм.

- Работает, - говорит. - Только, Серёг... - мнётся.
- Что такое?
- Немного медленно работает. 19 минут на нашей тестовой схеме. Это нормально?

Мой прикидочный вариант, написанный на коленке, работал 12 секунд на той же схеме.

- Нет, - говорю, - не нормально. Очень медленно. Ты как это сделал?
- На матрицах, на умножении.
- Ты лучше на множествах сделай. Проще считать.

И мой коллега переделал решение на множествах. Через два дня его решение работало 19 секунд. Я спросил его, смотрел ли он профайлером на свой код. Он смотрел. Просто коллекции Java не давали возможности работать быстрее.

На том и остановились.

Проблема с поиском фиксированной точки в том, что умножение не совсем уж тривиальных матриц делает результат более плотным, чем исходные матрицы. Поэтому работа с разреженным представлением становится всё менее и менее выгодным. К тому же легко выбрать неправильное представление и словить O(N2) (что у нас и произошло).
with Cat The Cat

Количество цифр в факториале 100000.

fact1 n = product [1..n]

reduceProduct [] = []
reduceProduct [x] = [x]
reduceProduct (a:b:xs) = (a*b) : reduceProduct xs

product' [] = 1
product' [x] = x
product' xs = product' (reduceProduct xs)

fact2 n = product' [1..n]
Вот время вычисления для разных величин n:
*Main> length $ show $ fact1 10000
35660
(0.80 secs, 90772044 bytes)
*Main> length $ show $ fact2 10000
35660
(0.05 secs, 4062092 bytes)
*Main> length $ show $ fact1 30000
121288
(7.86 secs, 789229120 bytes)
*Main> length $ show $ fact2 30000
121288
(0.27 secs, 11794628 bytes)
Вот, в чём прикол:
*Main> map (map (length . show)) $ take 3 $ reverse
      $ takeWhile ((>2) . length) $ iterate reduceProduct [1..10000]
[[13020,15484,7157],[5895,7126,7591,7893,7157],
 [2640,3255,3488,3639,3751,3841,3915,3979,4035,3123]
]
Логарифмы перемножаемых на одной итерации reduceProduct чисел примерно равны, что позволяет использовать быстрое умножение.

Обнаружилось случайно. Коллега вывел на экран fact 100000 и сказал, что там очень много цифр. Нам стало интересно, сколько же их там, мы посчитали length $ show $ fact 100000. Мне стало неинтересно ждать долго (я прождал целых 15 секунд) и я переписал алгоритм произведения списка на приведённый выше. Мы тут же посчитали число цифр в fact 1000000. Потом стало интересно, почему же происходит такое ускорение. vshabanov посчитал и сказал, что число умножений будет всего вдвое меньше, мы пообсуждали, поизучали вопрос и пришли к выводу, что умножение больших чисел выгодней, когда они примерно равны по размеру. Что и получается в случае рекурсивного произведения.
with Cat The Cat

Анекдоты про Веллингтона.

http://antoin.livejournal.com/746365.html

«Скульптору сэру Джону Стиллу поручили сделать конную статую Веллингтона в Эдинбурге. В поисках вдохновения Стилл долго убеждал герцога вспомнить славные страницы пиренейской кампании и Ватерлоо.
В конце концов скульптор предложил вылепить герцога таким, как он появился в утро битвы при Саламанке, и «как галопом объезжал поле битвы, вдохновляя свои войска на подвиг».
— Если вы действительно хотите вылепить меня, каким я был при Саламанке, — фыркнул Веллингтон, — то вы должны показать меня ползающим в канаве на брюхе с подзорной трубой в руках!»