C++

Forum

 
Reducing processing time of two maps

ajlahmed (21)
Hi everyone

I have two maps: Pkt_creatingmap and Pkt_arrivalmap. The number of elements in (Pkt_creatingmap) map is much more than the number of elements in (Pkt_arrivalmap) map [i.e.: total number of elements in Pkt_creatingmap about 650000 elements and total number of element in Pkt_arrivalmap about 72000 elements].
I want to compare the key IDs (firsts) in (Pkt_creatingmap) map and (Pkt_arrivalmap) map. If it is equal then subtract the values of key IDs (seconds) and store the result in list (TotalTrafficETED).
I write below code to do this task, However it takes a long time to accomplish (i.e.: it is time consuming). Not all elements in (Pkt_creatingmap) map are needed in this process. The process of subtraction depends only on the elements of (Pkt_arrivalmap) map.
Is there method to reduce the running time? (i.e.: can the iterator of (Pkt_creatingmap) map end at the end location of (Pkt_arrivalmap) map iterator?
Hope my question is clear.
Anyone can help me please ..
[
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
 
#include <iostream>
#include <fstream>
#include <string>
#include <stdint.h>
#include <sstream>
#include <cmath>
#include <map>
#include <iterator>
#include <list>
using namespace std;

int main()
{
 map<double_t,double_t> Pkt_arrivalmap; 
 map<double_t,double_t> Pkt_creatingmap;  
 list<double_t> TotalTrafficETED;
int pos,pos2,pos3;
double_t ArrivingID,CreatingID,ArrivingTime,CreatingTime,Pkt_ETED,TTETED;
string line,search,word1="ns",word2="Pkt_create", word3="Pkt_recv";   
ifstream inf; 
inf.open ("123.txt");  
if (inf.is_open()) 
{   

	while (getline(inf,line))  
	{       
	    
   		if (line.find("Pkt_recv") != string::npos)   
		{  
		pos=line.find(word1); 
		pos3=line.find(word3);
		line.replace(pos,word1.length(),"  "); // to remove "ns"
		line.replace(pos3,word3.length(),"  "); // to remove "Pkt_recv" 
        istringstream iss (line);
        double_t column1;
        //double_t column3;
        double_t column2;
        iss >> column1 >> column2;
        //cout << column1 <<"  "<< column2 <<"  "<< " "<< endl;
	    Pkt_arrivalmap[column1]=column2;
	   
	    }

	 

}	    


inf.close();
}

else cout << "Unable to open file inf \n";	    
for (std::map<double_t,double_t>::iterator it = Pkt_arrivalmap.begin(); it != Pkt_arrivalmap.end(); it++)
	    {  
	     cout << "Arrival info." <<"  "<< it->first <<"  "<< it->second << "  "<< Pkt_arrivalmap.size()<< endl;
	    }	
	

inf.open ("123.txt");  
if (inf.is_open())  
{   

	while (getline(inf,line))   
	{       
	    
   		if (line.find("Pkt_create") != string::npos)    
		{  
		pos=line.find(word1); 
		pos2=line.find(word2);
		line.replace(pos,word1.length(),"  "); // to remove "ns"
		line.replace(pos2,word2.length(),"  "); // to remove "Pkt_create" 
        istringstream iss (line);
        double_t column1;
        //double_t column3;
        double_t column2;
        iss >> column1 >> column2;
        //cout << column1 <<"  "<< column2 <<"  "<< " "<< endl;
	    Pkt_creatingmap[column1]=column2;
	   
	    }	 
}	    

inf.close();
}

else cout << "Unable to open file inf \n";
for (std::map<double_t,double_t>::iterator it = Pkt_creatingmap.begin(); it != Pkt_creatingmap.end(); it++)
	    {  
	     cout << "Creating info." <<"  "<< it->first <<"  "<< it->second << "  "<< Pkt_creatingmap.size()<< endl;
	    }	

for (std::map<double_t,double_t>::iterator it = Pkt_arrivalmap.begin(); it != Pkt_arrivalmap.end(); it++)
	    { 
		  
         ArrivingID =it->first;
         ArrivingTime=it->second;
         //cout << "Ahmed" <<"  "<< ArrivingID <<endl; 	
         for (std::map<double_t,double_t>::iterator it = Pkt_creatingmap.begin(); it != Pkt_creatingmap.end(); it++)
          { 
			CreatingID=it->first;
			CreatingTime=it->second;
			if (ArrivingID==CreatingID)
			{ 
			  Pkt_ETED=(ArrivingTime-CreatingTime)/1000000000;
			  TotalTrafficETED.push_back(Pkt_ETED);
			  Pkt_creatingmap.erase(it->first);
			  Pkt_arrivalmap.erase(it->first);
			  cout <<"Pkt_ID:"<<CreatingID<<","<<"Pkt_ETED:"<<Pkt_ETED<<endl;
		    } 
		  }
	    }
for (std::list<double_t>::iterator it = TotalTrafficETED.begin(); it != TotalTrafficETED.end(); it++)
{
    TTETED+=*it/TotalTrafficETED.size();
}
    cout << "Total Traffic ETED" << "  "<< TTETED << endl;

return 0;



}



]
Put the code you need help with here.
[/code]
Last edited on
JLBorges (13770)
> map<double_t,double_t>

Even assuming that NaNs are not a concern, using a floating point type as the key for std::map is not a good idea.

Everywhere the standard library uses the Compare concept, uniqueness is determined by using the equivalence relation. In imprecise terms, two objects a and b are considered equivalent (not unique) if neither compares less than the other: !comp(a, b) && !comp(b, a).
http://en.cppreference.com/w/cpp/container/map

Otherwise, with something along these lines, performance should not be a problem.
Note: key type is not a floating point type.
Caveat: untested. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
 
#include <iostream>
#include <chrono>
#include <ctime>
#include <map>
#include <vector>
#include <random>
#include <algorithm>
#include <iomanip>
#include <numeric>
#include <iterator>

struct timer
{
    std::string label ;
    std::chrono::steady_clock::time_point start_c = std::chrono::steady_clock::now() ;
    std::clock_t start_p = std::clock() ;

    explicit timer( const std::string& label ) : label(label) {}

    ~timer()
    {
        const auto end_p = std::clock() ;
        const auto end_c = std::chrono::steady_clock::now() ;
        using namespace std::chrono ;
        std::cout << label << "\n--------------------\n"
                  << duration_cast<milliseconds>( end_c - start_c ).count() << " milliseconds elapsed\n"
                  << ( end_p - start_p ) * 1000.0 / CLOCKS_PER_SEC << " milliseconds processor\n" ;
    }
};

int main()
{
    const std::size_t BIG_N = 1'000'000 ; // one million entries in the big map
    const std::size_t SMALL_N = BIG_N / 10 ; // one hundred thousand entries in the small map

    std::map< int, double > big_map ;
    std::map< int, double > small_map ;

    /////////// create test data ///////////////
    static int ids[BIG_N] ;
    std::iota( ids, ids+BIG_N, 0 ) ;

    static double times[BIG_N] ;
    std::iota( ids, ids+BIG_N, 1000000 ) ;
    for( double& v : times ) v /= 1000 ;

    {
        std::mt19937 rng( std::time(nullptr) ) ;
        std::shuffle( ids, ids+BIG_N, rng ) ;
        std::shuffle( times, times+BIG_N, rng ) ;
    }

    for( std::size_t i = 0 ; i < BIG_N ; ++i ) big_map.emplace( ids[i], times[i] ) ;
    for( std::size_t i = 0 ; i < SMALL_N ; ++i ) small_map.emplace( ids[i], times[i] + i/10000.0 ) ;
    ///////////////////////////////////////////////////

    std::vector<int> traffic ;

    {
        timer t( "compare ids etc." ) ;

        auto small_map_iter = small_map.begin() ;
        auto small_map_end = small_map.end() ;

        const int lowest_key = small_map_iter->first ;
        // http://en.cppreference.com/w/cpp/container/map/lower_bound
        auto big_map_iter = big_map.lower_bound(lowest_key) ;
        auto big_map_end = big_map.end() ;

        // customised version adapted from std::set_intersection
        // see: http://en.cppreference.com/w/cpp/algorithm/set_intersection
        while( small_map_iter != small_map_end && big_map_iter != big_map_end )
        {
            if( small_map_iter->first < big_map_iter->first ) ++small_map_iter;
            else
            {
                if( small_map_iter->first == big_map_iter->first )
                {
                    traffic.push_back( small_map_iter->second - big_map_iter->second ) ;
                    small_map_iter = small_map.erase(small_map_iter) ;
                    big_map_iter = big_map.erase(big_map_iter) ;
                }
                else ++big_map_iter;
            }
        }
    }

    double ttted = 0.0 ;
    for( double v : traffic ) ttted += v ;
    std::cout << "\ntrafic size: " << traffic.size() << "  ttted: " << ttted << '\n' ;
}

193 milliseconds elapsed
190 milliseconds processor

http://coliru.stacked-crooked.com/a/eaa63b0867ea48ef
ajlahmed (21)
Thanks for your reply, Fantastic, I think it will work fast. Here it is the correct code:

But now I have this issue when compile the program using g++ ubuntu. The program object on using auto.

test.cpp:99:1: warning: ‘auto’ changes meaning in C++11; please remove it [-Wc++0x-compat]
auto Pkt_arrivalmap_it = Pkt_arrivalmap.begin();


I use g++ -Wall -o test test.cpp to compile the program.

Correct code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
 
#include <iostream>
#include <fstream>
#include <string>
#include <stdint.h>
#include <sstream>
#include <cmath>
#include <map>
#include <iterator>
#include <list>
using namespace std;

int main()
{
 std::map<int,double_t> Pkt_arrivalmap; // identify the map that contain the arrival information of packets.
 std::map<int,double_t> Pkt_creatingmap; // identify the map that contain the creating information of packets. 
 std::list<double_t> TotalTrafficETED;
int pos,pos2,pos3;
double_t ArrivingID,CreatingID,ArrivingTime,CreatingTime,Pkt_ETED,TTETED=0;
string line,search,word1="ns",word2="Pkt_create", word3="Pkt_recv";  // create an object from string use to read each line in file. 
ifstream inf; // create an object from class of input file stream for reading only

//// to store columns values of 123.txt file (receiving) into variables, then store variables in container arrival map:
// search each line of file 123.txt on Pkt_create and print this line   (okay)

inf.open ("123.txt");  // open file “123.txt” for reading
if (inf.is_open())  // condition to check if it is possible to open file or not. (if it exist), then open it and do following prcess.
{   

	while (getline(inf,line)) // loop continue until reaching the end of file.   
	{       
	    
   		if (line.find("Pkt_recv") != string::npos)   // search on "Pkt_recv" each line 
		{  
		pos=line.find(word1); // take the length of "ns" in string line.
		pos3=line.find(word3);// take the length of "Pkt_recv" in string line.
		line.replace(pos,word1.length(),"  "); // to remove "ns"
		line.replace(pos3,word3.length(),"  "); // to remove "Pkt_recv" 
        istringstream iss (line);
        double_t column1;
        //double_t column3;
        double_t column2;
        iss >> column1 >> column2;
        //cout << column1 <<"  "<< column2 <<"  "<< " "<< endl;
	    Pkt_arrivalmap[column1]=column2;
	   
	    }

	 

}	    


inf.close();
}

else cout << "Unable to open file inf \n";	    
/*for (std::map<int,double_t>::iterator it = Pkt_arrivalmap.begin(); it != Pkt_arrivalmap.end(); it++)
	    {  
	     cout << "Arrival info." <<"  "<< it->first <<"  "<< it->second << "  "<< Pkt_arrivalmap.size()<< endl;
	    }*/	
	
//// to store columns values of 123.txt file (creating) into variables, then store variables in container creatingmap:
// search each line of file 123.txt on Pkt_create and print this line   (okay)

inf.open ("123.txt");  // open file “123.txt” for reading
if (inf.is_open())  // condition to check if it is possible to open file or not. (if it exist), then open it and do following prcess.
{   

	while (getline(inf,line)) // loop continue until reaching the end of file.   
	{       
	    
   		if (line.find("Pkt_create") != string::npos)   // search on "Pkt_create" each line 
		{  
		pos=line.find(word1); // take the length of "ns" in string line.
		pos2=line.find(word2);// take the length of "Pkt_create" in string line.
		line.replace(pos,word1.length(),"  "); // to remove "ns"
		line.replace(pos2,word2.length(),"  "); // to remove "Pkt_create" 
        istringstream iss (line);
        double_t column1;
        //double_t column3;
        double_t column2;
        iss >> column1 >> column2;
        //cout << column1 <<"  "<< column2 <<"  "<< " "<< endl;
	    Pkt_creatingmap[column1]=column2;
	   
	    }	 
}	    

inf.close();
}
else cout << "Unable to open file inf \n";

for (std::map<int,double_t>::iterator it = Pkt_creatingmap.begin(); it != Pkt_creatingmap.end(); it++)
	    {  
	     cout << "Creating info." <<"  "<< it->first <<"  "<< it->second << "  "<< Pkt_creatingmap.size()<< endl;
	    }	

////////////////////////////////////////
auto Pkt_arrivalmap_it = Pkt_arrivalmap.begin();
auto Pkt_arrivalmap_end = Pkt_arrivalmap.end();
const int lowest_key=Pkt_arrivalmap_it->first;
auto Pkt_creatingmap_it = Pkt_creatingmap.lower_bound(lowest_key);
auto Pkt_creatingmap_end = Pkt_creatingmap.end();

while (Pkt_arrivalmap_it != Pkt_arrivalmap_end && Pkt_creatingmap_it != Pkt_creatingmap_end)
{
	if (Pkt_arrivalmap_it ->first < Pkt_creatingmap_it ->first)
	  ++ Pkt_arrivalmap_it;
	else
	   if (Pkt_arrivalmap_it ->first == Pkt_creatingmap_it ->first)
	   {
	   TotalTrafficETED.push_back(Pkt_arrivalmap_it ->second - Pkt_creatingmap_it ->second);
       Pkt_arrivalmap_it=Pkt_arrivalmap.erase(Pkt_arrivalmap_it);
       Pkt_creatingmap_it = Pkt_creatingmap.erase(Pkt_creatingmap_it);
	   }
	   else ++Pkt_creatingmap_it;
		   
}	

/////////////////////////////////////////


for (std::list<double_t>::iterator it = TotalTrafficETED.begin(); it != TotalTrafficETED.end(); it++)
{
    TTETED+=(*it/TotalTrafficETED.size())/1000000000;
}
    cout << "Total Traffic ETED" << "  "<< TTETED <<"Sec."<< endl;
return 0;
}







Last edited on
JLBorges (13770)
> I use g++ -Wall -o test test.cpp to compile the program.

Use g++ -std=c++14 -Wall -Wextra -pedantic-errors -O3 -o test test.cpp

-O3 - optimise
-std=c++14 - the current standard for C++
-pedantic-errors - the International Standard, not your home grown GNU dialect


> std::list<double_t> TotalTrafficETED;

There is no good reason to use std::list<> for this. Replace with std::vector<>
ajlahmed (21)
I appreciate too much your assistance....
Thanks again for your notification
Regards
Topic archived. No new replies allowed.