3
$\begingroup$

There's probably a Mathematica primitive to do this, but I don't know what it is...suppose I wanted to construct a list of all integers from $1$ to $n$ that were not divisible by $12$, and that were not squares. One way to do this is

Select[Table[i,{i,Range[n]}], Mod[#,12]!=0 && !IntegerQ[Sqrt@#]&]

(I'm not so much interested in the particular condition as in the method here; the condition could be arbitrarily simple or complicated.) The method above requires that the entire list be constructed, when all I care about is a potentially small subset of that list. Is there an efficient (by which I mean: more efficient in memory, roughly at least as efficient in CPU) to do this without constructing a list consisting of the entire universe?

$\endgroup$
13
$\begingroup$

What you face here is that you don't know how many values your result will have. There are two methods, that come instantly to my mind: The first one is to use Reap and Sow with a simple Do loop

n = 20;
Reap[Do[
   If[Mod[i, 12] != 0 && ! IntegerQ[Sqrt[i]],
    Sow[i]
    ], {i, n}]
  ][[2, 1]]
(* {2, 3, 5, 6, 7, 8, 10, 11, 13, 14, 15, 17, 18, 19, 20} *)

What happens is that the do-loop itself just iterates through your range and when it hits a value that fulfills your condition, it sows the value. All those values are reaped. This should be very efficient.

Another method is to construct nested lists. With this method, you can append values without really appending to a particular list which probably needs copying to get more memory. So let's say you have already some values collected in result and you hit another value you want to collect, then you store result = {result,value}.

Module[{result = {}},
 Do[
  If[Mod[i, 12] != 0 && ! IntegerQ[Sqrt[i]],
   result = {result, i};
   ], {i, n}];
 Flatten[result]
]

When you now look at the timings for these methods compared to your approach, then you'll find that they run about equally long: For n=10^6 I get here 7.9s, 8.2s and 7.8s where the first timing is your approach.

When I compare the memory before and after (always on a fresh kernel!), then one sees the differences. I used the following code, where I only calculated the length of the filtered lists:

m1 = MemoryInUse[];
Length[Select[Table[i, {i, Range[n]}], 
   Mod[#, 12] != 0 && ! IntegerQ[Sqrt@#] &]] // AbsoluteTiming
MemoryInUse[] - m1

Here I get the following byte-count: 4.220.984, 68.224, 68.224 so your approach needs about 60x the memory of the two I presented here.


Edit

Let me make a short statement in reply of your comment:

I guess it's unreasonable to hope for a method that is substantially more time-efficient. In the end, you have to examine each value in the range to determine if it fulfills the condition. Sigh.

Yes. In general, yes. Now people will cry why we don't parallelize the algorithm. Well, because then you loose some of the memory efficiency. We have two extreme situations when, like in your case, the membership of the resulting element or the calculation of a result depends only on a single element of the input list:

  1. Iterate through the input list and calculate the result for each element bit by bit. The memory you need does not depend on the length of your input list and since you need only them memory of the current element plus some temporary stuff for the calculation, this approach is very memory efficient.

  2. Take the complete input list into the memory. Now, you are free to calculate all resulting elements in parallel. This needs (at least) the memory for the input list you have already wasted, plus the memory which is needed for the calculation of every resulting element (better: the number of calculations that run in parallel). Clearly the overall memory required depends on the length of your input data. On the other hand, you can be extremely fast.

Let me give you an example: I rewrote the last part of your condition so that it can be compiled, because IntegerQ is not available for compiled code. The compiled function gets any i and returns True or False to indicate whether or not i is element of your output list

fc = Compile[{{i, _Integer, 0}},
  With[{sqrt = Sqrt[i]},
   Mod[i, 12] != 0 && Not[Round[sqrt] == sqrt]
   ],
  Parallelization -> True, RuntimeAttributes -> {Listable}
]

Now, I use this function and your input list r of the numbers 1...10^6 and calculate which element is included in your result list. Then I use Pick to pick all correct elements:

AbsoluteTiming[
 With[{r = Range[n]},
   Pick[r, fc[r]]] // Length
 ]

This does take 0.12s here. Your and my memory efficient approaches need about 65x as long for the same calculation.

What we have here is the black and the white of possible approaches to tackle your problem. My first solutions are memory optimized, the compiled code above is speed optimized. But as we know the world is not black and white, it's mostly pink and therefore:

When you know your specific problem, then you probably can choose an approach that is a variation between those two worlds and you get some advantages from both.

Let me give a small example. Assume you know that you have the memory to calculate 10^5 elements in parallel. Furthermore, you are only interested in the number of elements in your resulting list and not in the list itself. A straight forward way to calculate this without looking at the memory is

AbsoluteTiming[Count[Range[10^6], _?(Mod[#, 12] != 0 && ! IntegerQ[Sqrt[#]] &)]]
(* {8.193399, 915833} *)

It needs approximately the same time as your initial Select. Now, you think that to calculate 10^6 elements, you could divide this whole range into sub-ranges:

ranges = Table[{i - 1, i}*10^5 + {1, 0}, {i, 10}]
(* {{1, 100000}, {100001, 200000}, {200001, 300000}, {300001, 
  400000}, {400001, 500000}, {500001, 600000}, {600001, 
  700000}, {700001, 800000}, {800001, 900000}, {900001, 1000000}} *)

The next step is then to iterate over these ranges and calculate the result e.g. of the numbers from 100001...200000 in parallel. Then you simple add the number of positive elements to your resulting sum:

sum = 0;
Do[
  sum += Plus @@ fc[Range @@ r],
  {r, ranges}
  ];
sum
(* 915833 *)

On my machine this needs about 0.2s which is so fast, that I was not afraid to try it for 10^8 elements. This needs about 12s here. If you want, you can try to calculate this with Count.

Be aware that this was only a small example. Whether or not you can use it depends on your specific problem.

$\endgroup$
  • $\begingroup$ I guess it's unreasonable to hope for a method that is substantially more time-efficient. In the end, you have to examine each value in the range to determine if it fulfills the condition. Sigh. $\endgroup$ – rogerl Dec 29 '14 at 1:52
  • $\begingroup$ @rogerl See my update $\endgroup$ – halirutan Dec 29 '14 at 3:06
  • $\begingroup$ @halirutan +1, but see if my answer achieves both goals of speed and memory reasonably well, although it's a little slower than your fc/Pick version. -- Nice answer, though, especially the discussion of the factors in choosing an algorithm for this type of problem. $\endgroup$ – Michael E2 Dec 29 '14 at 3:16
  • $\begingroup$ Great answers, and more detail and analysis than I had any right to expect! $\endgroup$ – rogerl Dec 29 '14 at 14:34
7
$\begingroup$

This is an extended comment to halirutan's answer. I think you can get both speed and memory optimization for this problem. I made this a CW post because I used his code in his Q&A, Internal`Bag inside Compile, to remind myself how to use Internal`Bag, as well as some of his code from his answer to this question!

myInts = Compile[{{n, _Integer}},
  Module[{i, list = Internal`Bag[Most[{0}]]},
   Do[
    If[With[{sqrt = Sqrt[i]}, 
      Mod[i, 12] != 0 && Not[Round[sqrt] == sqrt]], 
     Internal`StuffBag[list, i]],
    {i, n}];
   Internal`BagPart[list, All]]];

myInts[10^6]; // AbsoluteTiming
(*  0.271917  *)
$\endgroup$
  • $\begingroup$ Now that's stealing with class ;) +1 $\endgroup$ – Dr. belisarius Dec 29 '14 at 3:06
  • $\begingroup$ +1 And you shouldn't have made it CW. One drawback here is that this approach will only work for machine integers (or machine types). The part that makes your answer so valuable is that it clearly shows how optimized Bag is if it works on those primitive types. The same code without compile is not really faster than nested lists or reap and sow.. $\endgroup$ – halirutan Dec 29 '14 at 3:30
0
$\begingroup$

I have some idea for you which could help:

f[n_] := Complement[Range[n], 
  12 Range[Ceiling[n/12]], (Range[Ceiling[Sqrt[n]]])^2];

I have tested this and compared the result with your method and here is what I have got:

f2[n_] := 
  Select[Table[i, {i, Range[n]}], 
   Mod[#, 12] != 0 && ! IntegerQ[Sqrt@#] &];

a = 10^7;
Timing[res1 = f[a];]
Timing[res2 = f2[a];]
res1 === res2


(*{0.171875, Null}*)

(*{98.500000, Null}*)

(*True*)

Now I am not sure how to test this for Memory issue.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.