|
锁定老帖子 主题：给大家娱乐一下，优化一个简单的算法
精华帖 (0) :: 良好帖 (0) :: 新手帖 (0) :: 隐藏帖 (0)
|
|
|---|---|
| 作者 | 正文 |
|
发表时间：2005-03-16
我先声明，这个算法本身简单，但要优化，就不是那么简单了。为啥，因为它太简单了。
要求是返回一个Comparator，该Comparator能比较两个byte数组的大小。byte数组大小的定义是:数组中每一个byte都是无符号的整数。即0xff不是-128，而是255；按数组中byte的顺序比较对应byte，如果相等，则比较下一个，如果不等，则byte数值大的数组为大。 byte数组的长度可以肯定是在1-50之间。 byte数组的长度在 getByteArrayComparator方法的参数中可以得到，也就是 int byteArrayLength. 这是我工作中遇到的一个真实问题。下面的code是我最初的算法。由于这个算法在某种情况下成为我程序中的瓶颈，因此我花了很大力气优化它，一共优化了三次。优化三次后的算法应该是非常快的算法了。 大家可以畅所欲言。任何理论上的算法优化都欢迎，但不要谈什么C啊汇编啊的。
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;
}
}
声明：ITeye文章版权属于作者，受法律保护。没有作者书面许可不得转载。
推荐链接
|
| 返回顶楼 | |
|
发表时间：2005-03-16
octfor 写道 我先声明，这个算法本身简单，但要优化，就不是那么简单了。为啥，因为它太简单了。
要求是返回一个Comparator，该Comparator能比较两个byte数组的大小。byte数组大小的定义是:数组中每一个byte都是无符号的整数。即0xff不是-128，而是255；按数组中byte的顺序比较对应byte，如果相等，则比较下一个，如果不等，则byte数值大的数组为大。 byte数组的长度可以肯定是在1-50之间。 byte数组的长度在 getByteArrayComparator方法的参数中可以得到，也就是 int byteArrayLength. 这是我工作中遇到的一个真实问题。下面的code是我最初的算法。由于这个算法在某种情况下成为我程序中的瓶颈，因此我花了很大力气优化它，一共优化了三次。优化三次后的算法应该是非常快的算法了。 大家可以畅所欲言。任何理论上的算法优化都欢迎，但不要谈什么C啊汇编啊的。
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 test 过。 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);;
}
前提，两个数组长度必须一致。 |
| 返回顶楼 | |
|
发表时间：2005-03-16
几点疑问:
这两个数组长度一样吗? byteArrayLength拿来干吗用,不是可以通过length来取数组长度吗? 某种情况是指哪种情况? 最后问一句, 既然都是正数,为啥要用byte[]而不用char[]呢? 当然char是16位的而byte是8位的,但是byte有正负啊. |
| 返回顶楼 | |
|
发表时间：2005-03-16
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本身，和这个算法无关了。 很期待大家的讨论，也期待楼主一步步展示优化的过程。:-) |
| 返回顶楼 | |
|
发表时间：2005-03-16
firebody 写道 给出一个思路，没有code test 过。 BigInteger bi1=new BigInteger(b1);; BigInteger bi2=new BigInteger(b2);; return bi1.compareTo(bi2);; } 前提，两个数组长度必须一致。 数组的长度是一致的，也就是参数中int byteArrayLength的值。 不过，我说老火，你一句new BigInteger，我原来的程序就可以运行好几次了。 mochow 写道 几点疑问:
这两个数组长度一样吗? byteArrayLength拿来干吗用,不是可以通过length来取数组长度吗? 某种情况是指哪种情况? 最后问一句, 既然都是正数,为啥要用byte[]而不用char[]呢? 当然char是16位的而byte是8位的,但是byte有正负啊. 数组长度一致。 某些情况是指我程序在收到某些客户计算请求时，Comparator.compare要运行tens of millions次 1.因为byte省空间。2.因为要比较的数据本来就是byte数组。 buaawhl 写道 不知道 long, int, short, char, byte 等类型的比较速度，差别大不大。 这个测试我做过，差别还是满大的。int最快，byte,short,稍慢，long是最慢了，大约比int慢三四倍。 |
| 返回顶楼 | |
|
发表时间：2005-03-16
可以这样比较:
1,先判断是否相等,如果不等则继续到2; 2,再判断如果符号不同,是一个正一个负,那么负的大 3,如果符号相同,那么取绝对值比较,绝对值大的就大,这一步也可以细分为都是正的和都是负的两种分别来处理,看哪个的效率高. |
| 返回顶楼 | |
|
发表时间：2005-03-16
mochow 写道 可以这样比较:
1,先判断是否相等,如果不等则继续到2; 2,再判断如果符号不同,是一个正一个负,那么负的大 3,如果符号相同,那么取绝对值比较,绝对值大的就大 1不错。 2,3怎么做？ mochow，这个代码很简单的，你就写两句吧。有代码大家好讨论点。 |
| 返回顶楼 | |
|
发表时间：2005-03-16
最后两步还可以改进一下,改为如果不相等,那么只用判断如果都是正的则大的大,
否则小的大. 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;
}
|
| 返回顶楼 | |
|
发表时间：2005-03-16
引用 数组中每一个byte都是无符号的整数。
|
| 返回顶楼 | |
|
发表时间：2005-03-16
good.mochow.
在我的机器上，我测试了一下。 楼顶我的方法所用时间是1472，你的是1232.优化了大约10％。 我的第一次优化和你的差不多，大约是1151。
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;
}
}
我最终的优化版本时间是641. |
| 返回顶楼 | |
