java - क्यों एक सॉर्ट किए गए सरणी*धीमे सरणी की तुलना में धीमी*प्रक्रिया कर रहा है?(जावा के ArrayList.indexOf)




performance (2)

एक सरल उदाहरण के रूप में जो उत्तर की पुष्टि wero द्वारा और अपंगिन (+1!) द्वारा उत्तर देता है : निम्नलिखित दोनों विकल्पों की एक सरल तुलना करता है:

  • यादृच्छिक संख्या बनाना, और उन्हें वैकल्पिक रूप से छांटना
  • अनुक्रमिक संख्याएं बनाना, और उन्हें वैकल्पिक रूप से फेरबदल करना

इसे जेएमएच बेंचमार्क के रूप में भी लागू नहीं किया जाता है, लेकिन मूल कोड के समान, प्रभाव का पालन करने के लिए केवल मामूली संशोधनों के साथ:

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Random;

public class SortedListTest
{
    private static final long SLOW_ITERATION_MILLIS = 1000L * 3L;

    public static void main(String[] args)
    {
        int size = 100000;
        testBinarySearchOriginal(size, true);
        testBinarySearchOriginal(size, false);
        testBinarySearchShuffled(size, true);
        testBinarySearchShuffled(size, false);
    }

    public static void testBinarySearchOriginal(int size, boolean sort)
    {
        Random r = new Random(0);
        List<Double> list = new ArrayList<>(size);
        for (int i = 0; i < size; i++)
        {
            list.add(r.nextDouble());
        }
        if (sort)
        {
            Collections.sort(list);
        }
        list = new ArrayList<>(list);

        int count = 0;
        int nIterations = 0;
        long startTime = System.currentTimeMillis();
        do
        {
            int index = r.nextInt(size);
            if (index == list.indexOf(list.get(index)))
            {
                count++;
            }
            nIterations++;
        }
        while (System.currentTimeMillis() < startTime + SLOW_ITERATION_MILLIS);
        long duration = System.currentTimeMillis() - startTime;
        double slowFindsPerSec = (double) nIterations / duration * 1000;

        System.out.printf("Size %8d sort %5s iterations %10.3f count %10d\n",
            size, sort, slowFindsPerSec, count);
    }

    public static void testBinarySearchShuffled(int size, boolean sort)
    {
        Random r = new Random(0);
        List<Double> list = new ArrayList<>(size);
        for (int i = 0; i < size; i++)
        {
            list.add((double) i / size);
        }
        if (!sort)
        {
            Collections.shuffle(list);
        }
        list = new ArrayList<>(list);

        int count = 0;
        int nIterations = 0;
        long startTime = System.currentTimeMillis();
        do
        {
            int index = r.nextInt(size);
            if (index == list.indexOf(list.get(index)))
            {
                count++;
            }
            nIterations++;
        }
        while (System.currentTimeMillis() < startTime + SLOW_ITERATION_MILLIS);
        long duration = System.currentTimeMillis() - startTime;
        double slowFindsPerSec = (double) nIterations / duration * 1000;

        System.out.printf("Size %8d sort %5s iterations %10.3f count %10d\n",
            size, sort, slowFindsPerSec, count);
    }

}

मेरी मशीन पर आउटपुट है

Size   100000 sort  true iterations   8560,333 count      25681
Size   100000 sort false iterations  19358,667 count      58076
Size   100000 sort  true iterations  18554,000 count      55662
Size   100000 sort false iterations   8845,333 count      26536

अच्छी तरह से दिखा रहा है कि समय बिल्कुल दूसरे के विपरीत हैं: यदि यादृच्छिक संख्याओं को क्रमबद्ध किया जाता है, तो क्रमबद्ध संस्करण धीमा है। यदि अनुक्रमिक संख्याओं में फेरबदल किया जाता है, तो फेरबदल संस्करण धीमा होता है।

शीर्षक इस संदर्भ में है कि अनसोल्ड सरणी की तुलना में सॉर्ट किए गए सरणी को संसाधित करना अधिक तेज़ क्यों है?

क्या यह एक शाखा भविष्यवाणी प्रभाव भी है? खबरदार: यहाँ सॉर्ट किए गए सरणी के लिए प्रसंस्करण धीमा है !!

निम्नलिखित कोड पर विचार करें:

private static final int LIST_LENGTH = 1000 * 1000;
private static final long SLOW_ITERATION_MILLIS = 1000L * 10L;

@Test
public void testBinarySearch() {
    Random r = new Random(0);
    List<Double> list = new ArrayList<>(LIST_LENGTH);
    for (int i = 0; i < LIST_LENGTH; i++) {
        list.add(r.nextDouble());
    }
    //Collections.sort(list);
    // remove possible artifacts due to the sorting call
    // and rebuild the list from scratch:
    list = new ArrayList<>(list);

    int nIterations = 0;
    long startTime = System.currentTimeMillis();
    do {
        int index = r.nextInt(LIST_LENGTH);
        assertEquals(index, list.indexOf(list.get(index)));
        nIterations++;
    } while (System.currentTimeMillis() < startTime + SLOW_ITERATION_MILLIS);
    long duration = System.currentTimeMillis() - startTime;
    double slowFindsPerSec = (double) nIterations / duration * 1000;
    System.out.println(slowFindsPerSec);

    ...
}

यह मेरी मशीन पर लगभग 720 के मूल्य को प्रिंट करता है।

अब अगर मैं संग्रह सॉर्ट कॉल को सक्रिय करता हूं, तो यह मूल्य 142 तक गिर जाता है। क्यों?

परिणाम निर्णायक हैं, अगर मैं पुनरावृत्तियों / समय की संख्या बढ़ाता हूं तो वे नहीं बदलते हैं।

जावा संस्करण 1.8.0_71 (ओरेकल वीएम, 64 बिट), विंडोज 10 के तहत चल रहा है, एक्लिप्स मंगल में जेनेट परीक्षण।

अपडेट करें

सन्निहित मेमोरी एक्सेस (यादृच्छिक क्रम में बनाम क्रमिक क्रम में एक्सेस की गई डबल ऑब्जेक्ट) से संबंधित प्रतीत होता है। प्रभाव मेरे लिए लगभग 10k और उससे कम की सरणी लंबाई के लिए गायब हो जाता है।

परिणाम प्रदान करने के लिए assylias का धन्यवाद:

/**
 * Benchmark                     Mode  Cnt  Score   Error  Units
 * SO35018999.shuffled           avgt   10  8.895 ± 1.534  ms/op
 * SO35018999.sorted             avgt   10  8.093 ± 3.093  ms/op
 * SO35018999.sorted_contiguous  avgt   10  1.665 ± 0.397  ms/op
 * SO35018999.unsorted           avgt   10  2.700 ± 0.302  ms/op
 */

मुझे लगता है कि हम मेमोरी कैश मिस का असर देख रहे हैं:

जब आप अनसुलझी सूची बनाते हैं

for (int i = 0; i < LIST_LENGTH; i++) {
    list.add(r.nextDouble());
}

सभी डबल एक सन्निहित स्मृति क्षेत्र में आवंटित किए जाने की संभावना है। इसके माध्यम से Iterating कुछ कैश मिस उत्पन्न करेगा।

दूसरी ओर क्रमबद्ध सूची में, संदर्भ अव्यवस्थित तरीके से स्मृति को इंगित करते हैं।

अब यदि आप सन्निहित स्मृति के साथ एक क्रमबद्ध सूची बनाते हैं:

Collection.sort(list);
List<Double> list2 = new ArrayList<>();
for (int i = 0; i < LIST_LENGTH; i++) {
    list2.add(new Double(list.get(i).doubleValue()));
}

इस क्रमबद्ध सूची में मूल एक (मेरे समय) की तुलना में समान प्रदर्शन है।






arraylist