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

[avva]

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

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

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

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

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

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

Comments

[pawa.livejournal.com]

Самое клевое в disjoin-set это то что его можно реализовать буквально в несколько строчек:

...
for (int i = 0; i < N; i++) P[i] = i;
...

int get(int i) {
if (P[i] == i) return i;
else return get(P[i]);
}

void unite(int i, int j) {
if (rand() % 2 == 0) P[get(i)] = get(j);
else P[get(j)] = get(i);
}


Конечно, тут вместо эвристики с рангами случайная балансировка, но для целей подобных Project Euler этого более чем достаточно.

[pawa.livejournal.com]

строчку "return get(P[i]);" следует читать как "return P[i] = get(P[i])" - сюда эвристика сжатия путей запихана.

[avva.livejournal.com]

Ага. Красиво, спасибо.