2
$\begingroup$


I have sample code:

Block[{n=100000,w,z},
 {
  z = {}; While[!MemberQ[z, w = RandomInteger[{0, n}]], AppendTo[z, w]]; z,
  z = {}; While[!MemberQ[z, w = RandomInteger[{0, n}]], AppendTo[z, w]]; z
  }
 ]

How can I improve it? I don't want create temporary variables w, z and slow function AppendTo. I have idea to use NestWhileList or Reap/Sow, but can't guess how to сheck condition "value already was added in array".

$\endgroup$
4
  • 1
    $\begingroup$ You might be interested in RandomSample[]. $\endgroup$ Sep 2, 2017 at 16:31
  • $\begingroup$ Well, this was my attempt but it is (surprisingly) slower than yours: Keys@FixedPoint[ <|#, RandomInteger[n] -> 0|> &, <||> ] $\endgroup$
    – Szabolcs
    Sep 2, 2017 at 16:51
  • $\begingroup$ @J.M. No, I was used RandomInteger only as an example. I have other more complex function $\endgroup$
    – 32seph
    Sep 2, 2017 at 16:53
  • $\begingroup$ The mistake in the above implementation is using === (implicitly in FixedPoint) as a stopping condition. The comparison is too slow. $\endgroup$
    – Szabolcs
    Sep 2, 2017 at 17:37

1 Answer 1

4
$\begingroup$

Your algorithm keeps adding random integers to a list until an element repeats. At that point it stops.

Here's your implementation wrapped up into a function:

fun1[n_] :=
 Module[{z = {}, w},
  While[Not@MemberQ[z, w = RandomInteger[n]],
   AppendTo[z, w]
   ];
  z
  ]

Here's the same, but using associations. This avoids the quadratic complexity that is caused by MemberQ and AppendTo.

fun4[n_] :=
 Module[{asc = <||>, k},
  While[Not@KeyMemberQ[asc, k = RandomInteger[n]],
   asc[k] = 0;
   ];
  Keys[asc]
  ]

Benchmarking:

timings[fun_] :=
 Table[
  {n, First@AbsoluteTiming@Do[fun[n], {5000}]},
  {n, 2^Range[6, 16]}
  ]

ListLogLogPlot[timings /@ {fun1, fun4}, PlotLegends -> {fun1, fun4}, 
 AxesLabel -> {"n", "timing"}]

Mathematica graphics

Above around $n \approx 1000$, the association method becomes faster.


I have idea to use NestWhileList or Reap/Sow, but can't guess how to сheck condition "value already was added in array".

I believe that a Nest-like implementation will be slower because it will force creating a full copy of the association at every step instead of changing it efficiently in-place (as asc[k] = 0 does in the code above). This will make the complexity of the algorithm worse again (just as AppendTo does in fun1 by forcing a full copy of z).

To overcome to difficulty with sharing a value between the iterating function and the test function in NestWhile, we can use a tail-recursive implementation:

Clear[fun5, fun5i]
fun5i[n_, asc_] :=
 With[{k = RandomInteger[n]},
  If[KeyMemberQ[asc, k], Keys[asc], fun5i[n, <|asc, k -> 0|>]]
  ]
fun5[n_] := fun5i[n, <||>]

This does essentially the same thing as fun4, but it is much slower due to copying the association at each step.

$\endgroup$
3
  • $\begingroup$ Very nice! Fantastic how much faster fun4 is than analogous construction based on DownValues -- this has convinced met to step away from some old and dusty patterns! $\endgroup$ Sep 2, 2017 at 19:03
  • $\begingroup$ @JohnJosephM.Carrasco I tried a DownValues-based one. Here's the benchmark. Seems to have the same asymptotic complexity as the one with associations, but have some extra overhead that is significant for small $n$. I often find it very hard to predict performance, and I need to experiment a lot. Code: fun6[n_] := Module[{store}, While[True, With[{k = RandomInteger[n]}, If[IntegerQ@store[k], Return@Values@DownValues[store], store[k] = k ] ] ] ] $\endgroup$
    – Szabolcs
    Sep 2, 2017 at 20:39
  • $\begingroup$ Yes, I looked at the same and was startled by the overhead after comparing to your fun4. Caused me to recognize I've been prejudiciously cynical re: associations (had imagined cheap wrapping around downvalues and never cared enough to poke at it). Interesting that discrete (and finite) mappings have this extra optimization that appeared relatively late in the game (v10?). This is great. Still....now curious about your funs: 2,3 :-) $\endgroup$ Sep 2, 2017 at 20:51

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.