# Fastest way to look up in a list of Associations

Given a list of associations tab where each association has keys {"name", "a", "b"}:

SeedRandom[2018]
n = 100;
names = RandomWord[n];
tab := Table[<|"name" -> names[[i]], "a" -> RandomReal[10],
"b" -> RandomReal[10]|>, {i, n}]
tab0 = tab
(* {<|"name" -> "nuke", "a" -> 4.41839, "b" -> 0.688305|>,
<|"name" -> "iodine", "a" -> 6.61215, "b" -> 4.315|>,
... } *)


and a static list of the form {"nameValue", "a"} or {"nameValue", "b"}:

randomNames = RandomSample[names, n];
list = Table[{randomNames[[i]], RandomChoice[{"a", "b"}]}, {i, n}]
(* {{"waterspout", "a"}, {"encouraging", "a"}, {"saber", "b"},  ... } *)


what is the fastest way of extracting the values from tab based on list? For example if list contains {"nuke","a"} it should return 4.41839 but if it contains {"nuke","b"} it should return 0.688305.

• Each name value in tab is exactly once in list (in particular, list and tab have the same length)
• The structure of tab and names is always the same, only the values for the keys a and b change (i.e. everything except the numerical values is static). The solution can have a high fixed cost, but after that should run as fast as possible on every new evaluation of tab.

The following works but is quite slow (about 0.01 second):

Table[First[Select[tab0, #["name"] == list[[i, 1]] &, 1]][list[[i, 2]]], {i, n}]
(* {2.48345, 8.47655, 7.92796, 1.6882, ..., 3.65979} *)

• @HenrikSchumacher Because in my application tab comes from a stream and is updated at high frequency. But you can work on tab0 if you want :). I want to process tab as fast as possible and wanted to highlight what changes (= the numerical values) and what is static. Commented Mar 7, 2018 at 18:13
• You know, the code just would not verify until I realized that tab changed all the time... =D Commented Mar 7, 2018 at 18:15
• @HenrikSchumacher I'm making you think out of the box, hehe :). Thanks for you very efficient solution! Commented Mar 7, 2018 at 21:32
• The order of the names in tab and list never change? Commented Mar 7, 2018 at 22:41
• @CarlWoll That's right. Commented Mar 7, 2018 at 23:30

The following function assumes that the order of the names in both list and tab don't change:

extractionFunction[list_, tab_] := Module[{rnk, a, b, s = Ordering[tab[[All, "name"]]]},
rnk = Ordering @ Ordering[list];
a = Pick[rnk, list[[All, 2]], "a"];
b = Pick[rnk, list[[All, 2]], "b"];
With[{sa=s[[a]], sb=s[[b]], r=PermutationList[FindPermutation[rnk,Join[a,b]], Length[list]]},
Join[#[[sa, "a"]], #[[sb, "b"]]][[r]]&
]
]


ef = extractionFunction[list, tab0]; //AbsoluteTiming


{0.000185, Null}

Extracting the data:

ef[tab0] //RepeatedTiming


{0.0000129, {2.48345, 8.47655, 7.92796, 1.6882, 1.86398, 3.81981, 3.66469, 5.79178, 5.52018, 6.61215, 2.34137, 3.56046, 7.02237, 0.148731, 4.94333, 9.47983, 3.25394, 5.08571, 7.15642, 0.000857735, 5.53244, 9.66373, 9.41381, 3.08944, 5.71462, 2.2408, 9.44, 0.640177, 0.148516, 8.96909, 9.70023, 0.507559, 1.89383, 0.600272, 6.77362, 6.62578, 9.28269, 6.40033, 0.689248, 9.17103, 0.677636, 0.950572, 0.322821, 7.40765, 6.46661, 0.484517, 3.34366, 0.298406, 4.88656, 6.84136, 2.39152, 1.72063, 9.26934, 0.195646, 0.695893, 0.750353, 1.16114, 7.09758, 4.77873, 2.36114, 1.11616, 8.87156, 8.04428, 8.39603, 5.66964, 0.688305, 3.89521, 5.58604, 6.29886, 0.751684, 9.65089, 4.188, 5.72688, 6.12588, 5.17795, 4.25081, 6.48617, 8.07723, 9.69531, 8.36877, 7.00888, 3.64206, 8.97193, 8.45415, 9.1015, 5.37611, 6.50624, 1.12191, 3.89697, 3.40464, 8.4333, 0.406116, 4.25232, 0.994173, 7.95154, 1.57853, 1.81928, 3.73122, 1.5254}}

Update

The OP requested a generalization where list need not have the same length as tab, with possibly duplicate names. As long as the names in list are all contained in tab, the following should work (I used some of @Henrik's ideas here):

extractionFunction[list_, tab_]:= Module[{assoc, rnk, grp},
grp = GroupBy[list, Last->First];
rnk = Ordering @ Ordering[list];
With[
{
a = Lookup[assoc, grp["a"]],
b = Lookup[assoc, grp["b"]],
r = PermutationList[
FindPermutation[
rnk,
Join[
Pick[rnk, list[[All, 2]], "a"],
Pick[rnk, list[[All, 2]], "b"]
]
],
Length[list]
]
},
Join[#[[a, "a"]], #[[b, "b"]]][[r]]&
]
]


As an example:

ef = extractionFunction[
{{"waterspout", "a"}, {"encouraging", "b"}, {"waterspout", "b"}, {"encouraging", "b"}},
tab0
]


Join[#1[[{53}, "a"]], #1[[{10, 53, 10}, "b"]]][[{1, 2, 3, 4}]] &

Extracting the data:

ef[tab0]


{2.48345, 8.47655, 8.52417, 8.47655}

Check:

Select[MatchQ["waterspout"|"encouraging"] @ #name&] @ tab0


{<|"name" -> "encouraging", "a" -> 2.12, "b" -> 8.47655|>, <|"name" -> "waterspout", "a" -> 2.48345, "b" -> 8.52417|>}

• Don't you loose the last item in r = PermutationList@FindPermutation[rnk, Join[a, b]]? Length@ef[tab0] returns 99. Apart from that, incredible speed... Commented Mar 8, 2018 at 0:39
• @anderstood I needed to use the 2-arg version of PermutationList. Commented Mar 8, 2018 at 0:42
• I know I specifically asked for list and tab of the same length. Just asking: would this method be able to deal with larger list, e.g. containing both {"waterspout", "a"} and {"waterspout", "b"}. It seems difficult because of FindPermutation. Commented Mar 8, 2018 at 1:00
• @anderstood I think it should be possible with a little bit of work Commented Mar 8, 2018 at 1:03

You can make a lookup table for the names and use Extract:

assoc = AssociationThread[tab0[[All, "name"]], Range[Length[tab0]]];
list1 = list;
list1[[All, 1]] = Lookup[assoc, list[[All, 1]]];
r = Extract[tab, list1]


Note that assoc can be reused and if list does not change, also list1 can be recycled. For n=100, the extraction takes half a millisecond.

ds = Dataset@<|#name -> <|"a" -> #a, "b" -> #b|> & /@ tab|>;
ds["nuke", "a"]


or using the list directly

ds[Sequence @@ {"nuke", "a"}]

• Not as fast as Henrik's answer but very convenient, thanks! Commented Mar 7, 2018 at 21:31
(tab // Query[GroupBy["name"], First]) //
Query[list // Query[All, Apply[Query]]]


{8.06993, 6.16562, 4.24211,...,0.755269}

Or equivalently in Dataset form to contract the Queries (note Dataset[list] needs to be normalized anyway)

Dataset[tab][GroupBy["name"], First /* KeyDrop["name"]] [
Normal@Dataset[list][All, Apply[Query]]]