C++中实现动态多维数组模板的分析-04 - 悲催的科学匠人 - 冷水's blog

C++中实现动态多维数组模板的分析-04

冷水 posted @ 2010年12月17日 00:52 in C++ , 1347 阅读

对于一维化存储的数据，实现多维编号访问，索引是必须的。

 

考虑2D数组 array[0..I-1][0..J-1]，为了方便采用FORTRAN的数组元素排列顺序，即

for （j=0；j<J;j++)
for （i=0；i<I;i++)

那么一维编号

n=i+j \times I

为了避免乘法，我们可以预先计算好S_j(j)=j*I。则有一维编号计算公式为

n=i+S_j(j)

代价是我们必须事先计算好J个S_j(j)。

 

再考虑3D数组 array[0..I-1][0..J-1][0..K-1]，其一维编号计算公式为

n=i+j*I+k*J*I

同理，令S_j(j)=j\times I和S_k(k)=k\times J\times I，上式可写为

n=i+S_j(j)+S_k(k)

 

这个方法可以推导到任意维数组。即对于N维数组，设其第i维范围是$\left[ 0 \dots D_i-1 \right ] $,我们事先计算好偏移

$$ S_i(i)=\prod_{k=1,i-1}D_k $$$$ S_i(i)=\prod_{k=1,i-1}D_k \qquad ,i>1$$

此外对于第一维

$$ S_1=1 $$

则元素$[k_1][k_2]\dots[k_i]\dots[k_N]$的一维编号计算格式为

$$n=\sum_{i=1}^{N} k_iS_i(k_i)$$

 

这样对于多维数组$A[N_1][N_2]\dots[N_n]$，只需要实现计算好$N_1+N_2+\dots +N_n$个常数，即可采用上式来快速计算一维编号。

 

  • 无匹配
  • 无匹配
Small_feed 评论 (3)
1
[回复]
Avatar_small
civaget 说:
2023年12月10日 08:27

구글 상위노출 isn't just a ranking—it's a reflection of your commitment to delivering value and a superior online experience.

2
[回复]
Avatar_small
civaget 说:
2023年12月26日 04:19

Discover the world of 무료스포츠중계 - your gateway to sports without costs.

3
[回复]
Avatar_small
civaget 说:
2024年1月14日 04:41

Thank you for the sensible critique. Me & my friend were just preparing to do a little research about this. We got a book from our area library but I think I learned better from this post. I am very glad to see such wonderful info being shared freely out there… เว็บตรง คืนยอดเสีย


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter
Host by is-Programmer.com | Power by Chito 1.3.3 beta | © 2007 LinuxGem | Design by Matthew "Agent Spork" McGee