I'm tackling a exercise which is supposed to exactly benchmark the time complexity of such code.
The data I'm handling is made up of pairs of strings like this hbFvMF,PZLmRb, each string is present two times in the dataset, once on position 1 and once on position 2 . so the first string would point to zvEcqe,hbFvMF for example and the list goes on....
I've been able to produce code which doesn't have much problem sorting these datasets up to 50k pairs, where it takes about 4-5 minutes. 10k gets sorted in a matter of seconds.
The problem is that my code is supposed to handle datasets of up to 5 million pairs. So I'm trying to see what more I can do. I will post my two best attempts, initial one with vectors, which I thought I could upgrade by replacing vector with unsorted_map because of the better time complexity when searching, but to my surprise, there was almost no difference between the two containers when I tested it. I'm not sure if my approach to the problem or the containers I'm choosing are causing the steep sorting times...
Attempt with vectors:
#include <iostream>
#include <fstream>
#include <string>
#include <sstream>
#include <map>
#include <unordered_map>
#include <stdio.h>
#include <vector>
#include <iterator>
#include <utility>
#include <functional>
#include <algorithm>
using namespace std;
template<typename T>
void search_bricks_backwards(string resume, vector<T>& vec, vector<string>& vec2) {
int index = 0;
int temp_index = 0;
while (true) {
if (index == vec.size()) {
vec2.insert(vec2.begin(), vec[temp_index].first);
cout << "end of backward search, exitting..." << endl;
break;
}
if (vec[index].second == resume) {
vec2.insert(vec2.begin(), resume);
resume = vec[index].first;
//vec.erase(vec.begin() + index);
temp_index = index;
index = 0;
}
index++;
}
}
template<typename T>
void search_bricks(string start, vector<T>& vec, vector<string>& vec2) {
int index = 0;
int temp_index = 0;
while (true) {
//cout << "iteration " << index << endl;
if (index == vec.size()) {
vec2.push_back(vec[temp_index].second);
cout << "all forward bricks sorted" << endl;
break;
}
if (vec[index].first == start) {
vec2.push_back(vec[index].first);
start = vec[index].second;
//vec.erase(vec.begin() + index);
temp_index = index;
index = 0;
}
index++;
}
search_bricks_backwards(vec[0].first, vec, vec2);
}
template<typename T>
void search_bricks_recursion(string start, vector<T>& vec, vector<string>& vec2) {
int index = 0;
for (const auto& pair : vec) {
//cout << "iteration " << index << endl;
if (pair.first == start) {
vec2.push_back(start);
cout << "found " << start << " and " << pair.first << endl;
search_bricks(pair.second, vec, vec2);
}
if (index + 1 == vec.size()) {
search_bricks_backwards(start, vec, vec2);
}
index++;
}
}
template<typename T>
void printVectorElements(vector<T>& vec)
{
for (auto i = 0; i < vec.size(); ++i) {
cout << "(" << vec.at(i).first << ","
<< vec.at(i).second << ")" << " ";
}
cout << endl;
}
vector<string> split(string s, string delimiter) {
size_t pos_start = 0, pos_end, delim_len = delimiter.length();
string token;
vector<string> res;
while ((pos_end = s.find(delimiter, pos_start)) != string::npos) {
token = s.substr(pos_start, pos_end - pos_start);
pos_start = pos_end + delim_len;
res.push_back(token);
}
res.push_back(s.substr(pos_start));
return res;
}
unordered_map<string, string> brick_to_map(string const& s)
{
unordered_map<string, string> m;
string key, val;
istringstream iss(s);
while (getline(getline(iss, key, ',') >> ws, val))
m[key] = val;
return m;
}
int main()
{
vector<pair<string, string>> bricks;
vector<string> sorted_bricks;
ifstream inFile;
inFile.open("input-pairs-50K.txt"); //open the input file
stringstream strStream;
strStream << inFile.rdbuf(); //read the file
string str = strStream.str(); //str holds the content of the file
//cout << str << endl;
istringstream iss(str);
for (string line; getline(iss, line); )
{
string delimiter = ",";
string s = line;
vector<string> v = split(s, delimiter);
string s1 = v.at(0);
string s2 = v.at(1);
bricks.push_back(make_pair(s1, s2));
}
search_bricks(bricks[0].second, bricks, sorted_bricks);
//display the results
for (auto i = sorted_bricks.begin(); i != sorted_bricks.end(); ++i)
cout << *i << " ";
}
Attempt with unsorted map:
#include <iostream>
#include <fstream>
#include <string>
#include <sstream>
#include <map>
#include <unordered_map>
#include <stdio.h>
#include <vector>
#include <iterator>
#include <utility>
#include <functional>
#include <algorithm>
using namespace std;
void search_bricks_backwards(string resume, unordered_map<string, string> brick_map, vector<string>& vec2) {
typedef unordered_map<string, string>::value_type map_value_type;
while (true) {
unordered_map<string, string>::const_iterator got = find_if(brick_map.begin(), brick_map.end(), [&resume](const map_value_type& vt)
{ return vt.second == resume; }
);
if (got == brick_map.end()) {
vec2.insert(vec2.begin(), resume);
cout << "end of backward search, exitting..." << endl;
break;
}
//cout << "iteration " << index << endl;
else if (got->second == resume) {
vec2.insert(vec2.begin(), resume);
resume = got->first;
}
}
}
void search_bricks(string start, unordered_map<string, string> brick_map, vector<string>& vec2) {
typedef unordered_map<string, string>::value_type map_value_type;
while (true) {
unordered_map<string, string>::const_iterator got = find_if(brick_map.begin(), brick_map.end(), [&start](const map_value_type& vt)
{ return vt.first == start; }
);
if (got == brick_map.end()) {
vec2.push_back(start);
cout << "all forward bricks sorted" << endl;
break;
}
else if (got->first == start) {
vec2.push_back(start);
//cout << "found " << start << " and " << vec[index].first << endl;
start = got->second;
}
}
auto it = brick_map.begin();
search_bricks_backwards(it->first, brick_map, vec2);
}
template<typename T>
void printVectorElements(vector<T>& vec)
{
for (auto i = 0; i < vec.size(); ++i) {
cout << "(" << vec.at(i).first << ","
<< vec.at(i).second << ")" << " ";
}
cout << endl;
}
vector<string> split(string s, string delimiter) {
size_t pos_start = 0, pos_end, delim_len = delimiter.length();
string token;
vector<string> res;
while ((pos_end = s.find(delimiter, pos_start)) != string::npos) {
token = s.substr(pos_start, pos_end - pos_start);
pos_start = pos_end + delim_len;
res.push_back(token);
}
res.push_back(s.substr(pos_start));
return res;
}
int main()
{
unordered_map<string, string> bricks;
vector<string> sorted_bricks;
ifstream inFile;
inFile.open("input-pairs-50K.txt"); //open the input file
for (string line; getline(inFile, line); )
{
string delimiter = ",";
string s = line;
vector<string> v = split(s, delimiter);
string s1 = v.at(0);
string s2 = v.at(1);
bricks.insert(make_pair(s1, s2));
}
/*for (auto& x : bricks)
std::cout << x.first << "," << x.second << " ";*/
auto it = bricks.begin();
search_bricks(it->second, bricks, sorted_bricks);
// display results
for (auto i = sorted_bricks.begin(); i != sorted_bricks.end(); ++i)
cout << *i << " ";
}
I'm looking to improve the time complexity of my code to be able to process the data more eficiently, if anyone can suggest what to improve in my code or container wise I'd be very thankful.
