我们如何动态分配和增长数组
我正在研究一个项目,但我不能使用任何现有的java数据结构(即ArraysList,树等)
我只能使用数组。 因此,我需要使用新内存动态更新数组。
我正在读取文本文件,并为arrays内存预先分配100:
String [] wordList; int wordCount = 0; int occurrence = 1; int arraySize = 100; wordList = new String[arraySize]; while ((strLine = br.readLine()) != null) { // Store the content into an array Scanner s = new Scanner(strLine); while(s.hasNext()) { wordList[wordCount] = s.next(); wordCount++; } }
现在这适用于100个以下列表项。 br.readline是遍历文本文件每一行的缓冲读取器。 我有它然后将每个单词存储到列表中然后递增我的索引(wordCount)。
但是,一旦我有一个包含超过100个项目的文本文件,我就会收到分配错误。
如何动态更新此arrays(从而重新发明轮子)?
谢谢!
你可以这样做:
String [] wordList; int wordCount = 0; int occurrence = 1; int arraySize = 100; int arrayGrowth = 50; wordList = new String[arraySize]; while ((strLine = br.readLine()) != null) { // Store the content into an array Scanner s = new Scanner(strLine); while(s.hasNext()) { if (wordList.length == wordCount) { // expand list wordList = Arrays.copyOf(wordList, wordList.length + arrayGrowth); } wordList[wordCount] = s.next(); wordCount++; } }
使用java.util.Arrays.copyOf(String[])
基本上做同样的事情:
if (wordList.length == wordCount) { String[] temp = new String[wordList.length + arrayGrowth]; System.arraycopy(wordList, 0, temp, 0, wordList.length); wordList = temp; }
除了它是一行代码而不是三行。 🙂
您分配一个新的Array(例如,容量加倍),并将所有元素移动到它。
基本上你需要检查wordCount
是否即将命中wordList.size()
,当它执行时,创建一个长度是前一个数组长度两倍的新数组,并将所有元素复制到它(创建一个辅助方法来执行此操作) ),并将wordList
分配给您的新数组。
要复制内容, 可以使用System.arraycopy
,但我不确定是否允许使用您的限制,因此您可以逐个复制元素:
public String[] createNewArray(String[] oldArray){ String[] newArray = new String[oldArray.length * 2]; for(int i = 0; i < oldArray.length; i++) { newArray[i] = oldArray[i]; } return newArray; }
继续。
看一下Java ArrayList的实现。 Java ArrayList
内部使用固定大小的数组,并在元素数量超过当前大小时重新分配数组。 您也可以在类似的行上实现。
你不能动态地增加数组大小,更好地复制到新array
。 使用System.arrayCopy
,它比将每个元素复制到新数组更好。 供参考为什么System.arraycopy在Java中是原生的? 。
private static Object resizeArray (Object oldArray, int newSize) { int oldSize = java.lang.reflect.Array.getLength(oldArray); Class elementType = oldArray.getClass().getComponentType(); Object newArray = java.lang.reflect.Array.newInstance( elementType, newSize); int preserveLength = Math.min(oldSize, newSize); if (preserveLength > 0) System.arraycopy(oldArray, 0, newArray, 0, preserveLength); return newArray; }
您必须手动创建一个新的更大的数组并复制项目。
这可能有所帮助
Visual Basic有一个很好的function: ReDim Preserve
。
有人写了一个等价函数 – 你可以在这里找到它。 我认为它完全符合您的要求(而且您不是在重新发明轮子 – 您正在复制别人的……)
让我们假设你有一个1元素的数组,并且想要扩展大小以动态容纳100万个元素。
情况1:
String [] wordList = new String[1]; String [] tmp = new String[wordList.length + 1]; for(int i = 0; i < wordList.length ; i++){ tmp[i] = wordList[i]; } wordList = tmp;
案例2(通过加法因子增加大小):
String [] wordList = new String[1]; String [] tmp = new String[wordList.length + 10]; for(int i = 0; i < wordList.length ; i++){ tmp[i] = wordList[i]; } wordList = tmp;
案例3(通过乘法因子增加大小):
String [] wordList = new String[1]; String [] tmp = new String[wordList.length * 2]; for(int i = 0; i < wordList.length ; i++){ tmp[i] = wordList[i]; } wordList = tmp;
当动态扩展数组的大小时,使用Array.copy或迭代数组并使用for循环将元素复制到新数组,实际上迭代数组的每个元素。 这是一项昂贵的操作。 Array.copy将是干净和优化的,仍然很昂贵。 所以,我建议用乘法因子增加数组长度。
它是如何帮助的,
在案例1中,为了容纳100万个元素,你必须增加100万个数组的大小 - 1倍,即999,999倍。
在案例2中,您必须增加arrays的大小100万/ 10 - 1倍,即99,999次。
在第3种情况下,你必须将数组的大小增加2 1百万 - 1次,即18.9(假设)。
public class Arr { public static void main(String[] args) { // TODO Auto-generated method stub int a[] = {1,2,3}; //let a[] is your original array System.out.println(a[0] + " " + a[1] + " " + a[2]); int b[]; //let b[] is your temporary array with size greater than a[] //I have took 5 b = new int[5]; //now assign all a[] values to b[] for(int i = 0 ; i < a.length ; i ++) b[i] = a[i]; //add next index values to b b[3] = 4; b[4] = 5; //now assign b[] to a[] a = b; //now you can heck that size of an original array increased System.out.println(a[0] + " " + a[1] + " " + a[2] + " " + a[3] + " " + a[4]); } }
上述代码的输出是:
1 2 3
1 2 3 4 5