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

我先声明，这个算法本身简单，但要优化，就不是那么简单了。为啥，因为它太简单了。

要求是返回一个Comparator，该Comparator能比较两个byte数组的大小。byte数组大小的定义是:数组中每一个byte都是无符号的整数。即0xff不是-128，而是255；按数组中byte的顺序比较对应byte，如果相等，则比较下一个，如果不等，则byte数值大的数组为大。

byte数组的长度可以肯定是在1-50之间。

byte数组的长度在 getByteArrayComparator方法的参数中可以得到，也就是 int byteArrayLength.

这是我工作中遇到的一个真实问题。下面的code是我最初的算法。由于这个算法在某种情况下成为我程序中的瓶颈，因此我花了很大力气优化它，一共优化了三次。优化三次后的算法应该是非常快的算法了。

大家可以畅所欲言。任何理论上的算法优化都欢迎，但不要谈什么C啊汇编啊的。

[code:1]
public Comparator getByteArrayComparator(int  byteArrayLength)
{
    return new ByteArrayComparator();
}

class ByteArrayComparator implements Comparator
{
    public int compare(Object o1,Object o2)
    {
        byte[] b1=(byte[])o1;
        byte[] b2=(byte[])o2;
        for(int =0;i<b1.length;i++)
        {
           int  s1=b1[i]&0xff
           int  s2=b2[i]&0xff
           if(s1>s2)
             return 1;
           else if(s1<s2)
              return -1;
         }
         return 0;
    }
}
[/code:1]

给出一个思路，没有code test 过。

[code:1] public int compare(Object o1,Object o2)
{
byte[] b1=(byte[])o1;
byte[] b2=(byte[])o2;
/*for(int i=0;i<b1.length;i++)
{
   int  s1=b1[i]&0xff;
   int  s2=b2[i]&0xff;
   if(s1>s2)
return 1;
   else if(s1<s2)
  return -1;
}
return 0;*/
BigInteger bi1=new BigInteger(b1);
BigInteger bi2=new BigInteger(b2);
return bi1.compareTo(bi2);
}[/code:1]
前提，两个数组长度必须一致。

几点疑问:
这两个数组长度一样吗?
byteArrayLength拿来干吗用,不是可以通过length来取数组长度吗?
某种情况是指哪种情况?

最后问一句, 既然都是正数,为啥要用byte[]而不用char[]呢?
当然char是16位的而byte是8位的,但是byte有正负啊.

BigInteger的内部比较方法：

    /*
     * Returns -1, 0 or +1 as big-endian unsigned int array arg1 is
     * less than, equal to, or greater than arg2.
     */
    private static int intArrayCmp(int[] arg1, int[] arg2) {
if (arg1.length < arg2.length)
    return -1;
if (arg1.length > arg2.length)
    return 1;

// Argument lengths are equal; compare the values
for (int i=0; i<arg1.length; i++) {
    long b1 = arg1[i] & LONG_MASK;
    long b2 = arg2[i] & LONG_MASK;
    if (b1 < b2)
return -1;
    if (b1 > b2)
return 1;
}
return 0;
    }

也是逐个比较。

不知道 long, int, short, char, byte 等类型的比较速度，差别大不大。

这种顺序比较的效率，确实值得关注。我有一个帖子，讨论QueryKey的SQL String 的比较速度。不过我用的是拆分SQL本身，和这个算法无关了。
很期待大家的讨论，也期待楼主一步步展示优化的过程。:-)

数组的长度是一致的，也就是参数中int byteArrayLength的值。
不过，我说老火，你一句new BigInteger，我原来的程序就可以运行好几次了。


数组长度一致。
某些情况是指我程序在收到某些客户计算请求时，Comparator.compare要运行tens of millions次

1.因为byte省空间。2.因为要比较的数据本来就是byte数组。


这个测试我做过，差别还是满大的。int最快，byte,short,稍慢，long是最慢了，大约比int慢三四倍。

可以这样比较:
1,先判断是否相等,如果不等则继续到2;
2,再判断如果符号不同,是一个正一个负,那么负的大
3,如果符号相同,那么取绝对值比较,绝对值大的就大,这一步也可以细分为都是正的和都是负的两种分别来处理,看哪个的效率高.

1不错。
2,3怎么做？
mochow，这个代码很简单的，你就写两句吧。有代码大家好讨论点。

最后两步还可以改进一下,改为如果不相等,那么只用判断如果都是正的则大的大,
否则小的大.
[code:1]    public int compareTo1(Object o1,Object o2)
       {
          
           byte[] b1 = (byte[]) o1;
           byte[] b2 = (byte[]) o2;
           for(int i=0;i<b1.length;i++) {
               if(b1[i]==b2[i]){
                   continue;
               }
               else if(b1[i]>0&&b2[i]>0){
                       if(b1[i]>b2[i]){
                           return 1;
                       }
                       else{
                           return -1;
                       }
                }
                else{
                    if (b1[i] > b2[i]) {
                        return -1;
                    }
                    else{
                        return 1;
                    }
                }
           }
           return 0;
       }

[/code:1]

good.mochow.
在我的机器上，我测试了一下。
楼顶我的方法所用时间是1472，你的是1232.优化了大约10％。
我的第一次优化和你的差不多，大约是1151。
[code:1]
  class byte3 implements Comparator
  {
    public int compare(Object o1,Object o2)
    {
      byte[] b1=(byte[])o1;
      byte[] b2=(byte[])o2;
      for(int i=0;i<b1.length;i++)
      {
        if(b1[i]!=b2[i])
          return (b1[i]&0xff)-(b2[i]&0xff);
      }
     return 0;
    }
  }
[/code:1]

我最终的优化版本时间是641.