Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > Клуб программистов > Свободное общение
Регистрация

Восстановить пароль

Купить рекламу на форуме - 42 тыс руб за месяц

Закрытая тема
Ваша тема закрыта, почему это могло произойти? Возможно,
Нет наработок или кода, если нужно готовое решение - создайте тему в разделе Фриланс и оплатите работу.
Название темы включает слова - "Помогите", "Нужна помощь", "Срочно", "Пожалуйста".
Название темы слишком короткое или не отражает сути вашего вопроса.
Тема исчерпала себя, помните, один вопрос - одна тема
Прочитайте правила и заново правильно создайте тему.
 
Опции темы Поиск в этой теме
Старый 09.02.2010, 07:10   #11
Zealint
Пользователь
 
Регистрация: 08.02.2010
Сообщений: 51
По умолчанию

Цитата:
Сообщение от mihali4 Посмотреть сообщение
Не все так просто, уважаемый.
Вы не учли "накладные" расходы.
Да, так как считает тов. Ulex, считать в общем случае нельзя. Во-первых, 10 тактов на цикл - это может в среднем и правильно, но на каждое новое выполнение может дать другое время, это связано с особенностью работы с памятью: элемент матрицы мог попасть в КЭШ, тогда все хорошо, а мог не попасть. Далее, никто не говорит, что нужно именно тройным циклом считать, есть еще куча методов, где организация вычислений куда более оптимальная. Например, вот моя программа работала почти 15 минут, учтя только возможность кэширования массивов я могу ускорить ее, примерно, втрое. Пока думаю как это сделать на практике...

Цитата:
Как время будет засекаться?
Есть у меня для этого подпрограмма вычисления процессорного времени. Во-вторых, процессор двухъядерный, поэтому даже если одно ядро будет занято рисованием морды для Windows, то второе будет работать на 100%. Погрешность измерения времени - 32 мс. Тут все нормально.

Цитата:
И что значит нельзя пользоваться dll. И системными тоже?
Имелось в виду, что ваша программа не должна подгружать никакие динамические библиотеки в процессе работы. Даже системные. Хотя, если они нужны для запуска программы, то это, конечно, не запрещается. Важно другое, что у вас "голый" Windows и все.

Цитата:
А почему не сделать входные и выходные файлы бинарными?
А вот это в тему! Дело в том, что была такая идея, но сначала хотел сделать конкурс для всех архитектур, и поэтому хранить файлы в бинарном виде не получится - они будут по-разному интерпретироваться. Потом я сделал конкурс только для Windows и под Intel, а про файлы забыл. Ну и ладно: время считывания файла - доля секунды (если использовать scanf, конечно, а не cin в С++), я проверил. А храню я их не в виде файла, а в виде генератора тестов. Хотя Ваше замечание я учту для будущих конкурсов.
Zealint вне форума
Старый 09.02.2010, 09:13   #12
ROD
Linux C++ Qt ARM
Старожил
 
Аватар для ROD
 
Регистрация: 30.11.2008
Сообщений: 3,030
По умолчанию

Цитата:
// Не курсак и не лаба - я даже исходников не требую
Так дезасамблировать можно. И будут у тебя исходники на асамблере.

Цитата:
Важно другое, что у вас "голый" Windows и все.
А какой виндус считать "голым" ?

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

"Слова ничего не стоят - покажите мне код!" © Линус Торвальдс

Последний раз редактировалось ROD; 09.02.2010 в 09:18.
ROD вне форума
Старый 09.02.2010, 09:57   #13
Zealint
Пользователь
 
Регистрация: 08.02.2010
Сообщений: 51
По умолчанию

Цитата:
Сообщение от ROD Посмотреть сообщение
Так дезасамблировать можно. И будут у тебя исходники на асамблере.
Больше мне делать нечего : ) Что у всех такое странное недоверие? Одна простая вещь: если мне любой ценой нужно будет очень быстро перемножить матрицы, я напишу программу для кластера. Здесь принципиальны именно те ограничения, которые я указал. Хочу понять, насколько можно написать эффективный последовательный код именно при таких условиях. Далее, заметьте, что я сам тоже принимаю участие в конкурсе, поэтому если бы это была лаба или курсовая, я бы сам ее написал. Тем более, я уже давно закончил университет. Ребята, да вы что?! Халявная тысяча лежит, а вы какие-то странные вопросы задаете!

Другие мои конкурсы будут гораздо сложнее.


Цитата:
Сообщение от ROD Посмотреть сообщение
А какой виндус считать "голым" ?
Ну вот установили вы Windows XP и все (стандартная установка + SP3). Он у меня называется "голым".
Zealint вне форума
Старый 09.02.2010, 10:06   #14
Utkin
Старожил
 
Аватар для Utkin
 
Регистрация: 04.02.2009
Сообщений: 17,351
По умолчанию

Зверь считается чистой виндой ?
А разве с чистой виндой поставляется GCC 3.4.5 ?
А можно использовать видеокарту в помощь расчетам?
И может где-то и было написано, я не углядел, а что 2 ядра использовать нельзя?
Маньяк-самоучка
Utkin появился в результате деления на нуль.
Осторожно! Альтернативная логика

Последний раз редактировалось Utkin; 09.02.2010 в 10:20.
Utkin вне форума
Старый 09.02.2010, 11:01   #15
Zealint
Пользователь
 
Регистрация: 08.02.2010
Сообщений: 51
По умолчанию

Цитата:
Сообщение от Utkin Посмотреть сообщение
Зверь считается чистой виндой ?
А разве с чистой виндой поставляется GCC 3.4.5 ?
А можно использовать видеокарту в помощь расчетам?
И может где-то и было написано, я не углядел, а что 2 ядра использовать нельзя?
Можете считать зверя чистой : ) Нет, компилятор не поставляется с чистой виндой, я компилировал вообще на другом компьютере. Не на том, на котором проводится тестирование. Видеокарту использовать нельзя, я же сказал, что нужна последовательная программа. На одном ядре - это принципиально ограничение. Конечно, я могу запустить на всех 80 ядрах, которые у меня есть, но смысл конкурса не в этом : )
Конкурсы по параллельным вычислениям и по видеокартам еще впереди. Всему свое время. Для начала выиграйте этот.
Zealint вне форума
Старый 09.02.2010, 11:19   #16
ROD
Linux C++ Qt ARM
Старожил
 
Аватар для ROD
 
Регистрация: 30.11.2008
Сообщений: 3,030
По умолчанию

Цитата:
Ну вот установили вы Windows XP и все (стандартная установка + SP3)
Windows XP бывает разный (если речь идет именно о нормальном, лицензионном, так сказать)
Дилетант широкого профиля.

"Слова ничего не стоят - покажите мне код!" © Линус Торвальдс
ROD вне форума
Старый 09.02.2010, 12:40   #17
Vago
Форумчанин
 
Регистрация: 15.01.2010
Сообщений: 948
По умолчанию

Алаверды первому из вопросов Ulex'a.
Как, всё-таки, будет засекаться время вычислений (без учёта времени I/O)? Я, ради интереса, наставил самых элементарных time'ов на старте, после окончания "ввода" (случайной генерации), после окончания перемножения и после окончания вывода в файл. Ввод-вывод (без какой бы то ни было оптимизации, естественно) у меня забирает от 40% (n=1024) до 16% (n=5000) от общего времени работы. И это ж при "вводе" у меня никаких дисковых операций на самом деле пока нет...

Последний раз редактировалось Vago; 09.02.2010 в 12:42.
Vago вне форума
Старый 09.02.2010, 13:24   #18
m0nax
Форумчанин
 
Аватар для m0nax
 
Регистрация: 25.09.2009
Сообщений: 525
По умолчанию

а какая разница как считать время?
оно же для всех одинаковое будет, т.е всем читать и всем записывать, а победит тот чья программа быстрей, а из-за чего и почему быстрей - не имеет значения, что не так?
m0nax вне форума
Старый 09.02.2010, 13:28   #19
Ulex
Непрофессионал
Участник клуба
 
Аватар для Ulex
 
Регистрация: 01.01.2008
Сообщений: 1,405
По умолчанию

Цитата:
Дело в том, что была такая идея, но сначала хотел сделать конкурс для всех архитектур, и поэтому хранить файлы в бинарном виде не получится - они будут по-разному интерпретироваться. Потом я сделал конкурс только для Windows и под Intel, а про файлы забыл. Ну и ладно: время считывания файла - доля секунды (если использовать scanf, конечно, а не cin в С++), я проверил.
Так вроде как раз если файлы бинарные, то к архитектуре то они как будут привязаны (просто набор байт). Читайте побайтно, или сразу весь файл в память и вперёд. Или это конкурс для определённой среды (С++).

Я, кстати, ошибся. Размер входного файла не 2, а ~200 Мбайт. (глазки спать хотели и два нолика не заметили). И как то я не верю, что время считывания текстового файла размером 200 М и разбор его (а это как минимум перевод символов в integer) будет занимать долю секунды. Признавайтесь - на какой максимальной размерности матрицы вы тестировали свою программу, и как было получено итоговое время прохождения теста?
Это ни в коем случае не наезды, мне просто действительно любопытно.

Я вот, например, накидал по быренькому умножение матриц (без всяких наворотов, просто строка на столбец).
Так как с файлом заморачиваться не хочу, то пока элементы входных матриц тоже генерятся рандомно.
Но, любопытно время.
Для матрицы 2500*2500 программа считает вых. матрицу примерно 5 мин.
Соответственно для 5000*5000 время будет ~ в 8 раз больше -> что такая матрица на моей конфигурации будет считаться ~ 40 мин. Это без всякого файлового ввода. Но я на такой размерности даже и запускать не стал.

Конфигурация:
3-ий Celeron ~1270 MГц (одно ядро, естественно). ОЗУ - 256 Мбайт.
Программа работала с приоритетом REAL_TIME.

Цитата:
оно же для всех одинаковое будет, т.е всем читать и всем записывать, а победит тот чья программа быстрей, а из-за чего и почему быстрей - не имеет значения, что не так?
Не так то, что конкурс называется быстрое перемножение матриц, а не быстрый парсинг огромных текстовых файлов.
Если бы задача ставилась как быстрое чтение и разбор файла, то зачем тогда тут матрица нужна?
И чем больше я узнавал людей, тем больше мне нравились компьютеры.
------------------------------------
Страничка с моими программками http://ulex-masm.ru

Последний раз редактировалось Stilet; 10.02.2010 в 13:22.
Ulex вне форума
Старый 09.02.2010, 14:08   #20
Zealint
Пользователь
 
Регистрация: 08.02.2010
Сообщений: 51
По умолчанию

Цитата:
Windows XP бывает разный (если речь идет именно о нормальном, лицензионном, так сказать)
Да ладно придираться, обычную винду не видели? Если ваша программа у меня не запустится, я скажу, почему это случилось. А так не вижу причины задавать вопросы про то, чем свежеустановленная видна отличается от винды, напичканной непонятно чем. Я всего лишь имею в виду, что никаких вспомогательных средств для вычислений программа не должна подгружать из вне.

Цитата:
Как, всё-таки, будет засекаться время вычислений
Вычисляется время работы программы полностью, а не время, которая она затрачивает на вычисления. Программа стартует (и мне все равно, что она в этот момент делает) - время пошло. Программа завершилась - время остановилось. Конечно, если вы пишите ввод вывод через какой-нибудь убогий cin, то работать это будет в разы дольше.


Цитата:
Так вроде как раз если файлы бинарные, то к архитектуре то они как будут привязаны (просто набор байт). Читайте побайтно, или сразу весь файл в память и вперёд. Или это конкурс для определённой среды (С++).
Нет. Некоторые архитектуры остроконечные, а некоторые - тупоконечные. То есть в одних слова хранятся в прямом порядке, а в других - в обратном.

Цитата:
Я, кстати, ошибся. Размер входного файла не 2, а ~200 Мбайт. (глазки спать хотели и два нолика не заметили). И как то я не верю, что время считывания текстового файла размером 200 М и разбор его (а это как минимум перевод символов в integer) будет занимать долю секунды. Признавайтесь - на какой максимальной размерности матрицы вы тестировали свою программу, и как было получено итоговое время прохождения теста?
Это ни в коем случае не наезды, мне просто действительно любопытно.
Да, 238 Мб, я кстати, тоже ошибся: за долю секунды работает ввод с моей собственной функцией (написанной за 6 минут). Программа, которая работает через scanf считывает 12 секунд. Эти цифры будут важны только если у вас очень быстрая программа и вам в рейтинге наступают на пятки... а пока никто даже прислать хоть какую-то версию не может, я даже не знаю, с кем соревноваться-то еще? Я математиков звал, так они программировать не умеют...



Цитата:
Я вот, например, накидал по быренькому умножение матриц (без всяких наворотов, просто строка на столбец).
Так как с файлом заморачиваться не хочу, то пока элементы входных матриц тоже генерятся рандомно.
Но, любопытно время.
Для матрицы 2500*2500 программа считает вых. матрицу примерно 5 мин.
Соответственно для 5000*5000 время будет ~ в 8 раз больше -> что такая матрица на моей конфигурации будет считаться ~ 40 мин. Это без всякого файлового ввода. Но я на такой размерности даже и запускать не стал.

Конфигурация:
3-ий Celeron ~1270 MГц (одно ядро, естественно). ОЗУ - 256 Мбайт.
Программа работала с приоритетом REAL_TIME.
Процессор у вас раза в три-четыре слабее моего (учтите еще, что у вас кэш обрезанный). Кроме того, 256 МБ не хватит для хранения матриц полного размера. Моя такая же тупая реализация работает 800 секунд, я могу еще её ускорить, если хоть кто-то покажет, что у него быстрее хотя бы втрое : ) Один уже показал, но у него Linux, он не хочет участвовать. Ждем Windows-программистов. Ребята, в этой задаче, чтобы выиграть, надо думать. Задача простая, согласен, но руки в вопросах оптимизации не у всех прямые - с этим согласны? В этом и суть. Конечно будут и задачи на поиск ответа любой ценой (хоть на 100 000 процессорах считайте) но это в другой раз. Сейчас решаем школьное упражнение. Для затравки : )

Цитата:
Не так то, что конкурс называется быстрое перемножение матриц, а не быстрый парсинг огромных текстовых файлов.
Если бы задача ставилась как быстрое чтение и разбор файла, то зачем тогда тут матрица нужна?
Как я уже сказал, 12 секунд на ввод данных - не много, когда программа работает больше 10 минут. Оптимизировать ввод можете начинать, если попадете в ТОП, тем более, что написать считывание целого числа руками - это дело нескольких минут. Так ведь? Ну и последнее, я ведь никого не заставляю "париться" : ) Можете подождать, когда будет конкурс на решение другой задачи. Но все мои конкурсы будут касаться эффективности (прямо или косвенно).

Хотя я рад, что началось бурное обсуждение : )
Zealint вне форума
Закрытая тема


Купить рекламу на форуме - 42 тыс руб за месяц



Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Перемножение матриц stscolt Помощь студентам 0 09.10.2009 16:54
Перемножение матриц jorjinho10 Паскаль, Turbo Pascal, PascalABC.NET 1 11.05.2009 12:56
Перемножение матриц Blad47 Общие вопросы C/C++ 1 02.02.2009 00:21
Перемножение матриц Арина Помощь студентам 1 18.05.2007 19:21