02 July 2016

Reduction Operation in functional programming

the operation "Reduce" or "Fold" is a very important operation in functional programming, as you could implement all other operations using the reduce operation. (see ProgFun course at Coursera)

Also, Java tutorial has a very straightforward illustration for Reduction in Java 8: https://docs.oracle.com/javase/tutorial/collections/streams/reduction.html

I want to talk about a case (from cobone-reviews project) that I needed low-level reduction operation.

First I have a Map<Object, List<Long>> that looks like:

{"dp.g.doubleclick.net": [0,1,0,0,0],"cobonereviews.tk": [0,1,0,0,0],"www.facebook.com": [3,4,0,0,0],"www.google.co.in": [0,1,0,0,0],"localhost:8080": [0,0,40,5,3],"l.facebook.com": [0,1,0,0,0],"www.google.com": [0,10,5,0,0],"www.google.com.sa": [0,11,0,0,0],"www.google.com.hk": [0,1,0,0,0],"www.google.ae": [0,3,0,0,0]}
I need to group each top private domain's result together, So the result would looks like:
 {  
   "localhost:8080":[  
    0,  
    0,  
    40,  
    5,  
    3  
   ],  
   "facebook":[  
    3,  
    5,  
    0,  
    0,  
    0  
   ],  
   "google":[  
    0,  
    26,  
    5,  
    0,  
    0  
   ],  
   "cobonereviews":[  
    0,  
    1,  
    0,  
    0,  
    0  
   ],  
   "doubleclick":[  
    0,  
    1,  
    0,  
    0,  
    0  
   ]  
 }  
So first I used the following method to get Top Private Domain from the Map's keys above:
 // Example: www.google.com.sa, google.com, google.eg all translated to  
 // google  
 private String getDomainName(Object referrer) {  
      try {  
           String topPrivateDomain = InternetDomainName.from(referrer.toString()).topPrivateDomain().name();  
           String publicSuffix = InternetDomainName.from(referrer.toString()).publicSuffix().name();  
           String onlyDomainName = topPrivateDomain.replace(publicSuffix, "");  
           return onlyDomainName.endsWith(".") ? onlyDomainName.substring(0, onlyDomainName.length() - 1)  
                     : onlyDomainName;  
      } catch (Exception ex) {  
           log.error(ex.getMessage());  
           return referrer.toString();  
      }  
 }  
Then, I need to use the getDomainName method above as a grouping key and then for the values, I need to concatenate the all lists under the same domain together, for example for case of facebook, I have the following map:
 "www.facebook.com":[   
  3,   
  4,   
  0,   
  0,   
  0   
  ], "l.facebook.com":[   
  0,   
  1,   
  0,   
  0,   
  0   
 ] 
And I need the result to be:

 "facebook":[   
  3,   
  5,   
  0,   
  0,   
  0   
  ]  
So, The reduction method that do the the concat operation looks like:
 collect2.entrySet().stream().collect(groupingBy(e -> getDomainName(e.getKey()),  
  reducing(new ArrayList<Long>(), e -> e.getValue(), (l1, l2) -> accumlateLists(l1, l2))));  
And here's the implementation of accumlateLists method
 private List<Long> accumlateLists(List<Long> accumlator, List<Long> list) {  
      if (accumlator.isEmpty()) {  
           return list;  
      } else {  
           for (int i = 0; i < accumlator.size(); i++) {  
                accumlator.set(i, accumlator.get(i) + list.get(i));  
           }  
           return accumlator;  
      }  
 }  
Note, In the reduction method above, we used the form:
 reducing(U identity, Function<? super T, ? extends U> mapper, BinaryOperator<U> op)  
The first parameter is the accumulator and the zero value (empty ArrayList), the second parameter is mapper, which maps the Entry object to List<Long> which is the object that will be used by the third parameter, hence the mapper Function returns object of type U the same that would be used as type parameter for the BinaryOperator (which is a BiFunction).

Complete source code would be found in this file.

No comments: