现在需要从一个文件中读取数据到一个数组中，数组的大小要到读完文件才能确定大小。最终结果可能数组会比较大也可能比较小，因此需要动态的分配一个数组。如果先分配100个长度的数组，如果读取时发现数组小了，就分配一个长度为200的数组，还小就分配个长度为300。将前一个数组拷贝过来，并丢弃前一个数组。结束时，再将得到的数组多余部分裁掉。这样的方法似乎比较低效，并且可能会比较消耗内存，因此想请问各位有没有比较高效的方法解决这个问题？
调试欢乐多
如果使用数据结构，由于java没有指针，要使用类实现，这样将更低效。
我的实现方法就是参照了ArrayList实现,ArrayList本来就比较低效。采用二倍扩容的话会比较耗内存，而且这个数值应该不用二倍怎么多，所以采用每次增加100。
System类的静态方法吧，
arraycopy(Object src, int srcPos, Object dest, int destPos, int length)
最简单的办法，首先你一切一切问题的源头是你不知道该分配多大的byte数组.对吧.
反过来说，如果你知道该分多大，一切一切的后面的考虑都不需要了. 所以那么就有
public static byte[] readFully(File f) throws IOException {
RandomAccessFile raf = new RandomAccessFile(f, "r");
// detertmine file length; if the file is too long, only retreive first Integer.MAX_VALUE
long llen;
int len;
llen = raf.length();
if (llen > Integer.MAX_VALUE) {
len = Integer.MAX_VALUE;
}else {
len = (int) llen;
}
byte[] bs = new byte[len];
raf.readFully(bs);
raf.close();
return bs;
}
如果你真的不知道大小，那ArrayList *2的方案其实比你想象的有效。你可以先试一试
我没有说高效，只是每次加100可以更节省内存。实际情况是读取一个png图片，而其中的IDAT块可能会有多块，但IDAT的块应该不会太大。测试了一个1920 * 5384的图片，有104块。当然这可能是个特例,再大应该也不会大到哪里去。因此采用每次加100。有哪位知道png的IDAT块是否有最大限制?
其中每个IDAT的大小也可能不固定。（IDAT看上面的解释）
http://book.51cto.com/art/200903/112741.htm
这个相当详细。
就平均情况而言，ArrayList中的二倍扩充一定比你每次增加100效率要高的多。
(1) 当数据数量比较少的情况下，每次扩充两倍也不会消耗多少内存的。逼近小数据量 乘以2 也不会大到哪去。
(2) 如果数据量比较大的话，那么开辟新数组并转移老数组的数据这个过程严重制约算法的效率。而每次增加100一定会照成数据转移(System.arraycopy)的次数远远大于2倍增长。或许真假100在运行过程中节约内存浪费的概率比较大。但是程序运行完毕以后也不会有太多影响，我们可以使用trimToSize()方法。
public class IntNode{
public int info;
public IntNode next;
public IntNode(int i){
this(i);
}
public IntNode(int i, IntNode n){
info = i;
next = n;
}}
实现，如果不是倒要请教楼上使用的是什么方法.创建对象时都要new，这当然都需要时间的。
数组是号称对象，但在底层实现的效率肯定要比上层实现的高。
没看Java源代码，这也是猜测。但对象里不含另一对象，肯定效率会更高。
按照PNG的格式，每一块的数据都是有规律的（除了PNG标记头的8字节外）
对于每一块，先是4字节的长度，然后是4字节块标志(比如'IDAT','IHDR')
然后是块内容，长度即为前面4字节标志的长度，然后是4字节的CRC32校验码因此就可以通过先读长度，然后分配好byte[]的长度，然后读取即可
18楼有说，另外就像他们说的，如果能获得所需资源大小就直接分配了
现在的问题就是事先不知道数组将是多大，否则也就没有这一问题了。因此png文件格式在这方面不太合理。像bmp就有标识数据大小的标识。Java手册里有：
add 操作以分摊的固定时间 运行，也就是说，添加 n 个元素需要 O(n) 时间。
O(n)的时间复杂度就是比较低效的。记得看过C++里面实现ArrayList就是以翻倍的形式扩展数组。
public static native void arraycopy();
至于内存，java本身就是个耗内存的主，呵呵。
* Increases the capacity of this <tt>ArrayList</tt> instance, if
* necessary, to ensure that it can hold at least the number of elements
* specified by the minimum capacity argument.
*
* @param minCapacity the desired minimum capacity
*/
public void ensureCapacity(int minCapacity) {
modCount++;
int oldCapacity = elementData.length;
if (minCapacity > oldCapacity) {
Object oldData[] = elementData;
int newCapacity = (oldCapacity * 3)/2 + 1;
if (newCapacity < minCapacity)
newCapacity = minCapacity;
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
}
算法时间复杂度是常数级O(1)或对数级O(log)比如对半查找。那是最好的。如果已知数组的长度分配内存就是常数级的。ArrayList的实现应该有多种方法，Java可能不是*2，这要看源代码。呵呵。
当然有。我前面说了。Java手册里ArrayList的add方法有说明：
add 操作以分摊的固定时间运行，也就是说，添加 n 个元素需要 O(n) 时间。数组在已知长度分配空间是常量级，当然不包括动态添加。所以就是要问一下有没有更高效的。或者是我所说的实际情况下，读取png文件的IDTA情况下有没有比动态分配空间更高效
如果是的话，前面说的#23就好了，
要不，你也可也考虑一个，每100个字节一个单位数组，不够的话创建另外一个 100 字段的数组，用另外一个 LinkedList 把这些数组装起来。这样就不需要在内存中复制数据。
如果我理解的没错，你现在的情况有两点.
第一个是 一个png文件里一共有多少chunk，无法知道.
第二个是每一个chunk的大小都不一样。这两个都是未知大小，所以你需要分别考虑这两种未知大小的分配。第一个没有很好的办法，因为png格式设计来的就是用链的形式的来存储块，png的结束是用一个IEND块来表式的。所以你没可能一上来就知道大小，而*只能*选取一个容器来跟踪。希望你同意这个观点.那么用容器跟踪的话，紧接着那么一般最关心的确就是容器的效率问题。首先有一点，对增，删，查，改，任何一个容器（这里是List)的实现这几个操作的效率都不会同时最高。
要么增，删好，查改差， 要么查改好，增删差。我想个你也同意.这样的话，那么这就是一个权衡，你要看看你的case到底是想到什么，天下没有免费的午餐，你要这个就得牺牲那个。你有的只是选择权. 下面这个三个是,纯大多数的实用的选择范围
java.util.ArrayList - 数组实现
java.util.LinkedLIst - 链表实现
org.apache.commons.collections.list.TreeList - 自平衡二叉树实现 O(log n) for add/remove它们的比较测试数据如下，
[code]
get add insert iterate remove
* TreeList 3 5 1 2 1
* ArrayList 1 1 40 1 40
* LinkedList 5800 1 350 2 325
[/code]
你看看你的case,选一个吧 :P
第二个问题相对来说比较简单，一个块的大小不是固定的这个没有错。
但是png块的设计里，一个块的长度可以很容易知道。你那个link.
[code]
块数据块定义 : **块数据长度(4bytes)**，块标志(4bytes)，块数据， 块CRC校验码(4bytes)
[/code]那这样就是知道大小的情形, 就比较好办. 你定义一个Chunk类,直接读成byte[].
直接用问题1里你选好的List<Chunk>来来跟踪读入就好示意代码:
class Chunk {int size;
int flag;
int crc;
byte[] data; void read(LittleEndianObjectInputStream ois) {
size = ois.readInt();
flag = ois.readInt();
data = new byte[size];
ios.readFully(data);
crc = ios.readInt();
} }public static List<Chunk> readPngFile(LittleEndianObjectInputStream is) {
readPngFileHeader(is);
Chunk c;
List<Chunk> chunks = new TreeList<Chunk>(); // 我这里用TreeSet
while(true) {
c = new Chunk();
c.read(is);
chunks.add(c);
if (c.size==0) // we met the IEND
break;
}
return chunks
}
我想你应该是真正来寻找你的问题答案来的,希望我的回复对你有用.
* get add insert iterate remove
* TreeList 3 5 1 2 1
* ArrayList 1 1 40 1 40
* LinkedList 5800 1 350 2 325
感谢热心回复。你的理解没错。我是想知道是否有比ArrayList方式更高效的方法。我感觉没必要使用ArrayList一样会很简单。判断一下数据是否超出，超出利用一个数组和System.arraycopy调整一下。最后再利用System.arraycopy裁剪一下就可以了。效率应该与ArrayList差不多。* get add insert iterate remove
* TreeList 3 5 1 2 1
* ArrayList 1 1 40 1 40
* LinkedList 5800 1 350 2 325这个数据里我觉得TreeList里的insert、remove操作（单纯操作不包括查找节点）应该和LinkedList里的一样。差异应该在查找节点上。
这个不就是 ArrayList的实现方面吗:) ，你愿意自己写一个也行啊
应该是的。 LinkedList的查找很费时，而且add虽然很好，但insert的时候也要先查找再add.不知道你是否会有 insert/remove操作 ， 如果只是add和 iterate操作的话, LinkedList无疑是最好的选择.另外大部分情况下ArrayList都是很好 的选择。除了一个情况：
就是你有大量的中间元素的insert和remove，这个时候TreeList优于ArrayList.看TreeList里的关于 三个list的说明。
* <code>ArrayList</code> is a good general purpose list implementation.
* It is faster than <code>TreeList</code> for most operations except inserting
* and removing in the middle of the list. <code>ArrayList</code> also uses less
* memory as <code>TreeList</code> uses one object per entry.
* <p>
* <code>LinkedList</code> is rarely a good choice of implementation.
* <code>TreeList</code> is almost always a good replacement for it, although it
* does use sligtly more memory.
不涉及add、remove这么多操作，只是读取数据，所以就没用ArrayList。
确定了数组长度以后不变了的，分配就是O(1)。ArrayList里add是每次操作是O(1)，而n次add操作就是O(n)。
数组除非是引用赋引用这样算O(1)，如
int[] a = {...};
int[] b = {...};
a = b;
其它情况如果单个元素逐个赋值，n个元素不也是O(n)吗？
不要盯住一个n一个数组确定长度比如100，那O(100)其实就是O(1)在算法复杂度里没有O(100)这样的说法，那是便于理解写的O(100)，所以就算O(1000)也是O(1),只要O(n)中的n是确定的，那O(n)就变为常量级的。常量级的时间复杂度就是算法每次花费的时间是固定的。
唉，不看你们形而上学了……TreeList 就是对数级的, 二叉平衡查找是对数级的
LinkedList 是对直接append和iterate是O(1) , 定点insert是O(n)
ArrayList 根据你的增长算法求均算算看吧。言止于此