c风格链表和c ++ std :: vector的速度差异很大

Question

从我读过的内容以及我理解内存结构如何工作的方式来看,向量创建了一个数组,其中所有的值都相互对齐,而我在下面放在一起的链表将指向内存中的随机点,其中下一个对象被分配.因此,该代码的向量应该更快.

当我编译下面的代码时,链接列表的运行时间为4秒,而向量在21秒内运行,这是向量的5倍速度增加.

我在这里错过了什么吗？或者有人对此有解释吗？

#include <vector>
#include <iostream>
#include <ctime>

using namespace std;

struct point{
    float t;
    float v;
};

struct pointlist{
    float t;
    float v;
    struct pointlist *next;
};

void fillpoints(std::vector<struct point> &points, struct pointlist *pointlist) {
    int i;

    for (i = 0; i<8;i++) {
        struct point newpoint; // Fill vector
        newpoint.t = (float)i;
        newpoint.v = (float)i/2;
        points.push_back(newpoint);

        pointlist->t = (float)i; // Fill linked list
        pointlist->v = (float)i/2;
        struct pointlist *temppoint = (struct pointlist *)malloc(sizeof(struct pointlist));
        pointlist->next = temppoint;
        pointlist = temppoint;
    }

    struct point newpoint;
    newpoint.t = 0;
    newpoint.v = (float)i/2;
    points.push_back(newpoint);
    pointlist->t = 0;
    pointlist->v = (float)i/2;
    pointlist->next = NULL;
}

float areavec(std::vector<struct point> pointlist) {
    float y1, z1, y2, z2, area;

    area = 0;
    y2 = pointlist[0].t - pointlist[0].v;
    z2 = pointlist[0].t + pointlist[0].v;

    for (unsigned int i = 1; i<pointlist.size();i++) {
        y1 = y2;
        z1 = z2;
        y2 = pointlist[i].t - pointlist[i].v;
        z2 = pointlist[i].t + pointlist[i].v;
        area += (y1*z2) - (y2*z1);
    }
    return area;
}

float arealist(struct pointlist *pointlist) {
    float y1, z1, y2, z2, area;

    area = 0;
    y2 = pointlist->t - pointlist->v;
    z2 = pointlist->t + pointlist->v;

    while (pointlist->next != NULL) {
        y1 = y2;
        z1 = z2;
        y2 = pointlist->next->t - pointlist->next->v;
        z2 = pointlist->next->t + pointlist->next->v;
        area += (y1*z2) - (y2*z1);

        pointlist = pointlist->next;
    }
    return area;
}

void main() {
    int runs = 200000000;
    float a;
    std::vector<struct point> points;
    struct pointlist *pointlist = (struct pointlist *)malloc(sizeof(struct pointlist));

    struct pointlist *test = pointlist;
    fillpoints(points, pointlist);

    clock_t start = clock();
    for (int i=0; i<runs; i++) {
        a = arealist(pointlist);
    }
    cout << "Time: " << (clock()-start)/CLOCKS_PER_SEC << " Area: " << a << endl;

    start = clock();
    for (int i=0; i<runs; i++) {
        a = areavec(points);
    }
    cout << "Time: " << (clock()-start)/CLOCKS_PER_SEC << " Area: " << a << endl;

    cin.get();
}

Answer 1

float areavec(std::vector<struct point> pointlist)

在这里,我将解决这个问题:

float areavec(const std::vector<struct point>& pointlist)

你正在复制矢量200000000次.而对于链表,您只是复制指针.