# Fast way to extract data from a list

I used data=Table[{i,f[i]},{i,1,n}] to produce a list, here n is greater than 2^20 = 1048576. The function f(N) runs in time O(N*Log(N)), it is defined as:

Mod[PowerMod[i,n,n]-i,n] (n is an argument in a function which use this)


Now I want to give a table which shows the values of i that f(i) is 0, and another table for f(i) non-zero.

I used zero = Select[data,#[[2]]==0&], but it is slow in the following sense:

n=2^22, timing for data =  10.171, timing for zero =  4.508
n=2^23, timing for data =  21.606, timing for zero =  9.250
n=2^24, timing for data =  43.399, timing for zero = 17.971
n=2^25, timing for data =  84.209, timing for zero = 34.523
n=2^26, timing for data = 167.420, timing for zero = 71.885


The hardest computation is the data, But after that I want to have a much faster way to know the zeros of the function f.

Of course I can use For or Do to append the zeros i each time f(i) is zero. But we know that AppendTo is slow, and For or Do is slower than Table.

Is there any way to construct a list + exact data fast?

Update:

Thanks for all the suggestion. Here is a table of comparison. The green columns is to find i such that f[i]=0 and the white columns (excluding the 1st and 2nd column) is to find i such that f[i]!=0. The last 2 columns are in fact using "NonzeroPositions" (the last column) as mentioned by ubpdqn, then do the complement (the second last column). This method is faster.

-
Can you please give f[i]? And how can you take #[[3]] while Length@data[[1]] is 2? – Öskå Feb 24 '14 at 10:06
@Öskå:Sorry, it is a typo. In my actual code, it should be 3, but I simplify the code here, so it should be 2. Thanks. – user565739 Feb 24 '14 at 10:11
@user565739 thank you for the update and performance assessment. rasher answer more thoughtful and analytical than mine. Just wanted to post an alternative exploiting "NonzeroPositions". – ubpdqn Feb 24 '14 at 23:27

Positions of zeros and non-zeros:

dataZeros = SparseArray[1 - Unitize[data[[All, 2]]]]["AdjacencyLists"]; // Timing

dataNonZeros = SparseArray[Unitize[data[[All, 2]]]]["AdjacencyLists"]; // Timing

(*
{0.249602,Null}
{0.374402,Null}
*)


That's for a 1M entry table, on a netbook. Just use the result with Part or Extract to get the actual data. The first for zero positions can also be done (with slightly faster results via verbosity) as:

dataZeros = SparseArray[Unitize[data[[All, 2]]], Automatic, 1]["AdjacencyLists"]


You can also use

Pick[data, Unitize[data[[All, 2]]], 0]
Pick[data, Unitize[data[[All, 2]]], 1]


to do the same, and get datasets directly.

For ideas on how the (sparsely documented) feature of SparseArray and things like Unitize have potentially huge performance benefits, search for the terms on the site, have a look an Mr. Wizard's posts regarding them, and see my answer here where using it made a problem solvable thousands of times more quickly.

As far as creating it more quickly, short of going parallel with multiple kernels, doing it as

Array[{#,f[#]}&,n]


might save 10% or so in time.

Edit: I've found this quite a bit faster for creation:

n = 1000000

data = Table[{i, Mod[PowerMod[i, n, n] - i, n]}, {i, 1, n}]; // Timing

data2 = Transpose[{l = Range[n], Mod[PowerMod[l, n, n] - l, n]}]; // Timing

data == data2

(*
{18.064916,Null}
{8.205653,Null}
True
*)


Timings again on lounge-netbook, curious what your results are...

-
Compile can also speed up the creation a lot...but be careful with large integer handling! – PlatoManiac Feb 24 '14 at 10:43
@PlatoManiac: good point - I forget about compile since I mostly deal symbolically or arbitrary precision. – ciao Feb 24 '14 at 10:45
@rasher +1 , link very useful – ubpdqn Feb 24 '14 at 13:54
@rasher : I found that Array[{#, f[#]} &, n]][[1] is a litte bit slower than Table[{b, f[b]}, {b, 1, n}], which is 124.426 vs 105.565 when n = 25. – user565739 Feb 24 '14 at 19:09
@user565739: check update re: creation. – ciao Feb 24 '14 at 23:23

Just exploiting another feature of SparseArray and for sample of size $10^6$.

Setting up:

fun[n_] := Table[{i, Mod[PowerMod[i, n, n] - i, n]}, {i, 1, n}];
data = fun[1000000];


Using "NonzeroPositions":

nozero= SparseArray[Last@Transpose@data]["NonzeroPositions"]; // Timing
zero = Complement[List /@ Range[Length@data], ans]; // Timing


yielded:{0.078125, Null}, {0.093750, Null} respectively.

Example:

zero
Extract[data, zero]


yields:

{{1}, {109376}, {890625}, {1000000}}
{{1, 0}, {109376, 0}, {890625, 0}, {1000000, 0}}

-
+1 - I feel like a dufus forgetting that property, that I use in the answer I linked... DOH! – ciao Feb 24 '14 at 23:28
@rasher sadly but productively DOH moments are how I learn – ubpdqn Feb 25 '14 at 1:08