【謠言】指針比數組速度快？指針比數組速度慢？

• 2022 年 4 月 2 日
• 筆記
• C++語言

最近總是聽說各類說法，例如數組的速度比指針快，或是指針的速度比數組快。事實上，這兩種的速度是基本一致的。

關於鏈表的兩種實現方式，經過測試，平均運行時間都在0.17s左右
剛才測得的一些數據：

• 鏈表 指針版
  0.1932
  0.1551
  0.1618
  0.1598
  0.2269
  平均0.1793
• 鏈表 數組版
  0.1513
  0.1901
  0.1651
  0.1615
  0.1852
  平均0.1706

實驗數據存在誤差，可以認定，數組和指針的運行時間基本相同。
至於其內部原理，我想說，數組本質就是指針，不理解的可以看看我之前寫過的文章，即：

p[i]=*(p+i)

使用數組的lst[p].next，尋址的時候需要使用一次指針，而p->next也是一次指針，效率相同。

最後附上測試代碼：
指針版

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
struct List{
	int val;
	struct List *next;
	List(){
		val=0;next=NULL;
	}
};
struct List *head;
void insert(){
	struct List *p=head;
	while(p->next!=NULL)p=p->next;
	p->next=new List;
}
int main(){
	head=new List;
	for(int i=1;i<=N;i++)insert();
	return 0;
}

數組版

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
struct List{
	int val;
	int next;
}lst[2*N];
int idx=1;
int head=1;
void insert(){
	int p=head;
	while(lst[p].next!=0)p=lst[p].next;
	lst[p].next=++idx;
	lst[idx].val=0;lst[idx].next=0;
}
int main(){
	lst[head].val=0;
	lst[head].next=0;
	for(int i=1;i<=N;i++)insert();
	return 0;
}