选择多维数组切片的算法



我正在开发一个开源科学库(用C编写),我们想要支持的操作之一是让"使用者"从"生产者"复制多维数组的任意切片。例如,假设我们有一个4x5 2D阵列(我为格式化道歉):

10、20、30、40

50、60、70、80

90、100、110、120

130140150160

170180190200

它们被暴露为尺寸为20∶10、20、30、40、50、60、…的线性阵列,。。。,200

用户代码基本上传递它想要选择的偏移量和计数(基本上是坐标):

start[2]={0,2}(x开始,y开始)

count[2]={3,2}(x计数,y计数)

这意味着,对于x维度,从0位置开始,给我3(x坐标范围为[0:2],对于y维度,从2位置开始,给出2(y坐标范围为[3,4])。

这将导致

130140150170180190

复制到用户缓冲区(长度为6)。

那么已知的是:我们知道数组的维度大小(4x5)、维度数量(2)以及用户想要的"坐标"。

数组维度可以是任意数量的维度。。。1,2,3.6?100?因为在科学应用程序中,数组的维度非常大是很常见的。

这是C代码,老实说,我想不出一个算法并将其转化为代码来解决问题。我有生物学背景,所以我对编码的算法思维方面没有太多经验。

有人对如何解决这个问题有什么建议吗?非常感谢您的帮助!

为了在线性数组中获得开始,您必须使用start[0]*numColumns+start[1]。你必须有一个循环,就像

即使使用线性数组,也可以使用多维语法访问元素,因为c在内部将多维数组存储为线性数组。

 for(int i = start[0], countx = 0, count < xcount; countx++, i++) {
      for( int j = start[1], county = 0; county < ycount; county++, j++) {
           // copy array[i][j] into another array.
      }
 }

您必须计算每个维度开始的偏移量。

给定数组[5][6][7][8]//索引a、b、c、d等和尺寸dim(a)=5,dim(b)=6,dim(c)=7,dimd(d)=8

对于索引a,位置(0):pos(a[0])=0,实际上是0*6*7*8

对于索引a,位置(a[1])为0{pos(a[0])+1(索引a的当前值)*6*7*8

并且通常对于索引a,位置(n)=pos(a[0])+n*dim(b)*dim

现在,在这样的线性排列中,你的问题变成了一个洋葱,剥去外部的尺寸来定位内部尺寸中的位置

对于索引b,位置(或值)0取决于索引a的值

所以对于索引b,我们将相对于pos(a[2])的位置写成pos(a[2]b[0])=pos(a[2])+位置(b[0])

与pos(a[0])一样,pos(b[0])也是0<0*dim(c)*dim(d)>,但对于任何有效值0<n<dim(a)

所以pos(a[2]b[0])=pos(a[2])+0

pos(a[2]b[1])是pos(a[2])+pos(b[1])其中posb[1]是0+1*dim(c)*dim

所以对于任何给定的坐标pos(a[i]b[j]c[k],d[l])你的陈述立场是pos(a[i])+pos(b[j],+pos

要选择任意数量的元素,您的值实际上将来自最后一个维度d的集合。

如果你想要a的2个单位,b的3个单位,c的1个单位和d的2个单元,你需要前进到pos(a[i]b[j]c[k]d[l]),并选择元素d[l]和d[l+1]

然后回溯到pos(a[i],b[j+1],c[k],d[l]),并再次选择两个项目d[l]和d[l+1]。

显然,这个解决方案最好由递归函数提供。

我有一个项目截止日期(还剩2.5周),但我可以在那之后尝试设置代码。。。如果没有人敢接受你的挑战。

最新更新