как написать код этой программы специально на математике?

Я реализовал решение приведенной ниже проблемы в Mathematica, но для вычисления f из ki или множества B для больших чисел требуется очень много времени (часы).

Кто-то предположил, что реализация этого на C++ привела к решению менее чем за 10 минут. Будет ли C++ подходящим языком для решения этих проблем, или мой код Mathematica можно улучшить, чтобы исправить проблемы с производительностью?

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

Описание проблемы

Пусть $f$ — арифметическая функция, а A={k1,k2,...,kn} — целые числа в порядке возрастания.

Теперь я хочу начать с k1 и сравнить f(ki) с f(k1). Если f(ki)>f(k1), поставьте ki как k1.

Теперь начните с ki и сравните f(kj) с f(ki) для j>i. Если f(kj)>f(ki), поставьте kj как ki и повторите эту процедуру.

В конце у нас будет подпоследовательность B={L1,...,Lm} последовательности A по этому свойству: f(L(i+1))>f(L(i)), для любого 1‹=i ‹=м-1

Например, пусть f — функция делителя целых чисел.

Здесь я помещаю часть своего кода, и это всего лишь пример, и вопрос в моей программе может быть больше, чем эти:

««««««««««««««««««««««««««««««««««««

f[n_] := DivisorSigma[0, n];

g[n_] := Product[Prime[i], {i, 1, PrimePi[n]}];


k1 = g[67757] g[353] g[59] g[19] g[11] g[7] g[5]^2 6^3 2^7;

k2 = g[67757] g[353] g[59] g[19] g[11] g[7] g[5] 6^5 2^7;

k3 = g[67757] g[359] g[53] g[19] g[11] g[7] g[5] 6^4 2^7;

k4 = g[67759] g[349] g[53] g[19] g[11] g[7] g[5] 6^5 2^6;

k5 = g[67757] g[359] g[53] g[19] g[11] g[7] g[5] 6^4 2^8;

k6 = g[67759] g[349] g[53] g[19] g[11] g[7] g[5]^2 6^3 2^7;

k7 = g[67757] g[359] g[53] g[19] g[11] g[7] g[5] 6^5 2^6;

k8 = g[67757] g[359] g[53] g[19] g[11] g[7] g[5] 6^4 2^9;

k9 = g[67757] g[359] g[53] g[19] g[11] g[7] g[5]^2 6^3 2^7;

k10 = g[67757] g[359] g[53] g[19] g[11] g[7] g[5] 6^5 2^7;

k11 = g[67759] g[349] g[53] g[19] g[11] g[7] g[5]^2 6^4 2^6;

k12 = g[67757] g[359] g[53] g[19] g[11] g[7] g[5]^2 6^3 2^8;

k13 = g[67757] g[359] g[53] g[19] g[11] g[7] g[5]^2 6^4 2^6;

k14 = g[67757] g[359] g[53] g[19] g[11] g[7] g[5]^2 6^3 2^9;

k15 = g[67757] g[359] g[53] g[19] g[11] g[7] g[5]^2 6^4 2^7;

k16 = g[67757] g[359] g[53] g[23] g[11] g[7] g[5] 6^4 2^8;

k17 = g[67757] g[359] g[59] g[19] g[11] g[7] g[5] 6^4 2^7;

k18 = g[67757] g[359] g[53] g[23] g[11] g[7] g[5] 6^4 2^9;

k19 = g[67759] g[353] g[53] g[19] g[11] g[7] g[5] 6^4 2^6;

k20 = g[67763] g[347] g[53] g[19] g[11] g[7] g[5] 6^4 2^7;

k = Table[k1, k2, k3, k4, k5, k6, k7, k8, k9, k10, k11, k12, k13, k14, k15, k16, k17, k18, k19, k20];

i = 1;

count = 0;

For[j = i, j <= 20, j++, 
  If[f[k[[j]]] - f[k[[i]]] > 0, i = j; Print["k",i];
   count = count + 1]];

Print["count= ", count]

««««««««««««««««««

результат:

k2

k5

k7

k8

k9

k10

k12

k13

k14

k15

k16

k17

k18

количество = 13

««««««««««««««««««««««««««««««««««««

wolfram-mathematica
person asd    schedule 28.01.2011    source источник
comment
Похоже, у вас проблемы с производительностью в существующей реализации. Я предлагаю вам опубликовать свой существующий код на StackOverflow.com и запросить предложения по его улучшению. Это своего рода вопрос, который принадлежит там, а не здесь.   -  person Adam Lear    schedule 28.01.2011
comment
Я попытался отредактировать вопрос, чтобы сделать его более понятным и читабельным. Я все еще думаю, что его следует перенести на SO, но у него может быть больше шансов выжить в этой форме. Не стесняйтесь вернуться, если мои правки вредны.   -  person Adam Lear    schedule 28.01.2011
comment
Реализация того же алгоритма на C++ вряд ли будет быстрее. Mathematica уже довольно быстра.   -  person devoured elysium    schedule 28.01.2011
comment
Ваше использование Table[...] неверно; вы хотите Список [k1, k2...]   -  person Tim    schedule 28.01.2011
comment
Не могли бы вы немного объяснить, чего вы пытаетесь достичь? Ваши примеры функций кажутся немного странными. Это настоящие те, с которыми вы имеете дело?   -  person Dr. belisarius    schedule 29.01.2011
comment
возможный дубликат Вычислить арифметические функции для больших целых чисел в Mathematica быстрее?   -  person Dr. belisarius    schedule 29.01.2011
comment
Я поставил результат для этого кода. Также о дублировании, да, я разместил это на этом сайте, и оно перенесено отсюда programmers.stackexchange.com   -  person asd    schedule 29.01.2011

Ответы (1)


arrow_upward
2
arrow_downward

Большая часть времени в вашем коде тратится на DivisorSigma, потому что он должен учитывать ваши целые числа. Но это нужно только учитывать их, потому что вы уже перемножили их вместе и потеряли информацию.

Но немедленное решение вашей проблемы заключается в предварительном вычислении f[k[[i]]].

k = List[k1, k2, k3, k4, k5, k6, k7, k8, k9, k10, k11, k12, k13, k14, 
   k15, k16, k17, k18, k19, k20];
fk = ParallelMap[f, k]; (* precompute *)

i = 1;
count = 0;
For[j = i, j <= 20, j++, 
  If[fk[[j]] - fk[[i]] > 0, i = j; Print["k", i];
   count = count + 1]];
Print["count= ", count]
person Sasha    schedule 28.01.2011