List construction improvement

Question

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".

Answer 1

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"}]

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.