Speed up replacement of very large alternatives expression

Question

I'm doing a computation which effectively has the same issue as this code:

Range@1000000 /. (Alternatives@@RandomSample[Range@1000000,500000]) -> 0

i.e. replacing each element of an arbitrary but large subset with a constant. So, how can code like list /. Alternatives@@subset->0 be made faster when subset is very large (close to half the size of list, so no benefit from inverting) and doesn't contain any exploitable patterns?

---

Perhaps the motivating problem is easier to solve: select those triangles in a mesh which cross an InfinitePlane, say InfinitePlane@{{0,0,0},{1,0,0},{0,0,1}}. So, given a MeshRegion m,

fwd=First/@Position[MeshCoordinates@m,{_,_?Positive,_}]
back=First/@Position[MeshCoordinates@m,{_,_?NonPositive,_}]
Position[
  MeshCells[m,{2}]/.{Alternatives@@fwd->0,Alternatives@@back->1}
Polygon@{OrderlessPatternSequence[{1,0,_}]}]

I'm sure this could be made better, but I'm curious about the question it prompts about large Alternatives statements.

A way to do it better: don't 'cache' the results of Positive, and simply delete those polygons that are entirely on one side or the other:

Delete[MeshCells[m,{2}], 
  Position[MeshPrimitives[m,{2}], 
    Polygon[{{_,_?Positive,_},
             {_,_?Positive,_},
             {_,_?Positive, _}} |
            {{_,_?NonPositive,_},
             {_,_?NonPositive,_},
             {_,_?NonPositive,_}}
    ]
  ]
]

---

I can't figure out how to effectively use Dispatch or some clever numerical/floating point tricks to speed it up.

Answer 1

Update: The Thread trick is not necessary any more in v13.3 to achieve full performance improvement; this trick is now effectively built-in behaviour. See the answer below.

---

Use threaded rules instead of alternatives: instead of 1 | 2 -> 0 use {1 -> 0, 2 -> 0}. Combined with a Dispatch or Association this is very quick:

r = Thread[RandomSample[Range@1000000, 500000] -> 0];
Range@1000000 /. r; // AbsoluteTiming
(*    about two hours    *)

d = Dispatch[r]; // AbsoluteTiming
(*    {0.116651, Null}    *)
RepeatedTiming[Range@1000000 /. d;, 10]
(*    {0.392904, Null}    *)

a = Association[r]; // AbsoluteTiming
(*    {0.122811, Null}    *)
RepeatedTiming[Range@1000000 /. a;, 10]
(*    {0.379022, Null}    *)

So both Dispatch and Association are about 20000× faster than a simple rule replacement in this case. Association is even a little bit faster than Dispatch.

Thanks to @HenrikSchumacher for pointing out the use of Association. It is true that as of version 13.2.0 there is no longer any advantage of using Dispatch.

Answer 2

v2 is not as fast as Roman's v1

r = Range@100000;
s = RandomSample[r, 50000];

AbsoluteTiming[v1 = (
   d = Dispatch[Thread[s -> 0]];
   r /. d);]

{0.104434, Null}

AbsoluteTiming[v2 = (
   Clear[test];
   Scan[(test[#] = True) &, s];
   test[_] = False;
   If[test[#], 0, #] & /@ r);]

{0.268603, Null}

AbsoluteTiming[v3 = (r /. (Alternatives @@ s) -> 0);]

{59.3356, Null}

v1 == v2 == v3

True

Answer 3

Using Dispatch outlined in the accepted answer is still highly beneficial in v13.3, but threading is not any more necessary since Mathematica now internally splits dispatch rules with alternatives on the left side to separate rules.

v13.2.1:

With[
 {dp = Dispatch[
    (Alternatives @@ RandomSample[Range@1000000, 500000]) -> 0]},
 Timing[Range@10000 /. dp;]]

(* {31.1677, Null} *)

vs. v13.3:

With[
 {dp = Dispatch[
    (Alternatives @@ RandomSample[Range@1000000, 500000]) -> 0]},
 Timing[Range@10000 /. dp;]]

(* {0.004174, Null} *)

A drawback of the new behaviour is that if the right-hand side of such a rule is large, the dispatch table may grow to a very large size. This can be worked around by first using a placeholder right hand side and replacing this placeholder with the large intended right hand side by applying a second replacement rule.