?

Log in

No account? Create an account
о разных алгоритмах - Поклонник деепричастий [entries|archive|friends|userinfo]
Anatoly Vorobey

[ website | Website ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

Links
[Links:| English-language weblog ]

о разных алгоритмах [мар. 16, 2008|12:51 am]
Anatoly Vorobey
(интересно будет только программистам)

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

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

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

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

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

Comments:
[User Picture]From: djuffin
2008-03-16 01:39 am
А как вы относитесь к Top Coder?
(Ответить) (Thread)
[User Picture]From: avva
2008-03-17 12:09 pm
Как-то не для меня все эти соревнования на скорость. Не люблю.
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: arno1251
2008-03-16 03:48 am
Как, интересно, можно точно перевести disjoint-set на русский?
(Ответить) (Thread)
[User Picture]From: flaass
2008-03-16 06:17 am
Классы эквивалентности.
Я этот алгоритм узнал из "Дисциплины программирования" Дейкстры; там он приписан Мартину Рему. Странно, что в Вики об этом не упомянуто.
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: spamsink
2008-03-16 04:52 am
1. (This would drive valgrind nuts.) Вот именно. :)

2. Сколько-то лет назад я был горд собой, когда существенно сократил время работы программы, реализовав компрессию при поиске в структуре, аналогичной disjoint set, но что у нее есть умное название, узнал только сегодня. :(

(Ответить) (Thread)
From: pawa
2008-03-16 07:23 am
Самое клевое в 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 этого более чем достаточно.
(Ответить) (Thread)
From: pawa
2008-03-16 07:25 am
строчку "return get(P[i]);" следует читать как "return P[i] = get(P[i])" - сюда эвристика сжатия путей запихана.
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: tnt23
2008-03-16 07:30 am
Спасибо за ссылку по инициализации массивов. (В цитате из Jon Bentley's 1986 book занятное - it should be considered only when space is cheap, time is dear)
(Ответить) (Thread)
[User Picture]From: ilya_dogolazky
2008-03-16 10:25 am
Спасибо! Очень забавный сайт с задачками. (просмотр комментов к первой задаче (которая имени Гаусса, 1+…+N) несколько расстраивает: язык программирования «бумажка с карандашом» вышел из моды)
(Ответить) (Thread)
[User Picture]From: netp_npokon
2008-03-16 02:05 pm
Комментариев к той задаче не читал, но наверняка народ меряется наиболее красивыми способами написать суммирование чисел. Это тоже своего рода искусство :)
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: eterevsky
2008-03-16 11:33 am
На Project Euler задачки по-моему, слишком простые, некоторые кажутся взятыми с потолка, а некоторые можно решить, только зная соответсвующую теорию (например, как решать уравнения Пелля).

Я бы порекомендовал spoj.pl, их там больше, они интереснее и сложнее + есть задачки challenge, в которых нужно написать самое быстрое или самое короткое решение. :)

Что до SAT -- в лаборатории в ПОМИ, где я учился рядом стояли кубки за лучшую реализацию SAT-решателя из за самую короткую SAT-задачу, которую никому не удалось решить. Собственно, edwardahirsch, которому принадлежит второй из кубков, является автором лучшего на данный момент алгоритма для решения SAT.
(Ответить) (Thread)
[User Picture]From: eterevsky
2008-03-16 11:37 am
К примеру, самое короткое решение этой задачи занимает 6 непробельных символов на перле.
(Ответить) (Parent) (Thread)
[User Picture]From: yasha
2008-03-16 04:53 pm
"Затаило дыхание"?
(Ответить) (Thread)
[User Picture]From: avva
2008-03-17 12:10 pm
Перехватило?
(Ответить) (Parent) (Thread) (Развернуть)
From: (Anonymous)
2008-03-16 11:20 pm

MiniSAT

I've tried an extension of SAT solver (with first-order logic for linear ineqalites) YICES just as a search engine for computing long gray codes( e.g. snakes, necklaces): sometimes it helps to break records

iz.
(Ответить) (Thread)
From: (Anonymous)
2008-03-17 01:57 pm

Re: MiniSAT

and one more thing about MiniSAT I forgot: Ed Clark (recent Turing award) has the papers where they applied MiniSAT for the search of bugs in C codes. I know his co-auther who works here in Switzerland on this topic: she visited Israel (IBM or Google) where she gave the presentation of the method. iz.
(Ответить) (Parent) (Thread) (Развернуть)
Re: MiniSAT - (Анонимно) Развернуть
[User Picture]From: malfet_
2008-03-17 01:15 am
В очередной раз спасибо за ссылку! Про Project Euler не знал - попробую выкраивать по нескольку часов на решение задачек..
(Ответить) (Thread)
[User Picture]From: avva
2008-03-17 12:10 pm
Ага, это отличное место.
(Ответить) (Parent) (Thread)
[User Picture]From: oxfv
2008-03-17 11:07 pm
Собрался наконец с силами и поборолся с projecteuler - спасибо за толчок. Решил последнюю задачку, буду решать еще (time permitting).
(Ответить) (Thread)
[User Picture]From: avva
2008-03-17 11:08 pm
Ура!
(Ответить) (Parent) (Thread)
[User Picture]From: nikat
2008-03-28 10:43 am
Мда.
Спасибо огромное за ссылку на Project Euler.
Только вот вошёл во вкус, что-то у них там стряслось и сайт остановили. К сожалению.
(Ответить) (Thread)