https://github.com/jonas-ellert/right-lyndon
Tip revision: f292fd218d0edb546530aaf517923eccb79b2736 authored by jonas-ellert on 12 April 2022, 19:32:52 UTC
Update README.md
Update README.md
Tip revision: f292fd2
bench.cpp
#include "right-lyndon-extension-improved.hpp"
#include "right-lyndon-extension-naive.hpp"
#include "right-lyndon-naive.hpp"
#include "right-lyndon.hpp"
#include <algorithm>
#include <chrono>
#include <fstream>
#include <iostream>
#include <limits>
#include <random>
struct timer {
using millisec = std::chrono::milliseconds;
std::chrono::steady_clock::time_point begin;
std::chrono::steady_clock::time_point end;
void start() { begin = std::chrono::steady_clock::now(); }
void stop() { end = std::chrono::steady_clock::now(); }
uint64_t millis() const {
return std::chrono::duration_cast<millisec>(end - begin).count();
}
double mibs(uint64_t const n) const {
auto ms = millis();
double const s = ms / 1000.0;
double const mib = n / 1024.0 / 1024.0;
return mib / s;
}
static auto measure(std::string s, uint64_t n, auto &&function) {
std::cout << s << " start!" << std::endl;
timer t;
t.start();
decltype(function()) result = function();
t.stop();
std::cout << s << " time: " << t.millis() << "[ms]"
<< " = " << t.mibs(n) << "mibs" << std::endl;
return result;
};
};
int main(int argc, char *argv[]) {
if (argc != 3 && argc != 2) {
std::cerr << "Wrong number of parameters." << std::endl;
std::cerr << "First parameter: path to input file (mandatory)."
<< std::endl;
std::cerr << "Second parameter: prefix size in bytes (optinal)."
<< std::endl;
return -1;
}
std::vector<uint8_t> string;
uint64_t const max_size =
(argc == 3) ? std::stoll(argv[2]) : std::numeric_limits<uint64_t>::max();
// read file
std::ifstream t(argv[1]);
t.seekg(0, std::ios::end);
uint64_t const n = std::min((uint64_t)t.tellg(), max_size);
t.seekg(0, std::ios::beg);
string.resize(n);
std::copy_n((std::istreambuf_iterator<char>(t)), n, string.begin());
std::vector<uint32_t> nss(n);
std::cout << "Ready!" << std::endl;
std::cout << "string = " << argv[1] << std::endl;
std::cout << " n = " << n << std::endl;
std::cout << std::endl;
std::cout << "\nFirst 800:\n";
for (size_t i = 0; i < std::min((uint64_t)800, n); ++i)
std::cout << ((i % 80) ? "" : "\n") << (char)string[i];
std::cout << std::endl << std::endl;
{
auto result = timer::measure("Extension linear", n, [&]() {
return right_lyndon(string.data(), string.size());
});
for (size_t i = 0; i < n; ++i) nss[i] = result[i].nss;
std::cout << std::endl;
}
{
auto result = timer::measure("Extension improved", n, [&]() {
return right_lyndon_extension_improved(string.data(), string.size());
});
for (size_t i = 0; i < n; ++i)
if (nss[i] != result[i].nss) std::exit(-1); // sanity check
std::cout << "Results consistent.\n" << std::endl;
}
{
auto result = timer::measure("Extension naive", n, [&]() {
return right_lyndon_extension_naive(string.data(), string.size());
});
for (size_t i = 0; i < n; ++i)
if (nss[i] != result[i].nss) std::exit(-1); // sanity check
std::cout << "Results consistent.\n" << std::endl;
}
{
auto result = timer::measure("Naive (no extension)", n, [&]() {
return right_lyndon_naive(string.data(), string.size());
});
for (size_t i = 0; i < n; ++i)
if (nss[i] != result[i].nss) std::exit(-1); // sanity check
std::cout << "Results consistent." << std::endl;
}
return 0;
}