java - live view on collection contained within a collection contained within ... etc

Question

I have a class A which can contain many instances of class B which may in turn contain many instances of Class C, which can contain many instances of class D

Now, in class A I have a method getAllD. Currently every time this is called there is a lot of iterating that takes place, and a rather large list is freshly created and returned. This cannot be very efficient.

I was wondering how I could do this better. This question Combine multiple Collections into a single logical Collection? seems to touch upon a similar topic, but I'm not really sure how I could apply it to my situation.

All comments are much appreciated!

Answer 1

I would combine Iterables.concat with Iterables.transform to obtain a live view of Ds:

public class A {
    private Collection<B> bs;

    /**
     * @return a live concatenated view of the Ds contained in the Cs
     *         contained in the Bs contained in this A.
     */
    public Iterable<D> getDs() {
        Iterable<C> cs = Iterables.concat(Iterables.transform(bs, BToCsFunction.INSTANCE));
        Iterable<D> ds = Iterables.concat(Iterables.transform(cs, CToDsFunction.INSTANCE));
        return ds;
    }

    private enum BToCsFunction implements Function<B, Collection<C>> {
        INSTANCE;

        @Override
        public Collection<C> apply(B b) {
            return b.getCs();
        }
    }

    private enum CToDsFunction implements Function<C, Collection<D>> {
        INSTANCE;

        @Override
        public Collection<D> apply(C c) {
            return c.getDs();
        }
    }
}


public class B {
    private Collection<C> cs;

    public Collection<C> getCs() {
        return cs;
    }
}

public class C {
    private Collection<D> ds;

    public Collection<D> getDs() {
        return ds;
    }
}

This works well if your goal is simply to iterate over the Ds and you don't really need a collection view. It avoids the instantiation of a big temporary collection.

Answer 2

This cannot be very efficient.

Iterating in-memory is pretty damn fast. Also the efficiency of creating an ArrayList of 10 k elements compared to creating 10 ArrayList with 1k elements each won't be that drastically different. So, in conclusion, you should probably first just go with the most straight-forward iterating. Chances are that this works just fine.

Even if you have gazillion elements, it is probably wise to implement a straight-forward iterating anyways for comparison. Otherwise you don't know if you are being able to optimize or if you are slowing things down by doing things clever.

Having said that, if you want to optimize for sequential read access of all Ds, I'd maintain an "index" outside. The index could be a LinkedList, ArrayList, TreeList etc. depending on your situation. For example, if you aren't sure of the length of the index, it is probably wise to avoid ArrayList. If you want to efficiently remove random elements using the reference of that element, OrderedSet might be much better than a list etc.

When you do this you have to worry about the consistency of the index & actual references in your classes. I.e. more complexity = more place to hide bugs. So, unless you find it necessary through performance testing, it is really not advisable to attempt an optimization.

(btw avoiding instantiation of new collection objects are unlikely to make things much faster unless you are talking about EXTREME high-performing code. Object instantiation in modern JVMs only take a few ten nano seconds or something. Also, you could mistakenly use an ArrayList having small initial length or something and make things worse)

Answer 3

The answer to your question is going to depend on the specifics of your situation. Are these collections static or dynamic? How big is your collection of B's in A? Are you only going to access the Ds from A, or will you sometimes want to be farther down in the tree or returning Bs or Cs? How frequently are you going to want to access the same set of Ds from a particular A? Can a D (or C or B) be associated with more than 1 A?

If everything is dynamic, then the best chance of improving performance is to have parent references from the Cs to A, and then updating the parent whenever C's list of Ds changes. This way, you can keep a collection of Ds in your A object and update A whenever one of the Cs gets a new one or has one deleted.

If everything is static and there is some reuse of the D collections from each A, then caching may be a good choice, particularly if there are a lot of Bs. A would have a map with a key of B and a value of a collection of Ds. The getAllDs() method would first check to see if the map had a key for B and if so return its collection of Ds. If not, then it would generate the collection, store it into the cache map, and return the collection.

You could also use a tree to store the objects, particularly if they were fairly simple. For example, you could create an XML DOM object and use XPath expressions to pull out the subset of Ds that you wanted. This would allow far more dynamic access to the sets of objects you were interested in.

Each of these solutions has different tradeoffs in terms of cost to setup, cost to maintain, timeliness of results, flexibility of use, and cost to fetch results. Which you should choose is going to depend on your context.

Answer 4

Actually, I think Iterables.concat (or IteratorChain from Apache Commons) would work fine for your case:

class A {
    Collection<B> children;
    Iterator<D> getAllD() {
        Iterator<Iterator<D>> iters = new ArrayList<Iterator<D>>();
        for (B child : children) {
            iters.add(child.getAllD());
        }
        Iterator<D> iter = Iterables.concat(iters);
        return iter;
    }
}
class B {
    Collection<C> children;
    Iterator<D> getAllD() {
        Iterator<Iterator<D>> iters = new ArrayList<Iterator<D>>();
        for (C child : children) {
            iters.add(child.getAllD());
        }
        Iterator<D> iter = Iterables.concat(iters);
        return iter;
    }
}
class C {
    Collection<D> children;
    Iterator<D> getAllD() {
        Iterator<D> iter = children.iterator();
        return iter;
    }
}