论坛首页 Java企业应用论坛

给大家娱乐一下,优化一个简单的算法

浏览 10183 次
精华帖 (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. 没有测试
0 请登录后投票
   发表时间: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怎么办?
0 请登录后投票
   发表时间:2005-03-17  
引用
最后再比较一下剩下的。

length只有2,这段不执行,直接执行下面那一段。那一段我没写。循环里再多放一点也可以。不过所谓节省也就是省了循环里面比较的开销。

不过看起来好像思路和楼主的不一样。如果很多情况下length都很小的话,这种方法效果估计不怎么样。仔细看了看,楼主的情况是1-50,不知道分布如何了 

有空测试一下看看。
0 请登录后投票
   发表时间: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%的性能,但提供了终及优化的思路,也就是减少循环的开销。
起码能提高一倍的性能呵!
0 请登录后投票
   发表时间: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;
  }
}

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: 依旧没有测试,所以性能真的好些还是坏些不知道,而且这回正确性也不保证!不过貌似是对的。每次循环都没有越界检查了,而且比前面一个循环里多做几次要美观许多
0 请登录后投票
   发表时间:2005-03-18  
问个问题

byte[i]&0xFF使用来干什么的呢?

a[i]和b[i]不都是byte了么
0 请登录后投票
   发表时间:2005-03-18  
Hint:
byte范围(-128~127),
0xFF字面量的类型应该是int
引用
数组中每一个byte都是无符号的整数。
0 请登录后投票
   发表时间:2005-03-18  
主要测试这种算法,测试用例要比较精确,否则也很难算出正确答案来
0 请登录后投票
   发表时间:2005-03-18  
cat 写道
Hint:
byte范围(-128~127),
0xFF字面量的类型应该是int
引用
数组中每一个byte都是无符号的整数。


我的错!
0 请登录后投票
论坛首页 Java企业应用版

跳转论坛:
Global site tag (gtag.js) - Google Analytics