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.
I have added some data structures like Range and Point for my purpose at work. Definition for Range and Point below.
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 < count) {
best = count;
beststart = p.getPoint();
if(i<(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;
}
}
where is the definition for PointComparator?
ReplyDeleteWhere is the PointComparator?
ReplyDelete