Skip to content

Instantly share code, notes, and snippets.

@firejox

firejox/FibFuzzyShellSort.hpp

Created December 28, 2018 05:45
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 firejox/09c34140e0a8869c2f11ca8774fed92e to your computer and use it in GitHub Desktop.
Save firejox/09c34140e0a8869c2f11ca8774fed92e to your computer and use it in GitHub Desktop.
Download ZIP
Shell Sort
Raw
FibFuzzyShellSort.hpp
#ifndef FIBFUZZYSHELLSORT_HPP
#define FIBFUZZYSHELLSORT_HPP
#include <limits>
#include "ShellSortTemplate.hpp"
#include "IntegralConstantArithmetic.hpp"
namespace FibFuzzyNS {
using namespace IntegralConstantArithmetic;
template <class Numeric, size_t sz>
struct Number {
using fib_type = add_t<typename Number<Numeric, sz - 1>::fib_type, typename Number<Numeric, sz - 2>::fib_type>;
using grand_type = neg_t<typename Number<Numeric, sz - 1>::grand_type>;
using type = add_t<fib_type, grand_type>;
};
template <class Numeric>
struct Number<Numeric, 0> {
using type = IC<Numeric, 1>;
};
template <class Numeric>
struct Number<Numeric, 1> {
using fib_type = IC<Numeric, 5>;
using grand_type = IC<Numeric, -1>;
using type = add_t<fib_type, grand_type>;
};
template <class Numeric>
struct Number<Numeric, 2> {
using fib_type = IC<Numeric, 8>;
using grand_type = IC<Numeric, 1>;
using type = add_t<fib_type, grand_type>;
};
template <class Numeric = int>
class Sequence {
// Fibonacci grand number generator
//
static constexpr size_t table_size() {
constexpr Numeric max_num = std::numeric_limits<Numeric>::max();
Numeric f0(5), f1(8), f2(1);
Numeric grand = -1;
size_t sz = 3;
while ((max_num - f1) >= (f0 + grand)) {
f2 = f1 + f0;
f0 = f1;
f1 = f2;
grand = - grand;
sz++;
}
return sz;
}
template <size_t ...I>
static constexpr decltype(auto) gen_seq(std::index_sequence<I...>) {
return std::integer_sequence<Numeric, Number<Numeric, sizeof...(I) - I - 1>::type::value...>{};
}
public:
using type = decltype(gen_seq(std::make_index_sequence<table_size()>()));
};
template<class Iterator, class Comparator=std::less<>>
void shellsort(Iterator first, Iterator last, Comparator comp = Comparator()) noexcept {
ShellSortTemplate::sort<Iterator, Sequence<typename std::iterator_traits<Iterator>::difference_type>, Comparator>(first, last, comp);
}
};
#endif
Raw
FibShellSort.hpp
#ifndef FIBSHELLSORT_HPP
#define FIBSHELLSORT_HPP
#include <limits>
#include "ShellSortTemplate.hpp"
#include "IntegralConstantArithmetic.hpp"
namespace FibNS {
using namespace IntegralConstantArithmetic;
template <class N, size_t sz>
struct Number {
using type = add_t<typename Number<N, sz - 1>::type, typename Number<N, sz - 2>::type>;
};
template <class N>
struct Number<N, 0> {
using type = IC<N, 1>;
};
template <class N>
struct Number<N, 1> {
using type = IC<N, 2>;
};
template <class Numeric = int>
class Sequence {
// Fibonacci number generator
//
static constexpr size_t table_size() {
constexpr Numeric max_num = std::numeric_limits<Numeric>::max();
Numeric f0(1), f1(2), f2(1);
size_t sz = 2;
while ((max_num - f1) >= f0) {
f2 = f1 + f0;
f0 = f1;
f1 = f2;
sz++;
}
return sz;
}
template <size_t ...I>
static constexpr decltype(auto) gen_seq(std::index_sequence<I...>) {
return std::integer_sequence<Numeric, Number<Numeric, sizeof...(I) - I - 1>::type::value...>{};
}
public:
using type = decltype(gen_seq(std::make_index_sequence<table_size()>()));
};
template<class Iterator, class Comparator=std::less<>>
void shellsort(Iterator first, Iterator last, Comparator comp = Comparator()) noexcept {
ShellSortTemplate::sort<Iterator, Sequence<typename std::iterator_traits<Iterator>::difference_type>, Comparator>(first, last, comp);
}
};
#endif
Raw
IntegralContantArithmetic.hpp
#ifndef INTEGRALCONSTANTARITHMETIC_HPP
#define INTEGRALCONSTANTARITHMETIC_HPP
#include <type_traits>
namespace IntegralConstantArithmetic {
template<class T, T ...I>
using ISeq = std::integer_sequence<T, I...>;
template<class T, T v>
using IC = std::integral_constant<T, v>;
template<class T, T v1, T v2>
constexpr auto add(IC<T, v1>, IC<T, v2>) -> IC<T, v1 + v2>;
template<class IC1, class IC2>
using add_t = decltype(add(IC1(), IC2()));
template<class T, T v>
constexpr auto neg(IC<T, v>) -> IC<T, -v>;
template<class IC1>
using neg_t = decltype(neg(IC1()));
template<class T, T v1, T v2>
constexpr auto substract(IC<T, v1>, IC<T, v2>) -> IC<T, v1 - v2>;
template<class IC1, class IC2>
using substract_t = decltype(substract(IC1(), IC2()));
template<class T, T v1, T v2>
constexpr auto multiply(IC<T, v1>, IC<T, v2>) -> IC<T, v1 * v2>;
template<class IC1, class IC2>
using multiply_t = decltype(multiply(IC1(), IC2()));
template<class T, T v1, T v2>
constexpr auto divide(IC<T, v1>, IC<T, v2>) -> IC<T, v1 / v2>;
template<class IC1, class IC2>
using divide_t = decltype(divide(IC1(), IC2()));
template<class T, T v1, T v2>
constexpr auto remainder(IC<T, v1>, IC<T, v2>) -> IC<T, v1 % v2>;
template<class IC1, class IC2>
using remainder_t = decltype(remainder(IC1(), IC2()));
};
#endif
Raw
main.cpp
#include <cstdio>
#include <cmath>
#include <array>
#include <algorithm>
#include <random>
#include "FibShellSort.hpp"
#include "FibFuzzyShellSort.hpp"
namespace Benchmark {
template <char ...ch>
struct TaskName {
static constexpr char name[sizeof...(ch) + 1] = { ch..., '\0' };
};
template <class T = char, T ...chars>
constexpr TaskName<chars...> operator ""_tname() { return {}; }
template <class Name, class Body>
struct Task : Name, Body {
static size_t size;
static double mean;
static double variance;
static double stddev;
static double relative_stddev;
using with = Name;
template <class Init>
void run(size_t times, Init init) const {
size_t counter = 0;
using self = typename std::remove_cv<std::remove_reference_t<decltype(*this)>>::type;
self::size = 0;
auto cmp = [&counter](const int &a, const int &b) ->bool { counter++; return a < b; };
for (size_t i = 0; i < times; i++) {
counter = 0;
init();
Body::operator()(cmp);
self::size++;
if (self::size > 1) {
auto delta = (double)counter - self::mean;
self::mean += delta / (double)self::size;
auto delta2 = (double)counter - self::mean;
self::variance += delta * delta2;
} else {
self::mean = counter;
}
}
self::variance /= (double)self::size;
self::stddev = std::sqrt(self::variance);
self::relative_stddev = 100.0 * (self::stddev / self::mean);
}
constexpr void clean() const {
using self = typename std::remove_cv<std::remove_reference_t<decltype(*this)>>::type;
self::size = 0;
self::mean = 0;
self::variance = 0;
self::stddev = 0;
self::relative_stddev = 0;
}
};
template<class Name, class Body>
size_t Task<Name, Body>::size = 0;
template<class Name, class Body>
double Task<Name, Body>::mean = 0;
template<class Name, class Body>
double Task<Name, Body>::variance = 0;
template<class Name, class Body>
double Task<Name, Body>::stddev = 0;
template<class Name, class Body>
double Task<Name, Body>::relative_stddev = 0;
template <class Name, class Body>
Task(Name, Body) -> Task<Name, Body>;
template <class Init, class ...Tasks>
class BM : Init, Tasks... {
template <size_t ...I>
constexpr void run(size_t times, bool is_tty, std::index_sequence<I...>) {
(([&]() constexpr {
const auto init = [this]() { Init::operator()(); };
Tasks::clean();
Tasks::run(times, init);
report(I, is_tty, std::make_index_sequence<sizeof...(Tasks)>());
}()),...);
}
template <size_t ...I>
constexpr void report(size_t x, bool is_tty, std::index_sequence<I...>) const {
auto lntsk = longest_name_task(is_tty ? x : (sizeof...(Tasks) - 1), std::make_index_sequence<sizeof...(Tasks)>());
if (is_tty && x)
printf("\e[%zuA", x);
(((I <= x) &&
(([&]()constexpr ->bool{
if (is_tty || I == x) {
printf("%*s", (int)lntsk, Tasks::with::name);
printf(" cmp: %14.2lf", Tasks::mean);
printf(" (±%5.2lf%%)\n", Tasks::relative_stddev);
}
return true;
})())) &&...);
}
template <size_t...I>
constexpr size_t longest_name_task(size_t x, std::index_sequence<I...>) const {
size_t sz = 0;
(((I <= x) && (((sz < sizeof(Tasks::with::name)) && (sz = sizeof(Tasks::with::name))) ||true)) &&...);
return sz;
}
public:
BM(Init init, Tasks ...task) : Init(init), Tasks(task)... {}
constexpr void run(size_t times, bool is_tty = true) {
run(times, is_tty, std::make_index_sequence<sizeof...(Tasks)>{});
}
};
};
constexpr size_t size = 10'000'000;
std::array<int, size> arr;
int main() {
std::random_device rd;
std::mt19937 gen(rd());
for (int i = 0; i < size; i++)
arr[i] = i;
for (size_t sz : {50'000, 100'000, 200'000, 400'000, 800'000, 1'600'000, 3'200'000, 6'400'000, 10'000'000}) {
printf("With the input size %zu\n"
"-------------------------", sz);
{
printf("\nrandom integer array\n");
using namespace Benchmark;
BM bm {
[&gen, &sz]() {
std::shuffle(arr.begin(), arr.begin() + sz, gen);
},
Task {
"fib shell sort"_tname,
[&sz](auto& cmp) {
FibNS::shellsort(arr.begin(), arr.begin() + sz, cmp);
}
},
Task {
"fib fuzzy shell sort"_tname,
[&sz](auto& cmp) {
FibFuzzyNS::shellsort(arr.begin(), arr.begin() + sz, cmp);
}
},
Task {
"std sort"_tname,
[&sz](auto& cmp) {
std::sort(arr.begin(), arr.begin() + sz, cmp);
}
},
Task {
"std sort heap"_tname,
[&sz](auto& cmp) {
std::make_heap(arr.begin(), arr.begin() + sz, cmp);
std::sort_heap(arr.begin(), arr.begin() + sz, cmp);
}
}
};
bm.run(100, false);
}
{
printf("\nascend integer array\n");
using namespace Benchmark;
BM bm {
[]() {
},
Task {
"fib shell sort"_tname,
[&sz](auto& cmp) {
FibNS::shellsort(arr.begin(), arr.begin() + sz, cmp);
}
},
Task {
"fib fuzzy shell sort"_tname,
[&sz](auto& cmp) {
FibFuzzyNS::shellsort(arr.begin(), arr.begin() + sz, cmp);
}
},
Task {
"std sort"_tname,
[&sz](auto& cmp) {
std::sort(arr.begin(), arr.begin() + sz, cmp);
}
},
Task {
"std sort heap"_tname,
[&sz](auto& cmp) {
std::make_heap(arr.begin(), arr.begin() + sz, cmp);
std::sort_heap(arr.begin(), arr.begin() + sz, cmp);
}
}
};
bm.run(1, false);
}
{
printf("\ndescend integer array\n");
using namespace Benchmark;
BM bm {
[&sz]() {
for (int i = 0; i < sz; i++)
arr[i] = sz - i - 1;
},
Task {
"fib shell sort"_tname,
[&sz](auto& cmp) {
FibNS::shellsort(arr.begin(), arr.begin() + sz, cmp);
}
},
Task {
"fib fuzzy shell sort"_tname,
[&sz](auto& cmp) {
FibFuzzyNS::shellsort(arr.begin(), arr.begin() + sz, cmp);
}
},
Task {
"std sort"_tname,
[&sz](auto& cmp) {
std::sort(arr.begin(), arr.begin() + sz, cmp);
}
},
Task {
"std sort heap"_tname,
[&sz](auto& cmp) {
std::make_heap(arr.begin(), arr.begin() + sz, cmp);
std::sort_heap(arr.begin(), arr.begin() + sz, cmp);
}
}
};
bm.run(1, false);
}
puts("\n");
}
return 0;
}
Raw
output
With the input size 50000
-------------------------
random integer array
fib shell sort cmp: 2215621.65 (± 3.13%)
fib fuzzy shell sort cmp: 1472151.98 (± 1.14%)
std sort cmp: 942999.37 (± 1.89%)
std sort heap cmp: 799776.41 (± 0.02%)
ascend integer array
fib shell sort cmp: 1028609.00 (± 0.00%)
fib fuzzy shell sort cmp: 928614.00 (± 0.00%)
std sort cmp: 981703.00 (± 0.00%)
std sort heap cmp: 807301.00 (± 0.00%)
descend integer array
fib shell sort cmp: 1146792.00 (± 0.00%)
fib fuzzy shell sort cmp: 1084243.00 (± 0.00%)
std sort cmp: 708202.00 (± 0.00%)
std sort heap cmp: 821721.00 (± 0.00%)
With the input size 100000
-------------------------
random integer array
fib shell sort cmp: 5075236.59 (± 2.76%)
fib fuzzy shell sort cmp: 3240900.91 (± 1.15%)
std sort cmp: 1998860.59 (± 1.62%)
std sort heap cmp: 1699597.89 (± 0.01%)
ascend integer array
fib shell sort cmp: 2203584.00 (± 0.00%)
fib fuzzy shell sort cmp: 2003590.00 (± 0.00%)
std sort cmp: 2113369.00 (± 0.00%)
std sort heap cmp: 1711988.00 (± 0.00%)
descend integer array
fib shell sort cmp: 2468484.00 (± 0.00%)
fib fuzzy shell sort cmp: 2333403.00 (± 0.00%)
std sort cmp: 1516394.00 (± 0.00%)
std sort heap cmp: 1743991.00 (± 0.00%)
With the input size 200000
-------------------------
random integer array
fib shell sort cmp: 11675874.97 (± 3.06%)
fib fuzzy shell sort cmp: 7099714.83 (± 1.16%)
std sort cmp: 4260059.06 (± 1.65%)
std sort heap cmp: 3599207.65 (± 0.01%)
ascend integer array
fib shell sort cmp: 4685773.00 (± 0.00%)
fib fuzzy shell sort cmp: 4285779.00 (± 0.00%)
std sort cmp: 4526699.00 (± 0.00%)
std sort heap cmp: 3628016.00 (± 0.00%)
descend integer array
fib shell sort cmp: 5267444.00 (± 0.00%)
fib fuzzy shell sort cmp: 4996120.00 (± 0.00%)
std sort cmp: 3232778.00 (± 0.00%)
std sort heap cmp: 3687179.00 (± 0.00%)
With the input size 400000
-------------------------
random integer array
fib shell sort cmp: 26816577.58 (± 2.88%)
fib fuzzy shell sort cmp: 15536927.50 (± 1.24%)
std sort cmp: 8994645.79 (± 1.60%)
std sort heap cmp: 7598375.46 (± 0.01%)
ascend integer array
fib shell sort cmp: 9967962.00 (± 0.00%)
fib fuzzy shell sort cmp: 9167967.00 (± 0.00%)
std sort cmp: 9653357.00 (± 0.00%)
std sort heap cmp: 7675669.00 (± 0.00%)
descend integer array
fib shell sort cmp: 11150635.00 (± 0.00%)
fib fuzzy shell sort cmp: 10625804.00 (± 0.00%)
std sort cmp: 6865546.00 (± 0.00%)
std sort heap cmp: 7757386.00 (± 0.00%)
With the input size 800000
-------------------------
random integer array
fib shell sort cmp: 62130961.66 (± 3.27%)
fib fuzzy shell sort cmp: 33813037.05 (± 1.26%)
std sort cmp: 18930180.01 (± 1.50%)
std sort heap cmp: 15996726.91 (± 0.00%)
ascend integer array
fib shell sort cmp: 21053733.00 (± 0.00%)
fib fuzzy shell sort cmp: 19453739.00 (± 0.00%)
std sort cmp: 20506671.00 (± 0.00%)
std sort heap cmp: 16116966.00 (± 0.00%)
descend integer array
fib shell sort cmp: 23496469.00 (± 0.00%)
fib fuzzy shell sort cmp: 22429701.00 (± 0.00%)
std sort cmp: 14531082.00 (± 0.00%)
std sort heap cmp: 16350221.00 (± 0.00%)
With the input size 1600000
-------------------------
random integer array
fib shell sort cmp: 143425454.91 (± 3.16%)
fib fuzzy shell sort cmp: 73686208.71 (± 1.30%)
std sort cmp: 40048025.14 (± 1.52%)
std sort heap cmp: 33593466.04 (± 0.00%)
ascend integer array
fib shell sort cmp: 44475424.00 (± 0.00%)
fib fuzzy shell sort cmp: 41275430.00 (± 0.00%)
std sort cmp: 43413297.00 (± 0.00%)
std sort heap cmp: 33787285.00 (± 0.00%)
descend integer array
fib shell sort cmp: 50724938.00 (± 0.00%)
fib fuzzy shell sort cmp: 48392503.00 (± 0.00%)
std sort cmp: 30662154.00 (± 0.00%)
std sort heap cmp: 34259007.00 (± 0.00%)
With the input size 3200000
-------------------------
random integer array
fib shell sort cmp: 332791166.85 (± 3.68%)
fib fuzzy shell sort cmp: 159664367.63 (± 1.20%)
std sort cmp: 83690281.78 (± 1.52%)
std sort heap cmp: 70387035.09 (± 0.00%)
ascend integer array
fib shell sort cmp: 93497115.00 (± 0.00%)
fib fuzzy shell sort cmp: 87097120.00 (± 0.00%)
std sort cmp: 91626547.00 (± 0.00%)
std sort heap cmp: 70885428.00 (± 0.00%)
descend integer array
fib shell sort cmp: 106421478.00 (± 0.00%)
fib fuzzy shell sort cmp: 101942801.00 (± 0.00%)
std sort cmp: 64524298.00 (± 0.00%)
std sort heap cmp: 71703176.00 (± 0.00%)
With the input size 6400000
-------------------------
random integer array
fib shell sort cmp: 771832518.00 (± 3.97%)
fib fuzzy shell sort cmp: 346152737.90 (± 1.36%)
std sort cmp: 175006889.43 (± 1.36%)
std sort heap cmp: 147173987.95 (± 0.00%)
ascend integer array
fib shell sort cmp: 196269650.00 (± 0.00%)
fib fuzzy shell sort cmp: 183469655.00 (± 0.00%)
std sort cmp: 192853045.00 (± 0.00%)
std sort heap cmp: 148440849.00 (± 0.00%)
descend integer array
fib shell sort cmp: 221611158.00 (± 0.00%)
fib fuzzy shell sort cmp: 213122689.00 (± 0.00%)
std sort cmp: 135448586.00 (± 0.00%)
std sort heap cmp: 149399449.00 (± 0.00%)
With the input size 10000000
-------------------------
random integer array
fib shell sort cmp: 1325095023.99 (± 3.73%)
fib fuzzy shell sort cmp: 572594719.24 (± 1.40%)
std sort cmp: 281854794.48 (± 1.17%)
std sort heap cmp: 236300381.92 (± 0.00%)
ascend integer array
fib shell sort cmp: 315842185.00 (± 0.00%)
fib fuzzy shell sort cmp: 295842191.00 (± 0.00%)
std sort cmp: 316531837.00 (± 0.00%)
std sort heap cmp: 238288048.00 (± 0.00%)
descend integer array
fib shell sort cmp: 353359827.00 (± 0.00%)
fib fuzzy shell sort cmp: 339869035.00 (± 0.00%)
std sort cmp: 222097162.00 (± 0.00%)
std sort heap cmp: 240430389.00 (± 0.00%)
Raw
ShellSortTemplate.hpp
#ifndef SHELLSORTTEMPLATE_HPP
#define SHELLSORTTEMPLATE_HPP
#include <algorithm>
#include <iterator>
#include <utility>
namespace ShellSortTemplate {
template<class Iterator, class Compare, class T, T ...Seq>
constexpr void sort_impl(Iterator first, Iterator last, Compare comp, const T size, std::integer_sequence<T, Seq...>) noexcept {
for (const auto gap : {Seq...}) {
if (size > gap) {
const auto h = first + gap;
for (auto i = h; i < last; i++) {
if (comp(*i, *(i - gap))) {
auto v = std::move(*i);
auto j = i;
do {
*j = std::move(*(j - gap));
j -= gap;
} while (j >= h && comp(v, *(j - gap)));
*j = std::move(v);
}
}
}
}
}
template<class Iterator, class Sequence, class Comparator = std::less<>>
constexpr void sort(Iterator first, Iterator last, Comparator comp = Comparator()) noexcept {
sort_impl(first, last, comp, std::distance(first, last), typename Sequence::type{});
}
}
#endif
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment