🛒 🤲🏻 🍖 स्विच स्टेटमेंट की सूक्ष्मता 🎳 👡 🕯️

हां, यह जेडीके 7 में सबसे आम स्विच पर एक संपूर्ण लेख है। ऐसा होता है कि संचित सामग्री दिलचस्प और कम ज्ञात लगती है, और फिर यह पता चलता है कि प्रवेश द्वार पर किसी भी दादी को 50 साल के लिए स्विच कार्यान्वयन सुविधाओं के बारे में पता है। लेकिन मैं कोशिश करूंगा। शुरुआत के लिए, मैं 3 प्रश्न सुझाता हूं:

(सरल) इस कोड का परिणाम क्या है?

switch(5){ default: System.out.print(0); case 1: System.out.print(1); break; case 4: System.out.print(4); case 2: System.out.print(2); }

निम्नलिखित 2 विकल्प लगभग समान हैं। थोड़ा अलग शाब्दिक।

 // 1 switch("BBBBBB"){ case "AaAaAa": break; case "AaAaBB": break; case "AaBBAa": break; case "AaBBBB": break; case "BBAaAa": break; case "BBAaBB": break; case "BBBBAa": break; case "BBBBBB": break; }

 // 2 switch("BBBBBB_8"){ case "AaAaAa_1": break; case "AaAaBB_2": break; case "AaBBAa_3": break; case "AaBBBB_4": break; case "BBAaAa_5": break; case "BBAaBB_6": break; case "BBBBAa_7": break; case "BBBBBB_8": break; }

पहला स्विच कई बार धीमा क्यों चल रहा है, कम से कम JIT अक्षम (-Djava.compiler = NONE) के साथ? अपने आप को एक लूप में जांचें! आप ऐसे कोड के साथ जेआईटी के लिए सक्षम नहीं होंगे, लेकिन यदि आप थोड़ा खेलते हैं, तो एक छोटा अंतर ध्यान देने योग्य होगा।

एन मामलों (कम से कम जेडीके 7 में) के बीच समान मूल्य खोजने के लिए एल्गोरिथ्म की कम्प्यूटेशनल जटिलता क्या है?

जवाब:

01
हैशकोड () विधि पहले स्विच की सभी लाइनों के लिए समान मान लौटाती है। नीचे विवरण।
मामले के आधार पर, यह ओ (1), ओ (लॉग एन) और यहां तक कि ओ (एन) तक पहुंच सकता है।

चलो ठीक है। मामला मूल्यों, संक्षिप्तता के लिए, मैं चाबियाँ कॉल करूंगा।

TableSwitch

पहले कार्य से एक उदाहरण लेते हैं। इसे संकलित करें और परिणामस्वरूप बाइटकोड को अलग करें।

 javap -c Main.class

  0: iconst_5 //  5   1: tableswitch { // 1 to 4 //  3       1: 39 // 39, 56, 32, 49 –    2: 56 3: 32 4: 49 default: 32 } 32: getstatic #27 // Field java/lang/System.out:Ljava/io/PrintStream; 35: iconst_0 36: invokevirtual #33 // Method java/io/PrintStream.print:(I)V 39: getstatic #27 // Field java/lang/System.out:Ljava/io/PrintStream; 42: iconst_1 43: invokevirtual #33 // Method java/io/PrintStream.print:(I)V 46: goto 63 // break 49: getstatic #27 // Field java/lang/System.out:Ljava/io/PrintStream; 52: iconst_4 53: invokevirtual #33 // Method java/io/PrintStream.print:(I)V 56: getstatic #27 // Field java/lang/System.out:Ljava/io/PrintStream; 59: iconst_2 60: invokevirtual #33 // Method java/io/PrintStream.print:(I)V 63: return

हम विशेष रूप से लेबल किए गए निर्देश में रुचि रखते हैं। इसका मतलब है कि कंपाइलर ने बिना किसी अपवाद के सबसे छोटी से लेकर सबसे बड़ी तक के सभी मूल्यों के लिए संक्रमण पतों से युक्त एक तालिका (सरणी) बनाई। स्विच निष्पादन एल्गोरिथ्म कुछ इस तरह है (छद्म कोड):

 if (val<low || val>high){ jump default; }else{ jump table[val - low]; }

हमारे मामले में: निम्न == 1, उच्च == 4, तालिका == {39, 56, 32, 49}। चूंकि कम से उच्च तक की सभी चाबियां अनुक्रम में तालिका में होनी चाहिए, इसलिए कंपाइलर को कुंजी 3 को जोड़ना होगा और इसके लिए उसी तरह का व्यवहार निर्धारित करना चाहिए जो डिफ़ॉल्ट रूप में है।

निर्देश 32 के साथ शुरू, सभी मामले और डिफ़ॉल्ट के लिए कोड उस क्रम में है जिसमें वे स्रोत कोड में स्थित हैं। मोटे तौर पर, यहां संकलक निरंतर प्रमुख हैंडलर का कोड बनाता है। मुझे लगता है कि अब यह स्पष्ट हो गया है कि, एक मैच पाए जाने के बाद, जब तक पहला ब्रेक नहीं होता तब तक निष्पादन जारी रहता है।

LookupSwitch

एक वाजिब सवाल उठता है: क्या होगा यदि कुंजियों के मूल्य बहुत कम हैं? यदि हमारे पास उनमें से केवल दो: 1 और 1,000,000 हैं, तो एक लाख तत्वों के साथ एक सरणी बनाने के लिए यह बहुत नासमझी है। हमारे उदाहरण में कुंजी 4 को 10 में बदलें, यह पर्याप्त होगा (यदि अचानक नहीं, तो इसे बढ़ाएं)। हम बायटेकोड को देखते हैं (हैंडलर का बायटेकोड लगभग समान ही रहा, इसलिए नहीं दिखाया गया):

  1: lookupswitch { // 3 1: 43 2: 60 10: 53 default: 36 }

यहां एक टेबल भी सेट की गई है, लेकिन जोड़े के लिए: कुंजी संक्रमण लेबल है। JVM विनिर्देशन कहता है कि हालाँकि खोज रैखिक हो सकती है, कुंजी को तेज़ खोज को सक्षम करने के लिए क्रमबद्ध किया जाना चाहिए, हालाँकि खोज विधि स्वयं निर्दिष्ट नहीं है। शायद कुछ कार्यान्वयन रैखिक खोज का उपयोग करते हैं। यह पहला मामला है जो मुझे पता है (यद्यपि सैद्धांतिक) स्विच ओ (एन) की जटिलता के साथ। आगे हम एक और, अधिक मूर्त देखेंगे।

असली लड़के और लड़कियां पूछते हैं: कंपाइलर कैसे तय करता है कि क्या चुनना है - टेबलवॉच या लुकअपस्विच? और सबसे वास्तविक लोग OpenJDK स्रोतों को डाउनलोड करते हैं (ध्यान दें, अन्य JDK कार्यान्वयन में पसंद की विधि भिन्न हो सकती है) और com.sun.tools.javac.jvm.Gv.jen.java में ओपनजडक / langtools / src / share / classes में सेस विधि का अध्ययन करें।

  // Determine whether to issue a tableswitch or a lookupswitch // instruction. long table_space_cost = 4 + ((long) hi - lo + 1); // words long table_time_cost = 3; // comparisons long lookup_space_cost = 3 + 2 * (long) nlabels; long lookup_time_cost = nlabels; int opcode = nlabels > 0 && table_space_cost + 3 * table_time_cost <= lookup_space_cost + 3 * lookup_time_cost ? tableswitch : lookupswitch;

table_space_cost - इस आकार में श्रेणी के सभी मानों की संख्या, लो के लिए एक मान, hi, default_address और चयनित स्विच विधि (टेबलविच) के मार्कर शामिल हैं।
table_time_cost - 3 ऑपरेशन: रेंज (न्यूनतम और अधिकतम) में प्रवेश की जांच करना और तालिका से पता लेबल निकालना।
लुकअप_स्पेस_कॉस्ट - प्रत्येक कुंजी-पता जोड़ी के लिए २ मान, और तालिका के आकार के लिए एक मान, default_address, और चयनित स्विच विधि (लुकअपस्विच) के लिए एक मार्कर।
लुकिंग_टाइम_कॉस्ट - सबसे खराब स्थिति मान ली जाती है - एक रेखीय खोज।

और एल्गोरिथ्म ही, जैसा कि आप देखते हैं, सरल है। जादू नंबर 3 ("और ये लोग हमें अपनी नाक चुनने के लिए मना करते हैं" (सी)) सबसे अधिक संभावना है।

स्ट्रिंग तुलना

"String.hashCode में आसानी से टकराव हो सकता है। String.equals बहुत धीमा है, हो सकता है कि स्ट्रिंग्स को नजरबंद कर दिया गया हो?" - इसलिए मैंने सोचा, जब तक मैंने बायटेकोड नहीं सीखा।

 switch(""){ case "AA": break; case "BB": break; }

  0: ldc #27 // String 2: dup 3: astore_0 4: invokevirtual #29 // Method java/lang/String.hashCode:()I 7: lookupswitch { // 2 2080: 32 2112: 44 default: 73 } 32: aload_0 33: ldc #35 // String AA 35: invokevirtual #37 // Method java/lang/String.equals:(Ljava/lang/Object;)Z 38: ifne 56 41: goto 73 44: aload_0 45: ldc #41 // String BB 47: invokevirtual #37 // Method java/lang/String.equals:(Ljava/lang/Object;)Z 50: ifne 66 53: goto 73 56: getstatic #43 // Field java/lang/System.out:Ljava/io/PrintStream; 59: iconst_1 60: invokevirtual #49 // Method java/io/PrintStream.println:(I)V 63: goto 73 66: getstatic #43 // Field java/lang/System.out:Ljava/io/PrintStream; 69: iconst_2 70: invokevirtual #49 // Method java/io/PrintStream.println:(I)V 73: return

यही है, संकलन चरण में, सभी कुंजी के हैश कोड की गणना की जाती है। लुकअपस्विच हमेशा स्ट्रिंग्स के लिए निष्पादित किया जाता है, भले ही हैश सुसंगत हो। जब निष्पादित किया जाता है, तो सशर्त अभिव्यक्ति के हैश कोड की गणना की जाती है और यह हैश की कुंजियों के साथ तुलना की जाती है। यदि वे मेल खाते हैं, तो स्ट्रिंग्स की तुलना भी की जाती है (संभावित 32-53 पते) का उपयोग करके संभावित टकराव को रोकने के लिए String.equals () विधि का उपयोग किया जाता है। और, सफल होने पर, संबंधित अभिव्यक्ति (56-70) के कार्यान्वयन के लिए संक्रमण।

और अगर हमारे पास एक ही हैश के साथ कई चाबियां हैं?

 switch(""){ case "Aa": break; case "BB": break; }

  7: lookupswitch { // 1 2112: 24 default: 62 } 24: aload_0 25: ldc #35 // String Aa 27: invokevirtual #37 // Method java/lang/String.equals:(Ljava/lang/Object;)Z 30: ifne 45 33: aload_0 34: ldc #41 // String BB 36: invokevirtual #37 // Method java/lang/String.equals:(Ljava/lang/Object;)Z 39: ifne 55 42: goto 62 45: getstatic #43 // Field java/lang/System.out:Ljava/io/PrintStream; 48: iconst_1 49: invokevirtual #49 // Method java/io/PrintStream.println:(I)V 52: goto 62 55: getstatic #43 // Field java/lang/System.out:Ljava/io/PrintStream; 58: iconst_2 59: invokevirtual #49 // Method java/io/PrintStream.println:(I)V 62: return

फिर इन कुंजियों को लुकअपस्विच में एक हैश कुंजी के तहत संयोजित किया जाता है, और, यदि कुंजी मेल खाती है, तो इस हैश के साथ सभी लाइनों पर पुनरावृत्तियां होती हैं और String.equals () का उपयोग करके उनकी तुलना करती हैं। 2 प्रश्न से उदाहरण के रूप में कई 8 तुलना करता है। यहाँ जटिलता ओ (n) के साथ दूसरा मामला है।

निष्कर्ष

यदि यह JIT के लिए नहीं था, तो हम स्विच ऑप्टिमाइज़ेशन के बारे में तर्क दे सकते हैं। लेकिन मुझे एक अच्छा उदाहरण नहीं मिल पा रहा था, जिसमें टेबलविच लुकस्विच (जेआईटी सक्षम के साथ) की तुलना में काफी तेज होगा। खैर, शायद यह:
1. मान लीजिए कि हमारे पास 1 से एन के मूल्यों के साथ एन कुंजी हैं। इस मामले में, टेबलवॉच का उपयोग किया जाएगा।
2. एक ही कुंजी, लेकिन प्लस एक और, एन के मुकाबले बहुत अधिक मूल्य के साथ। इस मामले में, लुकअपस्विच का उपयोग किया जाएगा।
(जेआईटी विकलांगों के साथ, सब कुछ स्पष्ट है, अंतर स्पष्ट है।)
JIT से कोई अंतर नहीं है। शायद वह सभी कुंजियों को कई श्रेणियों में तोड़ता है और उन्हें टेबलवॉच की तरह मानता है। हालांकि, एन = 721 से शुरू करके, मैंने दूसरे उदाहरण के प्रदर्शन में तेज गिरावट का अनुभव किया।

अंत में, केवल बहुत ही जंगली सलाह खुद को सुझाव देती है, उन्हें एक मज़ाक समझें: "दोस्तों, अगर आपके पास एक चक्र में कुछ को छोड़कर लगातार चाबियों के साथ 1000 मामले हैं जिन्हें प्रति सेकंड सौ मिलियन बार निष्पादित किया जाना चाहिए, तो इन कुछ कुंजियों को स्विच के बाहर संसाधित करें। और अगर इस लूप में उसी हैश के साथ स्ट्रिंग कुंजियों का एक गुच्छा है, तो अन्य कार्यान्वयन विधियों के बारे में सोचें। "

स्विच स्टेटमेंट की सूक्ष्मता

TableSwitch

LookupSwitch

स्ट्रिंग तुलना

निष्कर्ष

More articles: