算法之---数组动态扩容

最近几天做项目，遇到些比较棘手的问题，本来是上游系统接口数据可以送正确的，但是耍无赖不给送，导致我们自己的处理。因为是外网系统接口处理数据，接收到的是xml文件，而我们程序采用xmlbean对xml进行解析，于是会出现数组的情况。

产生问题的原因为，对于存在关系的xml中，当前xml会有个组信息的节点，通常关系为两两的关系，而如何识别他们是有关系的呢，考的是一个唯一id，也就是xml1中的组信息中有个这个id，xml2的组信息中也存在这个id，这样就可以建立关系了，如果有第三个关系，那么就是另外一个id了。而现在由于上游系统的恶心人畜，如3个xml有关系，那么这三个xml的组id是一样的，其中的一个xml中维护两套关系，如a、b、c，b要维护和a的关系，也要维护和c的关系，那么在c中就有两组信息，这就导致原两两关系的逻辑被打破，导致数据处理上的异常。

于是在对原逻辑的处理中，通过简单的if，for无法正确处理数据。并且过程中用的是数组，其实主要的问题在于b这个信息中的两套关系。因为要把具有两套关系的数据进行特殊处理，而其中还存在其它类型的组信息，所以在数组中可能存在不是同类型的组信息，为了保证大于2组的信息处理的正确性，于是通过数组copy的方式将需要的信息copy到信息的数组，由于数组大小不定，而且不能有空的元素，于是采用了动态扩容的方式。下面摘取代码片段并附说明

 

 

//原数组soGroupInfoArr，元素类型为SOGROUPINFO，长度≥1 
SOGROUPINFO[] newGroupInfo = new SOGROUPINFO[1];//声明长度为1的数组，用于数组copy
int j = 0;
for (int i = 0; i < soGroupInfoArr.length; i++) {
     groupSpecId = soGroupInfoArr[i].getGROUPTYPEID();
     if ((groupSpecIdForShareLine).indexOf(groupSpecId) != -1) {//这里是对数据的特殊判断，可以忽略
         if (j == newGroupInfo.length) {//往数组中加数据先判断数组是否满了，满了就扩容
  	         SOGROUPINFO[] arrays2 = new SOGROUPINFO[newGroupInfo.length + 1];//扩容，这里每次扩1，保证元素不存在空的
  	         System.arraycopy(newGroupInfo, 0, arrays2, 0, newGroupInfo.length);//数组copy
  	         newGroupInfo = arrays2;//将拷贝的数据赋值给扩容后的数组
  	     }
  						
  	     newGroupInfo[j++] = soGroupInfoArr[i];//将数据放到数组中
     }
}
 
soGroupInfoArr = newGroupInfo;//将处理完的数组赋值给原数组便于原逻辑复用    

 

 

 

突然发现有些算法还有有用的。哈哈，记下来

评论

11 楼 黑小子 2012-10-12  

leonayx123 写道

arraylist 本质还是数组，他自己的扩容也是把原数组 按一定比例（乘三除2什么的）创建一个新数组后。把原数组复制过来。

你非要自己写可以参考一下这个扩容比例。有时多几个空位其实没有关系。所以每次扩1不好。

主要是不能有空位,而且以现有逻辑不想做太大改动，所以初始1，扩1

10 楼 黑小子 2012-10-12  

godlewis 写道

每次扩1，来一次新数组的创建和数组复制，造成内存对象频繁创建与遍历，性能不好。建议采用ArrayList，先将可扩展的内容加完后，最后统一toArray一下，ArrayList的扩容算法比你的好。

这个说的不错。确实可以使用arraylist.toArray，但是对于现有的项目不想做太大的改动，而且这个数组容量最大值也就是2.所以才初始为1，

9 楼 crazoy 2012-08-28  

恰好刚看过ArrayList的源码，建议lz也看一下。参考一下

8 楼 sj0129 2012-08-24  

我倒。。。。。。。。。。。。 不解释。

7 楼 vieri122 2012-08-24  

楼主多看看书吧。

6 楼 Allen_Wang 2012-08-24  

godlewis 写道

每次扩1，来一次新数组的创建和数组复制，造成内存对象频繁创建与遍历，性能不好。建议采用ArrayList，先将可扩展的内容加完后，最后统一toArray一下，ArrayList的扩容算法比你的好。

是的，这种算法只能玩玩而已。

5 楼 mynewstudy 2012-08-24  

这完全就是数组扩容的底层实现啊

4 楼 leonayx123 2012-08-24  

arraylist 本质还是数组，他自己的扩容也是把原数组 按一定比例（乘三除2什么的）创建一个新数组后。把原数组复制过来。

你非要自己写可以参考一下这个扩容比例。有时多几个空位其实没有关系。所以每次扩1不好。

3 楼 zhowg 2012-08-24  

扩容完全可以用ArrayList，再接收和返回的时候再转换为数组，没必要这么麻烦。

2 楼 liguocai2009 2012-08-24  

这也叫算法，我瞎掉了

1 楼 godlewis 2012-08-24  

每次扩1，来一次新数组的创建和数组复制，造成内存对象频繁创建与遍历，性能不好。建议采用ArrayList，先将可扩展的内容加完后，最后统一toArray一下，ArrayList的扩容算法比你的好。