प्लेस रोटेशन में सी ++ प्रैक्टिस

Question

मेरे पास मेरे "आइटम" int सरणी के लिए एक काम करने वाला घूर्णन कार्य चल रहा है। नीचे दिया गया कोड यह हो जाता है, सिवाय इसके कि मैं अनावश्यक रूप से मूल्यों को स्थानांतरित कर रहा हूं। मैं "इनस्थल" रोटेशन को स्वीकार करने की कोशिश कर रहा हूं। मेरा मतलब यह है कि पीटीआरआर सरणी से मूल्यों को पकड़ने के बजाय बढ़ेगा या घट जाएगा .. जिसकी मुझे इस विधि के लिए इस तरह दक्षता स्तर को "ऊपर" करने की आवश्यकता है .. कोई सुझाव?

void quack::rotate(int nRotations) 
{ 
if (count <= 1) return; 
else // make sure our ptrs are where we want them. 
{ 
    intFrontPtr = &items[0].myInt; 
    intBackPtr = &items[count-1].myInt; 
} 
for (int temp = 0; nRotations != 0;) 
{ 
    if (nRotations > 0) 
    { 
    temp = *intFrontPtr; 
    *intFrontPtr = *intBackPtr; 
    *intBackPtr = temp; // Connect temps for the rotation 
    --intBackPtr; // Move left [...<-] into the array 
    } 
    else if (nRotations < 0) 
    { 
    temp = *intBackPtr; 
    *intBackPtr = *intFrontPtr; 
    *intFrontPtr = temp; // Connect temps for the rotation 
    ++intFrontPtr; // Move right [->...] into the array 
    } 
    if (intBackPtr == &items[0].myInt || 
    intFrontPtr == &items[count-1].myInt) 
    { 
    intFrontPtr = &items[0].myInt; 
    intBackPtr = &items[count-1].myInt; // need to re-set 
    if (nRotations > 0) nRotations--; // Which ways did we rotate? 
    else nRotations++; 
    } 
} 
} 

अरे हाँ, मैं ग अभ्यास करने के लिए कोशिश कर रहा ++ और पता उनके कई के आसपास चल कार्यों कि यह पहले से ही करने के लिए प्रोग्राम किया जाता है ... मैं "मेरी अपनी निर्माण" की कोशिश कर रहा। मुझे लगता है कि मैंने इसे वाक्य रचनात्मक रूप से नीचे कर लिया है, लेकिन दक्षता हमेशा होती है जहां मैं संघर्ष करता हूं। एक नौसिखिया के रूप में, मैं इस पहलू की ओर आलोचना की सराहना करता हूं ..

Answer 1

घूर्णन करना एक-एक करके वास्तव में जाने का तरीका नहीं है। यदि आप 2 या 3 घूर्णन से अधिक कुछ कर रहे हैं तो यह वास्तव में वास्तव में धीमा हो जाता है।

संपादित करें: अंतिम विचार के रूप में ... तत्वों को एक (डबल) लिंक्ड 'लूपेड' सूची में डालें (इसलिए अंतिम तत्व पहले को इंगित करता है), केवल घुमाव के लिए सिर पॉइंटर को स्थानांतरित करने की आवश्यकता होगी कुछ तत्व (लूप्ड सूची में कौन सा तत्व शुरुआत है यह इंगित करने के लिए हेड पॉइंटर एक सूचक है)।

इस अब तक तत्वों

Answer 2

एक सरणी में तत्वों घूर्णन के लिए एक पुरानी चाल है की एक सूची पर एक घुमाएं करने का सबसे त्वरित (और आसान) तरीका है (मैं पहली बार प्रोग्रामिंग मोती में यह देखा था)

कहें कि आप बाईं ओर एक सरणी को तीन तत्वों से घुमाने के लिए चाहते हैं।

पहले पहले तीन तत्वों को उलट दें, शेष शेष तत्वों को उलट दें, और फिर संपूर्ण सरणी को उलट दें। सरणी के

Starting Array: 
1 2 3 4 5 6 7 

After reversing the first three elements 
3 2 1 4 5 6 7 

After reversing the remaining elements 
3 2 1 7 6 5 4 

Finally reverse the entire array to get the final rotated array 
4 5 6 7 1 2 3 

पीछे भाग जगह में किया जा सकता है ताकि आप किसी अतिरिक्त स्मृति की जरूरत नहीं है।

Answer 3

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

class quack 
{ 
public: 
    explicit quack(int size) : items(new Item[size]), size(size), base(0) {} 
    ~quack() {delete [] items;} 

    void rotate(int n)  {base = (base + n) % size;} 
    Item &operator[](int i) {return items[(base + i) % size];} 

private: 
    quack(quack const&) = delete;   // or implement these if you want 
    void operator=(quack const&) = delete; // the container to be copyable 

    Item *items; 
    int size; 
    int base; 
}; 

हालांकि मैं यह RotatableArray की तरह कुछ फोन चाहते हैं, बल्कि quack से।

Answer 4

वास्तव में ऐसा करने का तरीका पॉइंटर्स के बजाय इंडेक्स का उपयोग करना है।

int to = 0; 
int from = (to + nRotations) % count; 
if (to == from) 
    return; 

for (int i=0; i < count; i++) { 
    swap(from, to); 
    from = advance(from); 
    to = advance(to); 
} 

// ... 
static inline int advance(int n, int count) { return (n + 1) % count; } 

Answer 5

हमेशा की तरह, यदि आप वास्तव में शारीरिक रूप से तत्वों बारी बारी से करने के लिए है, सी के लिए सही जवाब ++ std::rotate उपयोग करने के लिए है, जो करता है वास्तव में क्या आप क्या करना चाहते हो जाएगा।

यदि आपको इसे मैन्युअल रूप से लागू करना है (एक अभ्यास असाइनमेंट के रूप में), जॉन बेंटले के "प्रोग्रामिंग मोती" से एल्गोरिदम के लिए इन slides पर एक नज़र डालें।

Answer 6

मेरे पास सरणी इनलाइन को घुमाने के लिए वैकल्पिक समाधान हो सकता है।बल्कि, तत्वों के सेट पीछे के रूप में पहले प्रस्तावित की पुरानी चाल की तुलना में, इस दृष्टिकोण से काम करता है इस प्रकार है:

प्रारंभ:

(नोट q = राशि छोड़ दिया शिफ्ट करने के लिए, एन = सरणी की लंबाई)

1. पहला स्रोत तत्व है, जो x1 = q% n
2. गंतव्य तत्व x2 = 0
3. चार, ch1 पर है पर स्थित है का निर्धारण, ar [x 1] तत्व
4. चार, CH2 है , ए आर [x2] तत्व

लूप है पर मैं = 0 n-1 के लिए है, जहां एन = सरणी

1. की लंबाई ch1 साथ गंतव्य तत्व, ar [x2] ओवरराइट करें
2. ch1 सेट = CH2
3. सेट x 1 = x2
4. सेट x2 = x2 - क्ष
5. तो x2 ऊपर घटाव की वजह से नकारात्मक है, जोड़ने n इसे करने के लिए
6. ch2 = ar [x2]

निम्नलिखित यह समझाने में सहायता कर सकता है कि यह कैसे काम करता है।

उदाहरण के लिए, छोड़ दिया द्वारा 2 वर्णों के लिए बारी बारी से:

abcdefg

cdefgab

x1 ch1 x2 ch2 
2  c  0  a 
0  a  5  f 
5  f  3  d 
3  d  1  b 
1  b  6  g 
6  g  4  e 
4  e  2  c 

आप देख सकते हैं, यह कोई एन की तुलना में अधिक पुनरावृत्तियों की आवश्यकता है, तो यह रेखीय समय एल्गोरिथ्म है जो इनलाइन को भी घुमाता है (कुछ अस्थायी चर के अलावा अतिरिक्त संग्रहण की आवश्यकता नहीं होती है)।

void rotate(char *ar, int q) 
{ 
    if (strlen(ar) < 2) 
    { 
     return; 
    } 

    if (q <= 0) 
    { 
     return; 
    } 

    char ch1; 
    char ch2; 
    int x1; 
    int x2; 
    int i; 
    int n; 

    n = strlen(ar); 

    q %= n; 

    if (q == 0) 
    { 
     return; 
    } 

    x1 = q; 
    ch1 = ar[x1]; 
    x2 = 0; 
    ch2 = ar[x2]; 

    for (i=0;i<n;i++) 
    { 
     ar[x2] = ch1; 
     ch1 = ch2; 

     x1 = x2; 

     x2 -= q; 

     if (x2 < 0) 
     { 
      x2 += n; 
     } 

     ch2 = ar[x2]; 
    } 
} 

Answer 7

यहाँ एक है कि मैं कोड here संशोधित करके मिल गया है::

यहाँ एक समारोह है कि उपरोक्त एल्गोरिथ्म को लागू करता है, तो आप इसे बाहर की कोशिश कर सकते है

template<class It> 
It rotate(It begin, It const middle, It end) 
{ 
    typename std::iterator_traits<It>::difference_type i = 0, j; 
    if (begin != middle && middle != end) 
    { 
     while ((i = std::distance(begin, middle)) != 
       (j = std::distance(middle, end))) 
     { 
      It k = middle; 
      std::advance(
       k, 
       std::max(typename std::iterator_traits<It>::difference_type(), 
       j - i)); 
      std::swap_ranges(k, end, begin); 
      if (i > j) { std::advance(begin, j); } 
      else { std::advance(end, -i); } 
     } 
    } 
    return std::swap_ranges(middle - i, middle, middle); 
} 

Answer 8

यहाँ sdtom के लिए कोड है समाधान

void rotateArray(int arr[], int low, int high) 
{ 
    while (low<high) { 
     int temp = arr[low]; 
     arr[low]=arr[high]; 
     arr[high]=temp; 
     low++; 
     high--; 
    } 
} 
void rotate (int arr[], int k,int uperLimit) 
{ 
    rotateArray(arr,0,k); 
    rotateArray(arr,k+1,uperLimit-1); 
    rotateArray(arr,0,uperLimit-1); 

} 

Answer 9

https://stackoverflow.com/q/17119000/2383578 : यह कुछ हद तक समान है जिस पर चर्चा की गई है। एक विशेष राशि से सरणी घूर्णन।

Answer 10

डी स्थानों द्वारा सरणी रोटेशन करने के कई तरीके हैं।

1. ब्लॉक स्वैप एल्गोरिदम।
2. जुगलिंग एल्गोरिदम।
3. रिवर्सल एल्गोरिदम।

नीचे दिया गया लिंक प्रोग्रामिंग मोती पीडीएफ से है। इसकी जांच करें।कोड के साथ बहुत स्पष्ट रूप से समझाया।

http://www.cs.bell-labs.com/cm/cs/pearls/s02b.pdf