Конкурс на самое быстрое решение целочисленной системы линейных уравнений завершён. Вынужден признать, что это был самый скучный конкурс из всех, которые я проводил. Было довольно много участников, но у половины программы работали неправильно, а у остальных – слишком медленно и не укладывались в 600 с. Как минимум, предполагалось, что кто-то дойдёт то отметки в 5-10 с, но, к сожалению, этого не произошло. Значит я вынужден буду объяснить, как этого добиться. В этом посте подведём итоги, и я выскажу мои мысли по поводу данного мероприятия, а в следующем ждите подробного описания нормального метода решения поставленной задачи [Дополнение 11.02.2011 — Вот этот пост].

Результаты

Победителем на языке C# объявляется участник Shamil. Интересно то, что Shamil прислал свою последнюю программу за полтора часа до окончания конкурса.

Внимание! [Дополнено 14.02.2011]. К сожалению, я случайно сам нарушил одно из правил конкурса, разрешив победителю использовать внешнюю dll, но при этом забыл разрешить это публично. Поэтому будем считать, что Shamil участвовал на C#, а победителем на языке C++ объявляется Dmitry, и это при том, что родным языком участника является C#.

  1. Shamil :: 10.02.11 :: C# + libgmp-3.dll :: 139,75 с.
  1. Dmitry :: 04.02.11 :: C++/msvс2008 :: 174,88 с.
  2. Velifaro :: 02.02.11 :: C++/msvс2008 :: 185,61 с.

Уважаемые участники, которые попали в финальную таблицу, вы можете прислать мне адреса своих Интернет страниц (на почту), на которые я сделаю ссылки с этой страницы (по одной на каждого участника).

Тесты с ответами можно скачать (7 Мб). Самое долгое время почти у всех участников было на тесте 70. Тестирующая система испозовалась та же, что в конкурсе по перемножению матриц. К сожалению, эта система очень старая, поэтому на ней не работают программы, написанные на C#. Эти программы я прогонял по тестам вручную, а время замерял своей системой, она чуть менее точна, но тут сотые доли секунды роли не играют.

Трудности

В процессе проведения конкурса возникали некоторые трудности, которые следует отметить. Зачем я это делаю? Я, как уже было сказано ранее, ищу некую формулу проведения такого рода конкурсов. Через пару лет планирую создать отдельный ресурс для проведения конкурсов по трудным задачам на коммерческой основе. Но это как получится. А для начала нужно набраться опыта, пытаясь организовывать данные мероприятия разными способами. Итак, какие трудности…

Во-первых, судя по скорости работы программ, никто не пытался реализовывать что-то помимо Гаусса или Монтанте, что по сути своей почти одно и то же. Одна и та же сложность, те же операции. Пытался ли кто-нибудь поискать принципиально иной метод, я не знаю.

Во-вторых, разного рода Haskell, BigInteger (из Java) и аналог в C# работают страшно медленно. И, простите за пафос, я вообще сомневаюсь, что данные инструменты пригодны для решения задач, которые сложнее учебных примеров. Да, они удобны, по-своему красивы, но для проведения сложных вычислений непригодны. Доказать это можно любым их моих конкурсов (можно попытаться решить любую из предлагаемых задач на таких инструментах и самостоятельно убедиться в сказанном).

В-третьих, было замечено, что русскоязычная аудитория (делаю вывод на основе чтения форумов) вообще не знает, что для решения целочисленных систем применяется особая техника решения, известная уже почти 30 лет. Все везде пишут, что никаких принципиально других алгоритмов для целочисленного случая нет и быть не может. Поэтому я до проведения конкурса оставил на одном из форумов подсказку о том, какой из алгоритмов работает быстро даже в случае астрономических чисел в исходной матрице. Специально выждал, чтобы тот пост проиндексировался поисковиками. А зря я это сделал – никто советом не воспользовался. В гугле нужно набрать «решение целочисленной системы уравнений» и найдете ссылку на форум dxdy и тему «Матричный алгоритм решения целочисленной системы уравнений», где последний пост – моя подсказка. Её можно было найти, выполнив этот несложный квест. Возможно, кто-то нашёл, но не смог отыскать саму статью в Интернете (ну так и я не нашёл)… Любая государственная библиотека предоставит вам её, так как она связана с некоторыми западными библиотеками и может сделать запрос почти на что угодно. Из сотни статей, которые в Интернете можно найти только платно, в библиотеке нашего университета нам отказали только в двух-трех случаях.

В-четвертых, 5-6 раз у меня умудрились спросить является ли система вырожденной и что делать в таких случаях! Кто не спросил этого, спросил каков формат входных данных и как вообще участвовать. Такое ощущение, что около 1000 слов с правилами участия было написано зря. Я понимаю, на других сайтах бывают подобные любительские конкурсы, где фиг поймешь, что делать, как и куда слать. Но тут-то всё чётко и до предела понятно… Ладно, будем считать, что не все умеют читать.

Правильное решение

Утверждается, что системы такого размера могут быть решены в пределах одной–двух секунд. Моя реализация работает 8 с, но она не слишком аккуратная и допускает существенную оптимизацию. Такими оптимизациями я занимаюсь только если очень надо, а так, меня пока вполне устраивает.

Следующий пост будет посвящён этому замечательному алгоритму.

Откуда я взял 1-2 с? Обратите внимание, что система компьютерной алгебры Maple (от 12-й версии и старше) решает такую систему уравнений за 3.2 с. Но Maple – это не бинарный код. Бинарный код можно написать куда аккуратнее, чем реализованы команды в Maple. Поэтому я надеюсь, что участники, узнав новый для себя алгоритм, легко уделают Maple и дадут мне об этом знать. Алгоритм, реализованный там, называется алгоритмом Диксона и работает для невырожденных систем любого типа с любой структурой матрицы. Он был придумал в 1982 году, но на русском языке вы про него ничего не найдёте (а в каком месте, по-вашему находится российская наука?). Поэтому читайте этот пост.

Всем спасибо за участие, явное и неявное.

Обсуждение конкурса на форуме в этой теме.