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