平行数组

平行数组是程序设计采用多个数组隐式表示一个以记录（record）为元素的数组。多个数组在同一下标的元素隐式对应于记录的各个域。

例子
例如，可以声明一个数组包含100个名字，另一个数组包含100个年龄（整型），相同下标的元素成对表示一个人：
int  ages[]   = {0,          17,        2,          52,         25};
char *names[] = {"None",     "Mike",    "Billy",    "Tom",      "Stan"};
int  parent[] = {0 /*None*/, 3 /*Tom*/, 1 /*Mike*/, 0 /*None*/, 3 /*Tom*/};

for(i = 1; i <= 4; i++) {
    printf("Name: %s, Age: %d, Parent: %s \n",
           names[i], ages[i], names[parent[i]]);
}
Perl语言:
my %data = (
    first_name   => ['Joe',  'Bob',  'Frank',  'Hans'    ],
    last_name    => ['Smith','Seger','Sinatra','Schultze'],
    height_in_cm => [169,     158,    201,      199      ]);

for $i (0..$#{$data{first_name}}) {
    printf "Name: %s %s\n", $data{first_name}[$i], $data{last_name}[$i];
    printf "Height in CM: %i\n", $data{height_in_cm}[$i];
}
Python语言:
first_names   = ['Joe',  'Bob',  'Frank',  'Hans'    ]
last_names    = ['Smith','Seger','Sinatra','Schultze']
heights_in_cm = [169,     158,    201,      199      ]

for i in range(len(first_names)):
    print "Name: %s %s" % (first_names[i], last_names[i])
    print "Height in CM: %s" % heights_in_cm[i]

# Using zip:
for first_name, last_name, height in zip(first_names, last_names, heights_in_cm):
    print "Name: %s %s" % (first_name, last_name)
    print "Height in CM: %s" % height_in_cm

优点与缺点

优点：
 可用于仅支持基本类型作为数组元素类型的那些编程语言
 易于理解使用
 可能会避免了内存对齐从而节省了内存占用。
 顺序遍历小数组有利于提高cache一致性。
 有利于使用SIMD指令。

缺点：
 使用多个域时不利于cache性能
 增加或删除元素时代价高昂。

 参见 
 链表
 列式数据库

 参考文献 

 Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. . Page 209 of section 10.3: Implementing pointers and objects.


Category:数组