CN111201559B - 置换装置、置换方法、以及记录介质 - Google Patents

Abstract

高速地进行置换处理。元素数决定单元(22)计算各分配目的地中包含的元素的数。开始位置决定单元(23)计算与各分配目的地对应的开始位置。分配目的地决定单元(24)计算表示缓存器内的分配目的地的值的列。置换生成单元(25)计算表示各分配目的地中的置换目的地的值的列。初始位置设定单元(31)将开始位置设定为表示与各分配目的地对应的处理中的位置的值。排序单元(32)将向量的元素设定到缓存器的各分配目的地。置换执行单元(33)通过对各分配目的地执行任意的逆置换算法，生成输出向量。

Description

置换装置、置换方法、以及记录介质

技术领域

本发明涉及高速地进行置换处理的技术。

背景技术

置换技术是计算机等中的基本的数据处理之一，被利用于各种情形。作为以往的置换技术，已知将数据移动至置换信息中记载的位置的不言而喻的置换，将排列随机地调换的Fisher-Yates算法(例如，参照非专利文献1)等。

现有技术文献

非专利文献

非专利文献1：Fisher,Ronald A.,Yates,Frank,"Statistical tables forbiological,agricultural and medical research",Oliver&Boyd,pp.26-27,1938.

发明内容

发明要解决的课题

在以往的置换技术中，在进行置换处理时IO访问成为随机访问。而且，在对象数据比高速缓冲存储器大时发生对非高速缓冲存储器的访问。通常，在高速缓冲存储器和非高速缓冲存储器中，速度不同1位以上，在顺序访问个随机访问中速度不同1位以上。因此，在以往的置换技术中，在对象数据较大的情况下，存在发生对非高速缓冲存储器的随机访问，处理变为低速的课题。

本发明的目的是鉴于上述的问题点，提供与以往相比，可以高速地进行置换处理的置换技术。

用于解决课题的手段

为了解决上述的课题，本发明的第一方式的置换装置，将D设为规定的分割数，将a^→设为长度为m的向量，将b^→设为小于表示缓存器内的分配目的地的D的值的列，将x^→设为表示各分配目的地中的置换目的地的值的列，将d^→设为表示长度为m的缓存器的向量，将i设为大于等于0且小于D的各整数，将j设为大于等于0且小于m的各整数，将S_i设为与第i分配目的地对应的开始位置，将N_i设为第i分配目的地中包含的元素的数，置换装置包括：初始位置设定单元，各整数i，将开始位置S_i设定为表示与第i分配目的地对应的处理中的位置的值P_i；排序单元，对各整数j，将向量a^→的第j元素a_j设定到缓存器d^→的第P_{b_j}个元素d_{P_b_j}；以及置换执行单元，对各整数i，通过对从缓存器d^→的第S_i元素起的N_i个元素d_{S_i},…,d_{S_i+N_i-1}，使用从列x^→的第S_i元素起的N_i个元素执行任意的逆置换算法，生成从输出向量c^→的第S_i元素起的N_i个元素c_{S_i},…,c_{S_i+N_i-1}。

为了解决上述的课题，本发明的第二方式的置换装置，将D设为规定的分割数，将a^→设为长度为m的向量，将b^→设为小于表示缓存器内的分配目的地的D的值的列，将x^→设为表示各分配目的地中的置换目的地的值的列，将d^→设为表示长度为m的缓存器的向量，将i设为大于等于0且小于D的各整数，将j设为大于等于0且小于m的各整数，将S_i设为与第i分配目的地对应的开始位置，将N_i设为第i分配目的地中包含的元素的数，置换装置包括：置换执行单元，对各整数i，通过对从向量a^→的第S_i元素起的N_i个元素，使用从列x^→第S_i元素起的N_i个元素执行任意的置换算法，设定从缓存器d^→的第S_i元素起的N_i个元素d_{S_i},…,d_{S_i+N_i-1}；初始位置设定单元，对于各整数i，将开始位置S_i设定为表示与第i分配目的地对应的处理中的位置的值P_i；以及排序单元，对各整数j，将缓存器d^→的第P_{b_j}个元素d_{P_b_j}设定到输出向量c^→的第j个元素c_j。

发明的效果

按照本发明，通过事前进行将置换的对象数据分配到高速缓存中容纳的缓存器中的处理，可以抑制对非高速缓冲存储器的随机访问，所以与以往相比，可以高速地进行置换处理。

附图说明

图1是例示了第一实施方式的置换装置的功能结构的图。

图2是例示了第一实施方式的置换方法的处理过程的图。

图3是例示了第二实施方式的置换装置的功能结构的图。

图4是例示了第二实施方式的置换方法的处理过程的图。

图5是例示了第三实施方式的置换装置的功能结构的图。

图6是例示了第三实施方式的置换方法的处理过程的图。

图7是例示了第四实施方式的置换装置的功能结构的图。

图8是例示了第四实施方式的置换方法的处理过程的图。

图9是例示了第五实施方式的置换装置的功能结构的图。

图10是例示了第五实施方式的置换方法的处理过程的图。

具体实施方式

本说明书中使用的“x^→”表示向量x或者列x。对于紧接“^→”前面的字符的下标表示向量或者列中的元素的号。例如，“x_i”表示向量x^→的第i元素。

在下标中使用的记号“_”表示将紧后面的字符设为下标。例如，A_{b_c}表示b_c作为下标附加到A上。同样，A_{B_c_d}表示B_{c_d}作为下标附加到A上。

本发明的置换技术，在置换m(≧2)个数据时，将对高速缓存中容纳的大小为D(≧2)个的缓存器大致分配的处理执行E(≧1)次(该部分为对非高速缓冲存储器的顺序访问处理)，m/D^E个数据中的高速缓存命中率变得足够高，但是通过切换为伴随随机访问的通常的置换(该部分是对高速缓冲存储器的随机访问处理)，抑制对低速的非高速缓冲存储器的随机访问，实现高速的置换。以下，D称为分割数，E称为递归深度。

“高速缓存中容纳的D个缓存器”不意味着D个各缓存器的大小为高速缓冲存储器大小以下。在程序访问了某个存储区域时，高速缓存机构将其周边的数据存储在高速缓存中。若将该存储单位设为X，将高速缓存大小设为C，若访问位置被限定为C/X个左右，则高速缓存就始终命中。而且，若D位置分别进行顺序访问，则在各位置顺序地访问，成为仅在突入了未进入高速缓存的区域时的高速缓存错误，在该情况下，成为与通常的顺序访问相同的速度。因此，希望D设为C/X左右的值。

如上述那样，在高速缓冲存储器和非高速缓冲存储器中速度不同1位以上，并且在顺序访问和随机访问中速度不同1位以上。因此，与进行1次对非高速缓冲存储器的随机访问的以往技术相比，对非高速缓冲存储器的顺序访问进行数次和对高速缓冲存储器的随机访问进行1次的本发明为高速。例如，在4字节的数据为100万个，高速缓冲存储器为256千字节，高速缓存的存储单位为16千字节时，数据大小为4兆字节，高速缓存命中率变为8％左右。另一方面，若将分割数D设为16，将递归深度E设为1而进行本发明的置换，在1次顺序访问相当的处理中，可以将数据16分割而逐一分割为256千字节，可以将剩余的处理设为高速缓存命中率大致100％的随机访问。由此，可以避免对最慢的非高速缓冲存储器的随机访问。

以下表示按本发明的方法进行随机置换的情况的算法(方案1)。因为分割被随机进行，所以分割后的缓存器的各部分的大小不确定。但是，若m的值足够大，则各部分的大小以非常高的几率分别成为m/D附近的大小。而且，适用本发明的是数据不被容纳在高速缓存的情况，所以前提是原来的m较大。

递归深度E依赖于数据数m的大小而决定。若缓存器的各部分的大小(在上述的例子为m/D左右)是高速缓存中容纳的大小，则设为E＝1。在缓存器的各部分的大小都没有被容纳在高速缓存中的情况下，设为E≧2，将各部分的数据设为对象，递归地执行算法，直至在高速缓存中容纳的大小即可。

方案(方案)1随机置换算法

输入：长度为m的向量a^→，递归深度E(≧1)

参数：分割数D(≧2)

输出：均匀随机地被置换的πa^→

1:随机置换生成

2:生成小于D的m个随机数b₀,b₁,…,b_m-1，设为b^→:＝(b₀,b₁,…,b_m-1)。

3:在b^→之中，对各i<D，合计i出现了多少个并设为N_i。

4:实施置换

5:在各i<D中，设S_i＝P_i:＝Σ_j<iN_j。其中，设S₀＝P₀:＝0。

6:for j＝0to m-1

7:设d_{P_b_j}:＝a_j。

8:设P_{b_j}:＝P_{b_j}+1。

9:for i＝0to D-1

10:将d_{S_i},…,d_{S_i+N_i-1}设为输入向量，若E≧2则将递归深度设为E-1，递归地执行方案1。若E＝1则执行任意的随机置换算法，输出作为结果得到的置换后的向量c_{S_i},…,c_{S_i+N_i-1}。

本发明也可以适用于非随机的置换。在该情况下，以下所示的算法(方案2)，将被提供的通常的置换形式变换为表示分配目的地的值的列和表示分配目的地中的置换目的地的值的列，以与本发明的处理过程一致。

方案2通常的置换的形式变换算法

输入：通常的置换π^→

输出：小于表示分配目的地的D的值的列b^→，表示分配目的地中的置换目的地的值的列x^→

1:q:＝m/D

2:r:＝m mod D

3:在各i<D中，S_i＝P_i:＝iq+min(r,i)。

4:for j＝0to m-1

5:设π_j与q的商为k'，余数为s。

6:设b_j:＝k'-(s<min(r,k')？1:0)。

7:设x_{P_b_j}:＝π_j-S_j。

8:更新为P_{b_j}:＝P_{b_j}+1。

其中，“？1:0”是运算符，在跟前的命题为真的情况设为1，假的情况下设为0。

在方案2中求商k'和余数s，但是若原样用除法进行计算则变为低速。因此，希望利用q在反复中为固定的事实，使用将除法变换为乘法的方法。例如，将M设为一定以上的位的2的幂，计算满足qp≧M的最小的p通过π_jp>>M计算π_j÷q(>>是移位运算)。因为qp≒M，所以p大致为q的倒数M。将除法变换为乘法的方法，例如记载在下记参考文献1中。

〔参考文献1〕Torbjorn Granlund,Peter L.Montgomery,"Division byinvariant integers using multiplication",PLDI 1994,pp.61-72.

若适用上述的方案2，则输出为了将长度为m均等地分配在D位置的部分的表示分配目的地的值的列b^→、表示各分配目的地中的置换目的地的值的列x^→。而且，“将长度为m均等地分配在D位置的部分”是指，例如在m＝80时，若D＝16则分割为每次5元素的部分，在其中例如置换目的地为第6的值，按照出现顺序移动至16位置之中第1部分，即在全体中相当于第5～9部分。而且，这里顺序都从0开始。

在以下中说明的方案3、4中，使用N_i、S_i，但是在将方案2和方案3、4组合来执行的情况下，也可以将N_i、S_i设为以下来执行。

各第i部分的元素数：N_i＝q+(i<r？1:0)

各第i部分的开始位置：S_i＝iq+min(r,i)

可适用该方法的情况是m≧256时，如前述那样，因为m为相当大的值的前提，所以没有问题。N_i、S_i成为上述的情况的证明在后叙述。

例如在E＝1时的方案1中，将方案2中生成的表示分配目的地的值的列b^→取代在方案1的步骤1中生成的随机置换b^→来使用，进而在方案1的步骤10的第i置换中，若将从第S_i元素起的N_i个元素设为置换而进行逆置换，则成为与将a^→设为置换来看进行了逆置换时相同的结果。对各i，从x^→的第S_i元素起的N_i个元素成为置换，所以通过递归地进行方案2，可以生成与E≧2的时的方案1对应的置换。而且，置换在记述从输入的哪个位置取得值的形式时为通常的置换，所以在将方案2和方案1组合时，应注意为逆映射即逆置换。

具体地说，以下表示在E＝1的情况下，使用方案2的输出进行逆置换的算法(方案3)。在E≧2的情况，只要将方案3的步骤7中执行的任意的逆置换算法设为方案3本身而递归地进行处理即可。

方案3逆置换算法

输入：长度为m的向量a^→，小于表示分配目的地的D的值的列b^→，表示分配目的地中的置换目的地的值的列x^→，递归深度E(≧1)

参数：分割数D(≧2)

输出：将a^→以b^→,x^→进行了逆置换后的列c^→

1:确保长度为m的缓存器d^→。

2:在各i<D中，设P_i:＝S_i。

在输入的b^→,x^→为使用方案1生成的结果的情况下，只要计算S_i:＝Σ_j<iN_j即可。这时，只要存储在方案1中生成的N_i即可。

在输入的b^→,x^→为使用方案2生成的结果的情况下，只要计算S_i:＝iq+min(r,i)即可。这时，通过q:＝m/D,r:＝m mod D计算q,r即可。

3:for j＝0to m-1

4:设d_{P_b_j}:＝a_j。

5:设P_{b_j}:＝P_{b_j}+1。

6:for i＝0to D-1

7:将d_{S_i},…,d_{S_i+N_i-1}作为输入向量，若E≧2则将递归深度设为E-1，递归地执行方案3。若E＝1则执行任意的逆置换算法，输出作为结果得到的置换后的向量c_{S_i},…,c_{S_i+N_i-1}。

而且，步骤6～7的反复可以并行地处理。

具体地说，以下示出在E＝1的情况下使用方案2的输出进行置换的算法(方案4)。在E≧2的情况下，与方案3同样，将在方案4的步骤3中执行的任意的置换算法作为方案4本身递归地处理即可。

方案4置换算法

输入：长度为m的向量a^→，小于表示分配目的地的D的值的列b^→，表示分配目的地中的置换目的地的值的列x^→，递归深度E(≧1)

参数：分割数D(≧2)

输出：将a^→通过b^→,x^→进行了逆置换的列c^→

1:确保长度为m的缓存器d^→。

2:for i＝0to D-1

3:将a_{S_i},…,a_{S_i+N_i-1}和x_{S_i},…,x_{S_i+N_i-1}设为输入向量，若E≧2则将递归深度设为E-1，递归地执行方案4。若E＝1则执行任意的置换算法，输出作为结果得到的置换后的向量d_{S_i},…,d_{S_i+N_i-1}。

在输入的b^→,x^→为使用方案1生成的情况下，存储以方案1生成的N_i，计算S_i:＝Σ_{j< i}N_j即可。

在输入的b^→,x^→为使用方案2生成的情况下，计算S_i:＝iq+min(r,i),N_i＝q+(i<r？1:0)即可。这时，通过q:＝m/D,r:＝m mod D计算q,r即可。

4:在各i<D中，设P_i:＝S_i。

5:for j＝0to m-1

6:设c_j:＝d_{P_b_j}。

7:设P_{b_j}:＝P_{b_j}+1。

而且，步骤2～3的反复可以并行地处理。另一方面，步骤5～7的反复无法并行地处理。

＜证明＞

以下示出在将方案2和方案3、4组合执行的情况下，N_i,S_i为上述的值的证明。

某个移动目的地j＝k'q+s的元素被存储在第k缓存器中的必要充分条件，从处理的定义如下。

(k'＝k∧s≧min(r,k'))∨(k'＝k+1∧s<min(r,k'))

因为k'＝k和k'＝k+1是不相容的，所以被∨夹住的左项和右项不相容，第k缓存器中所存储的元素数为满足左项的j和满足右项的j的数之和。

考虑左项。若考虑满足k'＝k的j，则由于k'＝k，所以min(r,k')＝min(r,k)。在k≧r时，min(r,k)＝r，在k<r时，同样地s≧k，左项与k'＝k∧((k≧r∧s≧r)∨(k<r∧s≧k))

为同值。若考虑右项，则同样与

k'＝k+1∧((k≧r∧s<r)∨(k<r∧s<k+1))

为同值。进行合计，在k≧r时，为

(k'＝k∧s≧r)∨(k'＝k+1∧s<r)

在k<r时，为

(k'＝k∧s≧k)∨(k'＝k+1∧s<k+1)

。这里，在m≧256时，q≧16。

(i)在m不是16的倍数时，k'≦16，满足k'＝16的j为j＝16q,16q+1,…,16q+r-1(注意，m不是16的倍数，所以r>0)。

上述基于反证法。若设k'≧17，则因q≧16而与k'q>16q+r＝m矛盾。若不设为k'＝16，则j的最大值为m-1，所以m-1≦15q+(q-1)，与m＝16q+r矛盾。因此，若注意到k'≦16，m-1＝16q+r-1，则满足k'＝16的j为j＝16q,16q+1,…,16q+r-1。

在k≦15时，s取0～q-1的全部的值，k'＝k的j在q个为s。这时，满足k'＝k∧s≧r的j的数为q-r个，满足k'＝k∧s≧k的j的数为q-k个。

在k≦14时，满足k'＝k+1∧s<r的j的数为r个，满足k'＝k+1∧s<k+1的j的数为k+1个。因此，在k≦14中，k<r时j的个数为q+1个，在k≧r时为q个。

在k＝15中，始终k≧r，满足k'＝k∧s≧r的j的数为q-r个，满足k'＝16的j为j＝16q,16q+1,…,16q+r-1，所以成为s<r的j为r个。因此，k＝15的j的个数为q个。这样，在k≦15中，在k<r中为q+1个，在k≧r中为q个，所以与q+(k<r？1:0)相等。而且，k≦15的合计为16q+r，所以k＝16的个数为0。

(ii)在m为16的倍数时，r＝0，所以s<min(r,k')始终为“假”，k＝k'。这样，在从第0至第15为止的全部缓存器中，j的个数为q个。由于r为0，所以k<r也始终为“假”，由于q+(k<r？1:0)＝q，所以命题正确。

以下，详细地说明本发明的实施方式。而且，对附图中具有相同的功能的结构单元附加相同标号，省略重复说明。

＜第一实施方式＞

本发明的第一实施方式是执行方案1所示的随机置换的置换装置以及方法。

如图1中例示的那样，第一实施方式的置换装置1包括：分配目的地决定单元11、元素数决定单元12、开始位置决定单元13、初始位置设定单元14、排序单元15、以及置换执行单元16。置换装置1将长度为m的向量a^→:＝(a₀,a₁,…,a_m-1)、和递归深度E(≧1)作为输入，输出将向量a^→均匀随机地置换后的输出向量c^→。该置换装置1通过进行图2中例示的各步骤的处理，实现第一实施方式的置换方法。

置换装置1例如是在具有中央运算处理装置(CPU:Central Processing Unit；中央处理单元)，主存储装置(RAM:Random Access Memory；随机存取存储器)等的公知或者专用的计算机中读入特别的程序而构成的特别的装置。置换装置1例如在中央运算处理装置的控制下执行各处理。被输入到置换装置1中的数据或在各处理中得到的数据，例如被存储在主存储装置中，主存储装置中存储的数据根据需要被读出至中央运算处理装置，被用于其它处理。置换装置1的各处理单元的至少一部分也可以由集成电路等硬件构成。

参照图2，说明第一实施方式的置换装置1执行的置换方法。

在步骤S11中，分配目的地决定单元11生成小于D的m个随机数b₀,b₁,…,b_m-1，生成随机数的列b^→:＝(b₀,b₁,…,b_m-1)。随机数b₀,b₁,…,b_m-1是表示在缓存器内分配作为置换对象的向量a^→的各元素a₀,a₁,…,a_m-1时的分配目的地的值。

在步骤S12中，元素数决定单元12对于大于等于0且小于D的各整数i，通过合计列b^→中的整数i的出现数，决定第i分配目的地的元素数N_i。

在步骤S13中，开始位置决定单元13对于大于等于0且小于D的各整数i，通过计算S_i:＝Σ_j<iN_j，决定与第i分配目的地对应的开始位置S_i。其中，设S₀:＝0。

在步骤S14中，初始位置设定单元14对于大于等于0且小于D的各整数i，将第i分配目的地的开始位置S_i设定为表示与缓存器的第i分配目的地对应的处理中的位置的值P_i。即，计算P_i:＝S_i。

在步骤S15中，排序单元15对于表示预先确保的长度为m的缓存器的向量d^→:＝(d₀,d₁,…,d_m-1)，按照随机数的列b^→，设定长度为m的向量a^→的各元素。具体地说，对大于等于0且小于m的各整数j，将向量a^→的第j元素a_j设定到缓存器d^→的第P_{b_j}元素。即，计算d_{P_b_j}:＝a_j。之后，更新为P_{b_j}:＝P_{b_j}+1。

在步骤S16中，置换执行单元16对于大于等于0且小于D的各整数i，在E≧2的情况下，将从向量d^→的第S_i元素起的N_i个元素d_{S_i},…,d_{S_i+N_i-1}设为输入向量，将递归深度E设为E-1，递归地执行步骤S11～S16。在E＝1的情况下，通过对从向量d^→的第S_i元素起的N_i个元素d_{S_i},…,d_{S_i+N_i-1}执行任意的逆置换算法，生成从输出向量c^→:＝(c₀,c₁,…,c_m-1)的第S_i元素起的N_i个元素c_{S_i},…,c_{S_i+N_i-1}。

＜第二实施方式＞

本发明的第二实施方式是，使用表示通过方案2所示的形式变换生成的缓存器内的分配目的地的值的列、和各分配目的地中的置换目的地的列，执行方案3中所示的逆置换的置换装置以及方法。

如图3中例示的那样，第二实施方式的置换装置2包括：除法单元21、元素数决定单元22、开始位置决定单元23、分配目的地决定单元24、置换生成单元25、初始位置设定单元31、排序单元32、以及置换执行单元33。置换装置2将长度为m的向量a^→:＝(a₀,a₁,…,a_m-1)、长度为m的置换π^→:＝(π₀,π₁,…,π_m-1)设为输入，输出将向量a^→按照置换π^→置换后的向量c^→:＝(c₀,c₁,…,c_m-1)。该置换装置2通过进行图4中例示的各步骤的处理，实现第二实施方式的置换方法。

参照图4，说明第二实施方式的置换装置2执行的置换方法。

在步骤S21中，除法单元21计算q:＝m/D,r:＝m mod D。

在步骤S22中，对于大于等于0且小于D的各整数i，元素数决定单元22通过计算N_i:＝q+(i<r？1:0)，决定第i分配目的地中包含的元素的数N_i。

在步骤S23中，对于大于等于0且小于D的各整数i，开始位置决定单元23通过计算S_i:＝iq+min(r,i)，决定与第i分配目的地对应的开始位置S_i。

在步骤S24中，对于大于等于0且小于m的各整数j，分配目的地决定单元24将π_j与q的商设为k'，将余数设为s，计算b_j:＝k'-(s<min(r,k')？1:0)，生成表示缓存器内的分配目的地的值的列b^→:＝(b₀,b₁,…,b_m-1)。

在步骤S25中，对于大于等于0且小于m的各整数j，置换生成单元25计算x_{P_b_j}:＝π_j-S_j，生成表示各分配目的地中的置换目的地的值的列x^→:＝(x₀,x₁,…,x_m-1)。

在步骤S31中，对于大于等于0且小于D的各整数i，初始位置设定单元31将第i分配目的地的开始位置S_i设定为表示与缓存器的第i分配目的地对应的处理中的位置的值P_i。即，计算P_i:＝S_i。

在步骤S32中，对于预先确保的表示长度为m的缓存器的向量d^→:＝(d₀,d₁,…,d_m-1)，排序单元32按照表示缓存器内的分配目的地的值的列b^→，设定长度为m的向量a^→的各元素。具体地说，对于大于等于0且小于m的各整数j，将向量a^→的第j个元素a_j设定到缓存器d^→的第P_{b_j}个元素。即，设定d_{P_b_j}:＝a_j。之后，更新为P_{b_j}:＝P_{b_j}+1。

在步骤S33中，对于大于等于0且小于D的各整数i，置换执行单元33通过对于从向量d^→的第S_i元素起的N_i个元素d_{S_i},…,d_{S_i+N_i-1}执行任意的逆置换算法，生成从输出向量c^→:＝(c₀,c₁,…,c_m-1)的第S_i元素起的N_i个元素c_{S_i},…,c_{S_i+N_i-1}。

＜第三实施方式＞

本发明的第三实施方式是，使用表示通过方案2所示的形式变换生成的缓存器内的分配目的地的值的列、和表示各分配目的地中的置换目的地的值的列，执行方案4所示的置换的置换装置以及方法。

如图5中例示的那样，第三实施方式的置换装置3包括：除法单元21、元素数决定单元22、开始位置决定单元23、分配目的地决定单元24、置换生成单元25、置换执行单元41、初始位置设定单元42、以及排序单元43。置换装置3将长度为m的向量a^→:＝(a₀,a₁,…,a_m-1)、长度为m的置换π^→:＝(π₀,π₁,…,π_m-1)设为输入，输出将向量a^→按照置换π^→置换后的向量c^→:＝(c₀,c₁,…,c_m-1)。该置换装置3通过进行图6中例示的各步骤的处理，实现第三实施方式的置换方法。

参照图6，说明第三实施方式的置换装置3执行的置换方法。以下，以与上述的各实施方式的不同点为中心进行说明。

从步骤S21至步骤S25的处理与第二实施方式是同样的。

在步骤S41中，对于大于等于0且小于D的各整数i，置换执行单元41通过使用表示各分配目的地中的置换目的地的值的列x^→的从第S_i元素起的N_i个元素，对长度为m的向量a^→的从第S_i元素起的N_i个元素执行任意的置换算法，设定预先确保的长度为m的向量d^→:＝(d₀,d₁,…,d_m-1)的从第S_i元素起的N_i个元素。

在步骤S42中，对于大于等于0且小于D的各整数i，初始位置设定单元42将第i分配目的地的开始位置S_i设定为表示与缓存器的第i分配目的地对应的处理中的位置的值P_i。即，计算P_i:＝S_i。

在步骤S43中，对于输出向量c^→:＝(c₀,c₁,…,c_m-1)，排序单元43按照表示缓存器内的分配目的地的值的列b^→，设定长度为m的向量d^→的各元素。具体地说，对于大于等于0且小于m的各整数j，将缓存器d^→的第P_{b_j}个元素d_{P_b_j}设定到输出向量c^→的第j个元素c_j。即，设定c_j:＝d_{P_b_j}。之后，更新为P_{b_j}:＝P_{b_j}+1。

＜第四实施方式＞

本发明的第四实施方式是，将通过方案1生成的2个随机置换(b^→,x^→)设为表示缓存器内的分配目的地的值的列和表示各分配目的地中的置换目的地的值的列，执行方案3所示的逆置换的置换装置以及方法。

如图7中例示的那样，第四实施方式的置换装置4包括：分配目的地决定单元11、元素数决定单元12、开始位置决定单元13、置换生成单元17、初始位置设定单元31、排序单元32、以及置换执行单元33。置换装置4将长度为m的向量a^→:＝(a₀,a₁,…,a_m-1)设为输入，输出将向量a^→进行了均匀随机地置换的输出向量c^→。该置换装置4通过进行图8中例示的各步骤的处理，实现第四实施方式的置换方法。

参照图8，说明第四实施方式的置换装置4执行的置换方法。以下，以与上述的各实施方式的不同点为中心进行说明。

步骤S11至步骤S13的处理与第一实施方式是同样的。

在步骤S17中，置换生成单元17对于大于等于0且小于D的各整数i，利用任意的逆置换算法，生成m个置换π_i。将依次连结了该置换π_i的值的列作为表示各分配目的地中的置换目的地的值的列x^→来处理。

步骤S31至步骤S33的处理与第二实施方式是同样的。

＜第五实施方式＞

本发明的第五实施方式是，将通过方案1生成的2个随机置换(b^→,x^→)设为表示缓存器内的分配目的地的值的列、和表示各分配目的地中的置换目的地的值的列，执行方案4所示的置换的置换装置以及方法。

如图9中例示的那样，第五实施方式的置换装置5包括：分配目的地决定单元11、元素数决定单元12、开始位置决定单元13、置换生成单元17、置换执行单元41、初始位置设定单元42、以及排序单元43。置换装置5将长度为m的向量a^→:＝(a₀,a₁,…,a_m-1)设为输入，输出均匀随机地置换了向量a^→后的输出向量c^→。该置换装置5通过进行图10中例示的各步骤的处理，实现第五实施方式的置换方法。

参照图10，说明第五实施方式的置换装置5执行的置换方法。以下，以与上述的各实施方式的不同点为中心进行说明。

从步骤S11至步骤S13的处理与第四实施方式是同样的。

步骤S17的处理与第四实施方式是同样的。

从步骤S41至步骤S43的处理与第三实施方式是同样的。

＜变形例＞

通过第一实施方式的置换装置执行随机置换，并且在进行了一些数据处理后，能够将随机置换复原。在该情况下，将在执行任意的置换算法时生成的置换π_i按顺序连结而设为表示各分配目的地中的置换目的地的值的列x^→，与表示执行了第一实施方式的置换装置时生成的缓存器内的分配目的地的值的列b^→一起使用，执行第二实施方式以及第四实施方式所示的步骤S31～S33的处理即可。这时，也可以构成为将表示缓存器内的分配目的地的值的列b^→和表示分配目的地中的置换目的地的值的列x^→保存在置换装置内的未图示的存储单元等中，适当读入并利用。

本发明的要点如下。利用与非高速缓存的随机访问相比，即使处理量增加，顺序访问数次和高速缓存的随机访问1次一方为高速的事实、以及若为对数个位置的随机访问则可以以相当于顺序访问的速度进行访问的事实，本发明实现高速的置换。而且，在从通常的置换的形式变换(方案2)中，除了每1元素乘法1次之外，设法使得仅以与现代的计算机中最高速的运算类似的加减比较运算数次进行均等地分配。

通过这样构成，本发明的置换技术具有以下的效果。可以几乎没有非高速缓存的随机访问，而进行高速地置换以及逆置换处理。例如，在32bit的数据100万件下，在以往的不言自明的置换和Fisher-Yates算法中为10Gbps左右的速度，而在E＝1的时的本发明中为20Gbps左右，在E＝2的时的本发明中为12Gbps左右。在1000万件下，在以往技术中为3Gbps左右，而在E＝1的时的本发明中为10Gbps左右，在E＝2的时的本发明中为12Gbps左右。在1亿件下，在以往技术中为2Gbps左右，而在E＝1的时的本发明下为5Gbps左右，在E＝2的时的本发明下为10Gbps左右。若数据数增加，则为了排除随机访问而需要增加E，但是若增加E则反而会增加访问次数本身，所以可知对每个数据量存在最佳的E的值。

以上，说明了本发明的实施方式，但是不用说，具体的结构不限于这些实施方式，即使在不脱离本发明的宗旨的范围内有适当设计的变更等，也被包含在本发明中。实施方式中说明的各种的处理不仅按照记载的顺序被时序地执行，也可以根据执行处理的装置的处理能力或者需要被并行地或者单独地执行。

[程序，记录介质]

在通过计算机实现上述实施方式中说明的各装置中的各种处理功能的情况下，通过程序记述各装置应具有的功能的处理内容。然后，通过计算机执行该程序，在计算机上实现上述各装置中的各种处理功能。

记述了该处理内容的程序可以记录在计算机可读取的记录介质中。作为计算机可读取的记录介质，例如可以是磁记录装置、光盘、光磁记录介质、半导体存储器等任何介质。

而且，该程序的流通例如通过销售、转让、租借等记录了该程序的DVD、CD-ROM等可拆装型记录介质来进行。进而，也可以设为将该程序存储在服务器计算机的存储装置中，经由网络，通过将该程序从服务器计算机转发到其它计算机，使该程序流通的结构。

执行这样的程序的计算机例如首先将可拆装型记录介质中记录的程序或者从服务器计算机转发的程序暂时存储在自己的存储装置中。然后，在执行处理时，该计算机读取自身的存储装置中存储的程序，执行按照读取的程序的处理。而且，作为该程序其它执行方式，计算机也可以从可拆装型记录介质直接读取程序，执行按照该程序的处理，进而，也可以在每次从服务器计算机对该计算机转发程序时，逐次执行按照接受的程序的处理。而且，也可以设为通过不进行从服务器计算机向该计算机的程序的转发，仅通过该执行指令和结果取得来实现处理功能的、所谓ASP(Application Service Provider，应用服务提供商)型的服务，执行上述的处理的结构。而且，本方式中的程序中，包含供电子计算机的处理用的信息即基于程序的信息(虽然不是对于计算机的直接的指令，但是具有规定计算机的处理的性质的数据等)。

而且，在本方式中，设为通过在计算机上执行规定的程序来构成本装置，但是也可以硬件性地实现这些处理内容的至少一部分。

Claims (9)

1.一种置换装置，包括初始位置设定单元和排序单元和置换执行单元，其特征在于，

将C设为该置换装置的高速缓存大小，将X设为存储单位，将D设为规定的分割数，将E设为递归深度，将a^→设为长度为m的向量，将b^→设为小于表示缓存器内的分配目的地的D的值的列，将x^→设为表示各分配目的地之中的置换目的地的值的列，将d^→设为表示长度为m的缓存器的向量，将i设为大于等于0且小于D的各整数，将j设为大于等于0且小于m的各整数，将S_i设为与第i分配目的地对应的开始位置，将N_i设为第i分配目的地中包含的元素的数，

m个数据的数据大小比C大，

D为C/X左右的值，

m/D^E个数据为容纳在高速缓存中的大小，

在E≧2时，

所述初始位置设定单元对各整数i，将所述开始位置S_i设定为表示与第i分配目的地对应的处理中的位置的值P_i；

所述排序单元对各整数j，将所述向量a^→的第j元素a_j设定到所述缓存器d^→的第P_{b_j}元素d_{P_b_j}；以及

所述置换执行单元对各整数i，通过对于从所述缓存器d^→的第S_i元素起的N_i个元素d_{S_i},…,d_{S_i+N_i-1}，使用从所述列x^→的第S_i元素起的N_i个元素执行任意的逆置换算法，生成从输出向量c^→的第S_i元素起的N_i个元素c_{S_i},…,cS_{_} ⁱ ₊N_{_} ⁱ-1。

2.如权利要求1所述的置换装置，还包括：

分配目的地决定单元，生成小于D的m个随机数b_j作为所述列b^→；

元素数决定单元，对各整数i，通过合计所述列b^→中的整数i的出现数，决定所述元素数N_i；

开始位置决定单元，对各整数i，通过计算S_i:＝Σ_j<iN_j，决定所述开始位置S_i；以及

置换生成单元，通过任意的随机置换算法生成所述列x^→。

3.如权利要求1所述的置换装置，

将π^→:＝(π₀,π₁,…,π_m-1)设为长度为m的置换，设q:＝m/D，设r:＝m mod D，

所述置换装置还包括：

元素数决定单元，对各整数i，通过计算N_i:＝q+(i<r？1:0)，决定所述元素数N_i；

开始位置决定单元，对各整数i，通过计算S_i:＝iq+min(r,i)，决定所述开始位置S_i；

分配目的地决定单元，将对各整数j的、所述置换π^→的第j元素π_j与q的商设为k'，将余数设为s，通过计算b_j:＝k'-(s<min(r,k')？1:0)生成所述列b^→；以及

置换生成单元，对各整数j，通过计算x_{P_b_j}:＝π_j-S_j，生成所述列x^→。

4.一种置换装置，包括置换执行单元和初始位置设定单元和排序单元，其特征在于，

将C设为该置换装置的高速缓存大小，将X设为存储单位，将D设为规定的分割数，将E设为递归深度，将a^→设为长度为m的向量，将b^→设为小于表示缓存器内的分配目的地的D的值的列，将x^→设为表示各分配目的地之中的置换目的地的值的列，将d^→设为表示长度为m的缓存器的向量，将i设为大于等于0且小于D的各整数，将j设为大于等于0且小于m的各整数，将S_i设为与第i分配目的地对应的开始位置，将N_i设为第i分配目的地中包含的元素的数，

m个数据的数据大小比C大，

D为C/X左右的值，

m/D^E个数据为容纳在高速缓存中的大小，

在E≧2时，

所述置换执行单元对各整数i，通过对于从所述向量a^→的第S_i元素起的N_i个元素，使用从所述列x^→的第S_i元素起的N_i个元素执行任意的置换算法，设定从所述缓存器d^→的第S_i元素起的N_i个元素d_{S_i},…,d_{S_i+N_i-1}；

所述初始位置设定单元对各整数i，将所述开始位置S_i设定为表示与第i分配目的地对应的处理中的位置的值P_i；以及

所述排序单元对各整数j，将所述缓存器d^→的第P_{b_j}元素d_{P_b_j}设定到输出向量c^→的第j元素c_j。

5.如权利要求4所述的置换装置，还包括：

分配目的地决定单元，生成小于D的m个随机数b_j作为所述列b^→；

元素数决定单元，对各整数i，通过合计所述列b^→中的整数i的出现数，决定所述元素数N_i；

开始位置决定单元，对各整数i，通过计算S_i:＝Σ_j<iN_j，决定所述开始位置S_i；以及

置换生成单元，通过任意的随机置换算法生成所述列x^→。

6.如权利要求4所述的置换装置，

将π^→:＝(π₀,π₁,…,π_m-1)设为长度为m的置换，设q:＝m/D，设r:＝m mod D，

所述置换装置还包括：

元素数决定单元，对各整数i，通过计算N_i:＝q+(i<r？1:0)，决定所述元素数N_i；

开始位置决定单元，对各整数i，通过计算S_i:＝iq+min(r,i)，决定所述开始位置S_i；

分配目的地决定单元，将对各整数j的、所述置换π^→的第j元素π_j与q的商设为k'，将余数设为s，通过计算b_j:＝k'-(s<min(r,k')？1:0)生成所述列b^→；以及

置换生成单元，对各整数j，通过计算x_{P_b_j}:＝π_j-S_j，生成所述列x^→。

7.一种置换方法，是包括初始位置设定单元和排序单元和置换执行单元的置换装置执行的置换方法，其特征在于，

将C设为该置换装置的高速缓存大小，将X设为存储单位，将D设为规定的分割数，将E设为递归深度，将a^→设为长度为m的向量，将b^→设为小于表示缓存器内的分配目的地的D的值的列，将设为x^→表示各分配目的地中的置换目的地的值的列，将d^→设为表示长度为m的缓存器的向量，将i设为大于等于0且小于D的各整数，将j设为大于等于0且小于m的各整数，将S_i设为与第i分配目的地对应的开始位置，将N_i设为第i分配目的地中包含的元素的数，

m个数据的数据大小比C大，

D为C/X左右的值，

m/D^E的数据大小为容纳在高速缓存中的大小，

在E≧2时，

对各整数i，所述初始位置设定单元将所述开始位置S_i设定为表示与第i分配目的地对应的处理中的位置的值P_i，

对各整数j，所述排序单元将所述向量a^→的第j元素a_j设定到所述缓存器d^→的第P_{b_j}个元素d_{P_b_j}，

对各整数i，所述置换执行单元通过对从所述缓存器d^→的第S_i元素起的N_i个元素d_{S_i},…,d_{S_i+N_i-1}，使用从所述列x^→的第S_i元素起的N_i个元素执行任意的逆置换算法，生成从输出向量c^→的第S_i元素起的N_i个元素c_{S_i},…,cS_{_} ⁱ ₊N_{_} ⁱ-1。

8.一种置换方法，是包括置换执行单元和初始位置设定单元和排序单元的置换装置执行的置换方法，其特征在于，

将C设为该置换装置的高速缓存大小，将X设为存储单位，将D设为规定的分割数，将E设为递归深度，将a^→设为长度为m的向量，将b^→设为小于表示缓存器内的分配目的地的D的值的列，将x^→设为表示各分配目的地中的置换目的地的值的列，将d^→设为表示长度为m的缓存器的向量，将i设为大于等于0且小于D的各整数，将j设为大于等于0且小于m的各整数，将S_i设为与第i分配目的地对应的开始位置，将N_i设为第i分配目的地中包含的元素的数，

m个数据的数据大小比C大，

D为C/X左右的值，

m/D^E的数据大小为容纳在高速缓存中的大小，

在E≧2时，

对各整数i，所述置换执行单元通过对从所述向量a^→的第S_i元素起的N_i个元素，使用从所述列x^→的第S_i元素起的N_i个元素执行任意的置换算法，设定从所述缓存器d^→的第S_i元素起的N_i个元素d_{S_i},…,d_{S_i+N_i-1}，

对各整数i，所述初始位置设定单元将所述开始位置S_i设定为表示与第i分配目的地对应的处理中的位置的值P_i，

对各整数j，所述排序单元将所述缓存器d^→的第P_{b_j}元素d_{P_b_j}设定到输出向量c^→的第j元素c_j。

9.一种记录介质，记录了用于使计算机具有权利要求1至6的任意一项所述的置换装置的功能的程序。