我必须在内存中保留数千个字符串,以便在Java中串行访问。我应该把它们存储在数组中还是应该使用某种列表?
由于数组将所有数据保存在一个连续的内存块中(与list不同),使用数组存储数千个字符串会导致问题吗?
我必须在内存中保留数千个字符串,以便在Java中串行访问。我应该把它们存储在数组中还是应该使用某种列表?
由于数组将所有数据保存在一个连续的内存块中(与list不同),使用数组存储数千个字符串会导致问题吗?
当前回答
既然这里已经有了很多好的答案,我想给你一些其他的实际观点的信息,这是插入和迭代性能的比较:Java中的基元数组与链表。
这是实际的简单性能检查。因此,结果将取决于机器的性能。
用于此的源代码如下:
import java.util.Iterator;
import java.util.LinkedList;
public class Array_vs_LinkedList {
private final static int MAX_SIZE = 40000000;
public static void main(String[] args) {
LinkedList lList = new LinkedList();
/* insertion performance check */
long startTime = System.currentTimeMillis();
for (int i=0; i<MAX_SIZE; i++) {
lList.add(i);
}
long stopTime = System.currentTimeMillis();
long elapsedTime = stopTime - startTime;
System.out.println("[Insert]LinkedList insert operation with " + MAX_SIZE + " number of integer elapsed time is " + elapsedTime + " millisecond.");
int[] arr = new int[MAX_SIZE];
startTime = System.currentTimeMillis();
for(int i=0; i<MAX_SIZE; i++){
arr[i] = i;
}
stopTime = System.currentTimeMillis();
elapsedTime = stopTime - startTime;
System.out.println("[Insert]Array Insert operation with " + MAX_SIZE + " number of integer elapsed time is " + elapsedTime + " millisecond.");
/* iteration performance check */
startTime = System.currentTimeMillis();
Iterator itr = lList.iterator();
while(itr.hasNext()) {
itr.next();
// System.out.println("Linked list running : " + itr.next());
}
stopTime = System.currentTimeMillis();
elapsedTime = stopTime - startTime;
System.out.println("[Loop]LinkedList iteration with " + MAX_SIZE + " number of integer elapsed time is " + elapsedTime + " millisecond.");
startTime = System.currentTimeMillis();
int t = 0;
for (int i=0; i < MAX_SIZE; i++) {
t = arr[i];
// System.out.println("array running : " + i);
}
stopTime = System.currentTimeMillis();
elapsedTime = stopTime - startTime;
System.out.println("[Loop]Array iteration with " + MAX_SIZE + " number of integer elapsed time is " + elapsedTime + " millisecond.");
}
}
表现结果如下:
其他回答
不要在没有适当基准测试的情况下陷入优化的陷阱。正如其他人建议的那样,在做出任何假设之前使用分析器。
您所列举的不同数据结构具有不同的用途。列表在开头和结尾插入元素时非常有效,但在访问随机元素时却很困难。数组具有固定的存储,但提供快速的随机访问。最后,ArrayList通过允许数组增长来改进与数组的接口。通常,要使用的数据结构应该由如何访问或添加存储的数据来决定。
About memory consumption. You seem to be mixing some things. An array will only give you a continuous chunk of memory for the type of data that you have. Don't forget that java has a fixed data types: boolean, char, int, long, float and Object (this include all objects, even an array is an Object). It means that if you declare an array of String strings [1000] or MyObject myObjects [1000] you only get a 1000 memory boxes big enough to store the location (references or pointers) of the objects. You don't get a 1000 memory boxes big enough to fit the size of the objects. Don't forget that your objects are first created with "new". This is when the memory allocation is done and later a reference (their memory address) is stored in the array. The object doesn't get copied into the array only it's reference.
我建议您使用分析器来测试哪个更快。
我个人的观点是你应该使用列表。
我在一个大型代码库中工作,之前的一组开发人员在任何地方都使用数组。这使得代码非常不灵活。在将大块数据转换为列表后,我们发现速度没有变化。
数组-当我们必须实现更快的结果获取时,它总是更好的
列表——执行插入和删除的结果,因为它们可以在O(1)中完成,这也提供了方便地添加、获取和删除数据的方法。更容易使用。
但是始终记住,当数据存储在数组中的索引位置是已知的时,数据的抓取将是快速的。
这可以通过对数组排序很好地实现。因此,这增加了获取数据的时间(即;存储数据+排序数据+寻找数据所在的位置)。因此,这增加了从数组中获取数据的额外延迟,即使它们可能擅长更快地获取数据。
因此,这可以用三元数据结构或三元数据结构来解决。如上所述,树数据结构在搜索数据时非常有效,对特定单词的搜索可以在O(1)量级上完成。当时间紧迫时;如果你必须快速搜索和检索数据,你可以使用三种数据结构。
如果你希望你的内存空间消耗更少,你希望有一个更好的性能,那么使用三元数据结构。这两个都适合存储大量的字符串(例如;比如字典里的单词)。
List是java 1.5及以上版本的首选方式,因为它可以使用泛型。数组不能有泛型。数组也有预定义的长度,不能动态增长。初始化一个大数组并不是一个好主意。 ArrayList是用泛型声明数组的方式,它可以动态增长。 但如果删除和插入使用得更频繁,那么链表是使用最快的数据结构。
我猜最初的海报来自c++ /STL背景,这引起了一些混乱。在c++中std::list是一个双链表。
在Java中[Java .util]。List是一个不需要实现的接口(c++术语中的纯抽象类)。List可以是一个双重链表——提供了java.util.LinkedList。然而,100次中有99次,当你想要创建一个新的List时,你想要使用java.util.ArrayList来代替,这是c++ std::vector的大致等价。还有其他标准实现,比如java.util.Collections.emptyList()和java.util.Arrays.asList()返回的那些。
从性能的角度来看,不得不通过一个接口和一个额外的对象会有很小的影响,但是运行时内联意味着这很少有任何意义。还要记住String通常是一个对象加数组。所以对于每个元素,你可能有两个其他的对象。在c++ std::vector<std::string>中,虽然按值复制而不使用指针,但字符数组将形成一个string对象(通常不会共享这些对象)。
如果这段代码对性能非常敏感,那么可以为所有字符串的所有字符创建一个char[]数组(甚至byte[]),然后创建一个偏移量数组。IIRC,这是javac的实现方式。