Home > Software design >  How to transform a Map<Set<A>, B> into a Map<A, Set<C>>
How to transform a Map<Set<A>, B> into a Map<A, Set<C>>

Time:03-30

I'm having a problem with finding an optimal solution (which is not multiple usage of forEach).

I have objects A, B and C. Object B contains set of objects C (i.e. B->Set`).

I'm being provided with a Map<Set<A>, B> which I need to turn into a Map<A,Met<C>>.

Is there any function in streams library that provides this particular solution?

The solution I came up with for now is to process this map through forEach.

With each iteration, I'm merging sets of C for each A in the map Map<A,Set<C>>. Here is outline of solution (there is a lot of things happening inside, the b->c is shortcut of whats happening).

With creating Map<A,Set<C>> where in each iteration I'm providing a merger of previous sets for each of them. Here is the outline of solution(there are a lot of things happening inside, the b->c is shortcut of what's happening).

Map<A, Set<C>> aSetCMap = new HashMap<>();
for (Map.Entry<Set<A>, B> entry : setABMap.EntrySet()) {
  var setA = entry.getKey();
  var setC = b.transformC();
  setA.forEach(item -> aSetCMap.merge(item, setC,
    (current, added) -> Streams.concat(current.stream(), added.stream())
      .collect(Collectors.toSet())));
}

The solution I came up with is a wonky way to do it in O(n^3) time. The thing I'm using it needs high performance, thus my question.

CodePudding user response:

You need to flatten each entry Map.Entry<Set<A>, B>. And associate each object A with a Set<C> extracted from the object B.

After that, apply collect() by using a flavor of Collectors.toMap() which takes three arguments: a keyMapper, a valueMapper and a mergeFunction (which is needed to combine sets mapped to the same object A)

Map<Set<A>, B> source = getSourceMap();

Map<A, Set<C>> result =
    source.entrySet().stream()
        .flatMap(entry -> entry.getKey().stream()
                    .map(a -> Map.entry(a,  entry.getValue().getC())))
        .collect(Collectors.toMap(Map.Entry::getKey, 
                                  Map.Entry::getValue,
                                  (set1, set2) -> {set1.addAll(set2); return set1;}));

The approach shown above is applicable if the Set<C> could be obtained from an object B in a constant time. Here I rely on your words:

B contains set of objects C

If this action entails an additional processing (I see a method transformC() in your code) and creates a new set after each invocation of transformC(), then for each entry in the source map it must be done only once (i.e. use multiline lambda).

In regard to time complexity of stream-based solution, your expectation of performance improvement will not come true (assuming that there's no logical fault in the iterative solution).

Note, the situation when a mutable object (Set<A>) is used as a key is vicious by itself and could cause incorrect behavior.

  • Related