1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
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
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
|
//===----------------------------------------------------------------------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
#ifndef LIBCXX_TEST_BENCHMARKS_ALGORITHMS_SORTING_COMMON_H
#define LIBCXX_TEST_BENCHMARKS_ALGORITHMS_SORTING_COMMON_H
#include <algorithm>
#include <cstddef>
#include <numeric>
#include <random>
#include <type_traits>
#include <vector>
namespace support {
// This function creates a vector with N int-like values.
//
// These values are arranged in such a way that they would invoke O(N^2)
// behavior on any quick sort implementation that satisifies certain conditions.
// Details are available in the following paper:
//
// "A Killer Adversary for Quicksort", M. D. McIlroy, Software-Practice &
// Experience Volume 29 Issue 4 April 10, 1999 pp 341-344.
// https://dl.acm.org/doi/10.5555/311868.311871.
template <class T>
std::vector<T> quicksort_adversarial_data(std::size_t n) {
static_assert(std::is_integral_v<T>);
assert(n > 0);
// If an element is equal to gas, it indicates that the value of the element
// is still to be decided and may change over the course of time.
T gas = n - 1;
std::vector<T> v;
v.resize(n);
for (unsigned int i = 0; i < n; ++i) {
v[i] = gas;
}
// Candidate for the pivot position.
int candidate = 0;
int nsolid = 0;
// Populate all positions in the generated input to gas.
std::vector<int> ascending_values(v.size());
// Fill up with ascending values from 0 to v.size()-1. These will act as
// indices into v.
std::iota(ascending_values.begin(), ascending_values.end(), 0);
std::sort(ascending_values.begin(), ascending_values.end(), [&](int x, int y) {
if (v[x] == gas && v[y] == gas) {
// We are comparing two inputs whose value is still to be decided.
if (x == candidate) {
v[x] = nsolid++;
} else {
v[y] = nsolid++;
}
}
if (v[x] == gas) {
candidate = x;
} else if (v[y] == gas) {
candidate = y;
}
return v[x] < v[y];
});
return v;
}
// ascending sorted values
template <class T>
std::vector<T> ascending_sorted_data(std::size_t n) {
std::vector<T> v(n);
std::iota(v.begin(), v.end(), 0);
return v;
}
// descending sorted values
template <class T>
std::vector<T> descending_sorted_data(std::size_t n) {
std::vector<T> v(n);
std::iota(v.begin(), v.end(), 0);
std::reverse(v.begin(), v.end());
return v;
}
// pipe-organ pattern
template <class T>
std::vector<T> pipe_organ_data(std::size_t n) {
std::vector<T> v(n);
std::iota(v.begin(), v.end(), 0);
auto half = v.begin() + v.size() / 2;
std::reverse(half, v.end());
return v;
}
// heap pattern
template <class T>
std::vector<T> heap_data(std::size_t n) {
std::vector<T> v(n);
std::iota(v.begin(), v.end(), 0);
std::make_heap(v.begin(), v.end());
return v;
}
// shuffled randomly
template <class T>
std::vector<T> shuffled_data(std::size_t n) {
std::vector<T> v(n);
std::iota(v.begin(), v.end(), 0);
std::mt19937 rng;
std::shuffle(v.begin(), v.end(), rng);
return v;
}
// single element in the whole sequence
template <class T>
std::vector<T> single_element_data(std::size_t n) {
std::vector<T> v(n);
return v;
}
struct NonIntegral {
NonIntegral() : value_(0) {}
NonIntegral(int i) : value_(i) {}
friend auto operator<(NonIntegral const& a, NonIntegral const& b) { return a.value_ < b.value_; }
friend auto operator>(NonIntegral const& a, NonIntegral const& b) { return a.value_ > b.value_; }
friend auto operator<=(NonIntegral const& a, NonIntegral const& b) { return a.value_ <= b.value_; }
friend auto operator>=(NonIntegral const& a, NonIntegral const& b) { return a.value_ >= b.value_; }
friend auto operator==(NonIntegral const& a, NonIntegral const& b) { return a.value_ == b.value_; }
friend auto operator!=(NonIntegral const& a, NonIntegral const& b) { return a.value_ != b.value_; }
private:
int value_;
};
} // namespace support
#endif // LIBCXX_TEST_BENCHMARKS_ALGORITHMS_SORTING_COMMON_H
|
