# Generating a position lookup function for an arbitrary list of integers

In my code, I generate a list of integers called numlist. Here is an example numlist:

numlist = Sort[Table[RandomInteger[{1, 100}], {3}]]


which gives, for example, the output:

{17, 74, 96}

I would like to write a function generateFun that, using numlist as input, generates the following function myfun:

myfun[int_Integer] := Which[
int == 17, 1,
int == 74, 2,
int == 96, 3
]


In other words, myfun takes an integer and returns the position of that integer in numlist. numlist is created at the beginning of the code and does not change during a given execution; however, a new execution will in general create a new list of integers numlist. The length of numlist varies (it is not guaranteed to be 3), although this fact is not present in the minimal working example that I gave above.

I could bypass generateFun and simply use this function myfun2:

myfun2[int_Integer, numlist_] := First[First[Position[numlist, int]]]


which returns the position of int_ in numlist_. However, since I will need to call the function (myfun or myfun2) many times (~1,000,000 times), I think that calling Position every time may be quite expensive -- since numlist, once generated, does not change during the execution.

Do you have any advice on how I can generate the Which expression automatically from numlist?

You really need a hash-table. Your method with Which statement won't scale to a large number of elements in a list, since Which does a linear look-up. Here are some possibilities.

### DownValues and SubValues

Create one via DownValues, like @belisarius demonstrated in his answer.

### Dispatch-ed replace rules

Another way (a little less stateful, since rules won't be attached to a symbol) is to use Dispatch-ed rules, like so:

lst = {2, 0, 11, 9, 20, 1, 16}

rules = Dispatch@Thread[# -> Range[Length[#]]] &[lst]


Then, for example,

11 /. rules

(*  3  *)


### SystemUtilitiesHashTable

Use SystemUtilitiesHashTable, like so:

h = SystemUtilitiesHashTable[];
MapThread[SystemUtilitiesHashTableAdd[h, ##] &, {lst, Range[Length[lst]]}];


where now you can extract the position for a given element as

SystemUtilitiesHashTableGet[h,11]

(* 3 *)


More details on the use of this hash table can be found in this excellent answer by Oleksandr.

### Using (sparse) arrays

Sometimes you may simply use arrays, or possibly sparse arrays, as a hash table. This is particularly useful for integer lists where integer values are not too large (although sparse arrays will handle also large values). I will demonstrate this by defining a new data type storage, like so:

Clear[makeStorage, storage];
makeStorage[lst_, $threshold_: 10^5] := With[{len = Max[lst] - Min[lst] + 1}, Module[{arr = If[len <$threshold,
Table[0, {len}],
SparseArray[{0}, {len}, 0]
]},
arr[[lst - Min[lst] + 1]] = Range[Length[lst]];
storage[arr, Min[lst]]]];

storage /: getPosition[storage[arr_, min_], elem_] := arr[[elem - min + 1]];


Here is how you use it:

st = makeStorage[lst];

getPosition[st,11]

(* 3 *)


The advantage of this method is that when plain (non-sparse) arrays can be used,this will be the fastest one. The disadvantage is that using plain arrays is very memory-wasteful, so you trade memory for speed. You may wish to also define a bulk element extractor method

storage /: getPositions[storage[arr_, min_], elems_List] :=
arr[[elems - min + 1]];


since this will be very efficient. You can see this approach put to practical use in this answer, where you can also see how much speed-up one can get by using it. I also put it (in a slightly different form) to use in this answer, where it was inside Compile.

I think the most straightforward way is:

MapIndexed[(f[#1] = #2[]) &, numlist]

{#, f@#} & /@ numlist // TableForm
(*
7   1
81  2
96  3
*)


Edit

If you need to do this for an unknown number of lists and functions in your program, you could go:

defFun[g_Symbol, l_List]:= MapIndexed[(g[#1] = #2[]) &, l]


Usage

ClearAll@h;
defFun[h, k = Table[Fibonacci@i, {i, 2, 10}]]
{#, h@#} & /@ k // TableForm
(*
1   1
2   2
3   3
5   4
8   5
13  6
21  7
34  8
55  9
*)

• Just a warning. If your list contains duplicates, only the second one will get assigned. Example: if your list is {1,2,1}, then f == 3 Sep 14, 2012 at 17:46

Nowadays, one can just build an Association[]. Using Leonid's example:

assoc = Association[MapIndexed[# -> #2[] &, {2, 0, 11, 9, 20, 1, 16}]];


or as Carl notes, you can use PositionIndex[] to build the required association:

assoc = First /@ PositionIndex[{2, 0, 11, 9, 20, 1, 16}];

assoc
3


If you need to get the values for two or more keys, use Lookup[]:

Lookup[assoc, {11, 9}]
{3, 4}

• You can use PositionIndex to create the association. Mar 25, 2018 at 1:40
• Thanks @Carl, I've edited. Mar 25, 2018 at 1:50

You can also use Nearest or Pick:

nf = Nearest[lst -> "Index"];
nf [ {11, 9, 3} , {1,0}]


{{3}, {4}, {}}

To get both the index and the element:

nf2 = Nearest[lst -> {"Element", "Index"}];
nf2[ {11, 9, 3} , {1,0}]


{{{11, 3}}, {{9, 4}}, {}}

Pick[Range @ Length @ lst, lst, #] & /@ {11,9,3}


{{3}, {4}, {}}