英文:
Why a list size lower than COPY_THRESHOLD means it is a arraylist?
问题
在java.util.Collections包中，这是关于copy函数的源代码：
public static <T> void copy(List<? super T> dest, List<? extends T> src) {
int srcSize = src.size();
if (srcSize > dest.size())
throw new IndexOutOfBoundsException("Source does not fit in dest");
if (srcSize < COPY_THRESHOLD ||
(src instanceof RandomAccess && dest instanceof RandomAccess)) {
for (int i=0; i<srcSize; i++)
dest.set(i, src.get(i));
} else {
ListIterator<? super T> di=dest.listIterator();
ListIterator<? extends T> si=src.listIterator();
for (int i=0; i<srcSize; i++) {
di.next();
di.set(si.next());
}
}
}
如果src列表的大小小于COPY_THRESHOLD，即 srcSize < COPY_THRESHOLD，那么它是一个ArrayList。我不知道为什么。
英文:
In package java.util.Collections, here is the source code about copy function:
public static <T> void copy(List<? super T> dest, List<? extends T> src) {
int srcSize = src.size();
if (srcSize > dest.size())
throw new IndexOutOfBoundsException("Source does not fit in dest");
if (srcSize < COPY_THRESHOLD ||
(src instanceof RandomAccess && dest instanceof RandomAccess)) {
for (int i=0; i<srcSize; i++)
dest.set(i, src.get(i));
} else {
ListIterator<? super T> di=dest.listIterator();
ListIterator<? extends T> si=src.listIterator();
for (int i=0; i<srcSize; i++) {
di.next();
di.set(si.next());
}
}
}
And if the src list size lower than COPY_THRESHOLD srcSize < COPY_THRESHOLD,then it is a arraylist.I don't know why.
答案1
得分: 2
这是一个诡计性的问题 - 它不会假设这是一个数组列表。如果它这样做了，你会知道，因为它可能会将其强制转换为 ArrayList。
相反，原因很可能是效率。List 的两种最常见的变体是 ArrayList 和 LinkedList；ArrayList 支持随机访问，因此访问任何单独的元素都同样快速，但 LinkedList 则不是，所以距离前面的任何元素越远，所需时间越长。
如果列表支持随机访问（这意味着访问任何元素的效率都与访问其他任何元素一样），那么将列表 A 复制到列表 B 的最快方法很可能是简单地使用 get() 和 set() 来操作相关索引。这就是条件 (src instanceof RandomAccess && dest instanceof RandomAccess) 所检查的。
如果列表不是随机访问的，例如链表或其他类型的列表，那么通过 get() 和 set() 在中间访问元素很可能效率低下。因此，Java 使用迭代器，逐个复制元素。这就是条件的 else 块。
问题在于，创建列表迭代器并使用它们进行迭代需要开销时间，如果你使用原始的 int，则不需要花费这些时间。如果你的链表足够小 - 也就是说，你需要复制的所有项都靠近前面 - 那么使用 get() 和 set() 可能仍然比使用迭代器更快。这就是条件 srcSize < COPY_THRESHOLD 所检查的。可以假设 COPY_THRESHOLD 是一个常数，根据 Java 开发人员基于实验确定的，以便始终选择最快的方法。
英文:
It's a trick question - it doesn't assume it's an array list. You would know if it did, because it would do a cast to ArrayList, probably.
Instead, the reason is likely efficiency. The two most common varieties of List are ArrayList and LinkedList; ArrayList is random-access, so getting to any individual element is equally fast, but LinkedList is not, so the further from the front any element is, the longer it takes.
If the list is random-access (which is to say, accessing any element is as efficient as accessing any other), then it makes sense that the fastest way to copy list A over to list B would be to simply get() and set() the relevant indices. This is what the condition (src instanceof RandomAccess && dest instanceof RandomAccess) checks.
If a list is not random-access, so is a linked list or some other type of list, then accessing elements in the middle via get() and set() is likely to be inefficient. So, Java uses iterators instead, copying elements one at a time. This is the else block of the conditional.
The problem with that, is that creating the list iterators, and iterating with them, requires overhead time that you wouldn't need to spend if you were using a primitive int. If your linked list is small enough - so, all the items you need to copy are close to the front - then it's probably still faster to use get() and set() than it is to use iterators. This is what the condition srcSize < COPY_THRESHOLD checks. Presumably, COPY_THRESHOLD is a constant that's been determined by the Java developers based on experimentation, so that the quickest approach is always chosen.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论