18
$\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"}

Improve this question
$\endgroup$
1
  • $\begingroup$ It is really very hard now to choose answer. most of the answers are good. $\endgroup$
    – Basheer Algohi
    Feb 18, 2015 at 4:26

7 Answers 7

Reset to default
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

Improve this answer
$\endgroup$
5
  • $\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, 2015 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, 2015 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, 2015 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, 2015 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, 2015 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} *)
Improve this answer
$\endgroup$
4
  • $\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, 2015 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, 2015 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, 2015 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, 2015 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"}|>
Improve this answer
$\endgroup$
2
  • $\begingroup$ +1 although I remember you always don't recommend using Position. You always prefer PositionIndex :) $\endgroup$
    – Basheer Algohi
    Feb 16, 2015 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, 2015 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"}
Improve this answer
$\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"}|> *)
Improve this answer
$\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}
Improve this answer
$\endgroup$
5
  • 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, 2015 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, 2015 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, 2015 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, 2015 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, 2015 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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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