?

Log in

о разных алгоритмах - Поклонник деепричастий [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)
From: (Anonymous)
2008-03-27 10:28 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)
From: mikkim08
2008-03-16 08:46 am
А это точно тот же самый алгоритм ?
(Ответить) (Parent) (Thread)
[User Picture]From: flaass
2008-03-16 10:59 am
Насколько я помню, в точности.
Может, описан слегка по-другому, но ключевые идеи все те же.
(Ответить) (Parent) (Thread)
[User Picture]From: arno1251
2008-03-16 12:55 pm
Спасибо!
(Ответить) (Parent) (Thread)
From: pawa
2008-03-16 07:19 am
Система непересекающихся множеств. См. русский перевод книжки Кормена, Лейзерсона и Ривеста.
(Ответить) (Parent) (Thread)
[User Picture]From: arno1251
2008-03-16 01:12 pm
+++ break them up or partition them into a number of separate, nonoverlapping sets +++
Не очень удачный выбор термина, это пример definitio per idem (тождесловия). Выше дано определение как "классы эквивалентности" -- по-моему, то, что надо.
(Ответить) (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: avva
2008-03-16 07:55 am
Ага. Красиво, спасибо.
(Ответить) (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: ilya_dogolazky
2008-03-16 02:13 pm
Там в основном какие-то циклы и массивы, но я их не читал. Насчитал всего 6 обычных решений из 4 страниц комментов и бросил. И одна программа на форте --- мелочь, но приятно.
(Ответить) (Parent) (Thread)
From: (Anonymous)
2008-03-27 10:44 pm
ещё здорово, что быстро привыкаешь к синтаксису других языков просматривая решения
(Ответить) (Parent) (Thread)
[User Picture]From: ilya_dogolazky
2008-04-15 07:17 pm
Я как раз сейчас читаю роман Даниэля Кельмана «Die Vermessung der Welt», там один персонаж складывает в школе натуральные числа от единицы до тысячи. У него очень ловко получается :-)
(Ответить) (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: avva
2008-03-17 12:10 pm
Вот, например, задачи типа "уместиться в поменьше символов" мне неинтересны. Когда-то увлекался, но прошло.
(Ответить) (Parent) (Thread)
[User Picture]From: eterevsky
2008-03-17 01:01 pm
Мне они интересны главным образом "со стороны" -- решать я их толком не умею.
(Ответить) (Parent) (Thread)
From: (Anonymous)
2008-03-27 10:35 pm
немного бесят решения некоторых задач, которые перестают работать даже при небольшом усложнении суть проблемы или даже при изменении данных

вновь баланс versatility vs. speed
(Ответить) (Parent) (Thread)
From: (Anonymous)
2008-03-27 10:40 pm
ещё по сравнению с spoj, на projecteuler очень легко понять задачу, но о сложности решения это ничего не говорит

там как бы и отмечено, в целях проекта, что math [should be presented] as an entertaining subject.
(Ответить) (Parent) (Thread)
[User Picture]From: eterevsky
2008-03-27 11:55 pm
Я, кстати, готов признать, что был не прав, объявляя все задачи с Эйлера слишком простыми. Как оказалось, во второй сотне там есть что порешать.

На счёт интересности -- для многих задач соглашусь, но есть там и тупая техника или применение готовой формулы. Если не знать, как строится рациональное приближение, или как решается уравнение Пелля или простую формулу для мат. ожидания количества бросков кубика прежде чем выпадут все грани, то придумать это самому почти невозможно. В результате, решение задачи сводится к упражнению по поиску в википедии.
(Ответить) (Parent) (Thread)
[User Picture]From: ilya_dogolazky
2008-04-15 07:12 pm
Можно конечно и в википедию лезть, но я обошёлся без этого («неспортивно», да и зачем? :-), а формул по теории вероятности и вовсе никаких не знаю, но решить задачу (кстати, а о которой Вы говорите?) это не помешало.
(Ответить) (Parent) (Thread)
[User Picture]From: eterevsky
2008-04-15 09:08 pm
Теория вероятности тут не причём. Это комбинаторика.

Задача такая (номер не помню). Есть кубик (dice, а не cube) c n сторонами. Каково матожидание количества бросков, после которых выпадут все его стороны?

Ещё была какая-то задача в которой в ответе фигурировала рекурентная последовательность x(n) = x(n-1) + x(n-2) - x(n-3) - x(n-4) + x(n-5) + x(n-6) - ... В упор не помню, что это была за задача, но по-моему, там эту формулу тоже придумать не зная почти не возможно.
(Ответить) (Parent) (Thread)
[User Picture]From: ilya_dogolazky
2008-04-15 07:05 pm
Про теорию Вы не совсем правы: конечно, если решать задачу №66 вне контекста и «по-честному» (то есть не только выдать правильный ответ, но и доказать, что он правильный), то придётся с ней очень помучаться. Но взгляните на №№64,65 --- прочтя их условия, немедленно понимаешь, что именно следует делать с номером 66. В кружке же тоже так часто делают: дают несколько задач сразу, так что их легко решить вместе, хотя по-отдельности это было бы очень и очень сложно.

Расскажите пожалуйста, как решить задачу на перле с шестью непробельными символами :-)
(Ответить) (Parent) (Thread)
[User Picture]From: eterevsky
2008-04-15 08:57 pm
Гм. Я решал 64, 65, 66 не подряд, так что не заметил совпадения. В принципе да, для решения 66-й задачи достаточно мысли о том, что хорошее рациональное приближение иррационального числа получается из цепной дроби.

Мда, надо наконец дорешать Эйлера. 50 задач всего осталось. :-)

За 6 непробельных символов я не умею. У меня лучшее решение получилось с 11-ю, что ли. Да и вообще, я не специалист по перлу и по подобного рода задачам. :-)
(Ответить) (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)
[User Picture]From: yasha
2008-03-17 12:31 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)
[User Picture]From: avva
2008-03-17 02:17 pm

Re: MiniSAT

How do you apply MiniSAT to searching bugs? Do you have a link to her paper?
(Ответить) (Parent) (Thread)
From: (Anonymous)
2008-03-17 06:47 pm

Re: MiniSAT

my understanding (but I am not in this business so may be wrong) is that they convert C/C++ code into a database of a special format. The format is convenient to run MiniSAT (or other SAT solver) over. The (assumed) bug (e.g. memory overflow etc.) itself is represented as a Boolean formula (in fact, it is negation of the statement that there is NO such bug). SAT searches satisfying assignment ( which is a counterexample) of this formula using the database as a context (i.e. set of the restrictions on the search space). If there is such assignment, it is decoded back into the fragment of the original C code and identifies the bug.

it's better to ask her, of course

webpage:

http://www.inf.unisi.ch/faculty/sharygina/

there are even some tools for such debugging on the webpage...

iz.

(Ответить) (Parent) (Thread)
[User Picture]From: avva
2008-03-17 07:16 pm

Re: MiniSAT

Alright, thanks a lot!
(Ответить) (Parent) (Thread)
[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)
From: (Anonymous)
2008-03-27 10:43 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)