मैं एक परिपत्र बफर को लागू करते समय एक समस्या में भाग गया जिसे कभी-कभी गठबंधन किया जाना चाहिए।

मान लें कि मेरे पास दो सरणियाँ हैं, leftArr और rightArr। मैं दाएं सरणी को byteArr और बाएं सरणी को byteArr + दाएं सरणी की लंबाई में ले जाना चाहता हूं। दोनों leftArr और rightArr, byteArr से बड़े हैं, और rightArr, leftArr से बड़े हैं। (यह सर्कुलर बफर को घुमाने जैसा नहीं है क्योंकि बाएं सरणी को byteArr से शुरू करने की आवश्यकता नहीं है) हालांकि बाएं और दाएं सरणी ओवरलैप नहीं करते हैं, byteArr पर संग्रहीत संयुक्त सरणी वर्तमान सरणी के साथ ओवरलैप हो सकती है, पर संग्रहीत leftArr और rightArrbyteArr से rightArr + rightArrLen तक की सभी मेमोरी को सुरक्षित रूप से लिखा जा सकता है। एक संभावित कार्यान्वयन है:

void align(char* byteArr, char* leftArr, int leftArrLen, char* rightArr, int rightArrLen) {
  char *t = malloc(rightArrLen + leftArrLen);

  // form concatenated data
  memcpy(t, right, rightArrLen);
  memcpy(t + rightArrLen, left, leftArrLen);

  // now replace
  memcpy(byteArr, t, rightArrLen + leftArrLen);
  free(t);
}

हालांकि, मुझे इसे निरंतर स्मृति जटिलता के साथ पूरा करना होगा।

मेरे पास अब तक जो कुछ है वह इस तरह दिखता है:

void align(char* byteArr, char* leftArr, int leftArrLen, char* rightArr, int rightArrLen)
{
    // first I check to see if some combination of memmove and memcpy will suffice, if not:
    unsigned int lStart = leftArr - byteArr;
    unsigned int lEnd = lStart + leftArrLen;
    unsigned int rStart = rightArr - byteArr;
    unsigned int rEnd = rStart + rightArrLen;
    unsigned int lShift = rEnd - rStart - lStart;
    unsigned int rShift = -rStart;
    char temp1;
    char temp2;
    unsigned int nextIndex;
    bool alreadyMoved;

    // move the right array
    for( unsigned int i = 0; i < rEnd - rStart; i++ )
    {
        alreadyMoved = false;

        for( unsigned int j = i; j < rEnd - rStart; j-= rShift )
        {
            if(    lStart <= j + rStart - lShift
                && j + rStart - lShift < lEnd
                && lStart <= (j + rStart) % lShift
                && (j + rStart) % lShift < lEnd
                && (j + rStart) % lShift < i )
            {
                alreadyMoved = true;
            }
        }

        if(alreadyMoved)
        {
            // byte has already been moved
            continue;
        }

        nextIndex = i - rShift;
        temp1 = byteArr[nextIndex];
        while( rStart <= nextIndex && nextIndex < rEnd )
        {
            nextIndex += rShift;
            temp2 = byteArr[nextIndex];
            byteArr[nextIndex] = temp1;
            temp1 = temp2;
            while( lStart <= nextIndex && nextIndex < lEnd )
            {
                nextIndex += lShift;
                temp2 = byteArr[nextIndex];
                byteArr[nextIndex] = temp1;
                temp1 = temp2;
            }
            if( nextIndex <= i - rShift )
            {
                // byte has already been moved
                break;
            }
        }
    }

    // move the left array
    for( unsigned int i = lStart; i < lShift && i < lEnd; i++ )
    {
        if( i >= rEnd - rStart )
        {
            nextIndex = i + lShift;
            temp1 = byteArr[nextIndex];
            byteArr[nextIndex] = byteArr[i];
            while( nextIndex < lEnd )
            {
                nextIndex += lShift;
                temp2 = byteArr[nextIndex];
                byteArr[nextIndex] = temp1;
                temp1 = temp2;
            }
        }
    }
}

यह कोड केस lStart = 0, lLength = 11, rStart = 26, rLength = 70 में काम करता है लेकिन केस lStart = 0, lLength = 46, rStart = 47, rLength = 53 में फेल हो जाता है। समाधान जो मैं देख सकता हूं वह यह निर्धारित करने के लिए तर्क जोड़ना है कि दाएं सरणी से बाइट पहले ही स्थानांतरित हो चुकी है। हालांकि मेरे लिए ऐसा करना संभव होगा, मैं सोच रहा था कि क्या इस समस्या का एक आसान समाधान है जो निरंतर स्मृति जटिलता के साथ चलता है और अतिरिक्त पढ़ने और लिखने के बिना?

कार्यान्वयन का परीक्षण करने के लिए यहां एक कार्यक्रम है:

bool testAlign(int lStart, int lLength, int rStart, int rLength)
{
    char* byteArr = (char*) malloc(100 * sizeof(char));
    char* leftArr = byteArr + lStart;
    char* rightArr = byteArr + rStart;
    for(int i = 0; i < rLength; i++)
    {
        rightArr[i] = i;
    }
    for(int i = 0; i < lLength; i++)
    {
        leftArr[i] = i + rLength;
    }
    align(byteArr, leftArr, lLength, rightArr, rLength);
    for(int i = 0; i < lLength + rLength; i++)
    {
        if(byteArr[i] != i) return false;
    }
    return true;
}
2
yinnonsanders 9 अक्टूबर 2017, 23:28
2
तो leftArr और rightArr हमेशा कहीं को उसी मेमोरी ब्लॉक की ओर इंगित करें जो byteArr से शुरू होता है?
 – 
chux - Reinstate Monica
9 अक्टूबर 2017, 23:48
2
ऐसा लगता है कि कोड void foo(char* byteArr, unsigned lStart, unsigned rStart, unsigned leftArrLen, unsigned rightArrLen); से शुरू हो सकता है
 – 
chux - Reinstate Monica
9 अक्टूबर 2017, 23:53
1
अच्छी तरह से घटाया गया (आपके हटाए गए उत्तर में), लेकिन char* byteArr की लंबाई नहीं जानने पर खतरा है - एक लापता फ़ंक्शन पैरामीटर।
 – 
Weather Vane
10 अक्टूबर 2017, 00:16
1
हालांकि वास्तव में byteArr की लंबाई नहीं है, यह वास्तव में मेरे उद्देश्यों के लिए "काफी लंबा" है।
 – 
yinnonsanders
10 अक्टूबर 2017, 00:21
1
क्या left+left_length को <= right माना जा सकता है? वरना उन्हें बाएँ, दाएँ क्यों कहते हैं?
 – 
chux - Reinstate Monica
10 अक्टूबर 2017, 00:29

1 उत्तर

सबसे बढ़िया उत्तर

byteArr को क्षेत्रों में विभाजित करने की कल्पना करें (जरूरी नहीं कि यह पैमाना हो):

 X1    Left   X2  Right
|---|--------|---|------|

X1 और X2 बाएं सरणी की शुरुआत से पहले और दो सरणियों के बीच byteArr में अंतराल हैं। सामान्य स्थिति में, उन चार क्षेत्रों में से किसी एक या सभी की लंबाई शून्य हो सकती है।

फिर आप इस तरह आगे बढ़ सकते हैं:

  1. byteArr में प्रमुख स्थान को आंशिक रूप से या पूर्ण रूप से भरकर प्रारंभ करें <उल>
  2. यदि लेफ्ट की लंबाई शून्य है तो memmove() से होते हुए राइट टू फ्रंट (यदि आवश्यक हो) ले जाएं। हो गया।
  3. अन्यथा यदि X1 दाएं सरणी के समान लंबाई या बड़ा है तो दाएं सरणी को memcpy() के माध्यम से उस स्थान में ले जाएं और संभवतः, बाएं सरणी को memmove() के माध्यम से समाप्त करने के लिए ऊपर ले जाएं। हो गया।
  4. अन्यथा, नीचे दिए गए लेआउट का निर्माण करते हुए, दाएं सरणी के मुख्य भाग को उस स्थान पर ले जाएं। यदि X1 की लंबाई शून्य होती तो R1 की लंबाई भी शून्य होती, X2' == X2, और R2 == दाईं ओर।
       R1    Left     X2'  R2
      |---|--------|------|---|
  1. अब दो विकल्प हैं

    • यदि R2 बाईं या उससे अधिक लंबाई के समान है, तो R2 के प्रारंभिक भाग के साथ बाईं ओर स्वैप करें (अभी भी पैमाने पर नहीं):
       R1'    X2''  Left    R2'
      |------|-----|-------|--|
  • अन्यथा, उत्पादन के लिए सभी R2 के साथ बाएं के प्रारंभिक भाग को स्वैप करें (अभी भी पैमाने पर नहीं):
       R1'    L2  X2''    L1
      |------|---|-------|----|
  1. अब पहचानें कि किसी भी मामले में, आपके पास मूल रूप के समान रूप की एक सख्ती से छोटी समस्या है, जहां नया byteArr क्षेत्र R1 के तुरंत बाद शुरू होने वाली मूल की पूंछ है। पहले मामले में नया leftArr (अंतिम) वाम क्षेत्र है और नया rightArr क्षेत्र R2' है। दूसरे मामले में, नया leftArr क्षेत्र L2 है, और नया rightArr क्षेत्र L1 है। इस नई समस्या को दर्शाने के लिए पैरामीटर रीसेट करें, और चरण (1) पर वापस जाएं।

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

1
John Bollinger 10 अक्टूबर 2017, 18:07
निश्चित रूप से निरंतर स्थान में काम करता है, लेकिन सबसे खराब स्थिति समय जटिलता ऐसा लगता है कि यह चरण 1 (मुझे इस बारे में निश्चित नहीं है) के बाद घूमने से कहीं अधिक खराब होगा, जो मुझे विश्वास है कि निरंतर स्थान का उपयोग करेगा।
 – 
yinnonsanders
10 अक्टूबर 2017, 18:16
1
आह मेरा बुरा, यह O(n + m) है क्योंकि प्रत्येक स्वैप/चाल में एक तत्व को सही स्थिति में ले जाना शामिल है।
 – 
yinnonsanders
10 अक्टूबर 2017, 18:36
1
मैं आपके विश्लेषण से सहमत हूं। वास्तव में, यदि मैं बाएं और दाएं सरणी के संयुक्त आकार के रूप में n लेता हूं, तो मेरा तर्क है कि मेरे एल्गोरिदम की कार्य की मात्रा ओ (एन) से घिरा हुआ है, और चरण 2 और 3 को घूर्णन के साथ बदलने से सख्त बाध्यता नहीं होती है . मैं इस बात से सहमत हूं कि रोटेशन विकल्प में शायद कम गुणांक है, लेकिन मैं ध्यान देता हूं कि दो विकल्प वास्तव में विशेष मामले में समान हैं कि बाएं और दाएं सरणी की लंबाई समान है और कोई अंतराल नहीं है।
 – 
John Bollinger
10 अक्टूबर 2017, 20:20
1
कैश के आधार पर, स्थान की वजह से घूमने की तुलना में स्वैपिंग बहुत तेज हो सकती है।
 – 
yinnonsanders
10 अक्टूबर 2017, 20:23
अगर आप ऐसा करना चाहते हैं तो मुझे कोई आपत्ति नहीं है। लेकिन आपका प्रतिनिधि समीक्षा के बिना संपादित करने के लिए पर्याप्त नहीं है, और समीक्षकों के पास इस तरह के संपादन को अस्वीकार करने का एक अच्छा मौका है।
 – 
John Bollinger
10 अक्टूबर 2017, 20:41