锁定老帖子 主题:给大家娱乐一下,优化一个简单的算法
精华帖 (0) :: 良好帖 (0) :: 新手帖 (0) :: 隐藏帖 (0)
|
|
---|---|
作者 | 正文 |
发表时间:2005-03-17
一次循环里面多比个几次?
比如: int len = b1.length - 4; for(int i=0;i<len;i++); { if(b1[i]!=b2[i]); return (b1[i]&0xff);-(b2[i]&0xff);; ++i; if(b1[i]!=b2[i]); return (b1[i]&0xff);-(b2[i]&0xff);; ++i; if(b1[i]!=b2[i]); return (b1[i]&0xff);-(b2[i]&0xff);; ++i; if(b1[i]!=b2[i]); return (b1[i]&0xff);-(b2[i]&0xff);; } 最后再比较一下剩下的。 P.S. 没有测试 |
|
返回顶楼 | |
发表时间:2005-03-17
cat 写道 一次循环里面多比个几次?
比如: int len = b1.length - 4; for(int i=0;i<len;i++); { if(b1[i]!=b2[i]); return (b1[i]&0xff);-(b2[i]&0xff);; ++i; if(b1[i]!=b2[i]); return (b1[i]&0xff);-(b2[i]&0xff);; ++i; if(b1[i]!=b2[i]); return (b1[i]&0xff);-(b2[i]&0xff);; ++i; if(b1[i]!=b2[i]); return (b1[i]&0xff);-(b2[i]&0xff);; } 最后再比较一下剩下的。 P.S. 没有测试 b1.length只有2怎么办? |
|
返回顶楼 | |
发表时间:2005-03-17
引用 最后再比较一下剩下的。
length只有2,这段不执行,直接执行下面那一段。那一段我没写。循环里再多放一点也可以。不过所谓节省也就是省了循环里面比较的开销。 不过看起来好像思路和楼主的不一样。如果很多情况下length都很小的话,这种方法效果估计不怎么样。仔细看了看,楼主的情况是1-50,不知道分布如何了 ![]() 有空测试一下看看。 |
|
返回顶楼 | |
发表时间:2005-03-17
cat 写道 引用 最后再比较一下剩下的。
不过所谓节省也就是省了循环里面比较的开销。 思路已经对了。 这里计数的增加和比较所用的时间比byte的比较还要多,优化只能在这里动脑筋了。 我的第二次优化 class byte3 implements Comparator { public int compare(Object o1,Object o2); { byte[] b1=(byte[]);o1; byte[] b2=(byte[]);o2; if(b1[0]!=b2[0]); return (b1[0]&0xff);-(b2[0]&0xff);; for(int i=1;i<b1.length;i++); { if(b1[i]!=b2[i]); return (b1[i]&0xff);-(b2[i]&0xff);; } return 0; } } 这次优化虽然只提高了5%的性能,但提供了终及优化的思路,也就是减少循环的开销。 起码能提高一倍的性能呵! |
|
返回顶楼 | |
发表时间:2005-03-17
final solution
public Comparator getByteArrayComparator(int byteArrayLength); { switch(arrayLength); { .......... case 3: return new BC3();; ......... case 10: return new BC10();; ............ default: return new BCGeneral(arrayLength);; } } class BC3 extends BytesComparator { public int compare(Object o1, Object o2); { byte[] a=(byte[]);o1; byte[] b=(byte[]);o2; if(a[0]!=b[0]); return (a[0]&0xff);-(b[0]&0xff);; if(a[1]!=b[1]); return (a[1]&0xff);-(b[1]&0xff);; if(a[2]!=b[2]); return (a[2]&0xff);-(b[2]&0xff);; return 0; } } class BC10 extends BytesComparator { public int compare(Object o1, Object o2); { byte[] a=(byte[]);o1; byte[] b=(byte[]);o2; if(a[0]!=b[0]); return (a[0]&0xff);-(b[0]&0xff);; if(a[1]!=b[1]); return (a[1]&0xff);-(b[1]&0xff);; if(a[2]!=b[2]); return (a[2]&0xff);-(b[2]&0xff);; if(a[3]!=b[3]); return (a[3]&0xff);-(b[3]&0xff);; if(a[4]!=b[4]); return (a[4]&0xff);-(b[4]&0xff);; if(a[5]!=b[5]); return (a[5]&0xff);-(b[5]&0xff);; if(a[6]!=b[6]); return (a[6]&0xff);-(b[6]&0xff);; if(a[7]!=b[7]); return (a[7]&0xff);-(b[7]&0xff);; if(a[8]!=b[8]); return (a[8]&0xff);-(b[8]&0xff);; if(a[9]!=b[9]); return (a[9]&0xff);-(b[9]&0xff);; return 0; } } class BCGeneral extends BytesComparator { private int bytelength; BCGeneral(int bytelength); { this.bytelength=bytelength; } public int compare(Object o1, Object o2); { byte[] a=(byte[]);o1; byte[] b=(byte[]);o2; for(int i=0;i<bytelength;i++); if(a[i]!=b[i]); return (a[i]&0xff);-(b[i]&0xff);; return 0; } } |
|
返回顶楼 | |
发表时间:2005-03-17
sigh, 连++i都没了……
不过下面那个BCGeneral还可以再优化一下: class BCGeneral extends BytesComparator { private int lastpos; BCGeneral(int bytelength); { this.lastpos=bytelength - 1; } public int compare(Object o1, Object o2); { byte[] a=(byte[]);o1; byte[] b=(byte[]);o2; byte aa = a[lastpos], bb = b[lastpos]; a[lastpos] = 0; b[lastpos] = 1; int i = 0; while (a[i] == b[i]); ++i; a[lastpos] = aa; a[lastpos] = bb; return (a[i]&0xff);-(b[i]&0xff);; } } 由于多了6次赋值,得要循环次数多一点才好。 Warning: 依旧没有测试,所以性能真的好些还是坏些不知道,而且这回正确性也不保证!不过貌似是对的。每次循环都没有越界检查了,而且比前面一个循环里多做几次要美观许多 ![]() |
|
返回顶楼 | |
发表时间:2005-03-18
问个问题
byte[i]&0xFF使用来干什么的呢? a[i]和b[i]不都是byte了么 |
|
返回顶楼 | |
发表时间:2005-03-18
Hint:
byte范围(-128~127), 0xFF字面量的类型应该是int 引用 数组中每一个byte都是无符号的整数。
|
|
返回顶楼 | |
发表时间:2005-03-18
主要测试这种算法,测试用例要比较精确,否则也很难算出正确答案来
|
|
返回顶楼 | |
发表时间:2005-03-18
cat 写道 Hint:
byte范围(-128~127), 0xFF字面量的类型应该是int 引用 数组中每一个byte都是无符号的整数。 我的错! |
|
返回顶楼 | |