Everyone Could Use a Buddy

This is not about Buddy Holly, and while it’s going to cover Big O notation, it’s not about The Big O himself: Roy Orbison.

I’d like to share a problem and solution with you.

Read More: 1Z0-900: Java EE 7 Application Developer

Consider these data structures in Java (other languages are also available):

public class Element {

    private String name;

    private ElementData someData;

    private ... // other stuff

    // getters and setters etc

}

public class UserData {

    private List<Element> elements;

}

The above data object, where UserData has some elements may be a deliberately anemic data model. The data may be in this format owing to some sort of wire format – say JSON for a REST API. We may wish to consume this in our services in a variety of ways, and we shouldn’t expect the raw model itself to get complicated by any of the needs of a service.

However, the problem with the above is that repeated lookups of an element by name would be time consuming:

public Optional<Element> getByName(String name) {

    for (Element element : elements) {

        if (element.getName().equals(name)) {

            return Optional.of(element);

        }

    }

    return Optional.empty();

}

Written like the above it also looks clumsy, though we can refactor it to a Stream operation:

public Optional<Element> getByName(String name) {

    return elements.stream()

        .filter(element -> 

           element.getName().equals(name))

        .findFirst()

}

And though that looks nicer (to me at least), it’s still fundamentally slow – after the first one!

If we wanted to do one search of these elements, then it doesn’t really matter. If, however, we happen to have a task that is intended to take each element by its different name and do something with that, then we run into a problem.

The search big O of a list is n. In other words, searching a list takes the whole of the list’s size to determine whether the element is in there (unless you get lucky and it’s in the first position).

If we’re doing the worst case of processing every element, but choosing them by their name/identity, then a data set of size n ends up with an n-squared complexity. In other words with, say, 8 entries, we’ve got approximately 8 x 8 = 64 operations to do on the list.

This is not incredibly efficient, and it would be better for this use case if the items were in a Map like structure. However, we don’t want the plain data object to carry this map around, as it’s not necessarily the job of the data object to optimise such a look up, and the pure data structure shouldn’t be concerned with this use case.

There are two elements of what I consider to be a nice solution here:

◉ Externalise an algorithm to produce an appropriate lookup for use cases when we want to do this sort of thing

◉ Give the data object a factory method to produce the lookup object, which a caller can use: this buddy is a good friend of the source object, so knows how to produce the useful view, and is also a nice ambassador to consumers that need this use case

So let’s define a class ElementLookup:

public class ElementLookup {

    private Map<String, Element> elements;

    public ElementLookup(List<Element> elements) {

        this.elements = produceLookupFrom(elements);

    }

    public Optional<Element> getByName(String name) {

        // just look it up

        return Optional.ofNullable(elements.get(name));

    }

}

We can put the factory method in the class in which we want to do looking up:

public class UserData {

    private List<Element> elements;

    // if you want to do a lookup

    public ElementLookup createLookup() {

        // this object has control of its internals

        // and is passing them to its buddy

        return new ElementLookup(elements);

    }

}

Which means it’s easy to do lookups with the above object:

UserData userData = someData();

// for some use cases this is still fine

Optional<Element> gotTheSlowWay = 

    userData.getByName("myelement");

// for several gets

ElementLookup lookup = userData.createLookup();

Optional<Element> el1 = lookup.getByName("thing1");

Optional<Element> el2 = lookup.getByName("thing2");

... etc

So how do we build the map?

This is possibly smaller than you might expect:

private static Map<String, Element> produceLookupFrom(

        List<Element> elements) {

    return elements.stream()

        .collect(toMap(element -> element.getName(),

          Function.identity());

}

What’s nice about this is it’s easy to use, it’s made of small pieces, and it’s low impact to an anemic data object.

The lookup could always be made away from the data object with the same techniques, but it seems like a friendly thing for this sort of object to be able to do for us.

So What’s The Big O?

The big O of a single search in the list is n. If we were always going to search for every item this way, then that means it would be an n-squared.

The cost of producing the lookup is also of complexity n. However, we can assume that the complexity of looking up from the completed lookup table is 1. The HashMap is probably so efficient that items can either be present in one place, or are absent.

Source: javacodegeeks.com