tstOrdering.cc 2.92 KB
Newer Older
1
#include <iostream>
LEFEBVREJP email's avatar
LEFEBVREJP email committed
2
#include <random>
3
4
5
#include "gtest/gtest.h"

#include "radixalgorithm/ordering.hh"
6
#include "radixbug/bug.hh"
7

8
9
TEST(radixalgorithm, Ordering)
{
10
11
12
13
14
15
16
17
18
  std::vector<double> list{2.0, 1.0, 3.0, 4.0, 5.0, 0.0, 10.0};
  // permutation              5,   1,   0,   2,   3,   4,    6
  // correct ordering
  std::vector<int> list2{0, 1, 2, 3, 4, 5, 6};
  auto comparator = [](double a, double b) {
    radix_line("\t[" << a << "," << b << "]");
    return a < b;
  };
  std::vector<size_t> permutation = radix::sort_permutation(list, comparator);
LEFEBVREJP email's avatar
LEFEBVREJP email committed
19
20
  std::vector<size_t> perm2;
  radix::sort_permutation(list.begin(), list.end(), perm2, comparator);
21
22
23
  // test edges
  EXPECT_EQ(permutation[0], 5);
  EXPECT_EQ(permutation[6], 6);
LEFEBVREJP email's avatar
LEFEBVREJP email committed
24
25
  EXPECT_EQ(perm2[0], 5);
  EXPECT_EQ(perm2[6], 6);
26
  std::cout << "Ordering:" << std::endl;
27
28
  for (size_t i = 0; i < permutation.size(); ++i)
  {
29
    std::cout << "index " << i << ". (" << list[i] << ") recieves value from "
LEFEBVREJP email's avatar
LEFEBVREJP email committed
30
31
              << permutation[i] << " (" << list[permutation[i]] << ") p2("
              << list[perm2[i]] << ")" << std::endl;
32
33
34
35
36
37
38
39
40
  }
  //
  // sort list given the
  radix::apply_permutation(list, permutation);
  EXPECT_DOUBLE_EQ(list[0], 0.0);
  EXPECT_DOUBLE_EQ(list[6], 10.0);
  radix::apply_permutation(list2, permutation);
  EXPECT_EQ(list2[0], 5);
  EXPECT_EQ(list2[6], 6);
41
42
  for (size_t i = 0; i < list.size(); ++i)
  {
43
44
    std::cout << "[" << list[i] << "," << list2[i] << "]" << std::endl;
  }
45
}
LEFEBVREJP email's avatar
LEFEBVREJP email committed
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
TEST(radixalgorithm, DISABLED_BenchmarkOrdering)
{
  std::vector<double> giant_list(1000000);
  // First create an instance of an engine.
  std::random_device rnd_device;
  // Specify the engine and distribution.
  std::mt19937 mersenne_engine{rnd_device()};
  std::uniform_real_distribution<double> dist{1, 1000};

  auto gen = [&dist, &mersenne_engine]() { return dist(mersenne_engine); };

  generate(std::begin(giant_list), std::end(giant_list), gen);

  auto comparator = [](double a, double b) { return a < b; };
  radix::Timer timer1, timer2, timer3;

  timer1.start();
  // test time for return
  std::vector<size_t> perm1;
  {
    perm1 = radix::sort_permutation(giant_list, comparator);
  }
  timer1.stop();
  timer2.start();
  std::vector<size_t> perm2(giant_list.size());
  {
    radix::sort_permutation(giant_list.begin(), giant_list.end(), perm2,
                            comparator);
  }
  timer2.stop();

  timer3.start();
  {
    radix::sort_permutation(giant_list.begin(), giant_list.end(), perm2,
                            comparator);
  }
  timer3.stop();
  std::cout << "Perm1 took " << timer1.duration() / 1e9 << " seconds"
            << std::endl;
  std::cout << "Perm2 took " << timer2.duration() / 1e9 << " seconds"
            << std::endl;
  std::cout << "Perm3 took " << timer3.duration() / 1e9 << " seconds"
            << std::endl;
  EXPECT_EQ(giant_list[perm1[0]], giant_list[perm2[0]]);
  EXPECT_EQ(giant_list[perm1[perm1.size() - 1]],
            giant_list[perm2[perm2.size() - 1]]);
}