如果你用过R语言，那么一定用过向量，如果用Python，那么一定用过列表。那么问题来了，这两类数据结构有什么区别呢？
为什么Python的列表，支持存放不同类型的数据，而R语言的向量只能放同一个类型的数据呢？还有，为什么R语言的向量化运算函数(如sum, nchar)速度会显著性高于R的循环呢？
对于下面的R代码，那种循环更好呢？
# loop 1
a <- c()
for (i in 1:1000){
a <- c(a,i)
}
# loop 2
a <- vector(length=1000)
for (i in 1:1000){
a[i] = i
}
要想解答这些问题，就必须得学习一下数组。数组是一种线性表数据结构，他在一段连续内存空间中存储相同大小的元素。这里有两个关键点，第一是线性表，也就是说数组里面的元素只有前后关系，同样属于线性表数据结构的还有链表、队列和栈，与之相反的是非线性表数据结构，例如树和图。
第二是连续内存，且里面的元素大小相同，这样子当知道数组的第一个元素的内存位置时，就可以迅速计算出第n个元素的内存地址，并获取该地址的存储内容。
有利就有弊。由于数组要占用一组连续的内存空间，当你要存储的数据要占据非常大的空间时，就会面临内存中找不到位置的尴尬情形。此外，为了保证数据存储的连续性，那么在你插入和删除数据的时候都要进行额外的数据移动操作，这些操作的时间复杂度是。如果数据已经满了，那么加入新的数据时就需要在内存中申请新的空间，同时将现有数据迁移过去。
尽管如此，数组依旧是最常用的数据结构，毕竟数组和CPU和缓存机制非常契合，在数据处理上效率较高。
在C语言中，数组的声明方式有如下方法:
float averages[200]; //在内存中预留200个位置
char word[] = { 'H', 'e', 'l', 'l', 'o', '!'}; // 让C自动确定数组的大小
char *words[] = {"hello", "world"}; 字符串数组
此外，指针与数组的关系十分密切，一般能用数组下标实现的操作，都能用数组完成。过去的时候，指针操作的速度会快于数组下标操作，但是随着编译器的优化，基本上两者的性能持平了。考虑指针实现的程序理解比较困难，因此更推荐用数组。示例：
int a[10]; //声明一个长度为10的存放整型的数组
int *pa; //声明一个指向整型的指针
pa = &a[0]; // 将数组a的起始地址赋值给指针
//等价于 pa = a;
那么a[i] 等价于 *(pa + i ) , 无论数组a中元素的类型或数组长度是什么，该结论始终成立。 ”指针加1“就意味着pa + 1 指向pa所指向对象的下一个对象。简而言之，一个通过数组和下标实现的表达式可等价地通过指针和偏移量实现。
但是，指针和数组还是有区别的，指针是一个变量，数组名不是变量。在函数定义中，形式参数char s[]; 和char *s 是等价的，这是因为把数组名传递给函数时，实际传递的时该数组的第一个元素的地址。
R语言的向量和Python的列表还不是普通的数组，因为他们的大小可变，同样特点的还有C++的标准库类型vector, 还有Java的ArrayList和Vector类，都支持动态进行扩容。举个C++的例子
#include <vector>
#include <iostream>
using std::cin;
using std::vector;
string word;
vector<string> text;
while (cin >> word){
text
}
当然C语言本身并没有这个功能，所以我就尝试着自己写了一个非常简单的实现，依旧分为两个头文件和C文件。
darray.h如下:
#ifndef _DARRAY_H
#define _DARRAY_H
typedef unsigned int position;
/* define the data struct */
typedef struct _cell cell;
typedef struct _darray darray;
/* define the manipulate function of darray */
darray *dCreate(char *strings[], int ssize);
darray *dInsert(darray *d, position pos, char *string);
darray *dExpand(darray *d, int ssize);
void dDestroy(darray *d);
void dRemove(darray *d, position pos);
void dPrint(darray *d);
#endif
darray.c:
#include <stdio.h>
#include <stdlib.h>
#include "dbg.h"
#include "darray.h"
// 用deleted标注删除，不做实际的搬移操作
enum status {empty, deleted, legitimate };
typedef struct _cell {
enum status info;
char *string ;
} cell;
typedef struct _darray{
int size;
int load;
cell *cells;
} darray;
// 根据初始大小申请内存
darray *dCreate(char *strings[], int ssize)
{
darray *d;
d = malloc(sizeof(darray));
d->size = 2 * ssize;
d->load = 0;
d->cells = calloc(d->size, sizeof(cell));
// initialize the array
int i;
for (i = 0; i < ssize; i++){
d->cells[i].info = legitimate;
d->cells[i].string = strings[i];
d->load ++;
}
debug("i shoule be %d", i);
for (; i < d->size; i++){
d->cells[i].info = empty;
}
return d;
}
//进行扩容
darray *dExpand(darray *d, int ssize)
{
darray *newArray;
newArray = malloc(sizeof(darray));
newArray->size = 2 * ssize;
newArray->cells = calloc(newArray->size, sizeof(cell));
newArray->load = 0;
int i;
int j = 0;
//复制元素
for (i = 0; i < d->size; i++){
if( d->cells[i].info == legitimate){
newArray->cells[j].string = d->cells[i].string;
debug("new arrys cell %d is %s", j, newArray->cells[j].string);
newArray->cells[j].info = legitimate;
newArray->load++ ;
j++ ;
}
}
for (; j < newArray->size; j++){
newArray->cells[j].info = empty;
}
//释放原来的内存
dDestroy(d);
return newArray;
}
//插入操作
darray *dInsert(darray *d, position pos, char *string)
{
if (d->load + 1 > d->size ){
d = dExpand(d, d->size);
}
if (pos > d->size ){
d = dExpand(d, pos);
}
debug("size of darray is %d", d->size);
if ( d->cells[pos].info == deleted ||
d->cells[pos].info == empty){
d->cells[pos].info = legitimate;
d->cells[pos].string = string;
} else{
int i = d->size;
d->cells[i].info = legitimate;
for (; i > pos; i--){
d->cells[i].string = d->cells[i-1].string;
}
d->cells[pos].string = string;
}
return d;
}
//删除操作
void dRemove(darray *d, position pos){
d->cells[pos].info = deleted;
}
//输出元素
void dPrint(darray *d)
{
int i = 0;
for (i = 0; i < d->size; i++){
if ( d->cells[i].info == legitimate)
printf("%d \t %s \n", i, d->cells[i].string);
}
putchar('\n');
}
void dDestroy(darray *d)
{
free(d->cells);
free(d);
}
int main(int argc, char *argv[])
{
darray *test;
char *input[] = {"hello", "my", "world","!"} ;
test = dCreate(input, 4);
dPrint(test);
char *h = "hello";
test = dInsert(test, 10, h);
dPrint(test);
dRemove(test,1);
dPrint(test);
dDestroy(test);
return 0;
}
目前代码还存在一些问题，因为我只是将元素标记了删除，那么后续删除同一个位置时需要向后移动才行。同样插入操作也会存在bug。但是能这样子写代码对之前只能hello world的我已经是很大进步了。
解答开篇: Python的列表中存放的是元素的引用，并非元素本身，因此可以放任意类型的数据，其实和R语言的list更加对应。而R语言的向量则更加接近数组结构。
当你使用a <c()的结果是在内存中申请了一块固定大小的空间。之后每次的a<- c(a, i)的效果就是在内存不断申请新空间，加入元素，因此时间消耗会很明显。所以，事先声明足够大的空间然后进行赋值操作才会比较经济。
当我看C++ Primer(第五版)的vector一节时(P91页)，里面提到，C++里面反而不应该像C，Java那样事先声明元素数目。事先声明元素大小反而会降低效率。
