• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    迪恩网络公众号

Java,C++和Ruby的性能PK(续文)--关于凸包算法(convex hull)的效率 ...

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

译者序

本篇blog实际上是Bob大叔对xreborner的一连串的发贴给于的回复(xreborner在上篇blog中对Bob大叔提出了一系列犀利的维护C++权益的观点)。

正文

我在最近的一篇blog中对比了C++、Java和Ruby的时间消耗,其中一个参与者(xreborner)提交了一个convex hull的凸包算法代码。我花了好久来研究其中的蹊跷,直到把算法绘制于图上,才发现自己是蒙在鼓里了。

xreborner用的算法像是一种Graham Scan算法,它的复杂度呈O(nLogn)级别。实际上,这个算法的时间主要是消耗在其中的快速排序上了。

还有一个算法叫做Jarvis March,也称作giftwrapping算法。它的复杂度呈O(kn)级别,k代表了凸包顶点的数目。

我非常好奇这两个算法哪个会更快些,显然,只有在logn < k的时候,O(nLogn)才会比O(kn)的快。不过也有另一种考量,因为Jarvis March比Graham Scan简单的多,所以我认为在绝大多数情况下,Jarvis March算法都会是个更优的选择,因为只有在凸包顶点数目非常大的情形下Graham算法的效率才会反超。于是我自己编写了Jarvis March算法,并且和xreborner的Graham Scan做了比较,结果如下:

是不是很有趣?我构造了1000个随机点并绘制了时间和凸包顶点数量的曲线。交叉点看起来正好位于这些随机的凸包顶点数量的中间位置,而且大概是在37点位!我猜想这是个巧合,不过也够神奇的啊。

噢,作为一个锻炼,看看你们是不是能读懂Jarvis March,也再看看能不能弄明白Graham Scan。

import java.util.*;

public class JarvisMarch {
Points pts;
private Points hullPoints = null;
private List<Double> hy;
private List<Double> hx;
private int startingPoint;
private double currentAngle;
private static final double MAX_ANGLE = 4;

public JarvisMarch(Points pts) {
this.pts = pts;
}

/**
* The Jarvis March, sometimes known as the Gift Wrap Algorithm.
* The next point is the point with the next largest angle.
* <p/>
* Imagine wrapping a string around a set of nails in a board. Tie the string to the leftmost nail
* and hold the string vertical. Now move the string clockwise until you hit the next, then the next, then
* the next. When the string is vertical again, you will have found the hull.
*/
public int calculateHull() {
initializeHull();

startingPoint = getStartingPoint();
currentAngle = 0;

addToHull(startingPoint);
for (int p = getNextPoint(startingPoint); p != startingPoint; p = getNextPoint(p))
addToHull(p);

buildHullPoints();
return hullPoints.x.length;
}

public int getStartingPoint() {
return pts.startingPoint();
}

private int getNextPoint(int p) {
double minAngle = MAX_ANGLE;
int minP = startingPoint;
for (int i = 0; i < pts.x.length; i++) {
if (i != p) {
double thisAngle = relativeAngle(i, p);
if (thisAngle >= currentAngle && thisAngle <= minAngle) {
minP = i;
minAngle = thisAngle;
}
}
}
currentAngle = minAngle;
return minP;
}

private double relativeAngle(int i, int p) {return pseudoAngle(pts.x[i] - pts.x[p], pts.y[i] - pts.y[p]);}

private void initializeHull() {
hx = new LinkedList<Double>();
hy = new LinkedList<Double>();
}

private void buildHullPoints() {
double[] ax = new double[hx.size()];
double[] ay = new double[hy.size()];
int n = 0;
for (Iterator<Double> ix = hx.iterator(); ix.hasNext();)
ax[n++] = ix.next();

n = 0;
for (Iterator<Double> iy = hy.iterator(); iy.hasNext();)
ay[n++] = iy.next();

hullPoints = new Points(ax, ay);
}

private void addToHull(int p) {
hx.add(pts.x[p]);
hy.add(pts.y[p]);
}

/**
* The PseudoAngle is a number that increases as the angle from vertical increases.
* The current implementation has the maximum pseudo angle < 4. The pseudo angle for each quadrant is 1.
* The algorithm is very simple. It just finds where the angle intesects a square and measures the
* perimeter of the square at that point. The math is in my Sept '06 notebook. UncleBob.
*/
public static double pseudoAngle(double dx, double dy) {
if (dx >= 0 && dy >= 0)
return quadrantOnePseudoAngle(dx, dy);
if (dx >= 0 && dy < 0)
return 1 + quadrantOnePseudoAngle(Math.abs(dy), dx);
if (dx < 0 && dy < 0)
return 2 + quadrantOnePseudoAngle(Math.abs(dx), Math.abs(dy));
if (dx < 0 && dy >= 0)
return 3 + quadrantOnePseudoAngle(dy, Math.abs(dx));
throw new Error("Impossible");
}

public static double quadrantOnePseudoAngle(double dx, double dy) {
return dx / (dy + dx);
}

public Points getHullPoints() {
return hullPoints;
}


public static class Points {
public double x[];
public double y[];

public Points(double[] x, double[] y) {
this.x = x;
this.y = y;
}

// The starting point is the point with the lowest X
// With ties going to the lowest Y. This guarantees
// that the next point over is clockwise.
int startingPoint() {
double minY = y[0];
double minX = x[0];
int iMin = 0;
for (int i = 1; i < x.length; i++) {
if (x[i] < minX) {
minX = x[i];
iMin = i;
} else if (minX == x[i] && y[i] < minY) {
minY = y[i];
iMin = i;
}
}
return iMin;
}

}
}

(原文链接网址:http://www.butunclebob.com/ArticleS.UncleBob.ConvexHullTiming; Robert C. Martin的英文blog网址:http://www.butunclebob.com/ArticleS.UncleBob

作者简介:Robert C. MartinObject Mentor公司总裁,面向对象设计、模式、UML、敏捷方法学和极限编程领域内的资深顾问。他不仅是Jolt获奖图书《敏捷软件开发:原则、模式与实践》(中文版)(《敏捷软件开发》(英文影印版))的作者,还是畅销书Designing Object-Oriented C++ Applications Using the Booch Method的作者。MartinPattern Languages of Program Design 3More C++ Gems的主编,并与James Newkirk合著了XP in Practice。他是国际程序员大会上著名的发言人,并在C++ Report杂志担任过4年的编辑。


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
Ruby:字符集和编码学习总结发布时间:2022-07-14
下一篇:
linux下安装ruby环境发布时间:2022-07-14
热门推荐
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap