5
$\begingroup$

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.

Important additional information

  • 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} *)
$\endgroup$
7
  • $\begingroup$ @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. $\endgroup$
    – anderstood
    Mar 7 '18 at 18:13
  • $\begingroup$ You know, the code just would not verify until I realized that tab changed all the time... =D $\endgroup$ Mar 7 '18 at 18:15
  • $\begingroup$ @HenrikSchumacher I'm making you think out of the box, hehe :). Thanks for you very efficient solution! $\endgroup$
    – anderstood
    Mar 7 '18 at 21:32
  • $\begingroup$ The order of the names in tab and list never change? $\endgroup$
    – Carl Woll
    Mar 7 '18 at 22:41
  • $\begingroup$ @CarlWoll That's right. $\endgroup$
    – anderstood
    Mar 7 '18 at 23:30
4
$\begingroup$

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]]&
    ]
]

For your example:

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},
    assoc = AssociationThread[tab[[All, "name"]], Range[Length[tab]]];
    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|>}

$\endgroup$
4
  • $\begingroup$ 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... $\endgroup$
    – anderstood
    Mar 8 '18 at 0:39
  • 1
    $\begingroup$ @anderstood I needed to use the 2-arg version of PermutationList. $\endgroup$
    – Carl Woll
    Mar 8 '18 at 0:42
  • $\begingroup$ 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. $\endgroup$
    – anderstood
    Mar 8 '18 at 1:00
  • $\begingroup$ @anderstood I think it should be possible with a little bit of work $\endgroup$
    – Carl Woll
    Mar 8 '18 at 1:03
6
$\begingroup$

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.

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

or using the list directly

ds[Sequence @@ {"nuke", "a"}]
$\endgroup$
1
  • $\begingroup$ Not as fast as Henrik's answer but very convenient, thanks! $\endgroup$
    – anderstood
    Mar 7 '18 at 21:31
3
$\begingroup$
(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]]]
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.