March 16th, 2008

moose, transparent

о разных алгоритмах

(интересно будет только программистам)

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

2. Я зашел на Project Euler впервые после долгого перерыва, и решил две последние задачки. Получил огромное удовольствие, хоть и написал решения на C не вполне понятно почему. В одной из них мне пригодился фокус из HAKMEM (перебор всех способов выбрать k элементов из n, с помощью битмаски), а в другой - disjoint-set, которым я тоже не пользовался очень давно.

Вообще disjoint-set - волшебно красивая штука. Я помню, что у меня затаило дыхание, когда я впервые увидел. Это алгоритм из Книги, поистине.

3. В связи с одной из задач наткнулся на страничку про MiniSat. Я не знал, что есть соревнования по решению SAT! Хочется найти время и почитать этот, вроде бы относительно простой и тем не менее эффективный, алгоритм. Исходники там есть.

4. Я тут узнал, что не все знают о Project Euler. Друзья, если вы получаете удовольствие от программирования, вам прямая дорога туда. Почти в каждой задаче там надо придумать способ ее решить, который даст ответ достаточно быстро - но суть не в бездумных оптимизациях, а в алгоритмах и структурах данных. Это, может, звучит сухо, но на деле невероятно увлекательно; а еще - умный ход - когда правильно решаешь задачу, получаешь доступ на тему на форуме, где уже решившие обсуждают свои решения и делятся кодом.
moose, transparent

трудности перевода

... на этот раз с русского на английский.
The metropolitan and arrogant elite considered Lvov parochial and dim — the liberal leader Pavel Miliukov, for example, called him 'simple-minded' (shliapa) — and this largely accounts for Lvov's poor reputation, even neglect, in the history books.


Из "A People's Tragedy", истории русской революции британского историка Орландо Файджеса.
moose, transparent

о безмозглых либералах

Дэйвид Мамет (драматург и режиссер) написал любопытную статью, и назвал ее "Почему я перестал быть безмозглым либералом".

"Либерал" здесь следует понимать, как в Америке, а не как в России.

I'd observed that lust, greed, envy, sloth, and their pals are giving the world a good run for its money, but that nonetheless, people in general seem to get from day to day; and that we in the United States get from day to day under rather wonderful and privileged circumstances—that we are not and never have been the villains that some of the world and some of our citizens make us out to be, but that we are a confection of normal (greedy, lustful, duplicitous, corrupt, inspired—in short, human) individuals living under a spectacularly effective compact called the Constitution, and lucky to get it.

Страшный человек просто-таки.