17
$\begingroup$

If I have the following Dataset

ds=Dataset[{
  <|"a" -> 1, "b" -> "x", "c" -> 6|>,
  <|"a" -> 2, "b" -> "y", "c" -> {2, 3}|>,
  <|"a" -> "x", "b" -> "z", "c" -> {3}|>,
  <|"a" -> 4, "b" -> "x", "c" -> {4, 5}|>,
  <|"a" -> 5, "b" -> "y", "c" -> {5, 6, 7}|>,
  <|"a" -> 6, "b" -> "z", "c" -> {}|>}]

how can I search the Dataset to find all keys that have same value. In the above example if I want to search in ds to find the keys that have "x" value what should I do. The answer should be {"a","b"}. If searching for 6 then the answer should be {"a","c"}

$\endgroup$
  • $\begingroup$ It is really very hard now to choose answer. most of the answers are good. $\endgroup$ – Algohi Feb 18 '15 at 4:26
9
$\begingroup$

General

One can feel that there should be some simple solution, but it just doesn't come to mind easily. I would argue that the Dataset set of built-in operations is yet missing some, where one relevant here is the one to invert many-to-many relationships - which is essentially what this question is about.

Many to many relationships

Here is one possible implementation:

ClearAll[invertManyToMany];
invertManyToMany[start_Association]:=
   Composition[
      Merge[Identity],
      Reverse[#,{2}]&,
      Catenate,
      Map[Thread],
      Normal
   ] @ start;

Here is an example:

invertManyToMany @ Association[{
  "programming" -> {1, 2, 3},"graphics" -> {2, 3, 4}, "plotting" -> {1, 3, 4, 5}}
]

(*
   <|
     1 -> {"programming", "plotting"}, 2 -> {"programming", "graphics"}, 
     3 -> {"programming", "graphics", "plotting"}, 4 -> {"graphics", "plotting"},
     5 -> {"plotting"}
   |>
*)

The case at hand

Here is then how this problem can be solved:

ds[Merge[Union]][invertManyToMany]

enter image description here

$\endgroup$
  • $\begingroup$ As with WReach's solution this is slower than more direct alternatives. I do see the general value in your construct but here I think it would be better to use: ds[Merge[Apply[Union]], PositionIndex]? $\endgroup$ – Mr.Wizard Feb 17 '15 at 17:54
  • $\begingroup$ @Mr.Wizard Yes, it is slower for any particular single value, but if you need to query this for several (many) different values, then I think it should be faster, since it only does it once. But, as you said, the main value is conceptual. We may in the future get some efficient version of invertManyToMany, which could even be lazy (do only as much as needed to service a particular query). The main point is - my solution stresses the conceptual problem we need to solve, and separates the high-level query from the lower-level implementation details - at least, this is what I like about it. $\endgroup$ – Leonid Shifrin Feb 17 '15 at 20:27
  • $\begingroup$ As I said I do see the value. ds[Merge[Apply[Union]], PositionIndex] also finds all indexes at once however. $\endgroup$ – Mr.Wizard Feb 17 '15 at 20:31
  • $\begingroup$ @Mr.Wizard Sorry, I apparently wasn't paying enough attention. Perhaps, my general hesitation to embrace position-based solutions is that I prefer to think about this problem in terms of data and relations, rather than the structure of expressions used to represent this data in Mathematica. Admittedly, such approach often isn't the right one for Mathematica code (particularly if we need it to be fast), but I decided that I can afford this luxury in this case :) $\endgroup$ – Leonid Shifrin Feb 17 '15 at 20:35
  • $\begingroup$ @Mr.Wizard Anyway, FWIW, your suggestion with PositionIndex is perhaps the most idiomatic for Mathematica (IMO). I already voted for it, but after this discussion I started to appreciate it more. $\endgroup$ – Leonid Shifrin Feb 17 '15 at 21:17
7
$\begingroup$

Here is one way:

ds[Merge[MemberQ[6]] /* Select[#&] /* Keys]

dataset screenshot

It works as follows. First, we extract each unique key along with an indication as to whether its associated value is the target value:

ds[Merge[MemberQ[6]]]

dataset screenshot

Next, we select the rows that have met the condition:

ds[Merge[MemberQ[6]] /* Select[#&]]

dataset screenshot

Finally, we keep only the keys themselves:

ds[Merge[MemberQ[6]] /* Select[#&] /* Keys]

dataset screenshot

The result is a dataset but if a simple list is desired, then:

ds[Merge[MemberQ[6]] /* Select[#&] /* Keys] // Normal

(* {a, c} *)
$\endgroup$
  • $\begingroup$ This looks nice but in a single test it appears to be much slower than Position. With ds = Table[ AssociationThread[CharacterRange["a", "z"], RandomInteger[9999, 26]], {5000}] // Dataset then fn[ds, 77] takes 0.01 second, while your methods takes 2.5 seconds. $\endgroup$ – Mr.Wizard Feb 17 '15 at 17:08
  • 1
    $\begingroup$ @Mr.Wizard Position remains my favourite solution among the answers so far. I added this variant because it closely conforms to the pipeline-style of expression that is encouraged by the Query syntax, and that one finds in "real" query-based databases. I am hoping that some day Query will grow up to be such a "real" engine and then these pipeline forms will become important. Incidentally, I usually find that for maximum performance in the present version, the first thing to do is to get the data out of Dataset and to then apply "normal" operators :) $\endgroup$ – WReach Feb 17 '15 at 17:25
  • $\begingroup$ @Mr.Wizard, you evaluated on single-value lookup 77. See my answer for a comparison across all values. $\endgroup$ – alancalvitti Feb 17 '15 at 18:36
  • $\begingroup$ @alancalvitti I already proposed my own all-values solution in a comment below Leonid's answer. I have incorporated it into my answer proper to reduce confusion. $\endgroup$ – Mr.Wizard Feb 17 '15 at 18:51
7
$\begingroup$

Isn't this a time to use Position?

fn[ds_, v_] := Union @ Position[ds, v][[All, 2, 1]]

Test:

fn[ds, "x"]

fn[ds, 6]
{"a", "b"}

{"a", "c"}

A levelspec can be included if needed.


If you wish to find all positions at once as several of the other answers are doing I proposed this in a comment below Leonid's answer:

ds[Merge[Apply[Union]], PositionIndex] // Normal
<|1 -> {"a"}, "x" -> {"a", "b"}, 6 -> {"a", "c"}, 2 -> {"a"},
 "y" -> {"b"}, {2, 3} -> {"c"}, "z" -> {"b"}, {3} -> {"c"}, 4 -> {"a"},
 {4, 5} -> {"c"}, 5 -> {"a"}, {5, 6, 7} -> {"c"}, {} -> {"c"}|>
$\endgroup$
  • $\begingroup$ +1 although I remember you always don't recommend using Position. You always prefer PositionIndex :) $\endgroup$ – Algohi Feb 16 '15 at 23:35
  • 2
    $\begingroup$ @Algohi Thanks for the vote. However you are mistaken: I am against extended iterative use of Position (via Map or otherwise) in place of a single-pass method such as PositionIndex. Of course of you were going to use fn for many different values one would do well to consider similar optimization but memory consumption could be considerable. $\endgroup$ – Mr.Wizard Feb 17 '15 at 0:27
5
$\begingroup$
q = Function[{dataset, value}, 
  dataset[All, Select[# == value &]] // Keys // Normal // Flatten // Union];


q[ds, "x"]
{"a", "b"}
q[ds, 6]
{"a", "c"}
$\endgroup$
4
$\begingroup$

This might go beyond your question a bit, but by reversing the dictionary you can quickly get a list of all repeated values

Select[Length[#] > 1 &][Merge[Union][Reverse /@ Flatten@Normal@Normal@ds]]

(* <|"x" -> {"a", "b"}, 6 -> {"a", "c"}|> *)
$\endgroup$
4
$\begingroup$

Simplifying Reverse approach:

ds[Merge[Union], AssociationMap[Reverse]]

enter image description here

that took 0.54s on Mr. Wizards random data vs. ~100s to Map fn to all 10k values. Call the random dataset ds2, then

vals = ds2[Catenate /* Union] // Normal
(* {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, ..., 9999 }*)
vals // Map[fn[ds2, #] &]; // Timing
{107.486297, Null}
$\endgroup$
  • 1
    $\begingroup$ +1, but beware that the simplified version assumes that the right-hand sides of the original rules are all unique (e.g. try it for ds = Dataset@{<|a -> 6, b -> 6|>}). $\endgroup$ – WReach Feb 17 '15 at 18:44
  • 1
    $\begingroup$ fn was never intended to be use this way; as everyone knows I am against mapping Position. $\endgroup$ – Mr.Wizard Feb 17 '15 at 18:54
  • $\begingroup$ @WReach Precisely the reason I discarded it too - in exactly the same form. But, also, +1. $\endgroup$ – Leonid Shifrin Feb 18 '15 at 1:12
  • $\begingroup$ @WReach, and Leonid, I inferred from OPs setup that value clashes only occur across Associations, not within. Doesn't that sound like an assumption that WRI would 'safely' fold in the inference engines? $\endgroup$ – alancalvitti Feb 18 '15 at 4:05
  • $\begingroup$ I think that it is application-dependent whether any given association can have two keys with the same value. If not, then your technique presents a valuable optimization. Otherwise, more elaborate measures are needed. Only the OP knows for sure. Ideally, any facility provided by WRI would allow an explicit choice in this matter. In the absence of choice, I think they would be forced to support the more general case (possible duplicates). [I'm pinging @Leonid in case he didn't see your comment.] $\endgroup$ – WReach Feb 18 '15 at 6:14
2
$\begingroup$

I came up with this solution:

q[ds_, value_] :=Union@Cases[Normal[Normal[ds]], Rule[v_, value] :> v, -1]

q[ds, "x"]
(*{"a", "b"}*)

q[ds, 6]

(*{"a", "c"}*)

But as can be seen, this method completely destroy the Dataset and the Association. I thing this kind of methods will not work for big Dataset.

$\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.