如何有效（性能）从列表中删除许多项目在Java？ [英] How to efficiently (performance) remove many items from List in Java?

查看：69 发布时间：2016/12/15 20:12:55 java performance list collections

本文介绍了如何有效（性能）从列表中删除许多项目在Java？的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！

问题描述

我有相当大的列表命名项目（> = 1,000,000项）和一些条件表示< cond>其选择要删除的项目和< cond>

我的目标是有效移除< cond>所选的项目。并保留所有其他项目，源列表可能会被修改，可能会创建新列表 - 最佳方式来选择它应考虑性能。

这里是我的测试代码：

  System.out.println（prepare items）; 
 List< Integer> items = new ArrayList< Integer>（）; // Integer for demo 
 for（int i = 0; i< 1000000; i ++）{
 items.add（i * 3）; // just for demo 
} 
 
 System.out.println（deleting items）; 
 long startMillis = System.currentTimeMillis（）; 
 items = removeMany（items）; 
 long endMillis = System.currentTimeMillis（）; 
 
 System.out.println（after remove：items.size =+ items.size（）+ 
并且它采取了+（endMillis  -  startMillis）+milli ））;

和naive实施：

  public static< T>列表< T> removeMany（List< T> items）{
 int i = 0; 
迭代器< T> iter = items.iterator（）; 
 while（iter.hasNext（））{
 T item = iter.next（）; 
 //< cond>这里
 if（/ *< cond> ;: * / i％2 == 0）{
 iter.remove（）; 
} 
 i ++; 
} 
 return item; 
}

正如你所看到的，我使用项目索引modulo 2 == 0作为删除条件

可以提供 removeMany 更好的版本这个更好的版本其实更好？

解决方案

在这里我测试了什么方法（每个方法的名称也是我的来源中的类名）：

NaiveRemoveManyPerformer - 使用迭代器和删除 - 首先和我的问题中给出的天真的实现。

 
   BetterNaiveRemoveManyPerformer   -   ArrayList 使用向后迭代并从头到尾移除。
 
   LinkedRemoveManyPerformer   - 初始迭代器并删除但工作在 LinkedList 。 Disadventage：只适用于 LinkedList 。
 
   CreateNewRemoveManyPerformer   -   ArrayList 作为副本（仅添加保留的元素），iterator用于遍历输入 ArrayList 。

SmartCreateNewRemoveManyPerformer - 更好 CreateNewRemoveManyPerformer - 结果的初始大小设置为最终列表大小。缺点：启动时必须知道列表的最终大小。

FasterSmartCreateNewRemoveManyPerformer - 更好（？） SmartCreateNewRemoveManyPerformer - 使用项索引（ items.get（idx））而不是迭代器。

MagicRemoveManyPerformer - 为 ArrayList 准备就绪（无列表副本），并从列表。 c> $ ArrayList

 
   GuavaArrayListRemoveManyPerformer  code>  - 保留项目以填充洞，最后返回subList（无最终删除或清除） -  Google Guava  Iterables.removeIf 用于 ArrayList   - 几乎与 ForwardInPlaceRemoveManyPerformer  
 
 完整的源代码在本答案的最后给出了
 。
 
 
 使用不同的列表大小（从10,000项到10,000,000项）和不同的删除因子（指定必须从列表中删除多少项）进行测试。
 
 
 正如我在评论中发布的其他答案 - 我认为将 ArrayList 复制到第二个 ArrayList 将比迭代 LinkedList 更快，只是删除项目。 Sun的Java文档说， ArrayList 的常量因子与 LinkedList 实现相比是低的，但令人惊讶的是，这不是
 
 
 在实践中 LinkedList 使用简单的迭代和删除在大多数情况下方法在 LinkedRemoveManyPerformer 中实现。通常只有 MagicRemoveManyPerformer 性能可以与 LinkedRemoveManyPerformer 相比，其他方法明显更慢。 Google Guava  GuavaArrayListRemoveManyPerformer 比手工制作的类似代码慢（因为我的代码不会在列表末尾删除不必要的项目）。
 
 
 从1,000,000个来源项目中移除500,000个项目的示例结果：
 
   NaiveRemoveManyPerformer  ：测试未执行 - 我不是那个病人，但它的执行比 BetterNaiveRemoveManyPerformer 。
 
   BetterNaiveRemoveManyPerformer ：226080 milli（s）
 
   LinkedRemoveManyPerformer ：69 milli $ b 
  CreateNewRemoveManyPerformer ：246毫秒
 
   SmartCreateNewRemoveManyPerformer  ：112 milli（s）
 
   FasterSmartCreateNewRemoveManyPerformer ：202毫秒
 
   MagicRemoveManyPerformer ：74 milli（s）
 
   ForwardInPlaceRemoveManyPerformer ：69 milli / li> 
 
  GuavaArrayListRemoveManyPerformer ：118 milli（s）
 
 
从1,000,000个来源项目中移除1个项目（第一个项目已移除）的示例结果：
 
  BetterNaiveRemoveManyPerformer：34 milli / li> 
 
 LinkedRemoveManyPerformer：41 milli（s）
 
  CreateNewRemoveManyPerformer：253 milli（s）
 
  SmartCreateNewRemoveManyPerformer：108 milli 
 
  FasterSmartCreateNewRemoveManyPerformer：71 milli（s）
 
  MagicRemoveManyPerformer：43 milli（s）
 
  
  
 
结果示例结果示例结果示例结果示例结果示例结果示例结果从1,000,000个来源项目中移除333,334个项目：
 
  BetterNaiveRemoveManyPerformer：253206 milli（s）
 
  LinkedRemoveManyPerformer ：69 milli（s）
 
  CreateNewRemoveManyPerformer：245 milli（s）
 
  SmartCreateNewRemoveManyPerformer：111 milli（s）
 
  
 
  ForwardInPlaceRemoveManyPerformer：72 milli（s）
 
  
 
 GuavaArrayListRemoveManyPerformer：102 milli（s）
 
 
从1,000,000个来源项目中移除1,000,000 （所有项目都被删除，但逐个处理，如果你知道所有项目都被删除，列表应该被清除）：
 
  BetterNaiveRemoveManyPerformer：58 milli（s）
 
  LinkedRemoveManyPerformer：88 milli（s）
 
  CreateNewRemoveManyPerformer：95 milli / li> 
 
 SmartCreateNewRemoveManyPerformer：91毫秒
 
  FasterSmartCreateNewRemoveManyPerformer：48毫秒
 
  MagicRemoveManyPerformer：61 milli 
 
  ForwardInPlaceRemoveManyPerformer：49 milli（s）
 
  GuavaArrayListRemoveManyPerformer：133 milli（s）
 
 
我的最终结论：使用混合方法 - 如果处理LinkedList  - 简单的迭代和删除是最好的，如果处理ArrayList  - 它取决于项顺序是否重要 - 使用ForwardInPlaceRemoveManyPerformer然后，if项目订单可能会更改 - 最好的选择是MagicRemoveManyPerformer。如果删除因子是先验已知的（你知道有多少项将被删除vs保留），那么一些更多的条件可以放到选择方法在特定情况下表现更好。但已知的删除因素不是通常的情况... Google Guava  Iterables.removeIf 是这样一个混合解决方案，但略有不同的假设（原始列表必须更改，新的不能创建和项目顺序总是重要） - 这些是最常见的假设，因此 removeIf 是大多数现实生活中的最佳选择。
 
 
 请注意，所有好的方法（天真不好！）是足够好的 - 他们中的任何一个在实际应用程序只是罚款，但天真的方法必须避免。
 
 
 最后 - 我的测试源代码。
  package WildWezyrListRemovalTesting; 
 
 import com.google.common.base.Predicate; 
 import com.google.common.collect.Iterables; 
 import java.util.ArrayList; 
 import java.util.Iterator; 
 import java.util.LinkedList; 
 import java.util.List; 
 
 public class RemoveManyFromList {
 
 public static abstract class BaseRemoveManyPerformer {
 
 protected String performerName（）{
 return getClass（）。getSimpleName （）; 
} 
 
 protected void info（String msg）{
 System.out.println（performerName（）+：+ msg）; 
} 
 
 protected void populateList（List< Integer> items，int itemCnt）{
 for（int i = 0; i< itemCnt; i ++）{
 items.add（i）; 
} 
} 
 
 protected boolean mustRemoveItem（Integer itemVal，int itemIdx，int removeFactor）{
 if（removeFactor == 0）{
 return false ; 
} 
 return itemIdx％removeFactor == 0; 
} 
 
 protected abstract List< Integer> removeItems（List< Integer> items，int removeFactor）; 
 
 protected abstract List< Integer> createInitialList（）; 
 
 public void testMe（int itemCnt，int removeFactor）{
 List< Integer> items = createInitialList（）; 
 populateList（items，itemCnt）; 
 long startMillis = System.currentTimeMillis（）; 
 items = removeItems（items，removeFactor）; 
 long endMillis = System.currentTimeMillis（）; 
 int chksum = 0; 
 for（Integer item：items）{
 chksum + = item; 
} 
 info（removed took+（endMillis  -  startMillis）
 +milli（s），itemCnt =+ itemCnt 
 +，removed items：+ item.cnt  -  items.size（））
 +，其余项目：+ items.size（）
 +，checksum：+ chksum）; 
} 
} 
 private List< BaseRemoveManyPerformer> rmps = 
 new ArrayList< BaseRemoveManyPerformer>（）; 
 
 public void addPerformer（BaseRemoveManyPerformer rmp）{
 rmps.add（rmp）; 
} 
 private Runtime运行时= Runtime.getRuntime（）; 
 
 private void runGc（）{
 for（int i = 0; i <5; i ++）{
 runtime.gc 
} 
} 
 
 public void testAll（int itemCnt，int removeFactor）{
 runGc（）; 
 for（BaseRemoveManyPerformer rmp：rmps）{
 rmp.testMe（itemCnt，removeFactor）; 
} 
 runGc（）; 
 System.out.println（\\\
 -------------------------- \\\
）; 
} 
 
 public static class NaiveRemoveManyPerformer 
 extends BaseRemoveManyPerformer {
 
 @Override 
 public List< Integer> removeItems（List< Integer> items，int removeFactor）{
 if（items.size（）> 300000&&&item arrayList）{
 info（this removeItems太慢，处理）; 
 return item; 
} 
 int i = 0; 
迭代器< Integer> iter = items.iterator（）; 
 while（iter.hasNext（））{
 Integer item = iter.next（）; 
 if（mustRemoveItem（item，i，removeFactor））{
 iter.remove（）; 
} 
 i ++; 
} 
 return item; 
} 
 
 @Override 
 public List< Integer> createInitialList（）{
 return new ArrayList< Integer>（）; 
} 
} 
 
 public static class BetterNaiveRemoveManyPerformer 
 extends NaiveRemoveManyPerformer {
 
 @Override 
 public List< Integer> removeItems（List< Integer> items，int removeFactor）{
 // if（items.size（）> 300000&& items instanceof ArrayList）{
 // info（this removeItems is too慢，返回无处理）; 
 // return items; 
 //} 
 
 for（int i = items.size（）; --i> = 0;）{
 Integer item = items.get（i）; 
 if（mustRemoveItem（item，i，removeFactor））{
 items.remove（i）; 
} 
} 
返回项目; 
} 
} 
 
 public static class LinkedRemoveManyPerformer 
 extends NaiveRemoveManyPerformer {
 
 @Override 
 public List< Integer> createInitialList（）{
 return new LinkedList< Integer>（）; 
} 
} 
 
 public static class CreateNewRemoveManyPerformer 
 extends NaiveRemoveManyPerformer {
 
 @Override 
 public List< Integer> removeItems（List< Integer> items，int removeFactor）{
 List< Integer> res = createResultList（items，removeFactor）; 
 int i = 0; 
 
 for（Integer item：items）{
 if（mustRemoveItem（item，i，removeFactor））{
 // no-op 
} else {
 res.add（item）; 
} 
 i ++; 
} 
 
 return res; 
} 
 
 protected List< Integer> createResultList（List< Integer> items，int removeFactor）{
 return new ArrayList< Integer>（）; 
} 
} 
 
 public static class SmartCreateNewRemoveManyPerformer 
 extends CreateNewRemoveManyPerformer {
 
 @Override 
 protected List< Integer> createResultList（List< Integer> items，int removeFactor）{
 int newCapacity = removeFactor == 0？ items.size（）
：（int）（items.size（）*（removeFactor  -  1L）/ removeFactor + 1）; 
 //System.out.println(\"newCapacity=+ newCapacity）; 
 return new ArrayList< Integer>（newCapacity）; 
} 
} 
 
 public static class FasterSmartCreateNewRemoveManyPerformer 
 extends SmartCreateNewRemoveManyPerformer {
 
 @Override 
 public List< Integer> removeItems（List< Integer> items，int removeFactor）{
 List< Integer> res = createResultList（items，removeFactor）; 
 
 for（int i = 0; i< items.size（）; i ++）{
 Integer item = items.get（i）; 
 if（mustRemoveItem（item，i，removeFactor））{
 // no-op 
} else {
 res.add（item）; 
} 
} 
 
 return res; 
} 
} 
 
 public static class ForwardInPlaceRemoveManyPerformer 
 extend NaiveRemoveManyPerformer {
 
 @Override 
 public List< Integer> removeItems（List< Integer> items，int removeFactor）{
 int j = 0; // destination idx 
 for（int i = 0; i< items.size（）; i ++）{
 Integer item = items.get（i）; 
 if（mustRemoveItem（item，i，removeFactor））{
 // no-op 
} else {
 if（j< i）{
 items。 set（j，item）; 
} 
 j ++; 
} 
} 
 
 return items.subList（0，j）; 
} 
} 
 
 public static class MagicRemoveManyPerformer 
 extends NaiveRemoveManyPerformer {
 
 @Override 
 public List< Integer> removeItems（List< Integer> items，int removeFactor）{
 for（int i = 0; i< items.size（）; i ++）{
 if（mustRemoveItem（items.get i，removeFactor））{
 Integer retainedItem = removeSomeFromEnd（items，removeFactor，i）; 
 if（retainedItem == null）{
 items.remove（i）; 
 break; 
} 
 items.set（i，retainedItem）; 
} 
} 
 
返回项目; 
} 
 
 private Integer removeSomeFromEnd（List< Integer> items，int removeFactor，int lowerBound）{
 for（int i = items.size（）; --i& lowerBound;）{
 Integer item = items.get（i）; 
 items.remove（i）; 
 if（！mustRemoveItem（item，i，removeFactor））{
 return item; 
} 
} 
 return null; 
} 
} 
 
 public static class GuavaArrayListRemoveManyPerformer 
 extends BaseRemoveManyPerformer {
 
 @Override 
 protected List< Integer> removeItems（List< Integer> items，final int removeFactor）{
 Iterables.removeIf（items，new Predicate< Integer>（）{
 
 public boolean apply（Integer input）{
 return mustRemoveItem（input，input，removeFactor）; 
} 
}）; 
 
返回项目; 
} 
 
 @Override 
 protected List< Integer> createInitialList（）{
 return new ArrayList< Integer>（）; 
} 
} 
 
 public void testForOneItemCnt（int itemCnt）{
 testAll（itemCnt，0）; 
 testAll（itemCnt，itemCnt）; 
 testAll（itemCnt，itemCnt  -  1）; 
 testAll（itemCnt，3）; 
 testAll（itemCnt，2）; 
 testAll（itemCnt，1）; 
} 
 
 public static void main（String [] args）{
 RemoveManyFromList t = new RemoveManyFromList（）; 
 t.addPerformer（new NaiveRemoveManyPerformer（））; 
 t.addPerformer（new BetterNaiveRemoveManyPerformer（））; 
 t.addPerformer（new LinkedRemoveManyPerformer（））; 
 t.addPerformer（new CreateNewRemoveManyPerformer（））; 
 t.addPerformer（new SmartCreateNewRemoveManyPerformer（））; 
 t.addPerformer（new FasterSmartCreateNewRemoveManyPerformer（））; 
 t.addPerformer（new MagicRemoveManyPerformer（））; 
 t.addPerformer（new ForwardInPlaceRemoveManyPerformer（））; 
 t.addPerformer（new GuavaArrayListRemoveManyPerformer（））; 
 
 t.testForOneItemCnt（1000）; 
 t.testForOneItemCnt（10000）; 
 t.testForOneItemCnt（100000）; 
 t.testForOneItemCnt（200000）; 
 t.testForOneItemCnt（300000）; 
 t.testForOneItemCnt（500000）; 
 t.testForOneItemCnt（1000000）; 
 t.testForOneItemCnt（10000000）; 
} 
} 
  
 
I have quite large List named items (>= 1,000,000 items) and some condition denoted by <cond> that selects items to be deleted and <cond> is true for many (maybe half) of items on my list.

My goal is to efficiently remove items selected by <cond> and retain all other items, source list may be modified, new list may be created - best way to do it should be chosen considering performance.

Here is my testing code:
    System.out.println("preparing items");
    List<Integer> items = new ArrayList<Integer>(); // Integer is for demo
    for (int i = 0; i < 1000000; i++) {
        items.add(i * 3); // just for demo
    }

    System.out.println("deleting items");
    long startMillis = System.currentTimeMillis();
    items = removeMany(items);
    long endMillis = System.currentTimeMillis();

    System.out.println("after remove: items.size=" + items.size() + 
            " and it took " + (endMillis - startMillis) + " milli(s)");
and naive implementation:
public static <T> List<T> removeMany(List<T> items) {
    int i = 0;
    Iterator<T> iter = items.iterator();
    while (iter.hasNext()) {
        T item = iter.next();
        // <cond> goes here
        if (/*<cond>: */i % 2 == 0) {
            iter.remove();
        }
        i++;
    }
    return items;
}
As you can see I used item index modulo 2 == 0 as remove condition (<cond>) - just for demonstation purposes.

What better version of removeMany may be provided and why this better version is actually better?
 解决方案 
OK, it's time for test results of proposed approaches. Here what approaches I have tested (name of each approach is also class name in my sources):

NaiveRemoveManyPerformer - ArrayList with iterator and remove - first and naive implementation given in my question.
BetterNaiveRemoveManyPerformer - ArrayList with backward iteration and removal from end to front.
LinkedRemoveManyPerformer - naive iterator and remove but working on LinkedList. Disadventage: works only for LinkedList.
CreateNewRemoveManyPerformer - ArrayList is made as a copy (only retained elements are added), iterator is used to traverse input ArrayList.
SmartCreateNewRemoveManyPerformer - better CreateNewRemoveManyPerformer - initial size (capacity) of result ArrayList is set to final list size. Disadvantage: you must know final size of list when starting.
FasterSmartCreateNewRemoveManyPerformer - even better (?) SmartCreateNewRemoveManyPerformer - use item index (items.get(idx)) instead of iterator.
MagicRemoveManyPerformer - works in place (no list copy) for ArrayList and compacts holes (removed items) from beginning with items from end of the list. Disadventage: this approach changes order of items in list.
ForwardInPlaceRemoveManyPerformer - works in place for ArrayList - move retaining items to fill holes, finally subList is returned (no final removal or clear).
GuavaArrayListRemoveManyPerformer - Google Guava Iterables.removeIf used for ArrayList - almost the same as ForwardInPlaceRemoveManyPerformer but does final removal of items at the end of list.
Full source code is given at the end of this answer.

Tests where performed with different list sizes (from 10,000 items to 10,000,000 items) and different remove factors (specifying how many items must be removed from list).

As I posted here in comments for other answers - I have thought that copying items from ArrayList to second ArrayList will be faster than iterating LinkedList and just removing items. Sun's Java Documentation says that constant factor of ArrayList is low compared to that for the LinkedList implementation, but surprisingly this is not the case in my problem.

In practice LinkedList with simple iteration and removal has best performance in most cases (this approach is implemented in LinkedRemoveManyPerformer). Usually only MagicRemoveManyPerformer performance is comparable to LinkedRemoveManyPerformer, other approaches are significantly slower. Google Guava GuavaArrayListRemoveManyPerformer is slower than hand made similar code (because my code does not remove unnecessary items at end of list).

Example results for removing 500,000 items from 1,000,000 source items:

NaiveRemoveManyPerformer: test not performed - I'm not that patient, but it performs worse than BetterNaiveRemoveManyPerformer.
BetterNaiveRemoveManyPerformer: 226080 milli(s)
LinkedRemoveManyPerformer: 69 milli(s)
CreateNewRemoveManyPerformer: 246 milli(s)
SmartCreateNewRemoveManyPerformer: 112 milli(s)
FasterSmartCreateNewRemoveManyPerformer: 202 milli(s)
MagicRemoveManyPerformer: 74 milli(s)
ForwardInPlaceRemoveManyPerformer: 69 milli(s)
GuavaArrayListRemoveManyPerformer: 118 milli(s)
Example results for removing 1 item from 1,000,000 source items (first item is removed):

BetterNaiveRemoveManyPerformer: 34 milli(s)
LinkedRemoveManyPerformer: 41 milli(s)
CreateNewRemoveManyPerformer: 253 milli(s)
SmartCreateNewRemoveManyPerformer: 108 milli(s)
FasterSmartCreateNewRemoveManyPerformer: 71 milli(s)
MagicRemoveManyPerformer: 43 milli(s)
ForwardInPlaceRemoveManyPerformer: 73 milli(s)
GuavaArrayListRemoveManyPerformer: 78 milli(s)
Example results for removing 333,334 items from 1,000,000 source items:

BetterNaiveRemoveManyPerformer: 253206 milli(s)
LinkedRemoveManyPerformer: 69 milli(s)
CreateNewRemoveManyPerformer: 245 milli(s)
SmartCreateNewRemoveManyPerformer: 111 milli(s)
FasterSmartCreateNewRemoveManyPerformer: 203 milli(s)
MagicRemoveManyPerformer: 69 milli(s)
ForwardInPlaceRemoveManyPerformer: 72 milli(s)
GuavaArrayListRemoveManyPerformer: 102 milli(s)
Example results for removing 1,000,000 (all) items from 1,000,000 source items (all items are removed but with one-by-one processing, if you know a priori that all items are to be removed, list should be simply cleared):

BetterNaiveRemoveManyPerformer: 58 milli(s)
LinkedRemoveManyPerformer: 88 milli(s)
CreateNewRemoveManyPerformer: 95 milli(s)
SmartCreateNewRemoveManyPerformer: 91 milli(s)
FasterSmartCreateNewRemoveManyPerformer: 48 milli(s)
MagicRemoveManyPerformer: 61 milli(s)
ForwardInPlaceRemoveManyPerformer: 49 milli(s)
GuavaArrayListRemoveManyPerformer: 133 milli(s)
My final conclusions: use hybrid approach - if dealing with LinkedList - simple iteration and removal is best, if dealing with ArrayList - it depends if item order is important - use ForwardInPlaceRemoveManyPerformer then, if item order may be changed - best choice is MagicRemoveManyPerformer. If remove factor is known a priori (you know how many items will be removed vs retained) then some more conditionals may be put to select approach performing even better in particular situation. But known remove factor is not usual case... Google Guava Iterables.removeIf is such a hybrid solution but with slightly different assumption (original list must be changed, new one cannot be created and item order always matters) - these are most common assumptions so removeIf is best choice in most real-life cases.

Notice also that all good approaches (naive is not good!) are good enough - any one of them shold do just fine in real application, but naive approach must be avoided.

At last - my source code for testing.
package WildWezyrListRemovalTesting;

import com.google.common.base.Predicate;
import com.google.common.collect.Iterables;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;

public class RemoveManyFromList {

    public static abstract class BaseRemoveManyPerformer {

        protected String performerName() {
            return getClass().getSimpleName();
        }

        protected void info(String msg) {
            System.out.println(performerName() + ": " + msg);
        }

        protected void populateList(List<Integer> items, int itemCnt) {
            for (int i = 0; i < itemCnt; i++) {
                items.add(i);
            }
        }

        protected boolean mustRemoveItem(Integer itemVal, int itemIdx, int removeFactor) {
            if (removeFactor == 0) {
                return false;
            }
            return itemIdx % removeFactor == 0;
        }

        protected abstract List<Integer> removeItems(List<Integer> items, int removeFactor);

        protected abstract List<Integer> createInitialList();

        public void testMe(int itemCnt, int removeFactor) {
            List<Integer> items = createInitialList();
            populateList(items, itemCnt);
            long startMillis = System.currentTimeMillis();
            items = removeItems(items, removeFactor);
            long endMillis = System.currentTimeMillis();
            int chksum = 0;
            for (Integer item : items) {
                chksum += item;
            }
            info("removing took " + (endMillis - startMillis)
                    + " milli(s), itemCnt=" + itemCnt
                    + ", removed items: " + (itemCnt - items.size())
                    + ", remaining items: " + items.size()
                    + ", checksum: " + chksum);
        }
    }
    private List<BaseRemoveManyPerformer> rmps =
            new ArrayList<BaseRemoveManyPerformer>();

    public void addPerformer(BaseRemoveManyPerformer rmp) {
        rmps.add(rmp);
    }
    private Runtime runtime = Runtime.getRuntime();

    private void runGc() {
        for (int i = 0; i < 5; i++) {
            runtime.gc();
        }
    }

    public void testAll(int itemCnt, int removeFactor) {
        runGc();
        for (BaseRemoveManyPerformer rmp : rmps) {
            rmp.testMe(itemCnt, removeFactor);
        }
        runGc();
        System.out.println("\n--------------------------\n");
    }

    public static class NaiveRemoveManyPerformer
            extends BaseRemoveManyPerformer {

        @Override
        public List<Integer> removeItems(List<Integer> items, int removeFactor) {
            if (items.size() > 300000 && items instanceof ArrayList) {
                info("this removeItems is too slow, returning without processing");
                return items;
            }
            int i = 0;
            Iterator<Integer> iter = items.iterator();
            while (iter.hasNext()) {
                Integer item = iter.next();
                if (mustRemoveItem(item, i, removeFactor)) {
                    iter.remove();
                }
                i++;
            }
            return items;
        }

        @Override
        public List<Integer> createInitialList() {
            return new ArrayList<Integer>();
        }
    }

    public static class BetterNaiveRemoveManyPerformer
            extends NaiveRemoveManyPerformer {

        @Override
        public List<Integer> removeItems(List<Integer> items, int removeFactor) {
//            if (items.size() > 300000 && items instanceof ArrayList) {
//                info("this removeItems is too slow, returning without processing");
//                return items;
//            }

            for (int i = items.size(); --i >= 0;) {
                Integer item = items.get(i);
                if (mustRemoveItem(item, i, removeFactor)) {
                    items.remove(i);
                }
            }
            return items;
        }
    }

    public static class LinkedRemoveManyPerformer
            extends NaiveRemoveManyPerformer {

        @Override
        public List<Integer> createInitialList() {
            return new LinkedList<Integer>();
        }
    }

    public static class CreateNewRemoveManyPerformer
            extends NaiveRemoveManyPerformer {

        @Override
        public List<Integer> removeItems(List<Integer> items, int removeFactor) {
            List<Integer> res = createResultList(items, removeFactor);
            int i = 0;

            for (Integer item : items) {
                if (mustRemoveItem(item, i, removeFactor)) {
                    // no-op
                } else {
                    res.add(item);
                }
                i++;
            }

            return res;
        }

        protected List<Integer> createResultList(List<Integer> items, int removeFactor) {
            return new ArrayList<Integer>();
        }
    }

    public static class SmartCreateNewRemoveManyPerformer
            extends CreateNewRemoveManyPerformer {

        @Override
        protected List<Integer> createResultList(List<Integer> items, int removeFactor) {
            int newCapacity = removeFactor == 0 ? items.size()
                    : (int) (items.size() * (removeFactor - 1L) / removeFactor + 1);
            //System.out.println("newCapacity=" + newCapacity);
            return new ArrayList<Integer>(newCapacity);
        }
    }

    public static class FasterSmartCreateNewRemoveManyPerformer
            extends SmartCreateNewRemoveManyPerformer {

        @Override
        public List<Integer> removeItems(List<Integer> items, int removeFactor) {
            List<Integer> res = createResultList(items, removeFactor);

            for (int i = 0; i < items.size(); i++) {
                Integer item = items.get(i);
                if (mustRemoveItem(item, i, removeFactor)) {
                    // no-op
                } else {
                    res.add(item);
                }
            }

            return res;
        }
    }

    public static class ForwardInPlaceRemoveManyPerformer
            extends NaiveRemoveManyPerformer {

        @Override
        public List<Integer> removeItems(List<Integer> items, int removeFactor) {
            int j = 0; // destination idx
            for (int i = 0; i < items.size(); i++) {
                Integer item = items.get(i);
                if (mustRemoveItem(item, i, removeFactor)) {
                    // no-op
                } else {
                    if (j < i) {
                        items.set(j, item);
                    }
                    j++;
                }
            }

            return items.subList(0, j);
        }
    }

    public static class MagicRemoveManyPerformer
            extends NaiveRemoveManyPerformer {

        @Override
        public List<Integer> removeItems(List<Integer> items, int removeFactor) {
            for (int i = 0; i < items.size(); i++) {
                if (mustRemoveItem(items.get(i), i, removeFactor)) {
                    Integer retainedItem = removeSomeFromEnd(items, removeFactor, i);
                    if (retainedItem == null) {
                        items.remove(i);
                        break;
                    }
                    items.set(i, retainedItem);
                }
            }

            return items;
        }

        private Integer removeSomeFromEnd(List<Integer> items, int removeFactor, int lowerBound) {
            for (int i = items.size(); --i > lowerBound;) {
                Integer item = items.get(i);
                items.remove(i);
                if (!mustRemoveItem(item, i, removeFactor)) {
                    return item;
                }
            }
            return null;
        }
    }

    public static class GuavaArrayListRemoveManyPerformer
            extends BaseRemoveManyPerformer {

        @Override
        protected List<Integer> removeItems(List<Integer> items, final int removeFactor) {
            Iterables.removeIf(items, new Predicate<Integer>() {

                public boolean apply(Integer input) {
                    return mustRemoveItem(input, input, removeFactor);
                }
            });

            return items;
        }

        @Override
        protected List<Integer> createInitialList() {
            return new ArrayList<Integer>();
        }
    }

    public void testForOneItemCnt(int itemCnt) {
        testAll(itemCnt, 0);
        testAll(itemCnt, itemCnt);
        testAll(itemCnt, itemCnt - 1);
        testAll(itemCnt, 3);
        testAll(itemCnt, 2);
        testAll(itemCnt, 1);
    }

    public static void main(String[] args) {
        RemoveManyFromList t = new RemoveManyFromList();
        t.addPerformer(new NaiveRemoveManyPerformer());
        t.addPerformer(new BetterNaiveRemoveManyPerformer());
        t.addPerformer(new LinkedRemoveManyPerformer());
        t.addPerformer(new CreateNewRemoveManyPerformer());
        t.addPerformer(new SmartCreateNewRemoveManyPerformer());
        t.addPerformer(new FasterSmartCreateNewRemoveManyPerformer());
        t.addPerformer(new MagicRemoveManyPerformer());
        t.addPerformer(new ForwardInPlaceRemoveManyPerformer());
        t.addPerformer(new GuavaArrayListRemoveManyPerformer());

        t.testForOneItemCnt(1000);
        t.testForOneItemCnt(10000);
        t.testForOneItemCnt(100000);
        t.testForOneItemCnt(200000);
        t.testForOneItemCnt(300000);
        t.testForOneItemCnt(500000);
        t.testForOneItemCnt(1000000);
        t.testForOneItemCnt(10000000);
    }
}


                        
这篇关于如何有效（性能）从列表中删除许多项目在Java？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！


                    
                        查看全文

如何有效（性能）从列表中删除许多项目在Java？ [英] How to efficiently (performance) remove many items from List in Java?

问题描述

相关文章

Java开发最新文章

热门教程

热门工具

登录关闭

如何有效（性能）从列表中删除许多项目在Java？ [英] How to efficiently (performance) remove many items from List in Java?

问题描述

相关文章

Java开发最新文章

热门教程

热门工具

登录 关闭

登录关闭