SORU
23 Mayıs 2011, PAZARTESİ


Neden Java'un ArrayList'un Kaldır işlevi çok pahalıya geliyor mu?

Çok büyük bir liste, yaklaşık 250.000 öğeleri aşan işleyen bir işlevi var. Bu öğelerin çoğu için, bu sadece konumundaki öğe x değiştirir. Ancak bunlardan 5'i hakkında, listeden kaldırmak gerekir.

Bir LinkedList kullanılarak pahalı taşınma önlemek için en bariz çözüm gibi görünüyordu. Ancak, doğal olarak, dizin tarafından bir LinkedList erişim zaman geçtikçe giderek daha yavaş olur. Maliyet burada dakika (ve onları bir sürü).

Bu LinkedList üzerinde bir Yineleyici kullanarak o listeyi düzenlerken Yineleyici eşzamanlılık sorunları önlemek için ayrı bir kopyasını ihtiyacı görünür olarak da pahalı. Maliyet burada dakikadır.

Aklım biraz şişmiş olduğu ancak, işte burada. Eğer Için bir değiştirirsem, neredeyse anında çalışır.

297515 öğeleri içeren bir liste için, 11958 unsurlarını çıkarmak ve her şeyi değiştirme 909ms alır. Sonuç listesi beklendiği gibi gerçekten boyutu 285557, bu doğrulandı, ve ihtiyacım güncelleştirilmiş bilgileri içerir.

Neden bu kadar hızlı? JDK6 içinde ArrayList için kaynak baktım ve beklendiği gibi arraycopy fonksiyonu gibi görünüyor. Sağduyu bu görev için bir dizi berbat bir fikir, birkaç yüz bin öğeleri değişen gerektiren olduğunu belirtmek gibi görünüyor zaman bir ArrayList burada çok iyi çalışıyor neden anlamak isterdim.

CEVAP
23 Mayıs 2011, PAZARTESİ


Bir kriter listesini süzmek için aşağıdaki stratejileri her element çalışıyorum koştu:

  • Yeni bir liste istedi öğeleri kopyalayın
  • Iterator.remove() ArrayList istenmeyen öğeleri kaldırmak için kullanın
  • Iterator.remove() LinkedList bir istenmeyen öğeleri kaldırmak için kullanın
  • Kompakt listesinde yer (daha düşük pozisyonlar için aranan unsurlar hareketli)
  • Dizin (List.remove(int)) ArrayList Kaldır
  • Dizin (List.remove(int)) LinkedList Kaldır

Her zaman kalabalık liste ile 100000 rasgele örnekleri Point ve kullanılan bir filtre koşulu (dayalı karma kodu) bunu kabul etmek elemanları ve reddetmek geri kalan %5'lik (aynı oranda belirtilen soru, ama daha küçük bir liste çünkü ben yapmadım çalıştırmak için test için 250000 elemanları.)

Ve ortalama süreleri (eski MacBook Pro, Core 2 Duo 2.2 GHz, 3 GB RAM):

CopyIntoNewListWithIterator   :      4.24ms
CopyIntoNewListWithoutIterator:      3.57ms
FilterLinkedListInPlace       :      4.21ms
RandomRemoveByIndex           :    312.50ms
SequentialRemoveByIndex       :  33632.28ms
ShiftDown                     :      3.75ms

Bu yüzden kaldırma elemanları tarafından dizinden bir LinkedList daha fazla 300 kat daha pahalı daha kaldırarak onları bir ArrayList, ve muhtemelen bir yere arasında 6000-10000 kat daha pahalı diğer yöntemler (doğrusal arama önlemek ve arraycopy)

Burada dört hızlı yöntemleri arasında fazla fark yok gibi, ama sadece o dördü yine aşağıdaki sonuçlar ile 500000 öğeli bir liste ile karşılaştım:

CopyIntoNewListWithIterator   :     92.49ms
CopyIntoNewListWithoutIterator:     71.77ms
FilterLinkedListInPlace       :     15.73ms
ShiftDown                     :     11.86ms

Daha büyük boyutta önbellek sınırlayıcı faktör olur tahminime göre, listenin ikinci bir kopyasını oluşturma maliyeti önemli hale geliyor.

İşte kod:

import java.awt.Point;
import java.security.SecureRandom;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Random;
import java.util.TreeMap;

public class ListBenchmark {

    public static void main(String[] args) {
        Random rnd = new SecureRandom();
        Map<String, Long> timings = new TreeMap<String, Long>();
        for (int outerPass = 0; outerPass < 10;    outerPass) {
            List<FilterStrategy> strategies =
                Arrays.asList(new CopyIntoNewListWithIterator(),
                              new CopyIntoNewListWithoutIterator(),
                              new FilterLinkedListInPlace(),
                              new RandomRemoveByIndex(),
                              new SequentialRemoveByIndex(),
                              new ShiftDown());
            for (FilterStrategy strategy: strategies) {
                String strategyName = strategy.getClass().getSimpleName();
                for (int innerPass = 0; innerPass < 10;    innerPass) {
                    strategy.populate(rnd);
                    if (outerPass >= 5 && innerPass >= 5) {
                        Long totalTime = timings.get(strategyName);
                        if (totalTime == null) totalTime = 0L;
                        timings.put(strategyName, totalTime - System.currentTimeMillis());
                    }
                    Collection<Point> filtered = strategy.filter();
                    if (outerPass >= 5 && innerPass >= 5) {
                        Long totalTime = timings.get(strategyName);
                        timings.put(strategy.getClass().getSimpleName(), totalTime   System.currentTimeMillis());
                    }
                    CHECKSUM  = filtered.hashCode();
                    System.err.printf("%-30s %d %d %d%n", strategy.getClass().getSimpleName(), outerPass, innerPass, filtered.size());
                    strategy.clear();
                }
            }
        }
        for (Map.Entry<String, Long> e: timings.entrySet()) {
            System.err.printf("%-30s: %9.2fms%n", e.getKey(), e.getValue() * (1.0/25.0));
        }
    }

    public static volatile int CHECKSUM = 0;

    static void populate(Collection<Point> dst, Random rnd) {
        for (int i = 0; i < INITIAL_SIZE;    i) {
            dst.add(new Point(rnd.nextInt(), rnd.nextInt()));
        }
    }

    static boolean wanted(Point p) {
        return p.hashCode() % 20 != 0;
    }

    static abstract class FilterStrategy {
        abstract void clear();
        abstract Collection<Point> filter();
        abstract void populate(Random rnd);
    }

    static final int INITIAL_SIZE = 100000;

    private static class CopyIntoNewListWithIterator extends FilterStrategy {
        public CopyIntoNewListWithIterator() {
            list = new ArrayList<Point>(INITIAL_SIZE);
        }
        @Override
        void clear() {
            list.clear();
        }
        @Override
        Collection<Point> filter() {
            ArrayList<Point> dst = new ArrayList<Point>(list.size());
            for (Point p: list) {
                if (wanted(p)) dst.add(p);
            }
            return dst;
        }
        @Override
        void populate(Random rnd) {
            ListBenchmark.populate(list, rnd);
        }
        private final ArrayList<Point> list;
    }

    private static class CopyIntoNewListWithoutIterator extends FilterStrategy {
        public CopyIntoNewListWithoutIterator() {
            list = new ArrayList<Point>(INITIAL_SIZE);
        }
        @Override
        void clear() {
            list.clear();
        }
        @Override
        Collection<Point> filter() {
            int inputSize = list.size();
            ArrayList<Point> dst = new ArrayList<Point>(inputSize);
            for (int i = 0; i < inputSize;    i) {
                Point p = list.get(i);
                if (wanted(p)) dst.add(p);
            }
            return dst;
        }
        @Override
        void populate(Random rnd) {
            ListBenchmark.populate(list, rnd);
        }
        private final ArrayList<Point> list;
    }

    private static class FilterLinkedListInPlace extends FilterStrategy {
        public String toString() {
            return getClass().getSimpleName();
        }
        FilterLinkedListInPlace() {
            list = new LinkedList<Point>();
        }
        @Override
        void clear() {
            list.clear();
        }
        @Override
        Collection<Point> filter() {
            for (Iterator<Point> it = list.iterator();
                 it.hasNext();
                 ) {
                Point p = it.next();
                if (! wanted(p)) it.remove();
            }
            return list;
        }
        @Override
        void populate(Random rnd) {
            ListBenchmark.populate(list, rnd);
        }
        private final LinkedList<Point> list;
    }

    private static class RandomRemoveByIndex extends FilterStrategy {
        public RandomRemoveByIndex() {
            list = new ArrayList<Point>(INITIAL_SIZE);
        }
        @Override
        void clear() {
            list.clear();
        }
        @Override
        Collection<Point> filter() {
            for (int i = 0; i < list.size();) {
                if (wanted(list.get(i))) {
                       i;
                } else {
                    list.remove(i);
                }
            }
            return list;
        }
        @Override
        void populate(Random rnd) {
            ListBenchmark.populate(list, rnd);
        }
        private final ArrayList<Point> list;
    }

    private static class SequentialRemoveByIndex extends FilterStrategy {
        public SequentialRemoveByIndex() {
            list = new LinkedList<Point>();
        }
        @Override
        void clear() {
            list.clear();
        }
        @Override
        Collection<Point> filter() {
            for (int i = 0; i < list.size();) {
                if (wanted(list.get(i))) {
                       i;
                } else {
                    list.remove(i);
                }
            }
            return list;
        }
        @Override
        void populate(Random rnd) {
            ListBenchmark.populate(list, rnd);
        }
        private final LinkedList<Point> list;
    }

    private static class ShiftDown extends FilterStrategy {
        public ShiftDown() {
            list = new ArrayList<Point>();
        }
        @Override
        void clear() {
            list.clear();
        }
        @Override
        Collection<Point> filter() {
            int inputSize = list.size();
            int outputSize = 0;
            for (int i = 0; i < inputSize;    i) {
                Point p = list.get(i);
                if (wanted(p)) {
                    list.set(outputSize  , p);
                }
            }
            list.subList(outputSize, inputSize).clear();
            return list;
        }
        @Override
        void populate(Random rnd) {
            ListBenchmark.populate(list, rnd);
        }
        private final ArrayList<Point> list;
    }

}

Bunu Paylaş:
  • Google+
  • E-Posta
Etiketler:

YORUMLAR

SPONSOR VİDEO

Rastgele Yazarlar

  • Autocar

    Autocar

    11 Mart 2006
  • Awesome Toys TV

    Awesome Toys

    18 HAZİRAN 2014
  • Kanál používateľa McsFuego

    Kanál použ

    12 EKİM 2011

İLGİLİ SORU / CEVAPLAR