☰

Java のリストから多くの項目を効率的に（パフォーマンス的に）削除するにはどうすればよいでしょうか? 質問する

tag-icon • tag-icon java performance list collections
Java のリストから多くの項目を効率的に（パフォーマンス的に）削除するにはどうすればよいでしょうか? 質問する

items という名前のかなり大きなリスト (>= 1,000,000 項目) があり、削除する項目を選択する <cond> で示される条件があり、リスト上の項目の多く (おそらく半分) に対して <cond> が true です。

私の目標は、<cond> によって選択された項目を効率的に削除し、他のすべての項目を保持することです。ソース リストは変更される可能性があり、新しいリストが作成される可能性もあります。パフォーマンスを考慮して、最適な方法を選択する必要があります。

これが私のテストコードです:

    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)");

そして単純な実装:

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;
}

ご覧のとおり、デモンストレーション目的で、アイテム インデックス モジュロ 2 == 0 を削除条件 (<cond>) として使用しました。

のより良いバージョンはどのようなremoveManyものが提供されるのでしょうか。また、このより良いバージョンが実際に優れているのはなぜでしょうか。

ベストアンサー1

さて、提案されたアプローチのテスト結果の時間です。以下は私がテストしたアプローチです (各アプローチの名前は、私のソースのクラス名でもあります)。

  1. NaiveRemoveManyPerformer-ArrayListイテレータと削除を使用 - 私の質問で示された最初の単純な実装。
  2. BetterNaiveRemoveManyPerformer-ArrayList後方への反復と、最後から前への削除を伴います。
  3. LinkedRemoveManyPerformer- 単純な反復子と削除ですが、 で動作しますLinkedList。欠点: でのみ動作しますLinkedList。
  4. CreateNewRemoveManyPerformer-ArrayListコピーとして作成され（保持された要素のみが追加されます）、反復子は入力を走査するために使用されますArrayList。
  5. SmartCreateNewRemoveManyPerformer- より良い方法CreateNewRemoveManyPerformer- 結果の初期サイズ (容量)ArrayListが最終的なリスト サイズに設定されます。欠点: 開始時にリストの最終的なサイズを知っておく必要があります。
  6. FasterSmartCreateNewRemoveManyPerformer- さらに良い方法 (?) -イテレータの代わりにSmartCreateNewRemoveManyPerformerアイテム インデックス ( ) を使用します。items.get(idx)
  7. MagicRemoveManyPerformer- リストのコピーなしでその場で動作しArrayList、リストの先頭の穴 (削除された項目) をリストの末尾の項目で圧縮します。欠点: このアプローチでは、リスト内の項目の順序が変更されます。
  8. ForwardInPlaceRemoveManyPerformer- 適切な場所で動作しますArrayList- 保持アイテムを移動して穴を埋め、最終的に subList が返されます (最終的な削除やクリアは行われません)。
  9. GuavaArrayListRemoveManyPerformer- Google GuavaIterables.removeIfの使用目的ArrayList- とほぼ同じですForwardInPlaceRemoveManyPerformerが、リストの最後にある項目を最終的に削除します。

完全なソースコードはこの回答の最後に記載されています。

テストは、さまざまなリスト サイズ (10,000 項目から 10,000,000 項目まで) とさまざまな削除係数 (リストから削除する必要がある項目の数を指定) を使用して実行されました。

他の回答に対するコメントでここに投稿したように、アイテムを から にコピーする方が、反復処理してアイテムを削除するだけよりも高速であると考えていましたArrayList。SunArrayListのLinkedListJava ドキュメントには、 の定数係数は実装ArrayListの定数係数に比べて低いと記載されていLinkedListますが、驚いたことに、私の問題ではそうではありません。

実際には、LinkedList単純な反復と削除を使用すると、ほとんどの場合で最高のパフォーマンスが得られます (このアプローチは で実装されていますLinkedRemoveManyPerformer)。通常、MagicRemoveManyPerformerパフォーマンスのみが に匹敵しLinkedRemoveManyPerformer、他のアプローチは大幅に遅くなります。Google Guava は、GuavaArrayListRemoveManyPerformer手動で作成した同様のコードよりも遅くなります (私のコードではリストの末尾にある不要な項目が削除されないため)。

1,000,000 個のソース アイテムから 500,000 個のアイテムを削除した結果の例:

  1. NaiveRemoveManyPerformer: テストは実行されません - 私はそれほど忍耐強いわけではありませんが、 よりもパフォーマンスが悪くなりますBetterNaiveRemoveManyPerformer。
  2. BetterNaiveRemoveManyPerformer: 226080 ミリ
  3. LinkedRemoveManyPerformer: 69 ミリ
  4. CreateNewRemoveManyPerformer: 246 ミリ
  5. SmartCreateNewRemoveManyPerformer: 112 ミリ
  6. FasterSmartCreateNewRemoveManyPerformer: 202 ミリ
  7. MagicRemoveManyPerformer: 74 ミリ秒
  8. ForwardInPlaceRemoveManyPerformer: 69 ミリ
  9. GuavaArrayListRemoveManyPerformer: 118 ミリ

1,000,000 個のソース アイテムから 1 つのアイテムを削除した結果の例 (最初のアイテムが削除される):

  1. BetterNaiveRemoveManyPerformer: 34 ミリ秒
  2. LinkedRemoveManyPerformer: 41 ミリ秒
  3. CreateNewRemoveManyPerformer: 253 ミリ秒
  4. SmartCreateNewRemoveManyPerformer: 108 ミリ秒
  5. より高速スマート新規作成削除多数実行者: 71 ミリ秒
  6. MagicRemoveManyPerformer: 43 ミリ秒
  7. ForwardInPlaceRemoveManyPerformer: 73 ミリ秒
  8. GuavaArrayListRemoveManyPerformer: 78 ミリ秒

1,000,000 個のソース項目から 333,334 個の項目を削除した結果の例:

  1. BetterNaiveRemoveManyPerformer: 253206 ミリ秒
  2. LinkedRemoveManyPerformer: 69 ミリ秒
  3. CreateNewRemoveManyPerformer: 245 ミリ秒
  4. SmartCreateNewRemoveManyPerformer: 111 ミリ秒
  5. より高速スマート新規作成削除多数実行者: 203 ミリ秒
  6. MagicRemoveManyPerformer: 69 ミリ秒
  7. ForwardInPlaceRemoveManyPerformer: 72 ミリ秒
  8. GuavaArrayListRemoveManyPerformer: 102 ミリ秒

1,000,000 個のソース項目から 1,000,000 個 (すべての) 項目を削除した結果の例 (すべての項目が削除されますが、処理は 1 つずつ行われます。すべての項目を削除することが事前にわかっている場合は、リストを単にクリアする必要があります)。

  1. BetterNaiveRemoveManyPerformer: 58 ミリ秒
  2. LinkedRemoveManyPerformer: 88 ミリ秒
  3. 新規作成削除多数実行者: 95 ミリ秒
  4. SmartCreateNewRemoveManyPerformer: 91 ミリ秒
  5. より高速スマート新規作成削除多数実行者: 48 ミリ秒
  6. MagicRemoveManyPerformer: 61 ミリ秒
  7. ForwardInPlaceRemoveManyPerformer: 49 ミリ秒
  8. GuavaArrayListRemoveManyPerformer: 133 ミリ秒

私の最終的な結論は、ハイブリッド アプローチを使用することです。LinkedList を扱う場合は、単純な反復と削除が最適です。ArrayList を扱う場合は、項目の順序が重要かどうかによって異なり、ForwardInPlaceRemoveManyPerformer を使用します。項目の順序が変更される場合は、MagicRemoveManyPerformer が最適な選択肢です。削除係数が事前にわかっている場合 (削除される項目と保持される項目の数がわかっている場合)、特定の状況でさらに優れたパフォーマンスを発揮するアプローチを選択するために、さらにいくつかの条件を設定できます。ただし、削除係数がわかっていることは通常のケースではありません... 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("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);
    }
}

おすすめ記事