TProcura
Biblioteca em C++ para testes paramétricos de algoritmos, e coleção de algoritmos de procura e otimização
Loading...
Searching...
No Matches
CTesteTVector.cpp
Go to the documentation of this file.
1#include "CTesteTVector.h"
2#include <stdio.h>
3#include <algorithm>
4#include <random>
5#include <iterator>
6
7static std::mt19937_64 rng{ std::random_device{}() };
8
12
16
17void CTesteTVector::ResetParametros()
18{
19 static const char* nomesMetodo[] = {
20 "Add()",
21 "Sort()",
22 "RandomOrder()",
23 "Invert()",
24 "BeASet()",
25 "Difference()",
26 "Union()",
27 "Contained()",
28 "Intersection()",
29 "operator=()",
30 "operator+=()",
31 "nada"
32 };
33 static const char* nomesEstrutura[] = {
34 "TVector",
35 "std::vector",
36 "TVector/std::algorithm",
37 };
38
39 TProcura::ResetParametros();
40
41 parametro[ALGORITMO] = { "Método",1,1,12,"Método para teste.", nomesMetodo };
42
43 // estrutura de dados
44 parametro += { "ESTRUTURA_DADOS",1,1,3,"Estrutura de dados utilizada para vetor.",nomesEstrutura };
45
46 indicador += { "IND_ORDENAR","verifica se o indicador está ordenado", IND_ORDENAR };
47 indAtivo += IND_ORDENAR;
48
49 instancia = { "Dados", 1,1,10, "Vetores aleatórios de K milhões", NULL };
50}
51
52void CTesteTVector::Inicializar(void)
53{
54 int tamanho = instancia.valor * 1000000;
55 if (Parametro(ESTRUTURA_DADOS) != 2) { // TVector
56 dadosA.Count(tamanho);
57 dadosB.Count(tamanho);
58 for (int i = 0; i < tamanho; i++) {
59 dadosA[i] = TRand::rand();
60 dadosB[i] = TRand::rand();
61 }
62 }
63 else { // std::vector
64 // define o tamanho e inicializa com zeros (ou itens padrão)
65 stdA.resize(tamanho);
66 stdB.resize(tamanho);
67 for (int i = 0; i < tamanho; i++) {
68 stdA[i] = TRand::rand();
69 stdB[i] = TRand::rand();
70 }
71 }
72}
73
74void CTesteTVector::Debug(bool completo)
75{
76 if (Parametro(ESTRUTURA_DADOS) != 2) {
77 if (dadosA.Count() < 6)
78 return;
79 printf("\nDados #%d: ", dadosA.Count());
80 for (int i = 0; i < 3; i++)
81 printf("%d ", dadosA[i]);
82 printf("... ");
83 for (int i = dadosA.Count() - 3; i < dadosA.Count(); i++)
84 printf("%d ", dadosA[i]);
85 }
86 else {
87 if (stdA.size() < 6)
88 return;
89 printf("\nDados #%" PRId64 ": ", stdA.size());
90 for (int i = 0; i < 3; i++)
91 printf("%d ", stdA[i]);
92 printf("... ");
93 for (std::size_t i = stdA.size() - 3; i < stdA.size(); i++)
94 printf("%d ", stdA[i]);
95 }
96}
97
98int CTesteTVector::ExecutaAlgoritmo()
99{
100 while (!Parar()) {
101 if (iteracoes > 0)
102 Inicializar();
103 if (Parametro(ESTRUTURA_DADOS) == 1) { // TVector
104 switch (Parametro(ALGORITMO)) {
105 case 1: // add
106 dadosA = {};
107 for (int i = 0; i < instancia.valor * 1000000; i++)
108 dadosA += TRand::rand();
109 break;
110 case 2: // Sort
111 dadosA.Sort();
112 break;
113 case 3: // RandomOrder
114 dadosA.RandomOrder();
115 break;
116 case 4: // Invert
117 dadosA.Invert();
118 break;
119 case 5: // BeASet
120 dadosA.BeASet();
121 break;
122 case 6: // Difference
123 dadosA.BeASet().Difference(dadosB.BeASet());
124 break;
125 case 7: // Union
126 dadosA.BeASet().Union(dadosB.BeASet());
127 break;
128 case 8: // Contained
129 dadosA.BeASet().Contained(dadosB.BeASet());
130 break;
131 case 9: // Intersection
132 dadosA.BeASet().Intersection(dadosB.BeASet());
133 break;
134 case 10: // operator=()
135 dadosA = dadosB;
136 break;
137 case 11: // operator+=()
138 dadosA += dadosB;
139 break;
140 case 12: // nada
141 break;
142 }
143 }
144 else { // std::vector ou TVegtor/std::algorithm
145 switch (Parametro(ALGORITMO)) {
146 case 1: // add
147 if (Parametro(ESTRUTURA_DADOS) == 2) {
148 stdA.clear();
149 for (int i = 0; i < instancia.valor * 1000000; i++)
150 stdA.push_back(TRand::rand());
151 }
152 else {
153 dadosA = {};
154 for (int i = 0; i < instancia.valor * 1000000; i++)
155 dadosA += TRand::rand();
156 }
157 break;
158 case 2: // Sort
159 if (Parametro(ESTRUTURA_DADOS) == 2)
160 std::sort(stdA.begin(), stdA.end());
161 else
162 std::sort(dadosA.begin(), dadosA.end());
163 break;
164 case 3: // RandomOrder
165 if (Parametro(ESTRUTURA_DADOS) == 2)
166 std::shuffle(stdA.begin(), stdA.end(), rng);
167 else
168 std::shuffle(dadosA.begin(), dadosA.end(), rng);
169 break;
170 case 4: // Invert
171 if (Parametro(ESTRUTURA_DADOS) == 2)
172 std::reverse(stdA.begin(), stdA.end());
173 else
174 std::reverse(dadosA.begin(), dadosA.end());
175 break;
176 case 5: // BeASet (sort + unique)
177 if (Parametro(ESTRUTURA_DADOS) == 2) {
178 std::sort(stdA.begin(), stdA.end());
179 stdA.erase(
180 std::unique(stdA.begin(), stdA.end()),
181 stdA.end()
182 );
183 }
184 else {
185 std::sort(dadosA.begin(), dadosA.end());
186 dadosA.Count((int)(std::unique(dadosA.begin(), dadosA.end()) - dadosA.begin()));
187 }
188 break;
189 case 6: // Difference
190 if (Parametro(ESTRUTURA_DADOS) == 2) {
191 // deixa A e B como sets
192 std::sort(stdA.begin(), stdA.end());
193 std::sort(stdB.begin(), stdB.end());
194 stdA.erase(
195 std::unique(stdA.begin(), stdA.end()),
196 stdA.end()
197 );
198 stdB.erase(
199 std::unique(stdB.begin(), stdB.end()),
200 stdB.end()
201 );
202 // diferença
203 {
204 std::vector<int> tmp;
205 tmp.reserve(stdA.size());
206 std::set_difference(
207 stdA.begin(), stdA.end(),
208 stdB.begin(), stdB.end(),
209 std::back_inserter(tmp)
210 );
211 stdA.swap(tmp);
212 }
213 }
214 else {
215 // deixa A e B como sets
216 std::sort(dadosA.begin(), dadosA.end());
217 dadosA.Count((int)(std::unique(dadosA.begin(), dadosA.end()) - dadosA.begin()));
218 std::sort(dadosB.begin(), dadosB.end());
219 dadosB.Count((int)(std::unique(dadosB.begin(), dadosB.end()) - dadosB.begin()));
220 dadosA.Difference(dadosB);
221 }
222 break;
223 case 7: // Union
224 if (Parametro(ESTRUTURA_DADOS) == 2) {
225 std::sort(stdA.begin(), stdA.end());
226 std::sort(stdB.begin(), stdB.end());
227 stdA.erase(
228 std::unique(stdA.begin(), stdA.end()),
229 stdA.end()
230 );
231 stdB.erase(
232 std::unique(stdB.begin(), stdB.end()),
233 stdB.end()
234 );
235 {
236 std::vector<int> tmp2;
237 tmp2.reserve(stdA.size() + stdB.size());
238 std::set_union(
239 stdA.begin(), stdA.end(),
240 stdB.begin(), stdB.end(),
241 std::back_inserter(tmp2)
242 );
243 stdA.swap(tmp2);
244 }
245 }
246 else {
247 std::sort(dadosA.begin(), dadosA.end());
248 dadosA.Count((int)(std::unique(dadosA.begin(), dadosA.end()) - dadosA.begin()));
249 std::sort(dadosB.begin(), dadosB.end());
250 dadosB.Count((int)(std::unique(dadosB.begin(), dadosB.end()) - dadosB.begin()));
251 dadosA.Union(dadosB);
252 }
253 break;
254 case 8: // Contained
255 if (Parametro(ESTRUTURA_DADOS) == 2) {
256 std::sort(stdA.begin(), stdA.end());
257 std::sort(stdB.begin(), stdB.end());
258 (void) std::includes(
259 stdB.begin(), stdB.end(),
260 stdA.begin(), stdA.end()
261 );
262 }
263 else {
264 std::sort(dadosA.begin(), dadosA.end());
265 std::sort(dadosB.begin(), dadosB.end());
266 (void) std::includes(
267 dadosB.begin(), dadosB.end(),
268 dadosA.begin(), dadosA.end()
269 );
270 }
271 break;
272 case 9: // Intersection
273 if (Parametro(ESTRUTURA_DADOS) == 2) {
274 std::sort(stdA.begin(), stdA.end());
275 std::sort(stdB.begin(), stdB.end());
276 stdA.erase(
277 std::unique(stdA.begin(), stdA.end()),
278 stdA.end()
279 );
280 stdB.erase(
281 std::unique(stdB.begin(), stdB.end()),
282 stdB.end()
283 );
284 {
285 std::vector<int> tmp3;
286 tmp3.reserve(std::min(stdA.size(), stdB.size()));
287 std::set_intersection(
288 stdA.begin(), stdA.end(),
289 stdB.begin(), stdB.end(),
290 std::back_inserter(tmp3)
291 );
292 stdA.swap(tmp3);
293 }
294 }
295 else {
296 std::sort(dadosA.begin(), dadosA.end());
297 dadosA.Count((int)(std::unique(dadosA.begin(), dadosA.end()) - dadosA.begin()));
298 std::sort(dadosB.begin(), dadosB.end());
299 dadosB.Count((int)(std::unique(dadosB.begin(), dadosB.end()) - dadosB.begin()));
300 dadosA.Intersection(dadosB);
301 }
302 break;
303 case 10: // operator=()
304 if (Parametro(ESTRUTURA_DADOS) == 2)
305 stdA = stdB;
306 else
307 dadosA = dadosB;
308 break;
309 case 11: // operator+=()
310 if (Parametro(ESTRUTURA_DADOS) == 2) {
311 stdA.insert(
312 stdA.end(),
313 stdB.begin(),
314 stdB.end()
315 );
316 }
317 else
318 dadosA += dadosB;
319 break;
320 case 12: // nada
321 break;
322 }
323 }
324
325 iteracoes++;
326 // se não foi definido limite de iterações, fazer apenas uma
327 if (Parametro(LIMITE_ITERACOES) == 0)
328 break;
329 }
330 return 1;
331}
332
333int64_t CTesteTVector::Indicador(int id)
334{
335 if (id == IND_ORDENAR) { // verifica se está ordenado
336 if (Parametro(ESTRUTURA_DADOS) != 2) {
337 for (int i = 0; i < dadosA.Count() - 1; i++)
338 if (dadosA[i] > dadosA[i + 1]) {
339 Debug(COMPLETO, false, "\nordem %d > %d (%d,%d)",
340 i, i + 1, dadosA[i], dadosA[i + 1]);
341 return 0;
342 }
343 }
344 else {
345 for (std::size_t i = 0; i < stdA.size() - 1; i++)
346 if (stdA[i] > stdA[i + 1]) {
347 Debug(COMPLETO, false, "\nordem %d > %d (%d,%d)",
348 i, i + 1, stdA[i], stdA[i + 1]);
349 return 0;
350 }
351 }
352 return 1;
353 }
354 return TProcura::Indicador(id);
355}
EParametrosVector
EParametrosVector
Definition CTesteTVector.cpp:9
ESTRUTURA_DADOS
@ ESTRUTURA_DADOS
estrutura base a utilizar
Definition CTesteTVector.cpp:10
EIndicadoresVector
EIndicadoresVector
Definition CTesteTVector.cpp:13
IND_ORDENAR
@ IND_ORDENAR
verifica se está ordenado
Definition CTesteTVector.cpp:14
IND_PROCURA
@ IND_PROCURA
Marcador para permitir a extensão do enum em subclasses.
Definition TProcura.h:20
COMPLETO
@ COMPLETO
Mostra toda a execução detalhadamente.
Definition TProcura.h:67
ALGORITMO
@ ALGORITMO
Algoritmo base a executar.
Definition TProcura.h:42
LIMITE_ITERACOES
@ LIMITE_ITERACOES
Número máximo de iterações (0 significa sem limite).
Definition TProcura.h:46
PARAMETROS_PROCURA
@ PARAMETROS_PROCURA
Marcador para permitir a extensão do enum em subclasses.
Definition TProcura.h:47
CTesteTVector::ResetParametros
void ResetParametros()
Inicializa parâmetros de teste.
Definition CTesteTVector.cpp:17
CTesteTVector::dadosA
TVector< int > dadosA
Definition CTesteTVector.h:20
CTesteTVector::stdB
std::vector< int > stdB
Vetores equivalentes em STL para comparação.
Definition CTesteTVector.h:21
CTesteTVector::dadosB
TVector< int > dadosB
Vetores de teste para operações TVector.
Definition CTesteTVector.h:20
CTesteTVector::Debug
void Debug(bool completo=true) override
Mostra informação de debug sobre o estado dos vetores.
Definition CTesteTVector.cpp:74
CTesteTVector::stdA
std::vector< int > stdA
Definition CTesteTVector.h:21
CTesteTVector::Indicador
int64_t Indicador(int id)
Calcula indicadores de teste.
Definition CTesteTVector.cpp:333
CTesteTVector::Inicializar
void Inicializar(void)
Inicializa dados e estado para teste.
Definition CTesteTVector.cpp:52
CTesteTVector::ExecutaAlgoritmo
int ExecutaAlgoritmo()
Executa o algoritmo de teste (a definir pelo utilizador).
Definition CTesteTVector.cpp:98
TProcura::Parametro
int Parametro(int id) const
Definition TProcura.h:522
TProcura::resultado
static int resultado
Resultado retornado pelo algoritmo na última execução.
Definition TProcura.h:493
TProcura::Indicador
virtual int64_t Indicador(int id)
Retorna um indicador, após a execução do algoritmo.
Definition TProcura.cpp:80
TProcura::iteracoes
static int iteracoes
Número total de iterações realizadas na última execução.
Definition TProcura.h:497
TProcura::ResetParametros
virtual void ResetParametros()
Inicializa os parametros, indicadores e instâncias.
Definition TProcura.cpp:47
TProcura::Parar
virtual bool Parar(void)
Verifica se a procura deve ser interrompida.
Definition TProcura.h:363
TProcura::indicador
static TVector< TIndicador > indicador
Indicadores que podem ser calculados após a execução, quer com informação da instãncia, quer com resultado da ...
Definition TProcura.h:488
TProcura::indAtivo
static TVector< int > indAtivo
Definition TProcura.h:489
TProcura::instancia
static TParametro instancia
ID da instância atual, a ser utilizado em SolucaoVazia().
Definition TProcura.h:24
TProcura::parametro
static TVector< TParametro > parametro
Parâmetros a serem utilizados na configuração atual.
Definition TProcura.h:485
TVector::end
Item * end() noexcept
Definition TVector.h:317
TVector::BeASet
TVector< Item > & BeASet()
Converte o vetor num conjunto: remove duplicados e ordena.
Definition TVector.h:836
TVector::RandomOrder
TVector< Item > & RandomOrder()
Coloca os elementos em ordem aleatória (Fisher–Yates shuffle).
Definition TVector.h:752
TVector::Difference
TVector< Item > & Difference(const TVector< Item > &v)
Diferença deste conjunto em relação a outro.
Definition TVector.h:910
TVector::Sort
TVector< Item > & Sort(TVector< int > *idxvect=nullptr)
Ordena todo o vetor, opcionalmente devolvendo índices ordenados.
Definition TVector.h:597
TVector::Intersection
TVector< Item > & Intersection(const TVector< Item > &v)
Interseção deste conjunto com outro.
Definition TVector.h:884
TVector::Contained
bool Contained(const TVector< Item > &v) const
Verifica se este conjunto está contido no outro.
Definition TVector.h:953
TVector::Invert
TVector< Item > & Invert()
Inverte a ordem dos elementos no vetor.
Definition TVector.h:1020
TVector::begin
Item * begin() noexcept
Definition TVector.h:316
TVector::Count
int Count() const
Definition TVector.h:227
TVector::Union
TVector< Item > & Union(const TVector< Item > &v)
Realiza a união deste conjunto com outro.
Definition TVector.h:859
TRand::rand
unsigned int rand(int seq)
Retorna o próximo valor pseudo-aleatório.
Definition TRand.cpp:46
SParametro::valor
int valor
valor do parametro
Definition TProcura.h:139