如何有效地用Y个项替换ArrayList的X个项(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}的数组，则可以将"1"项替换为2个项"99"，"100"，以便输出为{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()子列表，然后将所需元素批量添加到同一subList中?
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?
这篇关于如何有效地用Y个项替换ArrayList的X个项(X可能很大，并且与Y不同)?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
