1
$\begingroup$

I need a data structure, which allows efficient queries for 'give me the group of x'.

Let me give you an example:

Group 1: [a, b, c] 
Group 2: [d, e]
Group 3: [f]

getGroupOf(d) -> [d, e]

There are no significant constraints on storage or construction time. I only need getGroupOf to be O(logn) or faster.

I am thinking about using a Dictionary<Element, Set<Element>> where entries for all elements in a group share the same set reference. This would make lookup effectively O(1) or O(logn) depending on the dictionary implementation, but would result in a lot of entries.

This feels fairly bloated, and I am wondering: is there is a more elegant data structure to accomplish this?

Edit: the elements in a group can be completely arbitrary and they have no ordering.

$\endgroup$
6
  • 1
    $\begingroup$ In your example the groups are formed by contiguous sequences of elements. Is this always the case? If so you can get away by only saving at which points the groups change (in this case $d$ and $f$). $\endgroup$
    – orlp
    Jul 15, 2020 at 14:01
  • $\begingroup$ @orlp No, the groups can be completely arbitrary. The elements do not have an ordering. $\endgroup$
    – Dracam
    Jul 15, 2020 at 14:45
  • 1
    $\begingroup$ It doesn't seem bloated to me -- both hashtables and BSTs need $O(n)$ space to store $n$ elements, which is optimal up to constant factors. You can use a single Element object and keep 2 references to it (one for the key, one for the unique Set containing it). If you want to avoid keeping 2 references per element, can order the elements somehow and don't mind $O(k)$ time to find a group having $k$ elements, another option would be to use a Dictionary<Element, Element>, where each entry points to the next element in the given order, or to the first if it is the last. $\endgroup$ Jul 15, 2020 at 16:34
  • $\begingroup$ What formal language are you using? The data-structure that you call a 'group' is more commonly known as a list. $\endgroup$ Jul 15, 2020 at 22:07
  • $\begingroup$ And if unordered, a set. $\endgroup$ Jul 15, 2020 at 22:09

1 Answer 1

1
$\begingroup$

If the groups are static, your data structure is perfectly reasonable.

You can also consider the Union-Find data structure. Find is the getGroupOf operation. It is quite fast, and also allows you to modify the data structure by merging groups and adding a new item in its own group.

$\endgroup$
1
  • $\begingroup$ After reading through the Wikipedia article I can say that the Union-Find data structure is exactly what I am looking for, thank you. I will gladly accept your answer if you could edit your answer to provide a short summary of how the data structure works and why it is a good fit. $\endgroup$
    – Dracam
    Jul 16, 2020 at 0:53

Your Answer

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

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