So I had a similar problem to this:
Although it was already answered, I provided a different solution on that thread if anyone else came looking for something similar.
If you don't feel like reading through it, the long and short is I have a large data set (850k records) in an Access table that needs to be updated. In my company, we receive new data from a partner in a .xlsx file and need to update said Access database from this file. The unfortunate part is the file sent to us is the entire 850k set with additions and updates (NO DELETIONS). Import tools and macros in Access and Excel take on the order of 10-15 minutes for the entire comparison and import. My solution was to save previously received .xlsx files as .txt files and then compare them to new files using the std::unordered_map from the C++ STL to produce delta files. Then query the delta files for update and upload instead of using the entire data set. In short, compare last week's .xlsx file to this week's .xlsx file for the delta (about 1k records), then write update and insert queries (queries not written yet) for those 1000 or so updates/inserts instead of comparing all 850k records.
The structure of the files are like this:
Col1\tCol2\tCol3\tCol4\tCol5\tCol6\n <-----this is a header
string1\tstring2\tstring3\tstring4\tstring5\tstring6\n
string1\tstring2\tstring3\tstring4\tstring5\tstring6\n
string1\tstring2\tstring3\tstring4\tstring5\tstring6\n
....
//Through 850k rows//
It's important to note that Col1 in each row is a unique identifier. It's a string of numbers followed by a terminating "A" character. For example 0000001A.
1. First Attempt
My first attempt at this used the I/O stream, a single std::unordered_map with string data only, and the first '\t' character and '\n' character as delimiters as can be seen in the thread I linked above. Comparing the input files and writing the outputs took about 5 seconds.
2. Second Attempt
I made my second attempt after seeing a YouTube lecture on Robin Hood hashing, so I researched it a little and stumbled on this.
https://probablydance.com/2017/02/26/i-wrote-the-fastest-hashtable/
I'm not even going to attempt to create a faster hash table. This hashtable is implemented the same as the std::unordered_map, so I downloaded it and imported it to see how much faster it was. You can see this in my code below as #include "RobinHood.h" (I renamed the file so I would recognize it but to be 100% clear, I take NO CREDIT for any of that hash). Then its implementation (with integer instead of string):
ska::flat_hash_map<int, std::string> hashMap1;
ska::flat_hash_map<int, std::string>::iterator it;
This cut the comparison time in half. Down to 2.4 seconds.
3. Third Attempt
In my third attempt, I decided I would try to exploit the numbers in Col1 as a key because integer searching of a hash table is much faster than string searching. I tried a couple of string conversions using the std library but, it seemed that the most efficient conversion for this application was the atoi() function from <cstdlib>. In my code below, you'll see it in the CreateFileHash() function: int t_key{atoi(key.c_str())};
This cut my time further down to 1.75 seconds.
4. Fourth Attempt
Now I decided I could probably speed this up, just a bit more. I thought, what would happen if I used a second data structure to store the second file and read the two files into memory in parallel, then compared the data structures instead of comparing the hash table with the I/O stream on the fly? How much time could I save?
#include <iostream>
#include <fstream>
#include <iomanip>
#include <string>
#include <iterator>
#include <cstdlib>
//#include <unordered_map> -removed, used the ska::flat_hash_map
#include "RobinHood.h" //I renamed the ska robin hood hashing library to "RobinHood.h" so I would remember what it was.
#include <thread>
void OpenFiles(std::ifstream& f_in1, std::ifstream& f_in2, std::ofstream& f_out1, std::ofstream& f_out2, std::ofstream& f_out3);
void Get_Line_Data(std::ifstream& f_in, std::string& key, std::string& s_data);
void CreateFileVector(std::ifstream& f_in, std::vector<std::pair<int, std::string>> &f_vec, std::string& key, std::string& s_data);
void CreateFileHash(std::ifstream& f_in, ska::flat_hash_map<int, std::string> &hashMap1, ska::flat_hash_map<int, std::string>::iterator &it, std::string &key, std::string& s_data);
void printFileDivider(std::ofstream& fout, const int width);
int main(int argc, char* argv[])
{
const int width{81};
int newRecordIndex{1};
int changedRecordIndex{1};
std::string key1;
std::string key2;
std::string wholeLine1;
std::string wholeLine2;
std::vector<std::pair<int, std::string>> vec;
//robin hood hash map. interfaces just like std::unordered_map
ska::flat_hash_map<int, std::string> hashMap1;
ska::flat_hash_map<int, std::string>::iterator it;
std::ifstream fin1; //in files
std::ifstream fin2;
std::ofstream fout1; //out files
std::ofstream fout2;
std::ofstream fout3;
OpenFiles(fin1, fin2, fout1, fout2, fout3);
//skip the header
fin1.ignore(80, '\n');
//
std::thread t1(CreateFileHash, std::ref(fin1), std::ref(hashMap1), std::ref(it), std::ref(key1), std::ref(wholeLine1));
//skip the header
fin2.ignore(80, '\n');
std::thread t2(CreateFileVector, std::ref(fin2), std::ref(vec), std::ref(key2), std::ref(wholeLine2));
//closing threads and files
t2.join();
fin2.close();
t1.join();
fin1.close();
//put the header in the output files
fout2 << "COL1\t" << "COL2\t" << "COL3\t" << "COL4\t" << "COL5\t" << "COL6\n";
fout3 << "COL1\t" << "COL2\t" << "COL3\t" << "COL4\t" << "COL5\t" << "COL6\n";
//loop to compare the data structures
for(auto v_it = vec.begin(); v_it != vec.end(); ++v_it)
{
//look up the key1 data from the vector in the key2 data from hash map
it = hashMap1.find(v_it->first);
if(it != hashMap1.end()) //if the key is found compare the data
{
if(it->second != v_it->second)
{
//print the result to the changed record file. Don't forget to put the 'A' back in the string
printFileDivider(fout1, width);
fout1 << changedRecordIndex << ". CHANGED RECORD\n";
fout1 << "Old Record" << "\t" << it->first << "A" << it->second << "\n";
fout1 << "New Record" << "\t" << v_it->first << "A" << v_it->second << "\n";
printFileDivider(fout1, width);
fout1 << "\n";
//print the new record to the update file. Don't forget to put the 'A' back in the string
fout2 << v_it->first << "A" << v_it->second << "\n";
++changedRecordIndex;
}
}
else //if the key is not found - print the new record to the upload file
{
fout3 << v_it->first << "A" << v_it->second << "\n";
++newRecordIndex;
}
}
fout1.close();
fout2.close();
fout3.close();
return 0;
}
void OpenFiles(std::ifstream& f_in1, std::ifstream& f_in2, std::ofstream& f_out1, std::ofstream& f_out2, std::ofstream& f_out3)
{
f_in1.open("OldFile.txt"); //the old input file
f_in2.open("NewFile.txt"); //the new input file
f_out1.open("Changed Records.txt");
f_out2.open("Update.txt");
f_out3.open("Upload.txt");
}
void Get_Line_Data(std::ifstream& f_in, std::string& key, std::string& s_data)
{
getline(f_in, key, 'A');
getline(f_in, s_data, '\n');
}
void CreateFileVector(std::ifstream& f_in, std::vector<std::pair<int, std::string>> &f_vec, std::string& key, std::string& s_data) //
{
while(f_in)
{
if(f_in.eof())
break;
Get_Line_Data(f_in, key, s_data);
int t_key{atoi(key.c_str())};
f_vec.push_back(make_pair(t_key, s_data));
}
}
//Creates the hash table to store information from the old data file
void CreateFileHash(std::ifstream& f_in, ska::flat_hash_map<int, std::string> &hashMap1, ska::flat_hash_map<int, std::string>::iterator &it, std::string &key, std::string& s_data)
{
while(f_in)
{
if(f_in.eof()) //check for end of file if so break loop
break;
Get_Line_Data(f_in, key, s_data); //get the data
int t_key{atoi(key.c_str())}; //convert the key string to an int -- this is for faster hashing
hashMap1[t_key] = s_data; //add these to the hash table
}
}
Down to 1.4 seconds.
10-15 minutes - 1.4 seconds. This does not yet include the update and insert queries but we hope that inserting and updating 1k records will be much faster than an entire set of 850k records. I'm still learning. Want to learn more. Harsh criticism welcomed. Tell me what's wrong or what I could do better and please don't be nice about it. Should I use an array of structs instead of a vector as the second data structure? Is there a better more efficient way to do this? I want to make this more readable, more efficient and I want to get better at this. If that code doesn't compile, let me know. It's copied over from a different machine and SHOULD work. Thanks!
