如果你用過(guò)R語(yǔ)言，那么一定用過(guò)向量，如果用Python，那么一定用過(guò)列表。那么問(wèn)題來(lái)了，這兩類數(shù)據(jù)結(jié)構(gòu)有什么區(qū)別呢？
為什么Python的列表，支持存放不同類型的數(shù)據(jù)，而R語(yǔ)言的向量只能放同一個(gè)類型的數(shù)據(jù)呢？還有，為什么R語(yǔ)言的向量化運(yùn)算函數(shù)(如sum, nchar)速度會(huì)顯著性高于R的循環(huán)呢？
對(duì)于下面的R代碼，那種循環(huán)更好呢？
# 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
}
要想解答這些問(wèn)題，就必須得學(xué)習(xí)一下數(shù)組。數(shù)組是一種線性表數(shù)據(jù)結(jié)構(gòu)，他在一段連續(xù)內(nèi)存空間中存儲(chǔ)相同大小的元素。這里有兩個(gè)關(guān)鍵點(diǎn)，第一是線性表，也就是說(shuō)數(shù)組里面的元素只有前后關(guān)系，同樣屬于線性表數(shù)據(jù)結(jié)構(gòu)的還有鏈表、隊(duì)列和棧，與之相反的是非線性表數(shù)據(jù)結(jié)構(gòu)，例如樹和圖。
第二是連續(xù)內(nèi)存，且里面的元素大小相同，這樣子當(dāng)知道數(shù)組的第一個(gè)元素的內(nèi)存位置時(shí)，就可以迅速計(jì)算出第n個(gè)元素的內(nèi)存地址，并獲取該地址的存儲(chǔ)內(nèi)容。
有利就有弊。由于數(shù)組要占用一組連續(xù)的內(nèi)存空間，當(dāng)你要存儲(chǔ)的數(shù)據(jù)要占據(jù)非常大的空間時(shí)，就會(huì)面臨內(nèi)存中找不到位置的尷尬情形。此外，為了保證數(shù)據(jù)存儲(chǔ)的連續(xù)性，那么在你插入和刪除數(shù)據(jù)的時(shí)候都要進(jìn)行額外的數(shù)據(jù)移動(dòng)操作，這些操作的時(shí)間復(fù)雜度是。如果數(shù)據(jù)已經(jīng)滿了，那么加入新的數(shù)據(jù)時(shí)就需要在內(nèi)存中申請(qǐng)新的空間，同時(shí)將現(xiàn)有數(shù)據(jù)遷移過(guò)去。
盡管如此，數(shù)組依舊是最常用的數(shù)據(jù)結(jié)構(gòu)，畢竟數(shù)組和CPU和緩存機(jī)制非常契合，在數(shù)據(jù)處理上效率較高。
在C語(yǔ)言中，數(shù)組的聲明方式有如下方法:
float averages[200]; //在內(nèi)存中預(yù)留200個(gè)位置
char word[] = { 'H', 'e', 'l', 'l', 'o', '!'}; // 讓C自動(dòng)確定數(shù)組的大小
char *words[] = {"hello", "world"}; 字符串?dāng)?shù)組
此外，指針與數(shù)組的關(guān)系十分密切，一般能用數(shù)組下標(biāo)實(shí)現(xiàn)的操作，都能用數(shù)組完成。過(guò)去的時(shí)候，指針操作的速度會(huì)快于數(shù)組下標(biāo)操作，但是隨著編譯器的優(yōu)化，基本上兩者的性能持平了?？紤]指針實(shí)現(xiàn)的程序理解比較困難，因此更推薦用數(shù)組。示例：
int a[10]; //聲明一個(gè)長(zhǎng)度為10的存放整型的數(shù)組
int *pa; //聲明一個(gè)指向整型的指針
pa = &a[0]; // 將數(shù)組a的起始地址賦值給指針
//等價(jià)于 pa = a;
那么a[i] 等價(jià)于 *(pa + i ) , 無(wú)論數(shù)組a中元素的類型或數(shù)組長(zhǎng)度是什么，該結(jié)論始終成立。 ”指針加1“就意味著pa + 1 指向pa所指向?qū)ο蟮南乱粋€(gè)對(duì)象。簡(jiǎn)而言之，一個(gè)通過(guò)數(shù)組和下標(biāo)實(shí)現(xiàn)的表達(dá)式可等價(jià)地通過(guò)指針和偏移量實(shí)現(xiàn)。
但是，指針和數(shù)組還是有區(qū)別的，指針是一個(gè)變量，數(shù)組名不是變量。在函數(shù)定義中，形式參數(shù)char s[]; 和char *s 是等價(jià)的，這是因?yàn)榘褦?shù)組名傳遞給函數(shù)時(shí)，實(shí)際傳遞的時(shí)該數(shù)組的第一個(gè)元素的地址。
R語(yǔ)言的向量和Python的列表還不是普通的數(shù)組，因?yàn)樗麄兊拇笮】勺?，同樣特點(diǎn)的還有C++的標(biāo)準(zhǔn)庫(kù)類型vector, 還有Java的ArrayList和Vector類，都支持動(dòng)態(tài)進(jìn)行擴(kuò)容。舉個(gè)C++的例子
#include <vector>
#include <iostream>
using std::cin;
using std::vector;
string word;
vector<string> text;
while (cin >> word){
text
}
當(dāng)然C語(yǔ)言本身并沒有這個(gè)功能，所以我就嘗試著自己寫了一個(gè)非常簡(jiǎn)單的實(shí)現(xiàn)，依舊分為兩個(gè)頭文件和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標(biāo)注刪除，不做實(shí)際的搬移操作
enum status {empty, deleted, legitimate };
typedef struct _cell {
enum status info;
char *string ;
} cell;
typedef struct _darray{
int size;
int load;
cell *cells;
} darray;
// 根據(jù)初始大小申請(qǐng)內(nèi)存
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;
}
//進(jìn)行擴(kuò)容
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;
//復(fù)制元素
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;
}
//釋放原來(lái)的內(nèi)存
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;
}
目前代碼還存在一些問(wèn)題，因?yàn)槲抑皇菍⒃貥?biāo)記了刪除，那么后續(xù)刪除同一個(gè)位置時(shí)需要向后移動(dòng)才行。同樣插入操作也會(huì)存在bug。但是能這樣子寫代碼對(duì)之前只能hello world的我已經(jīng)是很大進(jìn)步了。
解答開篇: Python的列表中存放的是元素的引用，并非元素本身，因此可以放任意類型的數(shù)據(jù)，其實(shí)和R語(yǔ)言的list更加對(duì)應(yīng)。而R語(yǔ)言的向量則更加接近數(shù)組結(jié)構(gòu)。
當(dāng)你使用a <c()的結(jié)果是在內(nèi)存中申請(qǐng)了一塊固定大小的空間。之后每次的a<- c(a, i)的效果就是在內(nèi)存不斷申請(qǐng)新空間，加入元素，因此時(shí)間消耗會(huì)很明顯。所以，事先聲明足夠大的空間然后進(jìn)行賦值操作才會(huì)比較經(jīng)濟(jì)。
當(dāng)我看C++ Primer(第五版)的vector一節(jié)時(shí)(P91頁(yè))，里面提到，C++里面反而不應(yīng)該像C，Java那樣事先聲明元素?cái)?shù)目。事先聲明元素大小反而會(huì)降低效率。
