2
$\begingroup$

For a big matrix 5000 x 5000 or list2 i am trying to get positions of all entries Except[1.0]. I am using Position, however I find it quite odd that with Compile the result is comparatively slower.

Any ideas where i might be wrong in my implementation? and I would be grateful if you can let me know of an even faster implementation.

pos1 =  RandomInteger[{0, 1}, {5000, 2}];

pos2 = RandomInteger[{0, 1}, {5000, 2}];

list2 = DistanceMatrix[N@pos1, N@pos2];

(l2 = IntegerPart[
 Compile[{{lis, _Real, 2}},
   Position[lis, Except[1.], {2}, Heads -> False],
   CompilationTarget -> "C"
   ][list2]
 ];) // AbsoluteTiming

(* {9.70626, Null} *)

(l1 = Position[list2, Except[1.], {2}, 
 Heads -> False];) // AbsoluteTiming

(* {5.80316, Null} *)


l1 === l2
(* True *)
$\endgroup$
4
$\begingroup$

Load CompiledFunctionTools` and check whether Position compiled (your example probably doesn't compile because of the Except):

Needs["CompiledFunctionTools`"]

CompilePrint @ Compile[
    {{lis,_Real,2}},
    Position[lis, Except[1.], {2}, Heads->False],
    CompilationTarget->"C"
]

(*
        1 argument
        2 Tensor registers
        Underflow checking off
        Overflow checking off
        Integer overflow checking on
        RuntimeAttributes -> {}

        T(R2)0 = A1
        Result = T(R2)1

1   T(R2)1 = MainEvaluate[ Function[{lis}, Position[lis, Except[1.], {2}, Heads \
-> False]][ T(R2)0]]
2   Return
*)

Notice the MainEvaluate. When Compile has to call MainEvaluate it will be slower than the uncompiled version.

You asked for a faster method. The following is pretty fast:

sa = SparseArray[list2, Automatic, 1.];
sa // AbsoluteTiming

{0.593123, SparseArray[< 12499892 >, {5000, 5000}, 1.]}

Then, you can use the accessor functions like:

sa["MatrixColumns"]; //AbsoluteTiming

{0.055956, Null}

to get information related to the positions. Depending on what you want to do with the positions, this may be useful.

positions can be obtained using:

sa["NonzeroPositions"]//AbsoluteTiming;
(* {0.0689321, Null} *)

sa["NonzeroPositions"] === Position[list2, Except[1.], {2}, Heads -> False];
(* True *)
$\endgroup$
2
  • $\begingroup$ Worth to mention that simple cases will compile CompiledFunctionTools`CompilePrint @ Compile[{{lis, _Real, 2}}, Position[lis, 1.], CompilationTarget -> "C"] because one could be surprised it is mentioned in Compile`CompilerFunctions[] $\endgroup$ – Kuba Jul 21 '17 at 14:53
  • $\begingroup$ @Carl so is there a way to make my current implementation faster. I was thinking of using a compiled version of MapIndexed but apparently i am having trouble with Compile[{{list, _Real, 2}}, MapIndexed[If[#1 != 1.0, #2] &, list, {2}]][list2] $\endgroup$ – Ali Hashmi Jul 21 '17 at 14:58

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.