# 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. – anderstood Mar 7 '18 at 18:13
• You know, the code just would not verify until I realized that tab changed all the time... =D – Henrik Schumacher Mar 7 '18 at 18:15
• @HenrikSchumacher I'm making you think out of the box, hehe :). Thanks for you very efficient solution! – anderstood Mar 7 '18 at 21:32
• The order of the names in tab and list never change? – Carl Woll Mar 7 '18 at 22:41
• @CarlWoll That's right. – anderstood Mar 7 '18 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... – anderstood Mar 8 '18 at 0:39
• @anderstood I needed to use the 2-arg version of PermutationList. – Carl Woll Mar 8 '18 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. – anderstood Mar 8 '18 at 1:00
• @anderstood I think it should be possible with a little bit of work – Carl Woll Mar 8 '18 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! – anderstood Mar 7 '18 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]]]