# 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[[1]]) &, 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[[1]]) &, 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[1] == 3 –  belisarius Sep 14 '12 at 17:46