शिफ्ट ऑपरेशंस O(1) या O(n) हैं?थोड़ा स्थानांतरण ओ (1) या ओ (एन) है?
क्या यह समझ में आता है कि कंप्यूटर को आम तौर पर 1 स्थान स्थानांतरित करने के बजाय 31 स्थानों को स्थानांतरित करने के लिए अधिक संचालन की आवश्यकता होती है?
या यह समझ संचालन की संख्या स्थानांतरण के लिए आवश्यक पड़ता है की कितनी जगहों हम बदलाव की जरूरत है भले ही निरंतर है?
पुनश्च: सोच हार्डवेयर एक उपयुक्त टैग है ..
कुछ निर्देश सेट प्रति निर्देश एक बिट शिफ्ट तक ही सीमित हैं।और कुछ निर्देश सेट आपको एक निर्देश में स्थानांतरित करने के लिए किसी भी बिट्स को निर्दिष्ट करने की अनुमति देते हैं, जो आमतौर पर आधुनिक प्रोसेसर पर एक घड़ी चक्र लेता है (आधुनिक जानबूझकर अस्पष्ट शब्द)। एक बैरल शिफ्टर के बारे में dan04's answer देखें, एक सर्किट जो एक ऑपरेशन में एक से अधिक बिट को स्थानांतरित करता है।
यह सब लॉजिक एल्गोरिदम पर उबाल जाता है। परिणाम में प्रत्येक बिट इनपुट के आधार पर एक तर्क कार्य है। एक भी सही बदलाव के लिए, एल्गोरिथ्म की तरह कुछ होगा: शिक्षा [सही पारी] और इनपुट के बिट 1 1 है तो
लेकिन तर्क समीकरण बस के रूप में आसानी से हो सकता है:
लॉजिक गेट्स, असीमित होने के कारण, यह सब एक घड़ी चक्र में कर सकते हैं। फिर भी यह सच है कि एक ही शिफ्ट एक तेज घड़ी चक्र और कम द्वारों को व्यवस्थित करने की अनुमति देता है, यदि आप तुलना कर रहे हैं तो यह निर्देश के दो स्वाद हैं। या विकल्प इसे व्यवस्थित करने में अधिक समय ले रहा है, इसलिए निर्देश 2 या 3 घड़ियों या जो कुछ भी लेता है, और तर्क 3 की गणना करता है तो परिणाम को latches।
उदाहरण के लिए, एमएसपी 430, केवल थोड़ी सी घुमावदार सही निर्देशों को घुमाता है (क्योंकि आप एक ही बिट शिफ्ट या एक अन्य निर्देश के साथ एक घुमावदार बाएं कर सकते हैं, जिसे मैं समझने के लिए पाठक को छोड़ दूंगा)।
एआरएम निर्देश सेट तत्काल और पंजीकरण आधारित बहु-बिट घुमावदार, अंकगणितीय बदलाव और तार्किक बदलाव दोनों की अनुमति देता है। मुझे लगता है कि केवल एक वास्तविक घुमावदार निर्देश है और दूसरा एक उपनाम है, क्योंकि बाएं 1 घुमाएं एक घुमावदार दाएं 32 के समान है, आपको केवल एक दिशा बैरल शिफ्ट की आवश्यकता होती है ताकि एक बहु बिट घुमाने के लिए।
x86 में एसएचएल प्रति निर्देश एक से अधिक बिट की अनुमति देता है, लेकिन यह एक से अधिक घड़ी लेता था।
और इसी तरह, आप आसानी से वहां से किसी भी निर्देश सेट की जांच कर सकते हैं।
आपके प्रश्न का उत्तर यह है कि यह तय नहीं है। कभी-कभी यह एक ऑपरेशन, एक चक्र, एक निर्देश है। कभी-कभी यह एक निर्देश एकाधिक घड़ी चक्र है। कभी-कभी यह कई निर्देश हैं, एकाधिक घड़ी चक्र।
कंपाइलर अक्सर इस तरह के चीजों के लिए अनुकूलित करते हैं। मान लें कि आपके पास एक स्वैप बाइट निर्देश और तुरंत और एक निर्देश के साथ 16 बिट रजिस्टर निर्देश सेट है, लेकिन केवल एक ही बिट शिफ्ट है। आपको लगता है कि 8 बिट्स को स्थानांतरित करने के लिए 8 शिफ्ट निर्देश चक्रों की आवश्यकता होगी, लेकिन आप केवल बाइट्स (एक निर्देश) को स्वैप कर सकते हैं और फिर निचले आधे से ज़ीरो (जो दो निर्देश ले सकते हैं, या दो शब्दों का परिवर्तनीय शब्द लंबाई निर्देश हो सकता है, या यह एक ही निर्देश में एन्कोड हो सकता है) इसलिए इसमें केवल 8 या 3 निर्देश/घड़ी चक्र 8 की बजाय लेते हैं। 9 बिट्स की शिफ्ट के लिए, आप एक ही काम कर सकते हैं और एक शिफ्ट जोड़ सकते हैं, जिससे 9 घड़ियों बनाम 3 या 4 बनाते हैं इसके अलावा, कुछ आर्किटेक्चर पर, 256 से गुणा करने के लिए तेज़ी से 8, आदि इत्यादि की तुलना में गुणा करना तेज होता है। प्रत्येक निर्देश सेट की अपनी सीमाएं और चाल होती है।
यह भी मामला नहीं है कि या तो अधिकांश निर्देश सेट एकल बिट या एकाधिक बिट को अधिकतम सीमा प्रदान करते हैं। X86, ARM, PowerPC, और MIPS जैसे "कंप्यूटर" श्रेणी में आने वाले प्रोसेसर, एक ऑपरेशन को स्थानांतरित करने के लिए दुबला हो जाएंगे। सभी प्रोसेसर का विस्तार करें, लेकिन आमतौर पर "कंप्यूटर" का उपयोग नहीं किया जाता है, और यह दूसरी तरफ बदल जाता है, मैं कहूंगा कि उनमें से अधिकतर मल्टी बिट की तुलना में सिंगल बिट हैं, इसलिए बहु-बिट शिफ्ट करने के लिए कई संचालन की आवश्यकता होती है।
बिट स्थानांतरण हे (1) व्यावहारिक रूप से हर मौजूदा प्रोसेसर पर है।
उदाहरण के लिए, x86 "shrw" निर्देश पर एक नज़र डालें। पहला ऑपरेंड (एटी & टी सिंटैक्स में) शिफ्ट करने के लिए बिट्स की संख्या है। स्थानांतरण करने वाला एक कंपाइलर उपकरण कैसे संकलक पर निर्भर करता है, लेकिन एक प्रोसेसर एक बिट में एन बिट्स को स्थानांतरित कर सकता है, तो यह एक लूप में बदलाव डालना मूर्ख होगा।
अनुपूरक: पुन: "क्या उन्हें बाएं 31 को स्थानांतरित करने के लिए और अधिक संचालन की आवश्यकता है?" विभिन्न प्रकार के बदलाव होते हैं (यदि आप सोच रहे हैं कि, रजिस्टर से हटाए गए बिट्स के साथ क्या करना है) पर विचार करें, लेकिन अधिकांश प्रोसेसर जीपीआर स्टोर कर सकते हैं के रूप में कई बिट्स की एकल-निर्देश शिफ्ट कर सकते हैं। 32-बिट रजिस्टर पर 40-बिट शिफ्ट करने के लिए एकाधिक रजिस्टरों में स्थानांतरित करने की आवश्यकता होगी (यह माना जाता है कि 64-बिट संख्या 2 32-बिट रजिस्टरों में संग्रहीत की जाती है), जो मुझे पता है कि प्रत्येक प्रोसेसर पर अधिक निर्देशों की आवश्यकता होगी। यह अभी भी ओ (1) होगा, शायद 1 घड़ी नहीं। एक दिलचस्प साइड-नोट के रूप में, पेंटियम चतुर्थ प्रोसेसर थोड़ा बदलावों पर आश्चर्यजनक रूप से धीमा है। यह विडंबनापूर्ण है क्योंकि इंटेल ने ऐतिहासिक रूप से^2 विभाजनों के अनुकूलन की सिफारिश की है और बिट स्थानांतरण के माध्यम से गुणा किया है। देखें: this PDF और यदि दिलचस्पी है तो अधिक जानकारी के लिए Google।
केवल 386+ पर। 286 पर मनमाने ढंग से शिफ्ट गणना का उपयोग करते समय, यह ओ (एन) है क्योंकि घड़ी चक्र आवश्यक 5 + एन है। –
@MarcB: क्योंकि, ज़ाहिर है, मैं अभी भी 286 का उपयोग करता हूं, और इसलिए इसे जानने की आवश्यकता है। : पी –
क्या आपका मतलब है कि इन दिनों 9 0% प्रोसेसर x86 की तरह हैं कि वे एन बिट्स को एक बार में स्थानांतरित करने में सक्षम हैं? – Pacerier
सामान्य हार्डवेयर के लिए, निश्चित आकार पंजीकृत करता है कि आप कितनी जगहों को स्थानांतरित करते हैं, इस पर ध्यान दिए बिना।
यह भी ध्यान रखें, कि हे संकेतन का उपयोग यहाँ काफी अजीब है, आप सामान्य रूप से यह प्रयोग करेंगे स्थानों शिफ्ट करने की संख्या नहीं शिफ्ट करने के लिए एल्गोरिथम संख्या के आधार पर जटिलता को निरूपित करने के ..
हाँ मैंने सोचा था कि ओ नोटेशन अजीब है, लेकिन अन्यथा शीर्षक बहुत लंबा होगा .. – Pacerier
1) सामान्य रूप से, आपका मतलब आधुनिक है? 2) मुझे यहां ओ अजीब अजीब नहीं लगता है। –
1) मेरा मतलब है 99.99% एचडब्ल्यू ... –
एक barrel shifterO(log n) में — में बदलाव करने की अनुमति देता है जो एक ही घड़ी चक्र में किया जा सकता है, जिससे O(1) ऑपरेशन स्थानांतरित हो जाता है।
अहम, परीक्षण किया कि सी # में जिज्ञासा से बाहर और मजेदार परिणाम मिला।
var sw = Stopwatch.StartNew();
long l = 1;
for (long i = 0; i < 20000000; i++) {
l = l << 60; l = l >> 60;
l = l << 60; l = l >> 60;
l = l << 60; l = l >> 60;
//...
// 50 of ^them^ total
}
Console.WriteLine(l + " " + sw.Elapsed);
जो मेरे पीसी पर 1.2 सेकंड लेता है। लेकिन अगर मैं
l = l << 60; l = l >> 60;
समय बढ़ जाती है 2.0 सेकेंड की जगह
l = l << 1; l = l >> 1;
तो साथ। पता नहीं है कि यहां किस तरह के अनुकूलन खेल रहे हैं, लेकिन यह अजीब लग रहा है।
सिर्फ इसलिए कि आपका कंपाइलर स्मार्ट चीजें नहीं करता है, इसका मतलब यह नहीं है कि हार्डवेयर में निर्देश नहीं हैं। – Flexo
यह वास्तव में स्मार्ट चीजें करता है, क्योंकि मुझे 1 और 31 - 2.0 सेकेंड के बीच की सभी बदलावों के लिए एक ही समय मिलता है। तो मुझे 0.6 सेकेंड मिलते हैं यदि मैं बिल्कुल 32 बिट्स द्वारा स्थानांतरित करता हूं, लेकिन फिर अचानक मुझे केवल 1.2 सेकंड मिलते हैं यदि शिफ्ट की संख्या 32 से बड़ी है। यह अजीब है। – user1096188
आप किसी प्रबंधित भाषा की बजाय सी में इसे करने से बेहतर हो सकते हैं। जिटर संभवतः कुछ चीजें कर रहे हैं जो आप देख रहे हैं। –
जैसा कि पहले से ही उल्लेख किया गया है, एक बैरल शिफ्टर एक ऑपरेंड को निरंतर समय में मनमाने ढंग से दूरीांतरित कर सकता है। एक बैरल शिफ्ट, हालांकि, सीपीयू मरने पर एक उचित मात्रा में जगह का उपभोग करता है, इसलिए वे सभी सीपीयू डिज़ाइनों में शामिल नहीं होते हैं।
बस एक काफी प्रसिद्ध उदाहरण के लिए, इंटेल पेंटियम III में एक बैरल शिफ्ट शामिल था - लेकिन पेंटियम IV ने नहीं किया था। पेंटियम III के लिए लिखे गए कोड को बैरल शिफ्टर माना जाता है, कभी-कभी पेंटियम चतुर्थ पर थोड़ा धीमा हो जाता है। मेरे पास कुछ एन्क्रिप्शन कोड था (जिसमें बहुत सारे स्थानांतरण और घूर्णन शामिल थे) जो 1.2 गीगाहर्ट्ज़ पेंटियम III पर लगभग 2.8 गीगाहर्ट्ज़ पेंटियम चतुर्थ पर 4 गुना तेज था।
क्या उन्हें बाएं 31 को स्थानांतरित करने के लिए और अधिक संचालन की आवश्यकता है? – Flexo
मेरा सीपीयू ज्ञान बहुत पुराना है, लेकिन प्रत्येक शिफ्ट निर्देश मैंने एक बिट से बदलाव देखा है, इसलिए आपको एक से अधिक बार स्थानांतरित करने के लिए एक लूप चलाने की आवश्यकता है। मुझे लगता है कि यह संभव है कि आधुनिक सीपीयू के शिफ्ट निर्देश हैं जो एक घड़ी चक्र में निर्दिष्ट संख्या में बिट्स द्वारा स्थानांतरित होते हैं। –
मेरी मशीन 'इंट टेस्ट (int i) पर { वापसी मैं << 30; } 'एसए $ 30,% eax' – Flexo