Thursday 4 June 2015

Memoize functions in java 8

Memoization is not a grammar error,  memoization is an optimization technique used primarily to speed up computer programs by storing the results of expensive function calls and returning the cached result when the same inputs occur again.

http://en.wikipedia.org/wiki/Memoization

I will explain it with a simple example.

Context :

Table PIZZA, columns ID, NAME

We have a java function called "hereThePizzaGiveMeTheId" where you pass a String representing a pizza name and it will return the correspondent id retrieved from the DB.

Function<String, Integer> hereThePizzaGiveMeTheId = name -> {

            int pizzaId = -1;


            System.out.println("Select ID from PIZZA where name = '" + name + "'");

            pizzaId = pizzaDao.get(name);


            return pizzaId;

        };

Now, if I call this function with the same pizza name I will hit the DB each time :

        System.out.println(hereThePizzaGiveMeTheId.apply("Margherita"));
        System.out.println(hereThePizzaGiveMeTheId.apply("Margherita"));
        System.out.println(hereThePizzaGiveMeTheId.apply("Margherita"));
        System.out.println(hereThePizzaGiveMeTheId.apply("Margherita"));
        System.out.println(hereThePizzaGiveMeTheId.apply("Four Season"));
        System.out.println(hereThePizzaGiveMeTheId.apply("Four Season"));
        System.out.println(hereThePizzaGiveMeTheId.apply("Four Season"));
        System.out.println(hereThePizzaGiveMeTheId.apply("Four Season"));
        System.out.println(hereThePizzaGiveMeTheId.apply("Gorgonzola and figs"));
        System.out.println(hereThePizzaGiveMeTheId.apply("Gorgonzola and figs"));
        System.out.println(hereThePizzaGiveMeTheId.apply("Gorgonzola and figs"));
        System.out.println(hereThePizzaGiveMeTheId.apply("Gorgonzola and figs"));


OUTPUT:


Select ID from PIZZA where name = 'Margherita'
1
Select ID from PIZZA where name = 'Margherita'
1
Select ID from PIZZA where name = 'Margherita'
1
Select ID from PIZZA where name = 'Margherita'
1
Select ID from PIZZA where name = 'Four Season'
2
Select ID from PIZZA where name = 'Four Season'
2
Select ID from PIZZA where name = 'Four Season'
2
Select ID from PIZZA where name = 'Four Season'
2
Select ID from PIZZA where name = 'Gorgonzola and figs'
3
Select ID from PIZZA where name = 'Gorgonzola and figs'
3
Select ID from PIZZA where name = 'Gorgonzola and figs'
3
Select ID from PIZZA where name = 'Gorgonzola and figs'
3



Fantastic, but I don't want to run that function every time, if I already know the result based on the pizza name.
So, lets memoize (cache) the result of that function.

First we create a generic method that wraps a function into another function that will behave the same as the input one, but will check if the result is already computed : 

public static <X, Y> Function<X, Y> memoise(Function<X, Y> fn) {

        Map<X, Y> pp = new ConcurrentHashMap<X, Y>();

        return (a) -> pp.computeIfAbsent(a, fn);

    }


 Then we wrap our "hereThePizzaGiveMeTheId"  function :

Function<String, Integer> memoziedHereThePizzaGiveMeTheId = memoise(hereThePizzaGiveMeTheId);
 
Lastly, we call again the same logic as before, but using the new memoziedHereThePizzaGiveMeTheId function :

      
        System.out.println(memoziedHereThePizzaGiveMeTheId.apply("Margherita"));

        System.out.println(memoziedHereThePizzaGiveMeTheId.apply("Margherita"));

        System.out.println(memoziedHereThePizzaGiveMeTheId.apply("Margherita"));

        System.out.println(memoziedHereThePizzaGiveMeTheId.apply("Margherita"));

        System.out.println(memoziedHereThePizzaGiveMeTheId.apply("Four Season"));

        System.out.println(memoziedHereThePizzaGiveMeTheId.apply("Four Season"));

        System.out.println(memoziedHereThePizzaGiveMeTheId.apply("Four Season"));

        System.out.println(memoziedHereThePizzaGiveMeTheId.apply("Four Season"));

        System.out.println(memoziedHereThePizzaGiveMeTheId.apply("Gorgonzola and figs"));

        System.out.println(memoziedHereThePizzaGiveMeTheId.apply("Gorgonzola and figs"));

        System.out.println(memoziedHereThePizzaGiveMeTheId.apply("Gorgonzola and figs"));

        System.out.println(memoziedHereThePizzaGiveMeTheId.apply("Gorgonzola and figs"));



OUTPUT:

Select ID from PIZZA where name = 'Margherita'
1
1
1
1
Select ID from PIZZA where name = 'Four Season'
2
2
2
2
Select ID from PIZZA where name = 'Gorgonzola and figs'
3
3
3
3







We will hit the DB only if the result of the function is not already present in the map.

That's it.

p.s.

Gorgonzola and figs is a fantastic pizza :















No comments:

Post a Comment