एक असली स्टैक

Question

से एक नकली ढेर तेज है मैं कुछ रिकर्सिव पार्सिंग कर रहा हूं।

वर्तमान में मेरे पास एक नकली स्टैक है, जहां मैं अपनी परिमित राज्य मशीन के लिए राज्यों को संग्रहीत करता हूं, इसलिए जब मैं बार-बार ड्रिल करता हूं तो मैं उस राज्य को धक्का देता हूं जिसमें मैं अंदर था, और पाठ के रिकर्सिव बिट को संसाधित करने के बाद इसे पॉप करता हूं ।

यह एक 'राज्य आईडी' ढेर की तरह है करने के लिए तेजी से होगा:

int* stack = 0 
int top = 0; 
// ... 
// drill down bit 
if (stack == 0) 
    stack = (int*)malloc(STACK_JUMP_SIZE); 
else if (top % STACK_JUMP_SIZE == 0) 
    stack = (int*)realloc(stack, (top+STACK_JUMP_SIZE) * sizeof(int)); 
stack[top++] = currentState; 
// ... 
// pop up later 
{currentState = stack[--top]; { 
if (top == 0) { 
    free(stack); 
    stack = 0; 
} else if ((top+1) % STACK_JUMP_SIZE == 0) { 
    stack = (int*)realloc(stack, (top+1)*sizeof(int)); 
} 

या यह ऊपर उचित कार्यों में बात विभाजित है और सी ढेर के बारे में चिंता ++ जाने के लिए तेजी से होगा।

(मुझे पता है कि कोई मुझे बताएगा कि यह सी है, यह सी ++ नहीं है, इसलिए मैं पूर्व में स्पष्ट रूप से उत्तर देता हूं, मेरे प्रोग्राम के सी ++ लेकिन इसमें बहुत सी सी है)।

Answer 1

यह कार्यान्वयन पर निर्भर करता है — अग्रिम में कहने का कोई तरीका नहीं है। ऐसी मशीन पर जहां फ़ंक्शन कॉल सस्ते हैं (उदा। SPARC), फ़ंक्शन स्टैक शायद तेज़ होगा, लेकिन यहां तक ​​कि स्थानीयकरण हस्तक्षेप जैसे मुद्दे भी होंगे। (मशीन स्टैक अधिक कमरे लेता है, क्योंकि यह आपके अनुरूपित स्टैक की तुलना में अधिक जानकारी ढेर करता है।) मैं इस बात को उचित रिकर्सिव फ़ंक्शंस में विभाजित करता हूं, और केवल एक बाधा साबित होने पर मैन्युअल स्टैक प्रबंधन का प्रयास करें। जब तक ... मैनुअल स्टैक प्रबंधन में एक महत्वपूर्ण लाभ होता है: त्रुटि प्रबंधन। मशीन स्टैक ओवरफ़्लो अपरिभाषित व्यवहार है: यदि malloc या realloc एक शून्य सूचक लौटाता है, तो आप कम से कम त्रुटि को स्पष्ट रूप से रिपोर्ट कर सकते हैं।

आप ढेर अनुकरण करते हैं, तो आप std::vector, और नहीं malloc/realloc/free उपयोग करने पर विचार करना चाहिए। यदि अपवाद है तो यह आपको बचाएगा, और यह थोड़ा तेज़ होने की भी संभावना है। यदि आप स्टैक आकार की ऊपरी सीमा सेट कर सकते हैं, और यह अनावश्यक रूप से बड़ा नहीं है, स्टैक पर सी स्टाइल सरणी के रूप में स्टैक घोषित करना भी तेज होगा।