计算机科学

首页 > 计算机科学

平行数组

2018-08-27 10:38:58     所属分类:数组

平行数组是程序设计采用多个数组隐式表示一个以记录(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",
           namesi, agesi, namesparenti);
}

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 %sn", $data{first_name}$i, $data{last_name}$i;
    printf "Height in CM: %in", $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_namesi, last_namesi)
    print "Height in CM: %s" % heights_in_cmi

# 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性能
  • 增加或删除元素时代价高昂。

参见

  • 链表
  • Column-oriented DBMS英语Column-oriented DBMS

参考文献

  • Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Page 209 of section 10.3: Implementing pointers and objects.
  • Skeet, Jon. Anti-pattern: parallel collections. 2014-06-03 [2014-10-28]. 

上一篇:多重关连数组
下一篇:数组步长
相关推荐