- 可以添加未知数量的字符串,而不会因为调整大小而变慢
- 可以按添加顺序读取元素
(另一种解决方案是使用属性跟踪字典树中的字符串数量,但由于我只想返回字典树的一部分,这也不是完美的解决方案)
LinkedList<string>
对我来说似乎是很好的选择...
访问任意元素开销较大,这通常是不使用它的原因...但在你的情况下似乎不是问题。
LinkedList
可能表现出更稳定的添加时间,但插入许多元素时 LinkedList
的整体性能似乎略逊于 ArrayList
。(请参见我的答案以获取一些基准测试结果。)使用迭代器迭代 LinkedList
也稍微慢一些(使用显式索引迭代会更慢);跟随引用不如索引数组快。 - Ted HoppArrayList通常比LinkedList快。如果您未指定适当的大小,则每次容量耗尽时,它都将不得不重新分配一个新数组(大小加倍),并将元素复制到新数组中。
您可以使用LinkedList来避免这个成本,但平均时间可能会更长。
无论使用哪种集合,如果内存不足,则GC将触发,这可能还会引入一些延迟。在任何内存中的集合中,"未知数量"而没有任何限制是不可能存储的。如果"未知"可能非常非常大并禁止使用内存中的集合,则必须使用文件或数据库。
两个明显的选择是ArrayList
和LinkedList
。 LinkedList
似乎比ArrayList
稍微慢一些。这是我的基准测试代码:
import java.util.*;
public class ListTest {
private static final int N = 50000;
private static final float NANO_TO_MILLI = 1.0e-6f;
public static void main(String[] args) {
String[] strings = new String[N];
for (int i = 0; i < N; ++i) {
strings[i] = Integer.toString(i);
}
System.out.print("ArrayList: ");
benchmark(strings, new ArrayList<String>());
System.out.print("LinkedList: ");
benchmark(strings, new LinkedList<String>());
}
private static void benchmark(String[] strings, List<String> list) {
// measure how long it takes to add the strings
long start = System.nanoTime();
for (String s : strings) {
list.add(s);
}
long addTime = System.nanoTime() - start;
// measure how long it takes to iterate the list
start = System.nanoTime();
int i = 0;
for (String s : list) {
++i;
}
long iterateTime = System.nanoTime() - start;
// report the results
System.out.println(String.format("add: %.2fms; iterate: %.2fms (%d strings)",
addTime * NANO_TO_MILLI,
iterateTime * NANO_TO_MILLI,
i));
}
}
下面是一次典型运行的结果:
ArrayList:添加:5.52毫秒;迭代:7.66毫秒(50000个字符串)
LinkedList:添加:7.79毫秒;迭代:8.32毫秒(50000个字符串)
这是在一台装有Intel Core2 Quad Q6600 2.4GHz处理器的Windows机器上进行的。
请注意,这只测量了总时间。它没有测量单个字符串添加时间的变化,我预计ArrayList
比LinkedList
更高,因为需要重新分配内部数组。
编辑:如果我修改main
来重复五次测试,并在每次调用benchmark
后调用System.gc()
,那么我会得到一些有趣的结果:
ArrayList:添加:5.84毫秒;迭代:7.84毫秒(50000个字符串)
LinkedList:添加:7.24毫秒;迭代:8.27毫秒(50000个字符串)ArrayList:添加:0.45毫秒;迭代:0.60毫秒(50000个字符串)
LinkedList:添加:0.84毫秒;迭代:5.35毫秒(50000个字符串)ArrayList:添加:0.52毫秒;迭代:0.72毫秒(50000个字符串)
LinkedList:添加:0.81毫秒;迭代:5.57毫秒(50000个字符串)ArrayList:添加:3.77毫秒;迭代:0.71毫秒(50000个字符串)
LinkedList:添加:3.35毫秒;迭代:0.93毫秒(50000个字符串)ArrayList:添加:3.39毫秒;迭代:0.87毫秒(50000个字符串)
LinkedList:添加:3.38毫秒;迭代:0.86毫秒(50000个字符串)
这可能是由于CPU缓存引起的。请注意,对于添加字符串,LinkedList
可能会稍微快一些(例如,最后两次迭代),尽管它也可能慢得多。迭代对于LinkedList
来说也可能极其缓慢,这也可能是由于局部性不足所致。
使用List
接口的实现。通常认为ArrayList
是最好的通用集合,因此对于存储字符串,可以做一些简单的事情:
List<String> stringList = new ArrayList<String>();