Question

Language: C++

Conduct an evaluation of the performance of STL containers (vector, list, set, unordered_set) in inserting and finding elements, with a relatively large data set. What you'll be measuring is the execution time. Obviously it's dependent on the speed of the computer one uses, so what matters is the relative speed (relative to the vector's speed in percentage)

1. create a vector of 100,000 elements of integers, with the values initially set as 1~100,000, in this order.
2. randomize the ordering of these values so they are shuffled
3. measure the time of inserting all elements of this vector into another empty vector, list, set, and unordered_set, at the end of the container
   • that is, the time of populating 100K numbers in the 4 containers, respectively (4 resultant time durations)
   • you can write a universal function that does inserting at the iterator position returned by c.end(), where c is the container in question
4. do the same for the 4 containers (also from the empty state), but inserting elements at the beginning of the container (inserting at .begin())
5. with all containers properly populated, measure the time to find each value of (1~10,000, that's 10K) in vector, list, set, and unordered_set
   • that is, the time of finding all 10K numbers in the 4 containers, respectively (4 resultant time durations)
   • for vector/list, use the std::find() algorithm; for set/unordered_set, use the member function .find()
6. when reporting your results, please also output the percentage relative to data for the vector

Answer 1

Summary :

As part of the solution provided following (i) Notes , (ii) Code & (iii) Output

Notes :

Implemented function InsertAt() which accepts the initial vector and the stl object (set, vector, list or uset ) & insertAtBegin to inserts the 100k elements and prints the time taken .

Initially vector is inserted with 1-100k and later shuffled using 2 random numbers generated for 50k times and swapped the elements at those random indices. Next utilizing the function insertAt() all these shuffled elements are inserted into the respective stl objects. finally using the find() functions , search and print the time elapsed for each of the operations.

#################### Code ######################

#include <iostream>
#include <vector>
#include <iomanip>
#include <set>
#include <stdlib.h>
#include <time.h>
#include <chrono>
#include <list>
#include<unordered_set>
#include <typeinfo>
#include <algorithm>

#define TOTAL_ELEMENTS 100000
#define SEARCH_NUM 10000

using namespace std;

// Function to insert given elements using flag insertAtBegin 
template <class T>
void insertAt( vector<int> input_vect , T &stlObj , bool insertAtBegin )
{
        string str ;
        
        auto stime = chrono::steady_clock::now();
        
        if ( insertAtBegin )
        {
                str = "begin";
                for (auto it = input_vect.begin(); it != input_vect.end(); ++it) 
                        auto itr = stlObj.insert( stlObj.begin(), *it );
        }else 
        {
                str = "end";
                for (auto it = input_vect.begin(); it != input_vect.end(); ++it) 
                        auto itr = stlObj.insert( stlObj.end(), *it );
        }
        
        auto etime = chrono::steady_clock::now();
        
        //cout.precision(dbl::max_digits10);
        cout << " Insert at " << str  << "  for  type " << typeid(stlObj).name() << " time - " << fixed 
        << std::setprecision (15) <<  chrono::duration_cast<chrono::nanoseconds>(etime - stime ).count() << " nano sec \n";
        
}


int main()
{
        srand (time(NULL));
        
        vector<int> init_vect ;
        
        auto stime = chrono::steady_clock::now();

        for( int i=1; i <= TOTAL_ELEMENTS ; i++ )
                init_vect.insert(init_vect.end(),i);
        

        auto etime = chrono::steady_clock::now();
        
        
        cout << " Initial Vector creation time - " << fixed << std::setprecision (15) << chrono::duration_cast<chrono::nanoseconds>(etime - stime ).count() << " nano sec \n";
        
        // Shuffle the Vector elements 
        
        stime = chrono::steady_clock::now();

        int idx1 , idx2 , temp;
        for( int j = 0 ; j < TOTAL_ELEMENTS/2 ; j++ )
        {
                idx1 =  rand() % TOTAL_ELEMENTS  ;
                idx2 =  rand() % TOTAL_ELEMENTS  ;
                if ( idx1 != idx2 )
                {
                        temp = init_vect[idx1] ;
                        init_vect[idx1] = init_vect[idx2];
                        init_vect[idx2] = temp;
                }
        }

        etime = chrono::steady_clock::now();
        
        // Calculate the delta between end and start time and print with precision 15 
        
        cout << " Shuffling Vector time - " << fixed << std::setprecision (15) << chrono::duration_cast<chrono::nanoseconds>(etime - stime ).count() << " nano sec \n";
        
        // Insert at the begin for all stl objects 
        vector<int> vect1 ;
        insertAt(init_vect, vect1 ,true);
        
        set<int> set1 ;
        insertAt(init_vect, set1 , true );
        
        list<int> list1 ;
        insertAt(init_vect, list1 , true );
        
        unordered_set<int> uset1 ;
        insertAt(init_vect, uset1 , true );
        
        cout << "\n\n";
        // Insert at the end for all stl objects 
        vector<int> vect2 ;
        insertAt(init_vect, vect2 ,false);
        
        set<int> set2 ;
        insertAt(init_vect, set2 , false );
        
        list<int> list2 ;
        insertAt(init_vect, list2 , false );
        
        unordered_set<int> uset2 ;
        insertAt(init_vect, uset2 , false );
        
        cout << "\n\n";
        
        // find 1-10k elements in each of the stl 

        stime = chrono::steady_clock::now();
        for( int i = 1 ; i <= SEARCH_NUM ; i++ )
                auto it = find(vect1.begin(), vect1.end(), i); 
        etime = chrono::steady_clock::now();
        
        
        cout << " Searching elements in Vector1 time - " << chrono::duration_cast<chrono::nanoseconds>(etime - stime ).count() << " nano sec \n";
        
        stime = chrono::steady_clock::now();
        for( int i = 1 ; i <= SEARCH_NUM ; i++ )
                auto it = find(vect2.begin(), vect2.end(), i); 
        etime = chrono::steady_clock::now();
        
        
        cout << " Searching elements in Vector2 time - " << chrono::duration_cast<chrono::nanoseconds>(etime - stime ).count() << " nano sec \n";

        stime = chrono::steady_clock::now();
        for( int i = 1 ; i <= SEARCH_NUM ; i++ )
                auto it = find(list1.begin(), list1.end(), i); 
        etime = chrono::steady_clock::now();
        
        
        cout << " Searching elements in List1 time - " << chrono::duration_cast<chrono::nanoseconds>(etime - stime ).count() << " nano sec \n";
        
        stime = chrono::steady_clock::now();
        for( int i = 1 ; i <= SEARCH_NUM ; i++ )
                auto it = find(list2.begin(), list2.end(), i); 
        etime = chrono::steady_clock::now();
        
        
        cout << " Searching elements in List2 time - " << chrono::duration_cast<chrono::nanoseconds>(etime - stime ).count() << " nano sec \n";

        stime = chrono::steady_clock::now();
        for( int i = 1 ; i <= SEARCH_NUM ; i++ )
                auto it = set1.find(i); 
        etime = chrono::steady_clock::now();
        
        
        cout << " Searching elements in Set1 time - " << chrono::duration_cast<chrono::nanoseconds>(etime - stime ).count() << " nano sec \n";


        stime = chrono::steady_clock::now();
        for( int i = 1 ; i <= SEARCH_NUM ; i++ )
                auto it = set2.find(i); 
        etime = chrono::steady_clock::now();
        
        
        cout << " Searching elements in Set2 time - " << chrono::duration_cast<chrono::nanoseconds>(etime - stime ).count() << " nano sec \n";


        stime = chrono::steady_clock::now();
        for( int i = 1 ; i <= SEARCH_NUM ; i++ )
                auto it = uset1.find(i); 
        etime = chrono::steady_clock::now();
        
        
        cout << " Searching elements in Unordered Set1 time - " << chrono::duration_cast<chrono::nanoseconds>(etime - stime ).count() << " nano sec \n";


        stime = chrono::steady_clock::now();
        for( int i = 1 ; i <= SEARCH_NUM ; i++ )
                auto it = uset2.find(i); 
        etime = chrono::steady_clock::now();
        
        
        cout << " Searching elements in Unordered Set2 time - " << chrono::duration_cast<chrono::nanoseconds>(etime - stime ).count() << " nano sec \n";

        cout <<"\n";
        
}
        

######################output ########################