Monday, November 12, 2012

Marzullo's algorithm - in java

Marzullo's algorithm, invented by Keith Marzullo for his Ph.D. dissertation in 1984, is an agreement algorithm used to select sources for estimating accurate time from a number of noisy time sources. I was working on similar requirement at work and came across the algorithm in Wikipedia. Here is a Java implementation of the algorithm. 


public class MarzulloAlgorithm {

 public static void main(String[] args) {
  Range r1 = new Range("1",10,40);
  Range r2 = new Range("2",30,50);
  Range r3 = new Range("3",35,45);
  List<range> ranges = new ArrayList<range>();
  ranges.add(r1);
  ranges.add(r2);
  ranges.add(r3);
  MarzulloAlgorithm m = new MarzulloAlgorithm();
  Range r = m.marzulloAlgorithm(ranges);
 }
 
 public Range marzulloAlgorithm (List<range> ranges) {
  Range result = null;
  int best = 0;
  int count = 0;
  int beststart = 0;
  int bestend = 0;
  int i = 0;
  String name = "";
  List<point> points = new ArrayList<point>();
  for(Range r:ranges) {
   points.add(new Point(r.getName(),r.getStart(),-1));
   points.add(new Point(r.getName(),r.getEnd(),+1));
  }
  Collections.sort(points,new PointComparator());
  for(Point p:points) {
   count = count - p.getType();
   if(best &lt; count) {
    best = count;
    beststart = p.getPoint();
    if(i&lt;(points.size()-1)) {
     bestend = points.get(i+1).getPoint();
     name = p.getName() + "," + points.get(i+1).getName();
    }
   }
   i++;
  }
  result = new Range(name,beststart,bestend);
  return(result);
 }
}

I have added some data structures like Range and Point for my purpose at work. Definition for Range and Point below.

public class Point {
 String name;
 int point;
 int type;
 
 public Point(String name, int point, int type) {
  this.name = name;
  this.point = point;
  this.type = type;
 }
 
 public String getName() { 
  return name;
 }
 public int getPoint() {
  return point;
 }
 public int getType() {
  return type;
 }
}
public class Range {
 String name;
 int start;
 int end;

 public Range(String name, int start, int end) {
  this.name = name;
  this.start = start;
  this.end = end;
 }

 public String getName() {
  return name;
 }

 public int getStart() {
  return start;
 }

 public int getEnd() {
  return end;
 }
}