मैं सी में गहराई से रिकर्सिव फ़ंक्शन के स्टैक फ्रेम को कैसे कम कर सकता हूं?

Question

मान लीजिए मैं कुछ पुनरावर्ती क्रिया है कि एक ग्राफ संरचना manipulates है:

typedef struct Node { 
    Data data; 
    size_t visited; 
    size_t num_neighbors; 
    struct Node *neighbors[]; 
} Node; 

void doSomethingWithNode(Node *node) 
{ 
    if ((!node) || node->visited) 
     return; 
    node->visited = 1; 
    /* Do something with node->data */ 
    size_t /* some local variables */; 
    size_t i; 
    for (i = 0; i < node->num_neighbors; i++) 
    { 
     /* Do some calculations with the local variables */ 
     if (/* something */) 
      doSomethingWithNode(node->neighbors[i]); 
    } 
} 

क्योंकि स्थानीय चर मैं पाश में उपयोग किए जाने वाले

, संकलक (gcc) एक बड़े से भी मैं-होगा की तरह ढेर फ्रेम बनाता है इस फ़ंक्शन के लिए (pushq और popq की अच्छी संख्या -O3 के साथ भी निर्देश), जो एक समस्या है, क्योंकि यह गहराई से रिकर्सिव है। चूंकि इससे कोई फर्क नहीं पड़ता कि मैं किस क्रम में नोड्स पर जाता हूं, मैं Node पॉइंटर्स के ढेर का उपयोग करने के लिए इस कोड को दोबारा कर सकता हूं, इस प्रकार प्रतिरक्षा प्रति एक सूचक को ओवरहेड को कम करता है।

1. क्या कोई संकेत है कि मैं इस समस्या को हल करने के लिए संकलक (gcc) दे सकता हूं?
2. यदि नहीं, तो क्या असेंबली का उपयोग किए बिना पॉइंटर्स के मेरे ढेर के लिए कॉल स्टैक का उपयोग करना संभव है?

Answer 1

क्या आप गणना अपने स्वयं के, गैर-पुनरावर्ती कार्य में डाल सकते हैं? इस तरह जब आप रिकर्सिव कॉल करते हैं तो सभी अस्थायी चर के लिए ढेर नहीं होगा।

अद्यतन: स्थानीय चर में कम से कम कुछ डेटा रिकर्सन के लिए आवश्यक है जैसे दिखता है। स्टैक पर स्पष्ट रूप से आवंटित करने के लिए आप alloca का उपयोग कर सकते हैं।

Answer 2

समस्या को हल करने के लिए आप संकलक से क्या अपेक्षा करेंगे?

आप निश्चित रूप से अपने कोड से गुजर सकते हैं, और स्थानीय चर की संख्या को कम कर सकते हैं, जितना संभव हो उतना स्पष्ट करने की कोशिश करें कि वे (उदाहरण के लिए) केवल const का उपयोग कर एक बार असाइन किए गए हैं, और इसी तरह। यह संभव हो सकता है, तो कंपाइलर अंतरिक्ष को फिर से उपयोग करें।

विफल होने के कारण, आप संभवतया पुनरावृत्ति के द्वारा कुछ स्मृति को बचा सकते हैं क्योंकि इससे वापसी पते की आवश्यकता में कटौती होती है।

Answer 3

आप नोड्स के गतिशील रूप से बढ़ते ढेर को प्रबंधित करने के लिए malloc और realloc का उपयोग कर सकते हैं। यहाँ एक ढेर के प्रबंधन के लिए "वर्ग" है:

typedef struct Stack { 
    void **pointers; 
    size_t count; 
    size_t alloc; 
} Stack; 

void Stack_new(Stack *stack) 
{ 
    stack->alloc = 10; 
    stack->count = 0; 
    stack->pointers = malloc(stack->alloc * sizeof(void*)); 
} 

void Stack_free(Stack *stack) 
{ 
    free(stack->pointers); 
    stack->pointers = null; 
} 

void Stack_push(Stack *stack, void *value) 
{ 
    if (stack->alloc < stack->count + 1) { 
     stack->alloc *= 2; 
     stack->pointers = realloc(stack->pointers, stack->alloc * sizeof(void*)); 
    } 
    stack->pointers[stack->count++] = value; 
} 

void *Stack_pop(Stack *stack) 
{ 
    if (stack->count > 0) 
     return stack->pointers[--stack->count]; 
    return NULL; 
} 

Answer 4

आप एक वेक्टर या एक सूची (या कुछ कतार, या शायद एक ढेर, या यहाँ तक कि कुछ मनमाने ढंग से अव्यवस्थित सेट) नोड्स के दौरा किया जा करने के लिए बनाये रख सकता है (और आप शायद पहले से देखे गए नोड्स के सेट या हैश टेबल को बनाए रखना चाहते हैं)।

तो फिर तुम एक पाश जो होने वाली दौरा कंटेनर के सामने नोड उठाता होगा, और कहा कि कंटेनर की पीठ में कुछ विज़िट नहीं किए गए नोड्स जोड़ सकते हैं ....

के बारे में wikipages पढ़ें continuation passing style और के बारे में tail calls

Deutsch Schorr वैट के लिए भी गूगल एल्गोरिथ्म, तो यह आपको कुछ विचार दे सकता है।

Answer 5

यदि आपके पास स्थानीय चर और सरणी की अधिक संख्या है तो आप malloc का उपयोग करके स्मृति आवंटित करने का प्रयास कर सकते हैं, इसे एकल सूचक और निश्चित ऑफसेट का उपयोग करके कुशलतापूर्वक उपयोग कर सकते हैं। फ़ंक्शन से बाहर निकलने पर free स्मृति।

इस तरह आप सभी पुनरावृत्तियों के लिए ढेर को बचाएंगे और उसी ढेर (शायद) अनुभाग का पुन: उपयोग करेंगे।

Answer 6

"यह गहराई से पुनरावर्ती है" एक संकेत है कि गहन पुनरावृत्ति उन पथों में होती है जिनमें 1 से अधिक गैर-विज़िट neighbor नहीं हैं।

कोड केवल तभी भर्ती करें जब 1 से अधिक दिलचस्प पड़ोसी हों, अन्यथा सिर्फ लूप।

void doSomethingWithNode(Node *node) { 
    while (node) { 
    if (node->visited) return; 
    node->visited = 1; 
    /* Do something with node->data */ 
    size_t /* some local variables */; 
    size_t i; 
    Node *first = NULL; 
    for (i = 0; i < node->num_neighbors; i++) { 
     /* Do some calculations with the local variables */ 
     if (/* something */) { 

      // Save the first interesting node->neighbors[i] for later 
      if (first == NULL && 
       node->neighbors[i] != NULL && 
       node->neighbors[i]->visited == 0) { 
      first = node->neighbors[i]; 

     } else { 
      doSomethingWithNode(node->neighbors[i]); 
      } 
     } 
    } 
    node = first; 
    } 
} 

यह स्टैक फ्रेम को कम नहीं करता है, लेकिन केवल 1-प्लाई होने पर रिकर्सन को खत्म करता है। IOWs: जब रिकर्सन की आवश्यकता नहीं है।

प्रत्यावर्तन गहराई अब नहीं रह मूल बुरी से बुरी हालत हे (एन)

Answer 7

मैं कई करता है, तो अन्य उत्तर सुरुचिपूर्ण नहीं और भी बहुत कुछ भूमि के ऊपर की आवश्यकता होती है लगता है के बजाय ओ (log2 (एन)) होनी चाहिए। शायद कोई अच्छा रास्ता नहीं है और किसी भी तरह से हाथ में रिकर्सन के प्रकार पर निर्भर करता है।

आपके मामले में, रिकर्सन अंत में है और केवल परिवर्तनीय मुझे अभी भी आवश्यक है। स्टैक फ्रेम को कम करने के लिए, आप अन्य स्पेस ग्लोबल स्पेस के लिए उपयोग कर सकते हैं।

static struct VARS { 
    int iSomething; 
    Data *dataptr; 
    double avg; 
} gVars; 

void doSomethingWithNode(Node *node) 
{ 
    if ((!node) || node->visited) 
     return; 
    /* Do something with node->data */ 
    /* some local variables in global space */; 
    gVars.iSomething= 1; 
    for (; node->visited < node->num_neighbors; node->visited++) 
    { 
     /* Do some calculations with the local variables */ 
     if (/* something */) 
      doSomethingWithNode(node->neighbors[node->visited]); 
    } 
} 

Answer 8

सभी स्थानीय चर जो struct locals में प्रत्यावर्तन के लिए आवश्यक नहीं कर रहे हैं और plocals-> साथ उन तक पहुँच रखो:

आप और भी अधिक को कम करने और मैं निकालना चाहते हैं, तो आप उपयोग कर सकते हैं node-> एक काउंटर के रूप में visisted । गणना को अपने स्वयं के, गैर-पुनरावर्ती कार्य (Arkadiy का उत्तर) में रखने पर लाभ, यदि आवश्यक हो, तो चर मान्य हैं और रिकर्स पर उनके मूल्य बनाए रखे हैं।

#include <stddef.h> 

struct Data { 
    char data[1]; 
}; 

typedef struct Node { 
    struct Data data; 
    size_t visited; 
    size_t num_neighbors; 
    struct Node *neighbors; 
} Node; 

struct Locals { 
    /* local variables not essential for recursion */; 
}; 
static void doSomethingWithNodeRecurse(Node *node, struct Locals *plocals) 
{ 
    if ((!node) || node->visited) 
     return; 
    node->visited = 1; 
    /* Do something with node->data */ 
    /* local variables essential for recursion */ 
    size_t i; 
    for (i = 0; i < node->num_neighbors; i++) 
    { 
     /* Do some calculations with the local variables */ 
     if (1/* something */) 
      doSomethingWithNodeRecurse(&node->neighbors[i], plocals); 
     /* Do some calculations with the local variables */ 
    } 
} 

void doSomethingWithNode(Node *node) 
{ 
    struct Locals locals; 

    doSomethingWithNodeRecurse(node, &locals); 
} 

चर अभी भी बहुत ढेर पर उन्हें आवंटित करने के लिए बहुत बड़ा कर रहे हैं, वे ढेर पर आवंटित किया जा सकता है के रूप में Vagish सुझाव:

#include <stddef.h> 
#include <stdlib.h> 

struct Data { 
    char data[1]; 
}; 

typedef struct Node { 
    struct Data data; 
    size_t visited; 
    size_t num_neighbors; 
    struct Node *neighbors; 
} Node; 

struct Locals { 
    /* local variables too big for allocation on stack */; 
}; 
void doSomethingWithNode(Node *node) 
{ 
    struct Locals *plocals; 

    if ((!node) || node->visited) 
     return; 

    /* ---> allocate the variables on the heap <--- */ 
    if ((plocals = malloc(sizeof *plocals)) == NULL) abort(); 

    node->visited = 1; 
    /* Do something with node->data */ 
    size_t i; 
    for (i = 0; i < node->num_neighbors; i++) 
    { 
     /* Do some calculations with the local variables */ 
     if (1/* something */) 
      doSomethingWithNode(&node->neighbors[i]); 
     /* Do some calculations with the local variables */ 
    } 
    /* ---> free the variables <--- */ 
    free(plocals); 
}