メモリ移動アルゴリズム

メモリ移動アルゴリズム
個人のノート、転載して本人に連絡して下さい
このノートも私のgithubに置かれていて、そこに詳しいコードがあります.
概要
アルゴリズムの授業で先生はメモリ移動アルゴリズムを紹介した.正直、当時は聞き取れなかった.なぜなら、これには何の感触もなく、肝心な点がどこにあるか分からないからです.
問題の背景
メモリ上のデータを効率的にkビット移動するにはどうすればいいですか?時間の複雑さと空間の複雑さをできるだけ小さくする必要があります.
授業で右シフトの状況を話したことがあるので、ここでは左シフトだけを議論します.
通常のプログラミングでは,ループ移動は難しくない問題である.すべての要素を1つ移動するたびに、全体的にk回移動すればタスクを完了できます.しかし、計算によってこの繰り返し操作を複数回移動させることは明らかである.
もんだいぶんせき
今から簡単な分析をします.移動するシーケンスを次のように設定します.
a0,a1,a2,.....,ai,.....an−1
要素aiについては,kビットを左に移動した後,位置はi−kであった.メモ:
NewIndex(i,n,k)=i−k
限界を考慮して、次のように修正する必要があります.
NewIndex(i,n,k)=(i−k)modn
なお、型取り演算の結果を正数とする.この結論は明らかで,この問題の移動はもともと循環移動であるからである.初歩的な移動構想を得ることができます.

move_right(col,n,k):
  new_col=col.clone()
  for i in [0,col.size()):
    new_pos=NewIndex(i,n,k)
    new_col[new_pos]=col[i]
  return new_col

この考え方は合理的に見える.しかし、メモリ移動のアルゴリズムはO(n)の余分な空間消費を許可することができますか?もう少し改善しなければならないのではないかと心配しています.
上のアルゴリズムでは,既存の空間,すなわちcolの空間をうまく利用していない.各colのストレージスペースは、要素値が提供された後、実際には他の役割はありません.この要素の移動が完了すると、他の役割はなく、その空間を完全に多重化することができます.定数個しか使用できない記憶空間を限定すれば、この考えを十分に利用して、穴を掘るしかない.
この例を考慮します.
0,1,2,3,4,5,6,7
5ビット左シフトが要求される場合、このような移動シーケンスが得られる.

0 -> 3 -> 6 -> 1 -> 4 -> 7 -> 2 -> 5 -> 0

シーケンス全体がループを形成していることがわかる.では、どんな場合でも、一つのサイクルを形成することができるのではないでしょうか.
要素aiの場合、移動後の位置は次のとおりです.

i -> (i-k) mod n

一方、元素a(i−k)modnの移動後の位置は、

(i-k) mod n -> ((i-k) mod n - k) mod n

理解を容易にするために、kがnより小さいと仮定してもよい.すなわち、k=kmodnは、実際には、以下の推定に対しても、kがnより大きい場合の一般性を失わない.
現在、タッチ演算の法則に基づいて(証明できる):
(amodn−bmodn)modn=(a−b)modn
では、
((i−k)modn−k)modn=((i−k)modn−kmodn)modn=(i−2k)modn
すなわち、

  i -> (i-k) mod n -> (i-2k) mod n

これで得られます.

i -> (i-k) mod n ->....-> (i-p*k) mod n

pがnに等しい場合,明らかに先頭と末尾の2つが重なる.サイクルが形成されますしかし、これは、ループシーケンスにすべての要素が含まれていることを意味しません.すなわち、移動プロセスは、必ずしも1つのサイクルによって決定されるものではなく、複数のサイクルが必要である可能性がある.添付のコードmove-oder.cppでは、このような状況があります.
いくつかのサイクルで移動シーケンスを決定することができますが、私は確かに方法がありません.先生の解法は確かにいいですね.思い出せません.
y=q*k/n,k=a*e,n=b*e,eがkとnの最大公約数であるとすると、
kn=yq=ab
a bは互いに質的であるため、サイクルシーケンスの長さが最小であることを確保するために、qは必ず最小である.
q=b
すなわち,qサイクルは各要素に配慮できる.ここで、qは、nをkとnの最大公約数で割ったものである.
アルゴリズムの説明
改良されたアルゴリズムのビットコードが与えられるようになった.

move_left(col,n,k):
    e=     (k,n)
    for j in [0,e):
        backup=col[i]
        new_pos=NextIndex(j,n,k)
        for i in [0,n/e):
            temp=backup
            backup=col[new_pos]
            col[new_pos]=temp
            new_pos=NextIndex(new_pos,n,k)
    return col

余分に消費される空間的複雑度はO(1)時間的複雑度T(n)=Σn/eq=1(Σqi=04)である(求めないが,擬似コードによると,余分な操作は行わず,各内ループは1つの要素の移動に対応するよ,全体的な時間的複雑度はO(n))
コード実装
メモリーを見てcpp