1 Dベクトル回転アルゴリズム

「プログラミング珠玉」第2章では,n元一次元ベクトル回転アルゴリズム(配列循環シフトアルゴリズムとも呼ばれる)の5つの考え方について述べ,それらの時間と空間性能の違いと優劣を比較した.
一、問題の説明
n元の1次元ベクトルを左にi個の位置に回転させます.例えば、n=8、i=3とし、ベクトルabcdefghabcがベクトルdefghabcに回転する.簡単なコードは、n元の中間ベクトルを使用して、nステップ内でこの作業を完了することができる.数十バイトのメモリスペースだけを使って、nに比例する時間でベクトルの回転を完了できますか?
二、解決策
構想1:ベクトルxの前のi個の要素を1つの一時配列にコピーし、残りのn-i個の要素をi個の位置に左に移動し、その後、前のi個の要素を一時配列からxの残りの位置にコピーする.パフォーマンス:この方法ではi個の追加の場所が使用され、iが大きいとストレージスペースの消費が大きくなります.
C++コード実装:

/*************************************************************************
    > File Name: vector_rotate.cpp
    > Author: SongLee
    > E-mail: [email protected]
    > Created Time: 2014 06 04      17 07 06 
    > Personal Blog: http://songlee24.github.io
 ************************************************************************/
#include<iostream>
#include<string>
using namespace std;

int main()
{
    string s = "abcdefghijklmn";
    cout << "The origin is: " << s << endl;
    //     
    int i;
    cin >> i;
    if(i > s.size())
    {
        i = i%s.size();
    }
    //   i       
    string tmp(s, 0, i);
    //       i   
    for(int    j=i; j<s.size(); ++j)
    {
        s[j-i] = s[j];
    }
    s = s.substr(0, s.size()-i) + tmp;
    cout << "The result is: "<< s << endl;
    return 0;
}

    
構想2:xをnに比例して左に回転する関数を定義し、その関数をi回呼び出す.性能:この方法は空間複雑度がO(1)であるが、運転時間の消費が多すぎる.
C++コード実装:

/*************************************************************************
    > File Name: vector_rotate_1.cpp
    > Author: SongLee
    > E-mail: [email protected]
    > Created Time: 2014 06 04      19 49 59 
    > Personal Blog: http://songlee24.github.io
 ************************************************************************/
#include<iostream>
#include<string>
using namespace std;

void rotateOnce(string &s)
{
    char tmp = s[0];
    int i;
    for(i=1; i<s.size(); ++i)
    {
        s[i-1] = s[i];
    }
    s[i-1] = tmp;
}


int main()
{
    string s = "abcdefghijklmn";
    cout << "The origin is: " << s << endl;
    //     
    int i;
    cin >> i;
    if(i > s.size())
    {
        i = i%s.size();
    }
    //     i 
    while(i--)
    {
        rotateOnce(s);
    }
    cout << "The result is: "<< s << endl;
    return 0;
}

        
構想3:x[0]を一時変数tに移動し、x[i]からx[0]に移動し、x[2 i]からx[i]に順次類推し、x[0]の位置に戻って要素を抽出するまで、このとき一時変数tから要素を抽出するように変更する.そしてこのプロセスを終了する(下付きがnより大きい場合はnを型抜きまたはnを減算).このプロセスがすべての要素を移動しない場合はx[1]から再び移動し、合計iとnの最大公約数回移動する.性能:この方法は非常に精巧で、本で述べたように巧みなアクロバットショーとも言える.空間複雑度はO(1)であり、時間複雑度は線形時間であり、問題のパフォーマンス要件を満たしていますが、まだ最適ではありません.
C++コード実装:

/*************************************************************************
    > File Name: vector_rotate_2.cpp
    > Author: SongLee
    > E-mail: [email protected]
    > Created Time: 2014 06 04      20 21 59 
    > Personal Blog: http://songlee24.github.io
 ************************************************************************/
#include<iostream>
#include<string>
using namespace std;

//     （    ）        
int gcd(int i, int j)
{
    while(1)
    {
        if(i > j)
        {
            i = i%j;
            if(i == 0)
            {
                return j;
            }
        }
        if(j > i)
        {
            j = j%i;
            if(j == 0)
            {
                return i;
            }
        }
    }
}

int main()
{
    string s = "abcdefghijklmn";
    cout << "The origin is: "<< s << endl;
    //     
    int i;
    cin >> i;
    if(i > s.size())
    {
        i = i%s.size();
    }
    //   
    char tmp;
    int times = gcd(s.size(), i);
    for(int j=0; j<times; ++j)
    {
        tmp = s[j];
        int pre = j; //         
        while(1)
        {
            int t = pre+i;
            if(t >= s.size())
                t = t-s.size();
            if(t == j) //   tmp     j  
                break;
            s[pre] = s[t];
            pre = t;
        }
        s[pre] = tmp;
    }
    cout << "The result is: "<< s << endl;
    return 0;
}

        
構想4:回転ベクトルxは実際には交換ベクトルabの2つのセグメントであり、ベクトルbaが得られ、ここでaはxの前i要素を表す.aはbより短いと仮定する.bをblとbrに分割し,brの長さがaの長さと同じにする.aとbrを交換し、ablbrをbrblaに変換します.シーケンスaはすでにその最終位置にあるので、bの2つの部分を交換することに集中することができます.この新しい問題は元の問題と同じであるため,我々は再帰的に解決する.この方法は優雅なプログラムを得ることができるが,巧みなコードが必要であり,その効率が十分に高いことを見るにはいくつかの思考が必要である.

//  

       
構想5:(最適)この問題を配列abをbaに変換すると見なし、同時に配列中の特定の部分の元素を逆序にする関数を持つと仮定する.abから、まずaに対して逆を求め、arbを得、それからbに対して逆を求め、arbrを得る.最後に全体的に逆を求め、(arbr)r、すなわちbaを得る.
reverse(0, i-1)  /*cbadefgh*/reverse(i, n-1)  /*cbahgfed*/reverse(0, n-1)/*defghabc*/
パフォーマンス:逆シーケンスを求める方法は時間と空間的に効率的で、コードが非常に短く、エラーが発生しにくい.
C++コード実装:

/*************************************************************************
    > File Name: vector_rotate.cpp
    > Author: SongLee
    > E-mail: [email protected]
    > Created Time: 2014 06 04      23 37 54 
    > Personal Blog: http://songlee24.github.io
 ************************************************************************/
#include<iostream>
#include<string>
using namespace std;

void reverse(string &s, int begin, int end)
{
    while(begin < end)
    {
        char tmp = s[begin];
        s[begin] = s[end];
        s[end] = tmp;
        ++begin;
        --end;
    }
}

int main()
{
    string s = "abcdefghijklmn";
    cout << "The origin is: "<< s << endl;
    
    int i;
    cin >> i;
    if(i > s.size())
    {
        i = i%s.size();
    }

    reverse(s, 0, i-1);
    reverse(s, i, s.size()-1);
    reverse(s, 0, s.size()-1);

    cout << "The result is: "<< s << endl;
    return 0;
}

三、拡張延長
ベクトルabcをcbaに回転するにはどうすればいいですか?
前述の問題と同様に、このベクトル回転は隣接しないメモリブロックの交換モデルに対応する.解法はよく似ている,すなわち定式化:cba=(arbrcr)rを用いる
注意:面接や筆記試験でベクトル回転(メモリブロック交換)の問題が発生した場合は、効率的で簡潔な5つの問題を使用することが望ましい.