java - जावा के ऐरेलिस्ट के निकालने का कार्य इतना महंगा क्यों लगता है?




performance optimization (4)

मेरे पास एक ऐसा कार्य है जो 250,000 वस्तुओं से अधिक की एक बड़ी सूची में हेरफेर करता है। उन वस्तुओं में से अधिकांश के लिए, यह आइटम को स्थिति x पर बस बदल देता है। हालांकि, उनमें से लगभग 5% के लिए, उन्हें सूची से हटा देना चाहिए।

एक लिंक्डलिस्ट का उपयोग महंगा निकासी से बचने के लिए सबसे स्पष्ट समाधान प्रतीत होता था। हालांकि, स्वाभाविक रूप से, सूचकांक द्वारा लिंक्डलिस्ट तक पहुंचने से समय धीमा हो जाता है। यहां लागत मिनट है (और उनमें से बहुत से)।

उस लिंक्डलिस्ट पर एक इटरेटर का उपयोग करना भी महंगा है, क्योंकि मुझे उस सूची को संपादित करते समय इटरेटर समवर्ती मुद्दों से बचने के लिए एक अलग प्रति की आवश्यकता होती है। यहां लागत मिनट है।

हालांकि, यहां मेरा दिमाग उड़ाया गया है। अगर मैं एक ऐरेलिस्ट में बदल जाता हूं, तो यह लगभग तुरंत चलता है।

2 9 7515 तत्वों के साथ एक सूची के लिए, 11958 तत्वों को हटाने और बाकी सब कुछ संशोधित करने के लिए 90 9एमएस लगता है। मैंने सत्यापित किया कि परिणामस्वरूप सूची वास्तव में आकार में 285557 है, जैसा कि अपेक्षित है, और इसमें आवश्यक अद्यतन जानकारी शामिल है।

यह इतना तेज़ क्यों है? मैंने जेडीके 6 में ऐरेलिस्ट के स्रोत को देखा और ऐसा लगता है कि यह अपेक्षित के रूप में एक एरेकॉपी फ़ंक्शन का उपयोग कर रहा है। मुझे यह समझना अच्छा लगेगा कि क्यों एक ArrayList यहां अच्छा काम करता है जब सामान्य ज्ञान यह इंगित करता है कि इस कार्य के लिए एक सरणी एक भयानक विचार है, जिसमें कई सौ हजार वस्तुओं को स्थानांतरित करने की आवश्यकता है।


ऐरे कॉपी एक बल्कि सस्ती ऑपरेशन है। यह एक बहुत ही बुनियादी स्तर पर किया जाता है (इसकी जावा मूल स्थैतिक विधि) और आप अभी तक उस सीमा में नहीं हैं जहां प्रदर्शन वास्तव में महत्वपूर्ण हो जाता है।

आपके उदाहरण में आप आकार 150000 (औसतन) की लगभग 12000 गुना प्रतिलिपि बनाते हैं। इसमें ज्यादा समय नहीं लगता है। मैंने इसे अपने लैपटॉप पर यहां परीक्षण किया और इसमें 500 एमएस से भी कम समय लगा।

अद्यतन मैंने अपने लैपटॉप (इंटेल पी 8400) को मापने के लिए निम्न कोड का उपयोग किया

import java.util.Random;

public class PerformanceArrayCopy {

    public static void main(String[] args) {

        int[] lengths = new int[] { 10000, 50000, 125000, 250000 };
        int[] loops = new int[] { 1000, 5000, 10000, 20000 };

        for (int length : lengths) {
            for (int loop : loops) {

                Object[] list1 = new Object[length];
                Object[] list2 = new Object[length];

                for (int k = 0; k < 100; k++) {
                    System.arraycopy(list1, 0, list2, 0, list1.length);
                }

                int[] len = new int[loop];
                int[] ofs = new int[loop];

                Random rnd = new Random();
                for (int k = 0; k < loop; k++) {
                    len[k] = rnd.nextInt(length);
                    ofs[k] = rnd.nextInt(length - len[k]);
                }

                long n = System.nanoTime();
                for (int k = 0; k < loop; k++) {
                    System.arraycopy(list1, ofs[k], list2, ofs[k], len[k]);
                }
                n = System.nanoTime() - n;
                System.out.print("length: " + length);
                System.out.print("\tloop: " + loop);
                System.out.print("\truntime [ms]: " + n / 1000000);
                System.out.println();
            }
        }
    }
}

कुछ परिणाम:

length: 10000   loop: 10000 runtime [ms]: 47
length: 50000   loop: 10000 runtime [ms]: 228
length: 125000  loop: 10000 runtime [ms]: 575
length: 250000  loop: 10000 runtime [ms]: 1198

दिलचस्प और अप्रत्याशित परिणाम। यह सिर्फ एक परिकल्पना है, लेकिन ...

आपके सरणी तत्व निकासी के औसत में से एक को आपकी सूची का आधा भाग (इसके बाद सब कुछ) वापस ले जाना होगा। यदि प्रत्येक आइटम किसी ऑब्जेक्ट (8 बाइट्स) के लिए 64-बिट पॉइंटर है, तो इसका मतलब 125000 आइटम x 8 बाइट प्रति पॉइंटर = 1 एमबी की प्रतिलिपि बनाना है।

एक आधुनिक सीपीयू रैम को जल्दी से 1 एमबी रैम के एक संगत ब्लॉक की प्रतिलिपि बना सकता है।

प्रत्येक एक्सेस के लिए एक लिंक्ड सूची पर लूपिंग की तुलना में, जिसमें तुलना और शाखाकरण और अन्य सीपीयू असभ्य गतिविधियों की आवश्यकता होती है, रैम कॉपी तेज़ है।

आपको वास्तव में विभिन्न परिचालनों को स्वतंत्र रूप से बेंचमार्क करने का प्रयास करना चाहिए और विभिन्न सूची कार्यान्वयन के साथ वे कितने कुशल हैं। यदि आप करते हैं तो अपने परिणाम यहां साझा करें!


मैं सूची तत्वों को फ़िल्टर करने के लिए निम्न में से प्रत्येक रणनीति का प्रयास करके एक बेंचमार्क चला गया:

  • वांछित तत्वों को एक नई सूची में कॉपी करें
  • ArrayList से अवांछित तत्वों को निकालने के लिए Iterator.remove() का उपयोग करें
  • एक LinkedList से अवांछित तत्वों को हटाने के लिए Iterator.remove() का उपयोग करें
  • सूची में सूची को कॉम्पैक्ट करें (इच्छित तत्वों को कम पदों पर ले जाना)
  • एक ArrayList पर अनुक्रमणिका ( List.remove(int) ) द्वारा निकालें
  • एक List.remove(int) इंडेक्स ( List.remove(int) ) द्वारा निकालें

प्रत्येक बार जब मैंने Point 100000 यादृच्छिक उदाहरणों के साथ सूची बनाई और एक फ़िल्टर स्थिति (हैश कोड के आधार पर) का उपयोग किया जो 95% तत्व स्वीकार करेगा और शेष 5% को अस्वीकार करेगा (प्रश्न में वर्णित वही अनुपात, लेकिन एक छोटे से सूची क्योंकि मेरे पास 250000 तत्वों के लिए परीक्षण चलाने के लिए समय नहीं था।)

और औसत समय (मेरे पुराने मैकबुक प्रो पर: कोर 2 डुओ, 2.2GHz, 3 जीबी रैम) थे:

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

तो एक LinkedList से इंडेक्स द्वारा तत्वों को हटाकर उन्हें ऐरेलिस्ट से हटाने की तुलना में 300 गुना अधिक महंगा था, और शायद अन्य तरीकों की तुलना में कहीं अधिक 6000-10000 गुना अधिक महंगी (जो रैखिक खोज और arraycopy )

यहां चार तेज तरीकों के बीच बहुत अंतर नहीं लग रहा है, लेकिन मैंने निम्नलिखित परिणामों के साथ 500000-तत्व सूची के साथ उन चारों को फिर से चलाया:

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

मुझे लगता है कि बड़े आकार के कैश मेमोरी के साथ सीमित कारक बन जाता है, इसलिए सूची की दूसरी प्रति बनाने की लागत महत्वपूर्ण हो जाती है।

यहां कोड है:

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

}

मैं मौलिक अंतर की व्याख्या करने के लिए यहां उद्देश्य पर कुछ कार्यान्वयन विवरण छोड़ रहा हूं।

एम तत्वों की सूची के एन-वें तत्व को हटाने के लिए, लिंक्डलिस्ट कार्यान्वयन इस तत्व पर नेविगेट करेगा, फिर बस इसे हटा दें और तदनुसार एन -1 और एन + 1 तत्वों के पॉइंटर्स अपडेट करें। यह दूसरा ऑपरेशन बहुत आसान है, लेकिन यह इस तत्व तक पहुंच रहा है जो आपको समय देता है।

हालांकि, एक ArrayList के लिए, एक्सेस समय तात्कालिक है क्योंकि इसे एक सरणी द्वारा समर्थित किया जाता है, जिसका अर्थ है स्मृति स्मृति। आप प्रदर्शन करने के लिए सीधे, सही बोलने के लिए सही मेमोरी पते पर कूद सकते हैं:

  • एम -1 तत्वों की एक नई सरणी को पुन: आवंटित करें
  • नई सरणीसूची के सरणी में इंडेक्स 0 पर सबकुछ 0 से एन -1 तक रखें
  • सरणीसूची की सरणी में इंडेक्स एन पर सबकुछ एन + 1 से एम डाल दें।

इसके बारे में सोचते हुए, आप देखेंगे कि आप उसी सरणी का पुन: उपयोग भी कर सकते हैं क्योंकि जावा पूर्व-आवंटित आकारों के साथ ऐरेलिस्ट का उपयोग कर सकता है, इसलिए यदि आप तत्वों को हटाते हैं तो आप चरण 1 और 2 छोड़ सकते हैं और सीधे चरण 3 कर सकते हैं और अपना आकार अपडेट कर सकते हैं।

मेमोरी एक्सेस तेज हैं, और स्मृति के एक हिस्से की प्रतिलिपि बनाना संभवतः आधुनिक हार्डवेयर पर पर्याप्त तेज़ है जो एन-स्थिति में जाने में बहुत समय ले रहा है।

हालांकि, क्या आप अपनी लिंक्डलिस्ट को इस तरह से उपयोग कर सकते हैं कि यह आपको एक-दूसरे का अनुसरण करने वाले कई तत्वों को हटाने और आपकी स्थिति का ट्रैक रखने की अनुमति देता है, तो आप एक लाभ देखेंगे।

लेकिन स्पष्ट रूप से, एक लंबी सूची में, एक साधारण निकालना (i) करना महंगा होगा।

इस पर नमक और मसाले का एक झुकाव जोड़ने के लिए:

  • ऐरे डेटा संरचना पर दक्षता पर ध्यान दें और गतिशील ऐरे Wikipedia प्रविष्टियों पर प्रदर्शन पर नोट , जो आपकी चिंता का वर्णन करता है।
  • ध्यान रखें कि स्मृति मेमोरी का उपयोग करने के लिए जिसमें आवश्यक स्मृति की आवश्यकता होती है, अच्छी तरह से, संगत स्मृति की आवश्यकता होती है। जिसका अर्थ है कि आपकी वर्चुअल मेमोरी को संगत हिस्सों को आवंटित करने में सक्षम होना आवश्यक है। या यहां तक ​​कि जावा के साथ, आप अपने जेवीएम को एक अस्पष्ट आउटऑफमेमरी अपवाद के साथ खुशी से नीचे जाकर देखेंगे जो निम्न स्तर के क्रैश में अपना कारण ले रहा है।






arraylist