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

[Zealint]

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

Это легко отселить. Добавить в правила, что участвовать могут только форумчане со стажем.

Не получится. Форумов много и стаж у всех не объективен. Кроме того, участвуют еще другие люди, которых я нашел не на форумах. Где же гарантия, что не победит мой друг, которому я подарил программу? Все это не то. Зря вы так - приз не десять тысяч, чтобы так переживать. Когда приз будет в десятки тысяч, правила будут иными. Я не то, что участвовать, комментировать ход событий не буду, чтобы народ не дай бог не подумал, что я на чьей-то стороне.

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

Не могу, это даёт приемущество всем. А у кого-то могут быть секреты в коде, которые легко дизассемблировать (хотя вряд ли за 1000 р так будут убиваться, только если из профессионального интереса). Потому я решил по-другому делать: когда моя программа становится быстрее, я обязательно делаю подсказку - как я её ускорил. Остальные участники, конечно, подсказки друг другу не делают. То есть все свои выводы и размышления я открыто публикую. И даже потом могу всем раздать исходники, чтобы народ убедился, что все честно, что я пишу именно то, что думаю.

[akasex]

TS,

полный чайник в вопросах линейной алгебры

алгебра здесь ни при чем...грубо говоря задачу мойно решить стандартним способом "строка на столбец" или исползовать алгоритм штрассена который перемножит матрицы быстрее но при этом размер матрицы будет гораздо больше заявленних в конкурсе 5000, что само по себе уже дает понять что Штрассен вычеркивается по условию и задачей конкурса становится не перемножение матриц само по себе быстреишим способом, а тупое соревнование в скорости на чтении/запись....а сама линеиноя алгебра как таковая становиться и вовсе не причем....

[Zealint]

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

TS,
алгебра здесь ни при чем...грубо говоря задачу мойно решить стандартним способом "строка на столбец" или исползовать алгоритм штрассена который перемножит матрицы быстрее но при этом размер матрицы будет гораздо больше заявленних в конкурсе 5000, что само по себе уже дает понять что Штрассен вычеркивается по условию и задачей конкурса становится не перемножение матриц само по себе быстреишим способом, а тупое соревнование в скорости на чтении/запись....а сама линеиноя алгебра как таковая становиться и вовсе не причем....

Ваше рассуждение как раз показывает, что вы - мой коллега, то есть такой же чайник в этих вопросах. Итак, почему Штрассен вычеркивается? Один из участников реализовал его так, что все поместилось в 900 мегабайт. Только он пока не даёт программу. Еще один участник уже прислал мне программу, использующую Blus - там как раз этот метод реализован. Только, видимо, каким-то криворуким первокурсником, уж очень медленно работает. Хотя может так и должно быть. Я не знаю. Далее, с чего вы взяли, что размер матрицы будет сильно больше 5000? Вовсе не обязательно делать матрицу размером под степень двойки. Так что это вовсе не тупое соревнование по скорости чтения/записи : ) Если подумать, то ЛА очень даже причем. А ведь еще есть другие билинейные алгоритмы, которые быстрее Штрассена и жрут меньше памяти. Например, есть алгоритм, который сначала разбивает матрицу треугольные матрицы.... Так что знать линейную надо. Более того, я докажу, что Штрассен помещается в память, ведь я все-таки собрался его написать в скором времени.

Все-таки предлагаю закончить болтовню, если хотите что-то доказать, что придется потрудиться над аргументами. Как видите, не аргументированные доводы разбиваются очень легко и поэтому ничего не стоят. Вы согласны?

[Arigato]

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

Не могу, это даёт приемущество всем. А у кого-то могут быть секреты в коде, которые легко дизассемблировать (хотя вряд ли за 1000 р так будут убиваться, только если из профессионального интереса).

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

Может такой вариант будет лучше: Вы выкладываете программу для замера времени со всеми тестами, участники сами замеряют время, отписывая его в этой теме. Затем участник с лучшем временем в конце конкурса обязан показать своё решение всем, что бы доказать, что он не с потолка взял цифры. Ему (или себе, если это окажетесь Вы сами) Вы отдаёте призовой фонд. Как такая идея?

[LeBron]

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

Может такой вариант будет лучше: Вы выкладываете программу для замера времени со всеми тестами, участники сами замеряют время, отписывая его в этой теме. Затем участник с лучшем временем в конце конкурса обязан показать своё решение всем, что бы доказать, что он не с потолка взял цифры. Ему (или себе, если это окажетесь Вы сами) Вы отдаёте призовой фонд. Как такая идея?

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

[akasex]

TS,

мое первое решение на шарпе(!!!!!) тоже спокойно управлятся в 900мб....а кешированное второе решение делает тоже используя 40мб ...но работает естественно медленее ....так что память в этои "задаче" главное...

[Ulex]

Зря с файлами связались.

Программа должна записывать ответ в файл «output.txt» (и должна сама создавать его по мере необходимости).

Открыть файл для записи и создать файл для записи вещи чуть чуть разные.

Сейчас тестил свою умножалку. Если открыть файл - то данные в него пишутся ~ 10 сек. А если создать файл, то время увеличивается на порядок.
У меня это составило ~100 сек. При времени расчёта самой матрицы 180 сек, это уже очень ощутимый вклад в общее время.

[Zealint]

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

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

Может такой вариант будет лучше: Вы выкладываете программу для замера времени со всеми тестами, участники сами замеряют время, отписывая его в этой теме. Затем участник с лучшем временем в конце конкурса обязан показать своё решение всем, что бы доказать, что он не с потолка взял цифры. Ему (или себе, если это окажетесь Вы сами) Вы отдаёте призовой фонд. Как такая идея?

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

Далее, если бы я позволил каждому отписывать свое время, то конкурс превратился бы в балаган, где каждый пишет цифру меньше, чем предыдущий участник, а в конце конкурса просто исчезает и все вокруг остаются в идиотском положении. Кроме того, у всех разные процессоры, поэтому сравнение необъективно. Например, моя программа, которая работала 800 секунд на процессоре с кэшем вдвое большем (12Mb) на более медленно процессоре работала 108 секунд (компилятор, правда другой был). Понимаете?

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

Тем более, нет гарантии, что программисты пишут программу правильно. Например, 75% тех, кто присылал мне программы, решали задачу неправильно - ответы были неправильными. Так что проверять все это лучше только мне на уже точно правильных тестах.

Arigato, я вроде бы все доступно объяснил. Правила конкурса и участия я продумывал не одни сутки. Так что все в порядке. Все варианты, которые вы предлагаете, я тоже уже обдумывал. Вы просто зацепились и вам не терпится меня в чем-то упрекнуть. А зачем?

Как по мне, нормально бы было после окончания конкурса выложить решения первой пятерки для общего сравнения и оценки.

Я же уже сказал, что выложу весь архив с тестами. Проверялку могу тоже кинуть. Только не свою, а другую, которой проще пользоваться. В целом, она дает те же цифры (+/- пара секунд). Матрицы тоже выложу, только не сами матрицы, а генераторы. Конечно же на вашем компьютере числа будут другими. Особенно если у вас не Intel. Например, один человек прислал мне прогу, скомпилированную на Opteron. Так она даже не запустилась, вылетев с системной ошибкой.

Открыть файл для записи и создать файл для записи вещи чуть чуть разные.

Сейчас тестил свою умножалку. Если открыть файл - то данные в него пишутся ~ 10 сек. А если создать файл, то время увеличивается на порядок.
У меня это составило ~100 сек. При времени расчёта самой матрицы 180 сек, это уже очень ощутимый вклад в общее время.

Я согласен : ) конечно же есть разница. Но я же не запрещаю делать все, что угодно, чтобы файл с ответом появился там, где надо. Я же не сказал, что вам нужно именно открывать или создавать файл.
Правило говорит, что если файла в директории нет, то он должен создаваться. То есть программа не должна вылетать с ошибкой, если не нашла файл для вывода ответа. Да даже если бы этот файл был, он мог занимать 0 байт и все, все равно что создать новый. У меня на диске есть свободное место, поэтому создаваемый файл заполняется последовательно и довольно быстро. Не волнуйтесь.

[Arigato]

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

Далее, вы что правда думаете, что обладая EXE файлами я могу делать какие-то выводы? (сами исходники я не прошу предъявлять). Нет, конечно, я просто могу их "пощупать", но улучшить или понять на чем они основаны - нет. Это исключено, а дизассемблировать и сидеть с карандашом и блокнотом мне некогда.

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

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

Правила конкурса и участия я продумывал не одни сутки. Так что все в порядке. Все варианты, которые вы предлагаете, я тоже уже обдумывал. Вы просто зацепились и вам не терпится меня в чем-то упрекнуть. А зачем?

Затем, что Ваши правила не корректны, т.к. Вы являетесь привилегированным участником. Была как-то открытая олимпиада в Таганрогском универе, возил туда команду как тренер (не участвовал сам). Так там один из конкурсов был таким: была игра танчики, для которой нужно было написать dll-библиотеку - интеллект танка, используя определённый интерфейс. Побеждал тот, у кого по результатам нескольких боёв танк оказывался круче. Знаете кто победил? Те, кто движок этих танчиков и разработали. Да, они участвовали в конкурсе "на равных" с остальными. Результат предсказуем.

[LeBron]

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

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

Будете, в целях справедливости, грузить штук 10 файлов, каждый из которых далеко не по мегабайту?

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

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