Fast way to extract data from a list

Question

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.

Answer 1

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

Answer 2

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