What's fastest way of defining 10^5 down values?

Question

I want to define

isGood[___] = False;

isGood[#] = True & /@ list

where list is a list of several million integers. What's the fastest way of doing this?

Answer 1

As J. M. suggested:

isGood[___] = False;
list = RandomInteger[{-100000000, 100000000}, 1000000];
Scan[(isGood[#] = True) &, list]; // AbsoluteTiming

(* ==> {3.1651810, Null} *)

On my computer, this takes about 3 seconds for a million integers. Isn't this fast enough?

Retrieval of the results is also quite quick:

(*retrieve the results*)
ret = RandomInteger[{-100000000, 100000000}, 1000000];
isGood /@ ret; // AbsoluteTiming
(* ==> {1.8271045, Null} *)

Out of curiosity, I compared this to the undocumented HashTable (mentioned here) and got surprisingly poor results:

list = RandomInteger[{-100000000, 100000000}, 1000000];
h = System`Utilities`HashTable[];
 Scan[With[{i = #}, System`Utilities`HashTableAdd[h, i, True]] &, 
   list]; // AbsoluteTiming
(* ==> {26.7095277, Null} *)


(*retrieve the results*)
ret = RandomInteger[{-100000000, 100000000}, 1000000];
System`Utilities`HashTableContainsQ[h, #] & /@ ret; // AbsoluteTiming
(* ==> {1.4280817, Null} *)

We see that retrieval is a bit faster, but putting the keys into the HashTable is quite slow (unless I'm doing something wrong).

Answer 2

Are you sure you want to use UpValues? You can use Dispatch which is pretty fast when generating the lookup table and is equally fast when accessing values:

n = 6;
list = RandomInteger[{0, 10^(n + 1)}, {10^n}];

AbsoluteTiming[disp = Dispatch@Thread[list -> True];]

{1.6220927, Null}

Remove[isGood];
AbsoluteTiming[isGood[___] = False; Scan[(isGood[#] = True) &, list]]

{3.5982058, Null}

Query values:

test = RandomInteger[{0, 10^(n + 1)}, {10^n}];

AbsoluteTiming[Count[test /. disp, True]]

{1.9151096, 94844}

AbsoluteTiming[Count[isGood /@ test, True]]

{1.7601007, 94844}

Answer 3

This seems to be faster to define downvalues

list = RandomInteger[{-100000000, 100000000}, 1000000];
DownValues[isGood] = 
   HoldPattern[isGood[#]] :> True & /@ list; // AbsoluteTiming
isGood[___] = False;

Answer 4

My solution is ugly, but task-specific. It builds a bitmap out of machine-sized integers in imperative fashion and uses Compile. This works reasonably in memory usage for ranges that have at least couple percent of True values.

A million integers:

n = 6;
list = RandomInteger[{0, 10^(n + 1)}, {10^n}];

Function itself:

<< Developer`

isGood = With[
     {bits = Floor[Log[2, $MaxMachineInteger + 1]],
      min = Min@list,
      max = Max@list},
     With[
      {bv = Compile[{{list, _Integer, 1}},
          Module[
           {bitvec = Table[0, {(max - min + bits - 1)~Quotient~bits}]},
           Scan[(bitvec[[(# - min)~Quotient~bits + 1]] += 
               2^((# - min)~Mod~bits)) &, Union@list];
           bitvec
           ],
          CompilationOptions -> {"ExpressionOptimization" -> True, 
            "InlineExternalDefinitions" -> True}
          ]@list},
      Compile[{{x, _Integer}},
       min <= x <= max && 
          bv[[(x - min)~Quotient~bits + 1]]~BitAnd~(2^((x - min)~Mod~bits)) != 0,
       CompilationOptions -> {"ExpressionOptimization" -> True, 
         "InlineExternalDefinitions" -> True}
       ]
      ]
     ]; // AbsoluteTiming // First

(* 0.347843 *)

Usage:

isGood /@ list // AbsoluteTiming // First

(* 0.590347 *)

Originally I wanted to solve this problem using bitwise operations of arbitrarily large integers, but the issue with that is that functional programming with bigints has large return value overheads - even when just some individual bits are twiddled.