Создайте список в Mathematica с условным тестированием для каждого элемента - PullRequest
12 голосов
/ 16 июня 2011

Предположим, мы хотим создать список простых чисел p , для которых p + 2 также простое число.

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

Select[Table[Prime[k], {k, n}], PrimeQ[# + 2] &]

Однако это неэффективно, так как загружает большой список в память перед возвратомотфильтрованный список.Цикл For с Sow / Reap (или l = {}; AppendTo[l, k]) решает проблему с памятью, но это далеко не элегантно и неудобно для реализации несколько раз в сценарии Mathematica.

Reap[
  For[k = 1, k <= n, k++,
   p = Prime[k];
   If[PrimeQ[p + 2], Sow[p]]
  ]
 ][[-1, 1]]

Идеальное решениебудет встроенная функция, которая позволяет вариант, подобный этому.

Table[Prime[k], {k, n}, AddIf -> PrimeQ[# + 2] &]

Ответы [ 6 ]

18 голосов
/ 16 июня 2011

Я буду толковать это больше как вопрос об автоматизации и разработке программного обеспечения, а не о конкретной проблеме, с учетом большого количества уже опубликованных решений.Reap и Sow являются хорошими средствами (возможно, лучшими в символической настройке) для сбора промежуточных результатов.Давайте сделаем это вообще, чтобы избежать дублирования кода.

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

Clear[tableGen];
tableGen[f_, iter : {i_Symbol, __}, addif : Except[_List] : (True &)] :=
 Module[{sowTag},   
  If[# === {}, #, First@#] &@
       Last@Reap[Do[If[addif[#], Sow[#,sowTag]] &[f[i]], iter],sowTag]];

Преимущества использования Do над For в том, что переменная цикла локализуется динамически (таким образом, глобальные модификации для него не входят в область действия Do), а также синтаксис итератора Do ближе к синтаксису Table (Do также немного быстрее).

Теперь, здесь используется

In[56]:= tableGen[Prime, {i, 10}, PrimeQ[# + 2] &]

Out[56]= {3, 5, 11, 17, 29}

In[57]:= tableGen[Prime, {i, 3, 10}, PrimeQ[# + 1] &]

Out[57]= {}

In[58]:= tableGen[Prime, {i, 10}]

Out[58]= {2, 3, 5, 7, 11, 13, 17, 19, 23, 29}

РЕДАКТИРОВАТЬ

Эта версия ближе к синтаксису, который вы упомянули (он принимает выражение, а не функцию):

ClearAll[tableGenAlt];
SetAttributes[tableGenAlt, HoldAll];
tableGenAlt[expr_, iter_List, addif : Except[_List] : (True &)] :=
 Module[{sowTag}, 
  If[# === {}, #, First@#] &@
    Last@Reap[Do[If[addif[#], Sow[#,sowTag]] &[expr], iter],sowTag]];

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

In[65]:= tableGenAlt[Prime[i], {i, 10}, PrimeQ[# + 2] &]

Out[65]= {3, 5, 11, 17, 29}

In[68]:= tableGenAlt[Prime[i], {i, 10}]

Out[68]= {2, 3, 5, 7, 11, 13, 17, 19, 23, 29}

Обратите внимание, что поскольку синтаксис теперь другой, нам пришлось использовать атрибут Hold, чтобы предотвратить преждевременную оценку переданного выражения expr.

РЕДАКТИРОВАТЬ 2

В соответствии с запросом @ Саймона, здесь обобщение для многих измерений:

ClearAll[tableGenAltMD];
SetAttributes[tableGenAltMD, HoldAll];
tableGenAltMD[expr_, iter__List, addif : Except[_List] : (True &)] :=
Module[{indices, indexedRes, sowTag},
  SetDelayed @@  Prepend[Thread[Map[Take[#, 1] &, List @@ Hold @@@ Hold[iter]], 
      Hold], indices];
  indexedRes = 
    If[# === {}, #, First@#] &@
      Last@Reap[Do[If[addif[#], Sow[{#, indices},sowTag]] &[expr], iter],sowTag];
  Map[
    First, 
    SplitBy[indexedRes , 
      Table[With[{i = i}, Function[Slot[1][[2, i]]]], {i,Length[Hold[iter]] - 1}]], 
    {-3}]];

Это значительно менее тривиально, поскольку мне пришлось Sowиндексы вместе с добавленными значениями, а затем разбить получившийся плоский список в соответствии с индексами.Вот пример использования:

{i, j, k} = {1, 2, 3};
tableGenAltMD[i + j + k, {i, 1, 5}, {j, 1, 3}, {k, 1, 2}, # < 7 &]

{{{3, 4}, {4, 5}, {5, 6}}, {{4, 5}, {5, 6}, {6}}, {{5, 6}, {6}}, {{6}}}

Я присвоил значения i,j,k переменным итератора, чтобы проиллюстрировать, что эта функция локализует переменные итератора и нечувствительна к возможным глобальным значениям для них.Чтобы проверить результат, мы можем использовать Table, а затем удалить элементы, не удовлетворяющие условию:

In[126]:= 
DeleteCases[Table[i + j + k, {i, 1, 5}, {j, 1, 3}, {k, 1, 2}], 
    x_Integer /; x >= 7, Infinity] //. {} :> Sequence[]

Out[126]= {{{3, 4}, {4, 5}, {5, 6}}, {{4, 5}, {5, 6}, {6}}, {{5, 6}, {6}}, {{6}}}

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

РЕДАКТИРОВАТЬ 3 - ИСПРАВЛЕНИЕ ОШИБКИ

Обратите внимание на важное исправление ошибки: во всех функциях теперь я использую Sow с пользовательским уникальным тегом и Reap также.Без этого изменения функции не будут работать должным образом, когда вычисляемое выражение также использует Sow.Это общая ситуация с Reap - Sow, и она напоминает ситуацию для исключений (Throw - Catch).

EDIT 4 - SyntaxInformation

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

SyntaxInformation[tableGenAltMD] = {"ArgumentsPattern" -> {_, {_, _, _., _.}.., _.},
                                    "LocalVariables" -> {"Table", {2, -2}}};

Затем добавление сообщения об использовании позволяет пункту меню «Создать шаблон» (Shift+Ctrl+k) работать:

tableGenAltMD::usage = "tableGenAltMD[expr,{i,imax},addif] will generate \
a list of values expr when i runs from 1 to imax, \
only including elements if addif[expr] returns true.
The default of addiff is True&."

Более полное и отформатированное сообщение об использовании можно найти в этом гисте .

2 голосов
/ 16 июня 2011

Возможно, вы можете попробовать что-то вроде этого:

Clear[f, primesList]
f = With[{p = Prime[#]},Piecewise[{{p, PrimeQ[p + 2]}}, {}] ] &;
primesList[k_] := Union@Flatten@(f /@ Range[k]);

Если вы хотите и простое p, и простое p+2, тогда решение будет

Clear[f, primesList]
f = With[{p = Prime[#]},Piecewise[{{p, PrimeQ[p + 2]}}, {}] ] &;
primesList[k_] := 
  Module[{primes = f /@ Range[k]}, 
   Union@Flatten@{primes, primes + 2}];
2 голосов
/ 16 июня 2011

Да, это другой ответ. Другой альтернативой, которая включает в себя разновидность подхода Reap / Sow и подхода FoldList, было бы использование Scan.

result = {1};
Scan[With[{p=Prime[#]},If[PrimeQ[p+2],result={result,p}]]&,Range[2,K] ];
Flatten[result]

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

2 голосов
/ 16 июня 2011

Я думаю, что подход Reap / Sow, вероятно, будет наиболее эффективным с точки зрения использования памяти. Некоторые альтернативы могут быть:

DeleteCases[(With[{p=Prime[#]},If[PrimeQ[p+2],p,{}] ] ) & /@ Range[K]),_List]

Или (для исключения результатов Null может потребоваться какой-то DeleteCases):

FoldList[[(With[{p=Prime[#2]},If[PrimeQ[p+2],p] ] )& ,1.,Range[2,K] ]

Оба хранят в памяти большой список целых чисел от 1 до K, но простые числа ограничены внутри конструкции With [].

1 голос
/ 16 июня 2011

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

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

x=Table[0,{100}];  (*allocate maximum possible*)
j=0;
Table[ If[PrimeQ[k+2], x[[++j]]=k],{k,100}];

x[[1;;j]]  (*the result is here *)

{1,3,5,9,11,15,17,21,27,29,35,39,41,45,51,57,59,65,69,71,77,81,87,95,99}
0 голосов
/ 16 июня 2011

Вот еще пара альтернатив, использующих NextPrime:

pairs1[pmax_] := Select[Range[pmax], PrimeQ[#] && NextPrime[#] == 2 + # &]

pairs2[pnum_] := Module[{p}, NestList[(p = NextPrime[#];
                      While[p + 2 != (p = NextPrime[p])]; 
                      p - 2) &, 3, pnum]] 

и модификация вашего решения Reap / Sow, позволяющая указать максимальное простое число:

pairs3[pmax_] := Module[{k,p},
                   Reap[For[k = 1, (p = Prime[k]) <= pmax, k++,
                        If[PrimeQ[p + 2], Sow[p]]]][[-1, 1]]]

Выше приведен порядок увеличения скорости.

In[4]:= pairs2[10000]//Last//Timing
Out[4]= {3.48,1261079}
In[5]:= pairs1[1261079]//Last//Timing
Out[5]= {6.84,1261079}
In[6]:= pairs3[1261079]//Last//Timing
Out[7]= {0.58,1261079}
Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...