Конкурс - перемножение матриц

[Arigato]

Сообщение от LeBron

Ех, а интересно смотреть, я нескольким показал эту тему, так некоторые дальше говорят, что 30 секунд достаточно, а некоторые другие говорят, что меньше 36-38 нереально,

Сомневаюсь, что не написав программы можно так оценивать время, прямо до секунд. Тем более, что всё зависит от железа. На одном компе может и будет 38 сек, а на другом 5 минут.

[Zealint]

Сообщение от Arigato

Ну а в чём тогда проблема, публикуйте открыто все решения для всех желающих. В итоге все будут на равных условиях с Вами. Да, ещё не забудьте свои тесты выложить для участников.

Тов. Arigato, вы никак не хотите понять одну простую вещь: тесты (мои) ничем не отличаются от тестов, которые может сгенерировать для себя любой участник. Вы согласны? От того, какие там будут цифры ровным счетом ничего не зависит. Вот если бы мы решали, скажем, задачу о максимальном потоке (или что-нибудь еще по теории графов), то там есть разница - какие тесты. Далее, если выложить тесты участникам, они, конечно, смогут просто заранее посчитать ответ для каждого теста и написать программу исключительно "под тесты". Это вам понятно? Это очень просто делается. Я думаю, что этот бесполезный спор нужно заканчивать, уже всем очевидно, что я в таких же равных условиях. Тем более, меня сейчас дерут так, что я даже незнаю с чем дальше участвовать. Ulex такой темп задал, что многие участники вообще скорее всего выйдут из конкурса.

Кстати, я любому подсказываю, что неправильно с его программой и почему я её не засчитал (да, к сожалению многие не умеют тестировать код). Получается что я даже вообще в более худшем положении.

Все, вопрос закрыт. Вот когда будут задачи, в которых я большой специалист, тогда я буду в стороне. А сейчас все честно.

На третий день уже вышли с минуты Круто.

Дальше будет сложнее. В 30 секунд я не верю : ) Но очень бы хотелось!

Кстати, было бы здорово, если бы кто-нибудь поискал в сети чьи-нибудь программы (каких-нибудь известных ученых), которые якобы быстро работают и выступил бы с этими программами. Уж очень хочется оценить, чего вся это шелуха реально стоит. BLAS мы уже опустили (правда, тут не совсем честно, ведь у нас числа целые, а там - дробные). Кто-то мне про SUN говорил, что у них алгоритмы крутые. Я в это, конечно, не верю.

Просто есть у меня опыт в решении более сложных задач (в основном, NP-сложных), так там в 100% случаях ручной код оказывался в сотни (даже в тысячи) раз быстрее, чем чьи-то библиотеки. У меня еще будут конкурсы на эту тему.

[LeBron]

Сообщение от Zealint

Просто есть у меня опыт в решении более сложных задач (в основном, NP-сложных), так там в 100% случаях ручной код оказывался в сотни (даже в тысячи) раз быстрее, чем чьи-то библиотеки. У меня еще будут конкурсы на эту тему.

Ежу понятно, что NP-полная задача, реализованная в стандартной библиотеке алгоритмов - это малость смешно Но вот с NP-полными задачами Вас действительно задолбут с тестами, особенно, если народ будет пробовать просунуть эвристики, которые в ряде случаев дают не максимальные/минимальные ответы. Это сдесь все "влоб" (и надо заниматься именно "железной" оптимизацией, с этим у меня туго, так что не учавствую), а там так не будет...

Сообщение от Arigato

Сомневаюсь, что не написав программы можно так оценивать время, прямо до секунд. Тем более, что всё зависит от железа. На одном компе может и будет 38 сек, а на другом 5 минут.

Как бы всем понятно, что можно, если есть опыт работы с временными ограничениями, то это почти что устно делается (опыт, понятно, в разы больше, чем у меня). Есть мощность железа (ее описали в условиях конкурса), есть все остальное...

[Zealint]

Сообщение от LeBron

Ежу понятно, что NP-полная задача, реализованная в стандартной библиотеке алгоритмов - это малость смешно Но вот с NP-полными задачами Вас действительно задолбут с тестами, особенно, если народ будет пробовать просунуть эвристики, которые в ряде случаев дают не максимальные/минимальные ответы. Это сдесь все "влоб" (и надо заниматься именно "железной" оптимизацией, с этим у меня туго, так что не учавствую), а там так не будет...

Размышление правильное, но у меня есть задачи, в которых эвристики не пройдут. Их просто нет. И если кто-то придумает хоть одну - это будет научное достижение. А есть и другие задачи, где я не запрещаю пользоваться эвристиками. Там тоже все будет честно. Одна только проблема - эти задачи сверхложные. Их уже 50 лет решают и не далеко ушли. Палить пока не буду.

Кстати, вы не правы - здесь все не "в лоб". Сейчас народ пойдет Штрассена делать от безысходности. Разве это "в лоб"? Его тоже надо потрудиться написать правильно. Не по классике (где до 2^n дополнять надо), а по человечески (где не надо).

[LeBron]

Сообщение от Zealint

Кстати, вы не правы - здесь все не "в лоб". Сейчас народ пойдет Штрассена делать от безысходности. Разве это "в лоб"? Его тоже надо потрудиться написать правильно. Не по классике (где до 2^n дополнять надо), а по человечески (где не надо).

Сначала было влоб, дальше - пошло оптимальней. Но все равно, задача классическая, поэтому на эту тему очень много трудов в сети, все легко отискивается гуглом (в плане алго и его модификаций, а не в плане решения за 50 секунд).

[Zealint]

Сообщение от LeBron

Сначала было влоб, дальше - пошло оптимальней. Но все равно, задача классическая, поэтому на эту тему очень много трудов в сети, все легко отискивается гуглом (в плане алго и его модификаций, а не в плане решения за 50 секунд).

Я с вами не согласен. Во-первых, сейчас уже почти полминуты рекорд. Во-вторых, что-то я не наблюдаю, чтобы участники что-то легко отыскивали. Может, Вы попробуете?

[LeBron]

Сообщение от Zealint

Я с вами не согласен. Во-первых, сейчас уже почти полминуты рекорд. Во-вторых, что-то я не наблюдаю, чтобы участники что-то легко отыскивали. Может, Вы попробуете?

Сначала, если кто-то не знает, что такое перемножение матриц - он ищет Потом ищут всю литературу с базовых алгоритмов на эту тему.
Потом уже идет в дело теория из раздела "это и так всем понятно" (хотя, на самом деле, далеко не всем, но те, кому понятно, думают, что всем) и не связаные с алгоритмикой наработки. Согласен, готовое приложение с названием "перемножение матриц за 25 секунд" не гуглиться. И для результата 27-29 секунд нужны очень хорошие знания и очень хороша оптимизация. Но все "слогаемые" этой оптимизации можно найти, если знать, что искать, а не просто гуглить "ускорить прогу". Задача "классическая", так как была придумана для того, чтоб заинтересовать максимум народу, на эту тему найти что-то проще, чем на узоспециализированную задачу (решить NP-полную под Линуксом на видюхе или другое подобное извращение).
35.84 секунды - это уже хорошее время. Меньше 30, думаю, все же будет, я доверяю умным людям
Я пробовать не буду по 2 причинам. 1) Не мое. Гуглить что-то, не понимая что - нету смысла. Эксперементы с кешем, типами и компиляторами позволили сократить время примерно до 9 минут (с 12), но на фоне 36 секунд это выглядит смешно. А дальше эксперементировать - просто трата времени.
2) Нету времени. Завтра еду на областную, сейчас явно не конкурсами голова забита.

Давайте ставки принимать на лучшее время?
Пойду покажу тем двоим, которые заказывали время 37.5 и 38, что они недооценили человеческие возможности. Народ, постарайтесь, чтоб я еще до вечера обломал тех, кто говорил "35-36 примерно" и "36.6".

[Zealint]

Сообщение от LeBron

Народ, постарайтесь, чтоб я еще до вечера обломал тех, кто говорил "35-36 примерно" и "36.6".

Можете начинать обламывать. Сам в ужасе! Я только написал нормальную программу, как еще один участник прямо под вечер присылает самую быструю... - 22 секунды. Ладно, еще чуть больше недели - есть время отыграться : ) Давайте постараемся меньше 20?

[Arigato]

По сути задача сводится к тому, как можно быстро распарсить текстовый файл. Надо было тему назвать "Конкурс - парсинг текстового файла и перемножение матриц", т.к., боюсь, работа с файлами будет дольше, чем само умножение.

[alexBlack]

Пока еще нет. Ввод/вывод ~30% времени от 22с., т.е 2/3 все-таки умножение