Skip to content

Instantly share code, notes, and snippets.

@RadimBaca
Last active March 29, 2019 13:39
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save RadimBaca/16d7c612dbd9082cd49de5df0dd85ad9 to your computer and use it in GitHub Desktop.
Save RadimBaca/16d7c612dbd9082cd49de5df0dd85ad9 to your computer and use it in GitHub Desktop.
comparison of merge and concatenation of two vectors in C++
////////////////////////////////////////////////////////
//
// Task : merging two vectors of SortRecords into one vector
// Author: R.Baca
//
/////////////////////////////////////////////////////////
#include <vector>
#include <algorithm>
#include <random>
#include <numeric>
#include <iostream>
#include <sstream>
#include <array>
#include <chrono>
constexpr size_t TUPLE_SIZE = 90;
constexpr size_t KEY_SIZE = 10;
constexpr size_t TUPLE_COUNT = 1024 * 1024 * 20;
constexpr size_t ARRAY_COUNT = 2;
using Record = std::array<uint8_t, TUPLE_SIZE>;
using Header = std::array<uint8_t, KEY_SIZE>;
using TimerClock = std::chrono::system_clock;
struct SortRecord {
Header header;
Record record;
bool operator<(const SortRecord& record)
{
const uint64_t a = *reinterpret_cast<const uint64_t*>(&header[0]);
const uint64_t b = *reinterpret_cast<const uint64_t*>(&record.header[0]);
if (a == b)
{
const uint16_t c = *reinterpret_cast<const uint16_t*>(&header[8]);
const uint16_t d = *reinterpret_cast<const uint16_t*>(&record.header[8]);
return c < d;
}
return a < b;
}
void operator=(const SortRecord& r)
{
memcpy(this, &r, sizeof(uint8_t) * (KEY_SIZE + TUPLE_SIZE));
}
};
template<size_t tuplecount>
static auto CreateArray()
{
std::array<std::vector<SortRecord>, ARRAY_COUNT> data_array;
uint64_t hvalue = 0;
srand(100);
for (auto& data : data_array)
{
data.resize(tuplecount);
hvalue = 0;
std::for_each(data.begin(), data.end(), [&hvalue](auto& it)
{
*reinterpret_cast<uint64_t*>(&it.header[0]) = hvalue = hvalue + (rand() % 100);
});
}
return data_array;
}
int main(int argc, char* argv[])
{
auto data_array = CreateArray<TUPLE_COUNT>();
// merge
std::vector<SortRecord> result1;
result1.reserve(TUPLE_COUNT * 2);
auto start = TimerClock::now();
std::merge(data_array[0].begin(), data_array[0].end(),
data_array[1].begin(), data_array[1].end(),
std::back_inserter(result1));
auto end = TimerClock::now();
std::cout << std::to_string(std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count()) << " [ms]\n";
// concatenation
std::vector<SortRecord> result2;
result2.reserve(TUPLE_COUNT * 2);
auto start2 = TimerClock::now();
result2.insert(result2.end(), data_array[0].begin(), data_array[0].end());
result2.insert(result2.end(), data_array[1].begin(), data_array[1].end());
auto end2 = TimerClock::now();
std::cout << std::to_string(std::chrono::duration_cast<std::chrono::milliseconds>(end2 - start2).count()) << " [ms]\n";
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment