एक अनुक्रमित सरणी की तुलना में एक क्रमबद्ध सरणी * धीमी * प्रसंस्करण क्यों कर रहा है? (जावा का ArrayList.indexOf)

Question

शीर्षक Why is it faster to process a sorted array than an unsorted array?

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

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 और उससे कम की सरणी लंबाई के लिए प्रभाव मेरे लिए गायब हो जाता है। the results प्रदान करने के लिए 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 
*/ 

Answer 1

यह कैशिंग/प्रीफेचिंग प्रभाव की तरह दिखता है।

सुराग यह है कि आप डबल्स (ऑब्जेक्ट्स) की तुलना करते हैं, डबल्स (प्राइमेटिव्स) नहीं। जब आप एक थ्रेड में ऑब्जेक्ट आवंटित करते हैं, तो उन्हें आमतौर पर स्मृति में क्रमशः आवंटित किया जाता है। तो जब indexOf एक सूची स्कैन करता है, तो यह अनुक्रमिक स्मृति पते के माध्यम से जाता है। यह सीपीयू कैश prefetching heuristics के लिए अच्छा है।

लेकिन जब आप सूची को सॉर्ट करते हैं, तो आपको अभी भी औसत मेमोरी लुकअप की संख्या समान होती है, लेकिन इस बार मेमोरी एक्सेस यादृच्छिक क्रम में होगी।

अद्यतन

Here is the benchmark साबित होता है कि आवंटित वस्तुओं का क्रम महत्वपूर्ण।

Benchmark   (generator) (length) (postprocess) Mode Cnt Score Error Units 
ListIndexOf.indexOf  random 1000000   none avgt 10 1,243 ± 0,031 ms/op 
ListIndexOf.indexOf  random 1000000   sort avgt 10 6,496 ± 0,456 ms/op 
ListIndexOf.indexOf  random 1000000  shuffle avgt 10 6,485 ± 0,412 ms/op 
ListIndexOf.indexOf sequential 1000000   none avgt 10 1,249 ± 0,053 ms/op 
ListIndexOf.indexOf sequential 1000000   sort avgt 10 1,247 ± 0,037 ms/op 
ListIndexOf.indexOf sequential 1000000  shuffle avgt 10 6,579 ± 0,448 ms/op 

Answer 2

मुझे लगता है कि हम कैश मेमोरी छूट जाए के प्रभाव को देख रहे हैं:

आप अवर्गीकृत सूची

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

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

दूसरी ओर क्रमबद्ध सूची में संदर्भ एक अराजक तरीके से स्मृति को इंगित करते हैं।

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

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

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

Answer 3

एक सरल उदाहरण है कि answer by wero और answer by apangin की पुष्टि करता है के रूप में (+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 

अच्छी तरह से दिखा रहा है कि समय वास्तव में एक और के विपरीत हो रहा है: मूल कोड, केवल मामूली परिवर्तनों के साथ प्रभाव का निरीक्षण करने के लिए , तो क्रमबद्ध संस्करण धीमा है। यदि अनुक्रमिक संख्या shuffled हैं, तो shuffled संस्करण धीमा है।