如何有效地将 ArrayList 的 X 项替换为 Y 项(X 可能非常大，并且与 Y 不同)? [英] How to replace X items of ArrayList with Y items (X might be very large, and different from Y) , efficiently?
问题描述
众所周知，如果您想对其进行大量修改(插入/删除)，ArrayList 的性能会很差，因为它在幕后使用了数组.
ArrayList is known to have bad performance in case you want to perform a lot of modifications on it (insert/remove), as it uses an array behind the scenes.
原因是对于每次插入/删除，单元格都被移到一边，因为 ArrayList 在幕后使用了一个简单的数组.
The reason is that for each insert/remove, cells are shifted aside, as ArrayList is using a simple array behind the scenes.
这意味着，例如，如果 ArrayList 中有 N 个项目，并且向其中添加 M 个项目(例如，在开始时)，则可能至少需要 O(N*M) 添加它们.
This means, for example, that if you have N items in the ArrayList, and you add M items into it (say, in the beginning), it might take at least O(N*M) to add them.
这也写在文档中.关于添加:
This is also written in the docs. About addition:
在此列表中的指定位置插入指定元素.移动当前在该位置的元素(如果有)和任何右边的后续元素(在它们的索引上加一).
Inserts the specified element at the specified position in this list. Shifts the element currently at that position (if any) and any subsequent elements to the right (adds one to their indices).
以及关于移除:
删除此列表中指定位置的元素.任意移动左边的后续元素(从它们的索引中减去一).
Removes the element at the specified position in this list. Shifts any subsequent elements to the left (subtracts one from their indices).
这就是为什么简单的添加操作循环是不可能的，因为我可能需要向已经很大的项目列表添加很多项目.
This is why a simple loop of add operation is out of the question, as I might need to add a lot of items to an already large list of items.
我希望能够删除和可选地替换 ArrayList 的项目，即使项目数与原始项目数不同.
I wish to be able to remove and optionally replace items of an ArrayList, even with items count that's different than the original one.
例如:
如果输入是 {0,1,2,3,4,5} 的数组，我可以用 2 个项目99"，100"替换1"项目，所以输出将是 {0,99,100,2,3,4,5}
if the input is an array of {0,1,2,3,4,5}, I could replace the "1" item with 2 items "99","100" so that the output would be {0,99,100,2,3,4,5}
可以像这样删除多个项目:
It is possible to remove multiple items as such:
final ArrayList<Integer> list = new ArrayList<>();
for (int i = 0; i <= 5; ++i)
list.add(i);
// list is {0,1,2,3,4,5}
list.subList(1, 2).clear();
// list is now {0,2,3,4,5}
这比一个一个地删除项目要好，因为我认为这不会移动 ArrayList 对象中数组的单元格.
This is better than removing items one by one, as I think this won't shift the cells of the array within the ArrayList object.
我真正想要的是替换物品，所以这就是我所做的:
What I really want, is to replace items, so this is what I've made :
public static void replaceItems(ArrayList<Integer> list, int fromIndex, int toIndexExcluding, ArrayList<Integer> deltaItems) {
int indexToTakeItemFrom = 0;
Log.d("AppLog", "sizeBefore:" + list.size());
int minEnsuredCapacity = list.size() - (toIndexExcluding - fromIndex) + deltaItems.size();
Log.d("AppLog", "minEnsuredCapacity:" + minEnsuredCapacity);
list.ensureCapacity(minEnsuredCapacity);
//replacing items:
for (int i = fromIndex; i < toIndexExcluding && i < list.size(); ++i) {
if (indexToTakeItemFrom >= deltaItems.size()) {
list.subList(i, toIndexExcluding).clear();
Log.d("AppLog", "size after:" + list.size());
return;
}
list.set(i, deltaItems.get(indexToTakeItemFrom++));
}
//add remaining items
list.addAll(fromIndex + indexToTakeItemFrom, deltaItems.subList(indexToTakeItemFrom, deltaItems.size()));
Log.d("AppLog", "size after:" + list.size());
}
这似乎运作良好.示例:
This seems to work well. Examples:
// list is {0,1,2,3,4,5}
replaceItems(list, 1, 1, deltaList); //nothing to replace, so just add {99,100} to index 1
//list is now {0,99,100,1,2,3,4,5}
// list is {0,1,2,3,4,5}
replaceItems(list, 1, 2, deltaList); //replace {1} with {99,100}
//list is now {0,99,100,2,3,4,5}
// list is {0,1,2,3,4,5}
replaceItems(list, 1, 3, deltaList); //replace {1,2} with {99,100}
//list is now {0,99,100,3,4,5}
// list is {0,1,2,3,4,5}
replaceItems(list, 1, 4, deltaList); //replace {1,2,3} with {99,100}
//list is now {0,99,100,4,5}
在效率方面，由于移位最多进行1-2次，所以应该是O(M+N)，而不是O(M*N)，其中M是要替换的项数，并且N 是列表中当前项目的数量.
In terms of efficiency, since the shifting is done 1-2 times at most, it should be O(M+N), and not O(M*N), where M is the number of items to replace, and N is the number of current items in the list.
我的代码正确吗?我忘记了一些最终情况吗?也许在某些情况下容量计算是错误的?
Is my code correct? Have I forgotten of some end cases? Maybe capacity calculation is wrong in some cases?
subList 是否甚至创建了一个新的 List 对象，从原始对象复制项目?或者它只是在幕后有一些基本的指针，它们的大小是恒定的，所以我不应该担心使用它?
Does subList even create a new List object, copying items from the original? Or does it just have some basic pointers behind the scenes, which are constant in size, so I shouldn't worry about using it?
考虑到我使用 ArrayList，这是我能做出的最有效的方法吗?是否有更好的 API 用于此目的?有没有办法简化它的工作原理?我的代码是否仅在真正需要时才移动单元格，并且最多只能移动一个常数次(而不是基于输入)?
Is it the most efficient one I could make, given that I use ArrayList? Is there maybe a better API to use for this? Is there a way to simplify how this works? Does my code shift cells only when it really needs, and only max of a constant times (instead of based on input) ?
推荐答案
既然您已经了解如何使用 subList() 高效地进行批量删除和插入，为什么不先批量删除所需的范围，从而将两者结合起来通过 clear()ing 子列表，然后将所需元素批量添加到同一个子列表中?
Since you already understand how you can do bulk removal and insertion efficiently using subList(), why don't you combine the two by first bulk removing the desired range by clear()ing the sublist, and then bulk adding the desired elements into the same subList?
我不确定您到底想达到什么目的，但如果我理解正确，那么应该可以通过以下方式有效地实现:
I'm not sure what exactly you're trying to achieve, but if I understand it right then it should be possible efficiently via:
public static void replaceItems(ArrayList<Integer> list, int fromIndex, int toIndexExcluding, ArrayList<Integer> deltaItems) {
List<Integer> subList = list.subList(fromIndex, toIndexExcluding);
subList.clear();
subList.addAll(deltaItems);
}
但也许我误解了，因为我不知道为什么您的代码包含 for 循环；这看起来不正确?
But maybe I misunderstand because I have no idea why your code contains a for loop; that doesn't look correct?
这篇关于如何有效地将 ArrayList 的 X 项替换为 Y 项(X 可能非常大，并且与 Y 不同)?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
