Мастера DELPHI, Delphi programming community Рейтинг@Mail.ru Титульная страница Поиск, карта сайта Написать письмо 
| Новости |
Новости сайта
Поиск |
Поиск по лучшим сайтам о Delphi
FAQ |
Огромная база часто задаваемых вопросов и, конечно же, ответы к ним ;)
Статьи |
Подборка статей на самые разные темы. Все о DELPHI
Книги |
Новинки книжного рынка
Новости VCL
Обзор свежих компонент со всего мира, по-русски!
|
| Форумы
Здесь вы можете задать свой вопрос и наверняка получите ответ
| ЧАТ |
Место для общения :)
Орешник |
Коллекция курьезных вопросов из форумов
KOL и MCK |
KOL и MCK - Компактные программы на Delphi
Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / rsdn.org

 
Чтобы не потерять эту дискуссию, сделайте закладку « предыдущая ветвь | форум | следующая ветвь »
Страницы: 1 2

Количество разбиений на слагаемые?


xayam ©   (01.07.18 07:16[20]


> а сколько равных только единице непонятно

хотя по идее почти все симметрично и их ровно n!/2-1
минус один так как единичная матрица (все единицы на диагоналях) не имеет симметричного представления


xayam ©   (01.07.18 07:22[21]


> хотя по идее почти все симметрично и их ровно n!/2-1

опс точнее (n!-1)/2
но это только если n нечетно.
Если же n четно то непонятно.


Sha ©   (01.07.18 11:06[22]

>xayam ©   (01.07.18 06:50) [16]
>чего-то больно большие числа выдает алгоритм.

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

Можно выполнить компьютерную имитацию,
составить таблицы значений и потом сравнить.

Можно все это проделать намного быстрее, если отказаться от рекурсии:
function xayam5(Max, Sum, Count: integer): integer;
var
 a, b: array of array of integer;
 p: pointer;
 m, s, k, i, v: integer;
begin;
 Result:=0;
 if (Count<=0) or (Sum<=0) or (Max<=0) then exit;

 if Max>Sum then Max:=Sum;
 SetLength(a,1+Sum,1+Max);
 SetLength(b,1+Sum,1+Max);
 for s:=0 to Sum do for m:=0 to Max do b[s,m]:=0;
 for m:=1 to Max do b[m, m]:=1;
 for k:=2 to Count do begin;
   p:=pointer(a); pointer(a):=pointer(b); pointer(b):=p;
   for s:=0 to Sum do for m:=0 to Max do b[s,m]:=0;
   for s:=k to Sum do begin;
     i:=s; if i>Max then i:=Max;
     for m:=1 to i do begin;
       v:=0;
       for i:=1 to m-1 do v:=v+a[s-m,i];
       b[s,m]:=v;
       end;
     end;
   end;

 for i:=1 to Max do Result:=Result+b[Sum, i];
 end;


Можно все это проделать до запредельных значений,
если поменять тип результата на int64.

Было бы желание.


Mystic ©   (03.07.18 09:20[23]

Кешировать надо, у вас много повторений (ИМХО). Например, если рассмотреть 64, 61, а потом 63, 62, то при Max <= 60 у нас будут абсолютно идентичное количество, которое вы честно будете считать два раза. Так что лучше иметь массив 260x64x8, куда записывать уже вычисленные результаты (133k элементов).

Вообще, такой массив хочется заполнять снизу а не сверху, чтобы избежать проверок, а вычислено ли.


Sha ©   (03.07.18 10:20[24]

> Mystic ©   (03.07.18 09:20) [23]

... а вот это попробуйте )


Mystic ©   (03.07.18 13:07[25]

Попробовал сильно не вникая в оптимизацию

#include <stdint.h>
#include <stdio.h>
#include <string.h>

#define N 8
#define SUM 260
#define MAX 64

uint64_t cache[N][SUM+1][MAX+1];

uint64_t phi(void)
{
   /* No variants if MAX = 0 */
   for (uint64_t n=0; n<N; ++n)
   for (uint64_t sum=0; sum <= SUM; ++sum) {
       cache[n][sum][0] = 0;
   }  
   
   /* Fill data for N = 1 */
   for (uint64_t max = 1; max <= MAX; ++max)
   for (uint64_t sum = 1; sum <= SUM; ++sum) {
       cache[0][sum][max] = sum <= max;
   }  
   
   /* Calculate everything */
   for (uint64_t n=1; n<N; ++n)
   for (uint64_t max=1; max <= MAX; ++max)
   for (uint64_t sum=1; sum <= SUM; ++sum) {
       const uint64_t qinclude = sum > max ? cache[n-1][sum-max][max-1] : 0;
       const uint64_t qmiss = cache[n][sum][max-1];
       cache[n][sum][max] = qinclude + qmiss;
   }  
   
   return cache[N-1][SUM][MAX];
}

int main()
{
   printf("phi(%d, %d, %d) = %lu\n", N, SUM, MAX, phi());
   return 0;
}


$ gcc xayam.c -o xayam && time ./xayam
phi(8, 260, 64) = 35154340

real 0m0.001s
user 0m0.001s
sys 0m0.000s


Mystic ©   (03.07.18 13:08[26]

Угадал с ответом?


Mystic ©   (03.07.18 14:03[27]

http://tpcg.io/yM0RNx


Sha ©   (03.07.18 14:27[28]

> Mystic ©   (03.07.18 13:08) [26]
> Угадал с ответом?

Да, ответ верный и время совпадает.

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


Mystic ©   (03.07.18 16:37[29]

А почему время совпадает?


> Еще немного быстрее (1.25 сек на i7-7700)


У меня же получилось 0.001 секунды, при том, что

$ cat /proc/cpuinfo | grep 'model name' | head -1
model name : Intel(R) Core(TM) i3-4160 CPU @ 3.60GHz


Mystic ©   (03.07.18 16:50[30]

У меня такое чувство, что мы скорее упрёмся в производительность процессора, чем в память.

У моём примере используется 1085760 byte памяти (мегабайт).

Если увеличить все параметры в пять раз, а max в 50, мы получим

$ gcc xayam.c -o xayam && time ./xayam
sz = 1 332 640 320
phi(40, 1300, 3200) = 6 182 872 580 981 006 930

real 0m2.192s
user 0m1.903s
sys 0m0.288s


Т. е. надо около гигабайта памяти и почти переполнение типа uint64_t (30% от MAX_UINT64).


Sha ©   (03.07.18 17:02[31]

> Mystic ©   (03.07.18 16:37) [29]
> А почему время совпадает?

Это [15], которая с рекурсией, работает больше секунды.
А время [22], которая без рекурсии, тоже 0 ms.

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


Sha ©   (03.07.18 17:48[32]

> Mystic ©   (03.07.18 16:50) [30]
> Если увеличить все параметры в пять раз, а max в 50, мы получим

При таких размерах кеш сумм будет очень полезен.

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


Страницы: 1 2 версия для печати

Написать ответ

Ваше имя (регистрация  E-mail 







Разрешается использование тегов форматирования текста:
<b>жирный</b> <i>наклонный</i> <u>подчеркнутый</u>,
а для выделения текста программ, используйте <code> ... </code>
и не забывайте закрывать теги! </b></i></u></code> :)


Наверх

  Рейтинг@Mail.ru     Титульная страница Поиск, карта сайта Написать письмо