2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки





Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3, 4  След.
 
 Re: злопамятный tp7, помогите!
Сообщение14.03.2017, 20:14 
Заслуженный участник
Аватара пользователя


08/11/11
4253
EUgeneUS правильно говорит, по-моему.

 Профиль  
                  
 
 Re: злопамятный tp7, помогите!
Сообщение14.03.2017, 22:37 
Аватара пользователя


31/10/08
772
alcoholist
Если программа набрана и компилируется - это ещё не значит, что она завершена. Её ещё надо отладить! И тут начинается такое, отчего дух захватывает: оказывается, что отладка занимает 90% времени, а написание кода всего 10% времени. А ещё поговаривают, что иногда математиков просили вместо отладки провести доказать правильность работы ихней программы.

Зри в корень...
Давайте вспомним такие определения как «программа» и «алгоритм». Программа - это алгоритм записанный на языке программирования. А алгоритм - это чёткая последовательность действий преобразующий входные данные в выходные.

Вот вам и ошибка. В вашей программе не предусмотрен ввод данных. А между прочим в определение алгоритма и как следствие программы требуется что-бы были входные данные. Значит протестировать её подав на вход разные данные уже не возможно.

Вторая ошибка декомпозиция программы. Она у вас попросту отсутствует. Как минимум следовало разбить код на: модель, ввод, вывод.
Зачем нужна декомпозиция? Да, для отладки! Основным инструментом отладки являются тесты.

Так вот алгоритм тестируется по входным данным. И чем их больше тем больше вариантов данных надо подать на вход.
Если у нас 2 параметра то на потребуется проверить $T*2^2$ тестов. А если у нас 3 параметра то уже $T*2^3$ и тд $O(2^n)$
Число вариантов растёт экспоненциально! Это очень крутой рост.

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

Что нам даёт правильная декомпозиция?
1. Она повышает качество кода.
2. Снижается вероятность ошибки программиста.
3. Упрощает тестирование мы можем проверить разные участки программы по отдельности.
4. Элементарные функции можно проверить просто просмотрев код. (Это для опытных программистов) А так на элементарную функцию всего с одним или двумя параметрами проще написать тест.
5. Снижается число необходимых тестов, так как уже не требуется проверять все комбинации, а можно использовать правило сведения к предыдущему. Если функция от тестирована, то она гарантированно правильно работает.
Что по сути устремляет сложность тестирования к линейной функции.
6. Упрощается восприятие кода. Человек может сосредоточиться на небольшом куске кода. Одновременно человек может удерживать в уме порядка 7-10 предметов. Чем меньше код тем меньше таких «предметов» ему требуется запомнить. Следовательно исключается фактор забывчивости.

Знал бы где подстелил соломку(А горожанин газетку постелет).
Есть ещё ряд методик который позволят так сказать подстелить соломку. Избежать допуска ошибок при наборе программы.
За подробностями советую обратиться к книге «Совершенный код».

Объединять циклы не комильфо.
Используется синтаксис Pascal
  for j:=0 to 4 do
    begin
      S[j]:=0;
      for i:=0 to 4 do
        begin
        lt[i,j]:=0;
        llt[i,j]:=0;
        matr[i,j]:=0;
        end;
    end;

Разделяем:

Используется синтаксис Pascal
  for j:=0 to 4 do
      S[j]:=0;
  for j:=0 to 4 do
      for i:=0 to 4 do
        begin
        lt[i,j]:=0;
        llt[i,j]:=0;
        matr[i,j]:=0;
        end;
 


Разбиваем на функции
код: [ скачать ] [ спрятать ]
Используется синтаксис Pascal
type
  TArrayReal:array[0..8] of real;
  TMatrixReal:array[0..4,0..4] of real;

procedure doZeroArray(Value:TArrayReal);
var i:Integer;
begin
  for j:=0 to 4 do // Тут уже видно что массив не целиком обновляется так как тут вместо 4 должно быть 8
      Value[j]:=0;
end;

procedure doZeroMatrix(Value:TArrayReal);
var i,j:Integer;
begin
  for i:=0 to 4 do
    for j:=0 to 4 do
       Value[i,j]:=0;
end;
...
doZeroArray(Z);
doZeroMatrix(lt);
doZeroMatrix(llt);
doZeroMatrix(matr);
 


Волшебные константы зло их следует заменить параметрами. Оставляю на самостоятельную работу.

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

 Профиль  
                  
 
 Re: злопамятный tp7, помогите!
Сообщение14.03.2017, 22:53 
Экс-модератор


12/07/07
2920
Донецк, Украина
Как-то юмора маловато. :D
alcoholist в сообщении #1200139 писал(а):
Запускаю exe-шник из командной строки (стандартные программы в ХР), программа выдает ответ "1". Запускаю второй раз -- ответ "2". n-ый раз, ответ "n". Закрываю окошко командной строки, открываю снова, запускаю экзешник -- снова ответ "1". Почему так происходит?
Один из вариантов программы реализующей сценарий (ТP 7.0)

Программа проверяет, не превышает ли значение младшего бита байта области межпрограммного обмена значения 254. Если не превышает, то это значение увеличивается на 1. Если превышает, то значение обнуляется.
Как правило, область межпрограммного обмена содержит 0. Поэтому при первом запуске программа выведет 1, при втором 2 и т.д. пока не достигнет 255. Потом все повторяется.

Программа под DOS. Но в ХР тоже с горем работает. Запускал из far.
Если открыть ещё один far, то [добавлено] в нём [/добавлено] счет начнется с 1. Вроде с загадкой справился.
(Переменные окружения и диск не тронуты.)
Используется синтаксис Pascal
var
 Data: Byte absolute $0040:$00F0;
begin
 if Data > 254
  then begin writeln(Data);  Data:=0 end
  else begin Data:= Data +1; writeln(Data) end;
 readln;
end.

Два writeln — стилизация под исходник ТС. :D
Upd. Формально условия игры соблюдены: указателей нет.
Upd2. Зачеркнул бит и вставил байт. Это не был юмор; просто засыпал.

 Профиль  
                  
 
 Re: злопамятный tp7, помогите!
Сообщение14.03.2017, 22:57 
Заслуженный участник
Аватара пользователя


08/11/11
4253
Pavia в сообщении #1200422 писал(а):
Объединять циклы не комильфо.

Pavia в сообщении #1200422 писал(а):
Разделяем:


Уверен, что автор скажет вам спасибо за то, что потенциально замедлили его программу в два раза! (для численных расчётов характерны длинные циклы, а также существенная разница между одним часом работы и двумя часами).

 Профиль  
                  
 
 Re: злопамятный tp7, помогите!
Сообщение14.03.2017, 23:11 
Заслуженный участник
Аватара пользователя


30/01/06
62053
GAA
Ну вот, а вы говорите, юмора маловато!

 Профиль  
                  
 
 Re: злопамятный tp7, помогите!
Сообщение15.03.2017, 08:42 


11/12/16
713
Мне всё ещё интересно - программа у TC заработала?

 Профиль  
                  
 
 Re: злопамятный tp7, помогите!
Сообщение15.03.2017, 09:16 
Аватара пользователя


31/10/08
772
g______d в сообщении #1200428 писал(а):
Уверен, что автор скажет вам спасибо за то, что потенциально замедлили его программу в два раза! (для численных расчётов характерны длинные циклы, а также существенная разница между одним часом работы и двумя часами).

Грубо ошибаетесь. Не только не замедляет но и ускоряет. Убеждался не раз практически, а ни как вы теоретически.
Во-первых. Возьмите и посчитает число операций - их осталось столько же! Откуда падение возьмётся? Если учесть скрытые расходы, то они не могли повысить затраты в 2 раза максимум 1,3 раза. Но это ещё постараться надо, типичное 1,01 раза.
Во-вторых. Использование функций упрощает жизнь оптимизатору ему легче раскидать регистры по переменным. Это даст ускорение. Притом не мифическое, а самое натуральное.
В-третьих процессоры оптимизированы на короткие циклы. Короткий цикл это цикл с коротким телом у которого мало инструкций и он может целиком разместиться в кэше.
В худшим что я наблюдал был проигрыш в 10%, а в лучшем ускорение в 8 раз.

 Профиль  
                  
 
 Re: злопамятный tp7, помогите!
Сообщение15.03.2017, 12:33 
Заслуженный участник
Аватара пользователя


30/01/06
62053
Тут вопрос с кэшом не в длине цикла, то есть не в том, как в кэше помещаются инструкции. А в том, как цикл будет обращаться к данным, и как кэш с этим справится. Тут возможны разные фокусы, от того, что от "прямобегущего" цикла стоит отказаться, и до наоборот, разделить все циклы максимально.

 Профиль  
                  
 
 Re: злопамятный tp7, помогите!
Сообщение15.03.2017, 16:25 


20/08/14
2162
Россия, Москва
Pavia в сообщении #1200496 писал(а):
В-третьих процессоры оптимизированы на короткие циклы. Короткий цикл это цикл с коротким телом у которого мало инструкций и он может целиком разместиться в кэше.
Раз уж зашёл разговор про оптимизацию под размеры кэша процессора, напомню про существование кэша микроопераций, объём которого всего полторы тысячи микроопераций (или грубо 500-1000 команд). В данном случае оба цикла, и короткий и длинный, оба уложатся в полсотни команд и разницы в скорости выполнения команд не будет.
Гораздо сильнее повлияет порядок обращения к данным (последовательное или хватает ли ассоциативности кэша данных при обращениях вразброс) и количество вычислений адресов данных. Распределение данных по регистрам конечно помогает, но не так уж критично (да, я специально проверял, замена в однотактной AVX2 команде регистра на выровненную 32-х байтовую ячейку памяти скорость практически не уменьшает пока всё помещается в L1D), кэш L1D может выдавать и записывать по числу каждый такт, скалярных команд с потоком данных выше почти нет, важнее возможность предсказания адреса следующего обращения (т.е. последовательность обращений к данным).
А вообще это уже не имеет отношения к заданному ТС вопросу.
На его ошибку (может и не единственную) сразу же правильно указал:
EUgeneUS в сообщении #1200287 писал(а):
Вы S[j] инициализируете только для j от 0 до 4, а используете для j от 0 до 8

 Профиль  
                  
 
 Re: злопамятный tp7, помогите!
Сообщение15.03.2017, 16:44 
Заслуженный участник
Аватара пользователя


30/01/06
62053
Dmitriy40 в сообщении #1200627 писал(а):
На его ошибку (может и не единственную) сразу же правильно указал:
EUgeneUS в сообщении #1200287 писал(а):
Вы S[j] инициализируете только для j от 0 до 4, а используете для j от 0 до 8

Ага. И я всё жду, когда ТС отрапортует, что ошибку исправил, и эффект пропал.

 Профиль  
                  
 
 Re: злопамятный tp7, помогите!
Сообщение15.03.2017, 17:50 
Заслуженный участник
Аватара пользователя


08/11/11
4253
Pavia в сообщении #1200496 писал(а):
Грубо ошибаетесь. Не только не замедляет но и ускоряет. Убеждался не раз практически, а ни как вы теоретически.


Ну, разумеется, это было не про цикл длины 5. А, например, про цикл длины $10^{12}$. Тогда ваша "оптимизация" будет стоить порядка 20 минут процессорного времени.

 Профиль  
                  
 
 Re: злопамятный tp7, помогите!
Сообщение15.03.2017, 18:06 
Заслуженный участник
Аватара пользователя


30/01/06
62053
g______d в сообщении #1200652 писал(а):
Тогда ваша "оптимизация" будет стоить порядка 20 минут процессорного времени.

Объяснитесь всё-таки.

 Профиль  
                  
 
 Re: злопамятный tp7, помогите!
Сообщение15.03.2017, 18:29 
Заслуженный участник
Аватара пользователя


08/11/11
4253
Munin в сообщении #1200657 писал(а):
Объяснитесь всё-таки.


Операция "прибавить к $j$ единицу" после разбиения циклов делается в два раза больше раз.

 Профиль  
                  
 
 Re: злопамятный tp7, помогите!
Сообщение15.03.2017, 18:54 
Заслуженный участник
Аватара пользователя


30/01/06
62053
А, про неё вам уже сказали, она в цикле обычно занимает наименьшее время.

 Профиль  
                  
 
 Re: злопамятный tp7, помогите!
Сообщение15.03.2017, 19:00 
Заслуженный участник
Аватара пользователя


08/11/11
4253
Munin в сообщении #1200676 писал(а):
А, про неё вам уже сказали, она в цикле обычно занимает наименьшее время.


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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 53 ]  На страницу Пред.  1, 2, 3, 4  След.

Модераторы: Toucan, maxal, Karan, PAV, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group