Ovederax, собрал всё воедино
Кликните здесь для просмотра всего текста
| C++ |
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
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
| #include <iostream>
#include <set>
#include <vector>
#include <functional>
#include <ctime>
#include <random>
#include <limits>
template <typename Integer>
class Fibonacci
{
std::set<Integer> s;
public:
Fibonacci();
bool contains(const Integer value) { return s.find(value) != s.end(); }
Integer *max(std::vector<Integer> &v);
};
bool isFib(int64_t);
bool IsPerfectSquare(const int64_t n);
bool IsFibonacci(const int64_t n);
template <typename Integer>
double speed_test(size_t repeat, std::function<bool(Integer)> tested_function);
int main()
{
Fibonacci<int64_t> fib;
const size_t repeat = 1e7;
auto search_with_set = [&fib](const int64_t &value) { return fib.contains(value); };
auto search_with_switch = [&fib](const int64_t &value) { return isFib(value); };
auto search_with_expression = [&fib](const int64_t &value) { return IsFibonacci(value); };
std::cout << speed_test<int64_t>(repeat, search_with_set) << std::endl;
std::cout << speed_test<int64_t>(repeat, search_with_switch) << std::endl;
std::cout << speed_test<int64_t>(repeat, search_with_expression) << std::endl;
}
template <typename Integer>
double speed_test(size_t repeat, std::function<bool(Integer)> tested_function)
{
std::srand(1);
const Integer MAX = std::numeric_limits<Integer>::max();
clock_t start = clock();
while (repeat--)
tested_function(Integer(std::rand() * MAX));
clock_t end = clock();
return double(end - start) / CLOCKS_PER_SEC;
}
template <typename Integer>
Fibonacci<Integer>::Fibonacci()
{
for (Integer a{1}, b{1}; a + b < a + a + b;)
{
s.insert(b);
std::swap(a, b);
b += a;
}
}
template <typename Integer>
Integer *Fibonacci<Integer>::max(std::vector<Integer> &v)
{
Integer *link = nullptr;
for (auto &value : v)
if (contains(value) && (link == nullptr || *link < value))
link = &value;
return link;
}
bool IsPerfectSquare(const int64_t n)
{
if (n < 0)
return false;
const int64_t x = static_cast<int64_t>(sqrt(n * 1.0) + 0.5);
return (x * x == n);
}
bool IsFibonacci(const int64_t n)
{
const int64_t pos = 5 * n * n + 4;
const int64_t neg = 5 * n * n - 4;
return (IsPerfectSquare(pos) || IsPerfectSquare(neg));
}
bool isFib(int64_t n)
{
if (n < 0)
return false;
switch (n)
{
case 1:
case 2:
case 3:
case 5:
case 8:
case 13:
case 21:
case 34:
case 55:
case 89:
case 144:
case 233:
case 377:
case 610:
case 987:
case 1597:
case 2584:
case 4181:
case 6765:
case 10946:
case 17711:
case 28657:
case 46368:
case 75025:
case 121393:
case 196418:
case 317811:
case 514229:
case 832040:
case 1346269:
case 2178309:
case 3524578:
case 5702887:
case 9227465:
case 14930352:
case 24157817:
case 39088169:
case 63245986:
case 102334155:
case 165580141:
case 267914296:
case 433494437:
case 701408733:
case 1134903170:
case 1836311903:
case 2971215073:
case 4807526976:
case 7778742049:
case 12586269025:
case 20365011074:
case 32951280099:
case 53316291173:
case 86267571272:
case 139583862445:
case 225851433717:
case 365435296162:
case 591286729879:
case 956722026041:
case 1548008755920:
case 2504730781961:
case 4052739537881:
case 6557470319842:
case 10610209857723:
case 17167680177565:
case 27777890035288:
case 44945570212853:
case 72723460248141:
case 117669030460994:
case 190392490709135:
case 308061521170129:
case 498454011879264:
case 806515533049393:
case 1304969544928657:
case 2111485077978050:
case 3416454622906707:
case 5527939700884757:
case 8944394323791464:
case 14472334024676221:
case 23416728348467685:
case 37889062373143906:
case 61305790721611591:
case 99194853094755497:
case 160500643816367088:
case 259695496911122585:
case 420196140727489673:
case 679891637638612258:
case 1100087778366101931:
case 1779979416004714189:
case 2880067194370816120:
case 4660046610375530309:
case 7540113804746346429:
return true;
}
return false;
} |
|
Код
$ clang++ -Wall -fexceptions -O3 -std=c++11 -o run run.cpp
$ ./run
0.352641
0.190936
0.359706
Мое решение оказалось по производительности такое же как и у
HighPredator. Но получение корня, возможно, можно еще ускорить и формула дает чистое константное время, в отличии от switch который будет сравнивать весь список при больших значениях.
Кстати, а вот и еще одна идея для теста: проверка на большие и малые числа
Добавлено через 13 минут
Ovederax, доделал
Кликните здесь для просмотра всего текста
| C++ |
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
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
| #include <iostream>
#include <set>
#include <vector>
#include <functional>
#include <ctime>
#include <random>
#include <limits>
template <typename Integer>
class Fibonacci
{
std::set<Integer> s;
public:
Fibonacci();
bool contains(const Integer value) { return s.find(value) != s.end(); }
Integer *max(std::vector<Integer> &v);
};
bool isFib(int64_t);
bool IsPerfectSquare(const int64_t n);
bool IsFibonacci(const int64_t n);
template <typename Integer>
double speed_test(size_t repeat, std::function<bool(Integer)> tested_function, Integer *value = nullptr);
int main()
{
Fibonacci<int64_t> fib;
const size_t repeat = 1e7;
auto search_with_set = [&fib](const int64_t &value) { return fib.contains(value); };
auto search_with_switch = [&fib](const int64_t &value) { return isFib(value); };
auto search_with_expression = [&fib](const int64_t &value) { return IsFibonacci(value); };
std::cout << speed_test<int64_t>(repeat, search_with_set) << std::endl;
std::cout << speed_test<int64_t>(repeat, search_with_switch) << std::endl;
std::cout << speed_test<int64_t>(repeat, search_with_expression) << std::endl;
int64_t value = 1;
std::cout << "Fixed value: " << value << std::endl;
std::cout << speed_test<int64_t>(repeat, search_with_set, &value) << std::endl;
std::cout << speed_test<int64_t>(repeat, search_with_switch, &value) << std::endl;
std::cout << speed_test<int64_t>(repeat, search_with_expression, &value) << std::endl;
value = 7540113804746346429;
std::cout << "Fixed value: " << value << std::endl;
std::cout << speed_test<int64_t>(repeat, search_with_set, &value) << std::endl;
std::cout << speed_test<int64_t>(repeat, search_with_switch, &value) << std::endl;
std::cout << speed_test<int64_t>(repeat, search_with_expression, &value) << std::endl;
}
template <typename Integer>
double speed_test(size_t repeat, std::function<bool(Integer)> tested_function, Integer *value)
{
std::srand(1);
const Integer MAX = std::numeric_limits<Integer>::max();
clock_t start = clock();
if (value == nullptr)
while (repeat--)
tested_function(Integer(std::rand() * MAX));
else
while (repeat--)
tested_function(*value);
clock_t end = clock();
return double(end - start) / CLOCKS_PER_SEC;
}
template <typename Integer>
Fibonacci<Integer>::Fibonacci()
{
for (Integer a{1}, b{1}; a + b < a + a + b;)
{
s.insert(b);
std::swap(a, b);
b += a;
}
}
template <typename Integer>
Integer *Fibonacci<Integer>::max(std::vector<Integer> &v)
{
Integer *link = nullptr;
for (auto &value : v)
if (contains(value) && (link == nullptr || *link < value))
link = &value;
return link;
}
bool IsPerfectSquare(const int64_t n)
{
if (n < 0)
return false;
const int64_t x = static_cast<int64_t>(sqrt(n * 1.0) + 0.5);
return (x * x == n);
}
bool IsFibonacci(const int64_t n)
{
const int64_t pos = 5 * n * n + 4;
const int64_t neg = 5 * n * n - 4;
return (IsPerfectSquare(pos) || IsPerfectSquare(neg));
}
bool isFib(int64_t n)
{
if (n < 0)
return false;
switch (n)
{
case 1:
case 2:
case 3:
case 5:
case 8:
case 13:
case 21:
case 34:
case 55:
case 89:
case 144:
case 233:
case 377:
case 610:
case 987:
case 1597:
case 2584:
case 4181:
case 6765:
case 10946:
case 17711:
case 28657:
case 46368:
case 75025:
case 121393:
case 196418:
case 317811:
case 514229:
case 832040:
case 1346269:
case 2178309:
case 3524578:
case 5702887:
case 9227465:
case 14930352:
case 24157817:
case 39088169:
case 63245986:
case 102334155:
case 165580141:
case 267914296:
case 433494437:
case 701408733:
case 1134903170:
case 1836311903:
case 2971215073:
case 4807526976:
case 7778742049:
case 12586269025:
case 20365011074:
case 32951280099:
case 53316291173:
case 86267571272:
case 139583862445:
case 225851433717:
case 365435296162:
case 591286729879:
case 956722026041:
case 1548008755920:
case 2504730781961:
case 4052739537881:
case 6557470319842:
case 10610209857723:
case 17167680177565:
case 27777890035288:
case 44945570212853:
case 72723460248141:
case 117669030460994:
case 190392490709135:
case 308061521170129:
case 498454011879264:
case 806515533049393:
case 1304969544928657:
case 2111485077978050:
case 3416454622906707:
case 5527939700884757:
case 8944394323791464:
case 14472334024676221:
case 23416728348467685:
case 37889062373143906:
case 61305790721611591:
case 99194853094755497:
case 160500643816367088:
case 259695496911122585:
case 420196140727489673:
case 679891637638612258:
case 1100087778366101931:
case 1779979416004714189:
case 2880067194370816120:
case 4660046610375530309:
case 7540113804746346429:
return true;
}
return false;
} |
|
Код
$ clang++ -Wall -fexceptions -O3 -std=c++11 -o run run.cpp
$ ./run
0.362689
0.227071
0.361598
Fixed value: 1
0.155653
0.123166
0.129878
Fixed value: 7540113804746346429
0.316709
0.140357
0.042689
У
switch, по результатам, практически нет деградации. Также стабильно себя чувствует решение с
std::set. А вот формула удивила. Почти в 3 раза быстрее считается если число является числом фибоначи и оно попадает в
. Иначе, я не пойму с чего, вдруг, такой скачек производительности.
Добавлено через 2 минуты
rossohin647, бери формулу в качестве решения, она самая крутая.
(
Сообщение от HighPredator
