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