Generating a position lookup function for an arbitrary list of integers

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  *)

System`Utilities`HashTable

Use System`Utilities`HashTable, like so:

h = System`Utilities`HashTable[];
MapThread[System`Utilities`HashTableAdd[h, ##] &, {lst, Range[Length[lst]]}];

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

System`Utilities`HashTableGet[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
*)

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

assoc = Association[MapIndexed[# -> #2[[1]] &, {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[11]
   3

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

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

Tags:

Function Construction

Recent Posts