сфера nd

Форум пользователей пакета Maple

Модератор: Admin

Kitonum
Сообщения: 2084
Зарегистрирован: Ср дек 31, 2008 1:55 pm
Откуда: г. Пенза

Сообщение Kitonum » Вт окт 04, 2011 9:30 pm

алексей_алексей писал(а):...Не понял, зачем мы перед оператором конца процедуры пишем A[N]?…

По умолчанию любая процедура возвращает результат выполнения последней команды в её тексте перед end proc . Если необходимо возвращать какие-то промежуточные результаты, то следует использовать команду print. В данной процедуре A[N] перед end proc можно не писать, т.к. в цикле перед этим на последнем шаге как раз и вычисляется A[N]. В моём коде она была написана просто для удобочитаемости кода, чтобы сразу было видно что же именно возвращает процедура!

алексей_алексей
Сообщения: 1776
Зарегистрирован: Вс май 01, 2005 9:02 pm

Сообщение алексей_алексей » Вт окт 04, 2011 10:33 pm

Kitonum писал(а):A[N]. В моём коде она была написана просто для удобочитаемости кода, чтобы сразу было видно что же именно возвращает процедура!

Стало немного яснее, но с использованием имени процедуры выглядело куда лучше, плохо, что не все интерфейсы это одинаково понимают.

И вот такой технический вопрос: число 24^5 (P(1,4,12)) является, похоже, реальной границей для пакета по времени и памяти, а имеется информация о размерах массивов, с которыми Мэпл может нормально работать?

uni
Сообщения: 1817
Зарегистрирован: Сб ноя 13, 2004 3:06 pm
Откуда: п.г.т. Излучинск
Контактная информация:

Сообщение uni » Ср окт 05, 2011 4:03 pm

По поводу таблиц синусов. Код при этом может потерять свою красоту, т.к. он будет зависеть от внешних данных.

Нужно лишь создать одну или две таблицы (последовательности) со значениями sin(Pi*k/M) и cos(Pi*k/M) при изменении k в нужных пределах. А в тексте заменить эти выражения на SinTable[k] и CosTable[k] вместо вычисления синусов и косинусов. В коде идёт обращение к функциям sin() и cos() достаточно много раз, а их вычисление заведомо занимает больше времени, чем взятие уже готового результата из таблицы. Особенно это должно быть заметно при увеличении размерности задачи.

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

алексей_алексей
Сообщения: 1776
Зарегистрирован: Вс май 01, 2005 9:02 pm

Сообщение алексей_алексей » Ср окт 05, 2011 4:50 pm

Правильно, предварительно вычислять две небольшие таблицы со значениями выбранной плотности, а потом просто умножение. Тогда время счёта сократится на порядки и можно будет поднять предел размерности СНАУ.
Вот бы уже понемногу и опробовать для слегка визуализируемых размерностей… :)

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

Не знаю, а что для работы с памятью лучше?

uni
Сообщения: 1817
Зарегистрирован: Сб ноя 13, 2004 3:06 pm
Откуда: п.г.т. Излучинск
Контактная информация:

Сообщение uni » Ср окт 05, 2011 5:42 pm

Не знаю, а что для работы с памятью лучше?
Меньше операций выделения памяти и переразмещения массивов при изменении их размеров. Если однозначно знать (указать) сколько понадобится памяти для решения задачи, то это заведомо лучше всего остального вместе взятого.

Математические пакеты пытаются предсказать объём необходимой памяти для переменных и изменяют размеры отводимой памяти при изменении размеров переменных. Если в процессе расчёта массив масштабируется до неизвестных размеров и с неизвестной скоростью, то это заведомо плохо скажется на скоростных характеристиках реализации. Т.к. будут выполняться дополнительные действия по работе с памятью.

Во всех быстрых алгоритмах всегда точно заранее известно: что, сколько, когда и где нужно.

алексей_алексей
Сообщения: 1776
Зарегистрирован: Вс май 01, 2005 9:02 pm

Сообщение алексей_алексей » Ср окт 05, 2011 8:58 pm

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

Предполагая, что кому-то из заглядывающих в тему не очень понятно, поясню: мы (?) собираемся применить “прочёсывание” ограниченного множества размерности меньшего на единицу, чем само пространство. Роль этого множества играет гиперсфера, внутри которой будут находиться все корни СНАУ. Каждое из уравнений системы описывает неограниченное множество в пространстве 2*n и тем самым оставляет на сфере “след” от пересечения с нею. Например, каждое из сочетаний по 2*n-1 уравнений оставит на сфере точку, если система совместна и имеет конечное число корней, а эти точки приведут по линии пересечения 2*n-1уравнений к корням системы, которые находится внутри сферы…

Kitonum
Сообщения: 2084
Зарегистрирован: Ср дек 31, 2008 1:55 pm
Откуда: г. Пенза

Сообщение Kitonum » Чт окт 06, 2011 4:37 pm

uni писал(а):Нужно лишь создать одну или две таблицы (последовательности) со значениями sin(Pi*k/M) и cos(Pi*k/M) при изменении k в нужных пределах. А в тексте заменить эти выражения на SinTable[k] и CosTable[k] вместо вычисления синусов и косинусов. В коде идёт обращение к функциям sin() и cos() достаточно много раз, а их вычисление заведомо занимает больше времени, чем взятие уже готового результата из таблицы. Особенно это должно быть заметно при увеличении размерности задачи.

Полностью согласен! Очень хорошая идея! Подкорректировал свой код на её основе, работать стал заметно быстрее.

Подправленный код:

P:=proc(R, N, M)
local A,B;
A:=[seq(evalf[3](sin(Pi*m/M)),m=1..M-1)];
B:=[seq(evalf[3](cos(Pi*m/M)),m=1..M-1)];
P(R,1,M):=[seq([R*evalf[3](cos(Pi*k/M)),R*evalf[3](sin(Pi*k/M))],k=0..2*M-1)];
if N>1 then P(R,N,M):=[[seq(0,j=1..N),1],seq(seq([seq(P(R,N-1,M)[k][n]*A[m],n=1..N),R*B[m]],k=1..nops(P(R,N-1,M))),m=1..M-1),[seq(0,j=1..N),-1]];
fi;
end proc:


Эксперименты со временем:

st:= time(): (P(1,2,20)): time() - st;
0.031

st:= time(): (P(1,3,20)): time() - st;
0.171

st:= time(): (P(1,4,20)): time() - st;
4.914

st:= time(): (P(1,5,20)): time() - st;
257.932

Кстати, последняя сфера P(1,5,20) содержит 5227320 точек:
nops(P(1,5,20));
5227320


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

А вот с этим соглашусь, когда увижу такой альтернативный код! Пока это всего лишь декларация.

алексей_алексей писал(а):...И вот такой технический вопрос: число 24^5 (P(1,4,12)) является, похоже, реальной границей для пакета по времени и памяти, а имеется информация о размерах массивов, с которыми Мэпл может нормально работать?

Список P(1,4,12) содержит не 24^5 точек, а значительно меньше, а именно 275122 точки.

Точное количество точек при любых N и M можно найти, решая рекуррентное уравнение:

f:=unapply(rsolve({f(N+1,M)=(M-1)*f(N,M)+2,f(1,M)=2*M},f),N,M);
f := (N, M) -> 2*M/(M-1)*(M-1)^N-2/(-2+M)+2/(M-1)/(-2+M)*(M-1)^N

Для наглядности привожу количества точек при M=20 для сфер размерностей от 1 до 10:

seq(f(N,20),N=1..10);
40, 762, 14480, 275122, 5227320, 99319082, 1887062560, 35854188642, 681229584200, 12943362099802

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

uni
Сообщения: 1817
Зарегистрирован: Сб ноя 13, 2004 3:06 pm
Откуда: п.г.т. Излучинск
Контактная информация:

Сообщение uni » Чт окт 06, 2011 6:50 pm

А вот с этим соглашусь, когда увижу такой альтернативный код! Пока это всего лишь декларация.


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

Фишка вашего кода в алгоритме (он значительно эффективнее моего), а рекурсия - подходящая для него форма представления. Машина же всё равно работает по циклам, просто они вложенные. Их можно развернуть и записать в обычном виде, может это будет выглядеть не так красиво, но работать будет почти также.

Компьютер ничего не знает о рекурсии. Ему всё равно что перемалывать. Просто рекурсивная работа немножко по-другому организована в плане работы с памятью.

http://ru.wikipedia.org/wiki/Рекурсия
Любую рекурсивную функцию можно заменить циклом и стеком.

Kitonum
Сообщения: 2084
Зарегистрирован: Ср дек 31, 2008 1:55 pm
Откуда: г. Пенза

Сообщение Kitonum » Чт окт 06, 2011 8:41 pm

uni писал(а):Компьютер ничего не знает о рекурсии. Ему всё равно что перемалывать. Просто рекурсивная работа немножко по-другому организована в плане работы с памятью.

http://ru.wikipedia.org/wiki/Рекурсия
Любую рекурсивную функцию можно заменить циклом и стеком.

Спасибо за ссылку,почитаю! В теоретических вопросах программирования я, конечно, слабоват. Буду учиться!

алексей_алексей
Сообщения: 1776
Зарегистрирован: Вс май 01, 2005 9:02 pm

Сообщение алексей_алексей » Чт окт 06, 2011 10:40 pm

Kitonum писал(а):Список P(1,4,12) содержит не 24^5 точек, а значительно меньше, а именно 275122 точки.

Точное количество точек при любых N и M можно найти, решая рекуррентное уравнение:

f:=unapply(rsolve({f(N+1,M)=(M-1)*f(N,M)+2,f(1,M)=2*M},f),N,M);
f := (N, M) -> 2*M/(M-1)*(M-1)^N-2/(-2+M)+2/(M-1)/(-2+M)*(M-1)^N

Для наглядности привожу количества точек при M=20 для сфер размерностей от 1 до 10:

seq(f(N,20),N=1..10);
40, 762, 14480, 275122, 5227320, 99319082, 1887062560, 35854188642, 681229584200, 12943362099802


У меня при P(1,5,12) “выносит” программу на Вашей предыдущей версии процедуры, но теперь всё нормально. А оценку привел, запутавшись в размерностях сферы и пространства переменных. У нас 5 для сферы соответствует 6 для пространства, а 24 получилось уже само по себе, наверное, из другого примера… (Да и Вы, вижу, число 275122 получили не для 12 точек…) Кстати, что-то даёт зависание именно на 12 точках.
У Славы при (5,12) считает примерно 163 сек, точек выдаёт 248833 и не зависает. Теперь у Вас P(1,5,12) считает за 5,75 сек. Что очень быстро…


--------------------------------------------------------

Алгоритм движения по кривой, записанный совместными усилиями в коде Мэпл, имеется, практически, это метод Драгилева: http://forum.exponenta.ru/viewtopic.php ... c&start=45
моё сообщение от Апр 10, 2011 12:46 pm.( Там линия пересечения двух алгебраических поверхностей в виде решения системы диффуравнений.)
Таким же способом будут получаться линии пересечения для каждого из сочетаний 2*n-1 уравнений, таких сочетаний, понятно, всего 2*n, 2*n, потому что число уравнений исходной алгебраической системы удваивается за счёт представления каждой переменной в виде суммы её мнимой и действительной части. После подстановки переменных в исходные уравнения, приравниваем нулю отдельно мнимую часть уравнения и реальную, и получаем удвоенную систему уравнений с удвоенным же числом переменных. Подставляя точки сферы в уравнения, следим за величиной невязки каждого из них, выбирая те 2*n-1 из них, для которых невязка будет “приемлемой” для дальнейшего уточнения (например, отсутствие такой точки будет говорить о большой вероятности, что система несовместна). Потом уточняем точку, которая будет довольно точно принадлежать линии пересечения выбранных 2*n-1 уравнений, и движемся по линии до пересечения с оставшимся уравнением. Это пересечение будет соответствовать комплексному корню исходной системы… Направление движения внутрь сферы можно определить из знака невязки после подстановки следующей за начальной точки в неявное уравнение нашей сферы. Как ориентир, величина параметра интегрирования приблизительно равна радиусу сферы… Не совсем конкретика, но как частично работающие приближения… Стоит связываться?

Kitonum
Сообщения: 2084
Зарегистрирован: Ср дек 31, 2008 1:55 pm
Откуда: г. Пенза

Сообщение Kitonum » Пт окт 07, 2011 8:38 pm

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

Процедура с простым циклом:

F1:=proc(n)
local p,k;
p:=1;
if n>1 then
for k from 2 to n
do p:=p*k; od;
fi;
p;
end proc:


Аналогичная рекурсивная процедура:

F2:=proc(n)
F2(1):=1;
if n>1 then F2(n-1)*n; fi;
end proc;


Сравнение времени вычисления 20000! :

st:= time(): F1(20000): time() - st;
0.843

st:= time(): F2(20000): time() - st;
1.216

Переписал свою процедуру P, сделав её циклической P1. Работать стала несколько быстрее.

P1:=proc(R, N, M)
local A,B,Q,k;
A:=[seq(evalf[3](sin(Pi*m/M)),m=1..M-1)];
B:=[seq(evalf[3](cos(Pi*m/M)),m=1..M-1)];
Q:=[seq([R*evalf[3](cos(Pi*k/M)),R*evalf[3](sin(Pi*k/M))],k=0..2*M-1)];
if N>1 then
for k from 2 to N do Q:=[[seq(0,j=1..k),1],seq(seq(evalf[3]([op(A[m]*Q[n]),R*B[m]]),n=1..nops(Q)),m=1..M-1),[seq(0,j=1..k),-1]]; od;
fi;
end proc:


Время работы при разных N:

st:= time(): (P1(1,2,20)): time() - st;
0.

st:= time(): (P1(1,3,20)): time() - st;
0.172

st:= time(): (P1(1,4,20)): time() - st;
4.493

st:= time(): (P1(1,5,20)): time() - st;
183.270

Видим, что пятимерная сфера обсчитывается около 3 минут (раньше - 4 минут).

алексей_алексей
Сообщения: 1776
Зарегистрирован: Вс май 01, 2005 9:02 pm

Сообщение алексей_алексей » Пт окт 07, 2011 10:13 pm

В справку иногда заглядываю… откуда человек знает, что существует такая конструкция: for k from 2 to N do Q:=[[seq(0,j=1..k),1],seq(seq(evalf[3]([op(A[m]*Q[n]),R*B[m]]),n=1..nops(Q)),m=1..M-1),[seq(0,j=1..k),-1]]; od; особенно это место:… [seq(0,j=1..k),1]… или …[seq(0,j=1..k),-1]...?

--------------------------------------------------------------------------------------------------------------
C Математикой не посоревнуешься. Набрался терпения, заставив её решить несколько СНАУ 9-го порядка. Таки решила. Здесь со сферой ловить, похоже, нечего хотя бы из-за скорости. Но Математика не очень справляется, когда её просят решить ту же систему, но уже после изъятия одного или нескольких уравнений и пытается добавить в систему уравнения каких-то плоскостей до ровного счёта. Мягко говоря, она к таким численным решениям ещё не готова. Выходит, поле деятельности для предлагаемого алгоритма имеется…

uni
Сообщения: 1817
Зарегистрирован: Сб ноя 13, 2004 3:06 pm
Откуда: п.г.т. Излучинск
Контактная информация:

Сообщение uni » Сб окт 08, 2011 1:45 am

Kitonum, тут не всё так просто и не надо спешить с выводами. Полноценное понимание процессов, происходящих при работе алгоритма даёт только полное профилирование, где будет указано какие части кода какое время в процентах занимают в общем времени на разных типах данных в разных режимах. Конечно, всё это ещё зависит и от алгоритма, который исследуется.
Дело в том, что указанное вами правило - это теоретическое правило, на практике же дела обстоят по-разному. Компьютер - это не идеальная машина, у неё есть операционная система и конкретно заданные технические харакеристики + объём памяти. Один и тот же алгоритм на разных машинах может вести себя по-разному. При больших объёмах перемалываемых данных ОС вынуждена тратить время (если программист не позаботился о выделении памяти заранее) на переразмещение (копирование) массивов в памяти. Поскольку виртуальная память большей своей частью физически размещается на винте, то тормоза при обращении в жёсткому диску внесут очень большой вклад во время работы алгоритма. И это будут достаточно тупые потери, связанные с программной реализацией.

Я потому и делаю деление на тело цикла - это как правило почти чистое время работы CPU и работа с памятью. Если тело цикла небольшое и размеры массивов невелики, то разницы мы не почувствуем. А дальше уже всё зависит от соотношения между временем выполнения тела цикла и временем работы с памятью, при рекурсии есть дополнительные задержки рекурсивного вызова, т.к. рекурсия основана на стеке и нужно постоянно делать push|pop операции на каждой итерации.

Это, вообще говоря, целые исследования по оптимизации программ. Простые примеры типа факториала или чисел Фибоначчи не дают прочувствовать картины как она бывает на практике.

Когда считаете время при работе с большими массивами, то нужно разделять потери на непосредственное вычисление от потерь при работе с памятью. Иначе можно не правильно оценивать эффективность алгоритма. Нужно знать устройство ОС, знать сколько реальной физической памяти отведено под пользовательские приложения, сколько места занимает конкретный тип в СКМ, сколько места займёт массив в наихудшем варианте вычислений. Если размер массива превысит реально доступный физический объём ОЗУ выделенный для текущего процесса, то ОС скинет этот массив на винт и дальше уже будет совсем другая история.

Чтобы обо всём этом не думать народ наращивает мощность CPU, их ядрёность и объём RAM. Потом вычислительные кластеры, параллельные вычисления и т.д.

Kitonum
Сообщения: 2084
Зарегистрирован: Ср дек 31, 2008 1:55 pm
Откуда: г. Пенза

Сообщение Kitonum » Сб окт 08, 2011 7:40 pm

Уважаемый г-н uni! Большое спасибо за подробные разъяснения. Только хотелось бы чуть больше конкретики. Если Вы не вполне согласны с теми простыми рекомендациями, о которых я писал выше, приведите конкретный опровергающий пример! Всё-таки это форум по практической работе в Maple, а не по теоретическим вопросам программирования вообще...

uni
Сообщения: 1817
Зарегистрирован: Сб ноя 13, 2004 3:06 pm
Откуда: п.г.т. Излучинск
Контактная информация:

Сообщение uni » Сб окт 08, 2011 8:35 pm

Ну, во-первых, господа, как известно, "все в Париже" (с).

Во-вторых, мне откровенно лень было подробно разбирать ваш код, т.к. он плохо оформлен, о чём я писал пару страниц назад. Плохо оформлен - это означает:
1) Отсутствует структурирование на блоки;
2) Отсутствует форматирование вообще;
3) В коде напрочь остутствуют комментарии.
4) Читать: Макконнел "Совершенный код", скачать можно на bookfi.org
(это конкретика, как просили, ваш код не профессиональный в этом смысле, т.е. не предназначен для совместной разработки в команде (со мной в том числе))

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

Что же касается конкретики по поводу оптимизации после профилирования, то я не такой знаток Maple, чтобы на нём это продемонстрировать. Поищите в пакете, там должны быть специальные инструменты, которые так и называются: Profiler - профилировщик кода. Это либо набор функций, либо специальные средства среды. Если такой набор есть, то там будет и конкретика в виде примеров как им пользоваться. Фукция time() - это всего лишь небольшой инструмент, который должен использоваться в комплексе.

Сам я разрабатываю встраиваемые приложения, т.е. пишу программки для микроконтроллеров, где мне этим "профилированием" приходиться заниматься постоянно, причём во многих смыслах: размер кода, размер переменных в ОЗУ, время выполнения, размер стека, скорость работы и т.д.
Точность до микросекунд и до байта (иногда и до бита). В мире ПК условия другие, но отличие не так велики как могло бы показаться.

И ещё, когда я писал, что это целое исследование - нужно было понимать меня буквально. В журналах по программированию - это целые статьи, кучи графиков и разные примеры кода. Начинать нужно с устройства ОС Windows. Если у вас физически 4 Гб ОЗУ, к примеру, то это вовсе не означает, что все 4 Гб используется приложением. Это пространство квантовано системой на части и только некоторая часть из физической памяти реально доступна приложению. Остальная память эмулируется ОС за счёт пространства на жёстком диске. Скорость доступа к такой "ОЗУ" при этом заметно падает.
Учитывая ваши способности к программированию, вы и сами можете промоделировать такую ситуацию в Maple. Завалить работой при помощи СКМ можно любой комп всего парой строчек. К примеру, та же обработка больших изображений и вообще работа с большими файлами. У любого человека, который сталкивается с массивами, размерами с ОЗУ или близкими к этому, возникает проблема: а как работать с этим эффективно? Специально для этих целей в Windows есть "файлы отображаемые в память", когда лежащий на диске гигабайтный файл мы проецируем в доступное нам физической пространство ОЗУ частями и так небольшими кусочками проходим по всему файлу.

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