動態陣列和Linked list的Push back和Sum比較時間
===
### Dynamic Array和Linked list的Push back和Sum比較程式
附註:使用DynamicArray時，需註解Linkedlist部分的code(包含struct linklist)，反之使用Vector時，亦然。

#include<iostream>
#include<vector>
#include <cstdlib> /* 亂數相關函數 */
#include <ctime>   /* 時間相關函數 */
#include <chrono>  // for high_resolution_clock
using namespace std;

struct node
{
  int data;
  node *next;
};

uint64_t powers_of_2[65] = {1,
                2,  4,  8,  16, 32, 64, 128,256,512,1024,
                2048,4096,8192,16384,32768,65536,131072,262144,524288,1048576,
                2097152,4194304,8388608,16777216,33554432,67108864,134217728,268435456,536870912,1073741824,
                2147483648,4294967296,8589934592,17179869184,34359738368,68719476736,137438953472,274877906944,549755813888,1099511627776,
                2199023255552,4398046511104,8796093022208,17592186044416,35184372088832,70368744177664,140737488355328,281474976710656,562949953421312,1125899906842624,
                2251799813685248,4503599627370496,9007199254740992,18014398509481984,36028797018963968,72057594037927936,144115188075855872,288230376151711744,576460752303423488,1152921504606846976,
                2305843009213693952,4611686018427387904,9223372036854775808,18446744073709551615
                };

///Linked list chronos
//std::chrono::nanoseconds  push_back_duration = std::chrono::high_resolution_clock::now() - std::chrono::high_resolution_clock::now();
//std::chrono::nanoseconds  insert_time_duration = std::chrono::high_resolution_clock::now() - std::chrono::high_resolution_clock::now();
//std::chrono::nanoseconds  next_point_duration = std::chrono::high_resolution_clock::now() - std::chrono::high_resolution_clock::now();

///Vector chronos
std::chrono::nanoseconds  vector_push_back_duration = std::chrono::high_resolution_clock::now() - std::chrono::high_resolution_clock::now();


///Linked List

class linked_list
{
private:
    node *head,*tail;
public:
    linked_list()
    {
        head = NULL;
        tail = NULL;
    }

    void add_node(int n)
    {
        ///sum
        //sum+=n;
        
        ///push back duration
        auto start_time = std::chrono::high_resolution_clock::now();
        node *tmp = new node;
        auto end_time = std::chrono::high_resolution_clock::now();


        push_back_duration += (end_time-start_time);


        ///insert data duration
        start_time = std::chrono::high_resolution_clock::now();
        tmp->data = n;
        end_time = std::chrono::high_resolution_clock::now();

        insert_time_duration += (end_time-start_time);

        ///next point duration
        start_time = std::chrono::high_resolution_clock::now();
        tmp->next = NULL;
        end_time = std::chrono::high_resolution_clock::now();

        next_point_duration += (end_time-start_time);

        if(head == NULL)
        {
            head = tmp;
            tail = tmp;
        }
        else
        {
            tail->next = tmp;
            tail = tail->next;
        }
    }
};



int main(){
    int i = 20;

    int times = 0;
    int x;
    
    ///sum
    //uint64_t sum = 0;

///linked list
    linked_list list_a[10];
    

    uint64_t average_push_back_duration = 0;
    uint64_t average_insert_time_duration = 0;
    uint64_t average_next_point_duration = 0;

///Vector
    vector<int> Dynamic_Array[10];

    uint64_t average_vector_push_back_duration = 0;


    uint64_t ncount = powers_of_2[i];


    cout<<i<<"'s power"<<endl;
    cout<<ncount<<endl;

    while(times<1){
        srand( time(NULL) );
        
        ///sum
        //sum = 0;

        //cin>>i;
        ncount = powers_of_2[i];

        while(ncount--){
            //cout<<ncount<<endl;
            x = rand();
            
            ///sum
            //sum+=x;

            ///Vector push_back
            auto start_time = std::chrono::high_resolution_clock::now();
            Dynamic_Array[times].push_back(x);
            auto end_time = std::chrono::high_resolution_clock::now();
            
            vector_push_back_duration += (end_time-start_time);

            ///linked list push_back
            list_a[times].add_node(x);

        }



        ///linked list Print Test
        //cout <<" Test " << times <<":"<<endl;
        //cout << "push_back time: " << push_back_duration.count() << " ns\n";
        //cout << "data_insert time: " << insert_time_duration.count() << " ns\n";
        //cout << "next_pointer time: " << next_point_duration.count() << " ns\n";

        ///Linked List summing
//        average_push_back_duration += push_back_duration.count();
//        average_insert_time_duration += insert_time_duration.count();
//        average_next_point_duration += next_point_duration.count();

        ///Vector Print Test
//        cout <<" Test " << times <<":"<<endl;
//        cout << "push_back time: " << vector_push_back_duration.count() << " ns\n";



        average_vector_push_back_duration += vector_push_back_duration.count();

        times++;
        //cout<<endl;
    }
    cout<<endl<<endl;

    ///cout Linked List average time
    average_push_back_duration = average_push_back_duration/10;
    average_insert_time_duration = average_insert_time_duration/10;
    average_next_point_duration = average_next_point_duration/10;

    cout<<"---------------------"<<endl;
    cout <<" Average Test : " <<endl;
    cout << "Final_push_back time: " << average_push_back_duration << " ns\n";
    cout << "Final_data_insert time: " << average_insert_time_duration << " ns\n";
    cout << "Final_next_pointer time: " << average_next_point_duration << " ns\n";

    ///cout Vector average time
    average_vector_push_back_duration = average_vector_push_back_duration;

    cout<<"---------------------"<<endl;
    cout <<" Average Test : " <<endl;
    cout << "Final_push_back time: " << average_vector_push_back_duration << " ns\n";

}

實驗報告:

1. 實驗結果:
折線圖一代表Dynamic Array和Linked list的push back時間，以毫秒millisecond為單位，測量兩種方式在2的n次方(2^n)個資料執行的時間。
折線圖二則是Dynamic Array和Linked list加總2^n組資料的執行時間。
2^13至2^25的資料皆是做了10次在進行平均，而2^26以上的資料則受限設備只能計算一次。2^30無法計算，而是根據前面的資料推測得出。
根據實驗結果得出，Linked list無論是在Push back或隨機數相加的兩項任務皆較Dynamic Array花費了四倍近五倍的執行時間。我認為出現這類情況的原因是因為，Linked list相比Dynamic Array在新增data時，多了一個讀取pointer的過程，會多花時間。然而，Linked list多花的時間是固定的，若是pushed或sum的區域在陣列中間，而非push back時，由於Dynamic Array的資料位置是連續的，在插入資料時平均會需要動到陣列一半的資料，此時Dynamic Array執行時間便會超過Linked list.

Linked List Push back time verses Dynamic Array Push back time
Graph 1

Linked List Sum time verses Dynamic Array Sum time
Graph 2

---
2. Dynamic Array 和Linked List 程式碼來源
Linked List Code:

Linked List的部分，我參考了下列網站https://hackmd.io/@Zero871015/H12vTu8aX?type=view
Linked list 的概念是每次只給一格空間，用指標把每格空間串聯起來，一個指標接著一個指標。

我建立一個叫做節點node的型別，node有兩個部分 :
一個是當下node的資料data，和一個指向下一個node的指標*next
Add note函數則是負責增加新的節點(node)，但頭(head)和尾(tail)的部分需要另外判斷
這段程式符合上述講的Linked List概念，使用一格空間data來存資料，並使用指標next來連接不同的data。

Vector Code:

Dynamic Array是C++標準函式庫的std::vector，因此是動態陣列

3. 實驗的程式碼:
程式碼放在開頭。
---

4. 心得、疑問、與遇到的困難:
這次作業是比較Linked List和 Dynamic Array之間的時間，在實驗的過程因為較不熟悉計時方面的函數，因此在stack overflow上尋找，在<time.h>和<chrono>兩函數之間比較。同時遇到第一個困難，當陣列數量較小時，測量的秒數小於time函數的顯示標準，因此得出的數值皆是0，而chrono函數的測量單位可測量nanosecond，因此選擇了chrono函數。遇到另一困難chrono函數使用的變數型別是duration型別，而非常用的int, float…等等，這問題也在查找chrono的cpp reference中找到答案。第三個遇到的困難是測試資料太大，常常測試到一半電腦便重開機，之後每次紀錄單筆測資在手動平均將問題解決。
在實驗Linked list和Dynamic 時，我發現Linked list相較於Dynamic Array所用時間較慢了五倍的時間，我平常使用上也大都使用Vector之類的動態陣列，而較不常使用Linked list。我產生了疑問為何Linked list存在並仍然廣泛使用，而不會被Dynamic Array取代。因此查了Linked list和 Dynamic Array之間的特性得知，Linked list和Dynamic Array有幾大特性不同。

| 特性 | 動態陣列 | Linked List |
| -------- | -------- | -------- |
| 連續記憶體空間 | 是 | 可以非連續 |
|型態 | 型別皆需相同| 不一定要相同|
插入/刪除元素 |麻煩，平均會動到一半的陣列 |方便，只需改變前後和自身指標
支援隨機存取|可支援| 可以，但需要在串列上增加功能
可靠度| 高| 低，若是指標斷裂，資料便遺失

---

結論，Dynamic Array和 Linked list在特性上有諸多不同，各有優缺，Linked list的優點不在於新增資料的速度，而是在使用的彈性和功能性上。