1
$\begingroup$

What I have is the following:

  • A mapping $f : key \rightarrow set$ that works in constant time
  • An inefficient mapping $g : \{key\} \rightarrow \cup_{k \in \{key\}} f(k)$ where this union is slow

Is there a data structure that would make things faster?

I could precalculate for every possible set of keys the wanted output but for a fairly large number of possible keys this isn't feasible ($O(2^n)$), despite the fact that lookup would be fast enough.

Currently I'm using a dictionary to have an efficient mapping $f$. For each value in a set of keys, I get the result by applying $f$, and do a union over the results. This is inefficient.

Improve this question
$\endgroup$
7
  • $\begingroup$ Is $\{key\}$ a standard notation? $\endgroup$
    – babou
    Mar 9, 2015 at 18:15
  • $\begingroup$ Set of keys? What's there non-standard about it? Or would you prefer a more Java-like syntax Set<Key>? Or maybe $S$ where $S \in \mathcal{P}(O)$ where $O$ is a set of all possible keys? $\endgroup$
    – Looft
    Mar 9, 2015 at 21:26
  • $\begingroup$ I suspect you'll need to tell us more about your application, as I suspect whether this can be sped up will depend upon the access patterns and workload. What can you tell us? I presume you want to speed up the calls to $g$. Is there any locality or structure in the arguments to $g$? Do you know the set of arguments to $g$ in advance (so they can be preprocessed in batch mode) or are they supplied in an online fashion (where you must answer the previous query before getting the next query)? How large is the universe of values that the output of $f$ comes from? etc. $\endgroup$
    – D.W. ♦
    Mar 9, 2015 at 21:48
  • $\begingroup$ Yes, I know them in advance, there are exactly 3,200,000 different keys (we can behave as if they are integers), set argument to $g$ can be of size from 1 to around 30,000. $f$ returns a set of integers also. I'd say that union of 30,000 results is the most expensive operation. $\endgroup$
    – Looft
    Mar 9, 2015 at 22:07
  • $\begingroup$ If I were to precompute the fetches for all possible subsets of the key-set, I'd have to go through $O(2^n)$ subsets. It's obvious that I could use the previous results/unions (DP) but I would still have an exponential number of inputs (stored) in the final mapping. $\endgroup$
    – Looft
    Mar 10, 2015 at 15:45

0

Reset to default

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.

Browse other questions tagged or ask your own question.