#cpp #алгоритм #оптимизация #инспекция_кода #быстродействие
Здравствуйте! Сейчас пытаюсь искать алгоритмы Маркова с помощью генетических алгоритмов.
Есть такой вот код:
#include
#include
#include
#include
#include
#include
#include
using std::cin;
using std::cout;
using std::endl;
using std::sort;
using std::pair;
using std::vector;
using std::string;
typedef pair rule;
typedef vector algorithm;
typedef pair test;
void print_rule(rule r)
{
cout< "< prevs;
int step = 0;
bool loop=false;
bool found = false;
for(int i=0; i100)
break;
for(int i=0; i '"<0)
{
str.erase(rand()%str.length(), 1);
return str;
}
else if(chance<75 && str.length()>0)
{
auto index = str.begin()+rand()%str.length();
str.insert(index, 1, (char)(rand()%94+32));
return str;
}
return str;
}
rule mutate_rule(rule r)
{
string left = r.first;
string right = r.second;
int chance = rand()%100;
if(chance<33)
{
left = mutate_string(left);
}
else if(chance<66)
{
right = mutate_string(right);
}
else
{
left = mutate_string(left);
// cout< 1)
{
auto index = algo.begin()+rand()%algo.size();
algo.erase(index);
return algo;
}
else
{
int index = rand()%algo.size();
rule new_rule = mutate_rule(algo[index]);
algo[index] = new_rule;
return algo;
}
}
algorithm random_algoritm()
{
int length = rand()%10+1;
algorithm ret;
for(int i=0; i& tests)
{
int length = 0;
for(int i=0; i& tests)
{
int ret = 0;
for(int i=0; i& tests)
{
int ret = 0;
for(int i=0; i& tests)
{
const int goal = max_fitness(tests);
int best = -10000;
vector population;
for(int i=0; i<100; i++)
population.push_back(random_algoritm());
int generation = 0;
int last_print = 0;
int start = time(NULL);
pair pop[100];
while(best != goal)
{
generation++;
for(int i=0; i<100; i++)
pop[i]=make_pair(population[i], fitness(population[i], tests));
sort(pop, pop+100,
[](const pair& a, const pair& b)
{return a.second > b.second;});
population[0] = pop[0].first;
for(int i=1; i<100; i++)
{
int chance=rand()%100;
if(chance>i)
{
population[i] = mutate_algoritm(pop[0].first);
}
else
population[i] = pop[0].first;
}
const int first = fitness(population[0], tests);
if(first>best)
{
best=first;
}
}
return population[0];
}
algorithm optimize_algorithm(const vector tests, algorithm algo)
{
vector population;
for(int i=0; i<100; i++)
population.push_back(algo);
int generation = 0;
int last_print = 0;
int best = -algo.size();
pair pop[100];
while(generation<10000)
{
generation++;
for(int i=0; i<100; i++)
pop[i]=make_pair(population[i], fitness_opt(population[i], tests));
sort(pop, pop+100,
[](const pair& a, const pair& b)
{return a.second > b.second;});
population[0] = pop[0].first;
for(int i=1; i<100; i++)
{
int chance=rand()%100;
if(chance>i)
{
population[i] = mutate_algoritm(pop[0].first);
}
else
population[i] = pop[0].first;
}
const int first = fitness_opt(population[0], tests);
if(first>best)
best=first;
}
return population[0];
}
int main()
{
// const vector tests = {{"||*||", "||||"},
// {"||*|||", "||||||"},
// {"||||*||", "||||||||"},
// {"||||*||||", "||||||||||||||||"}};
// const vector tests = {{"||+||", "||||"},
// {"|+||", "|||"},
// {"|||+|", "||||"}};
// const vector tests = {{"||-||", ""},
// {"|||-|", "||"},
// {"||-|", "|"}};
const vector tests = {{"||+||", "||||"},
{"|||+|", "||||"},
{"|+|", "||"}};
int start = time(NULL);
algorithm un_add = find_algorithm(tests);
cout<<"Found in "<
#include
#include
#include
#include
#include
#include
using std::cin;
using std::cout;
using std::endl;
using std::sort;
using std::pair;
using std::vector;
using std::string;
typedef pair rule;
typedef vector algorithm;
typedef pair test;
void print_rule(rule r)
{
cout< "< prevs;
int step = 0;
bool loop=false;
bool found = false;
for(int i=0; i100)
break;
for(int i=0; i '"<0)
{
str.erase(rand()%str.length(), 1);
}
else if(chance<75 && str.length()>0)
{
auto index = str.begin()+rand()%str.length();
str.insert(index, 1, (char)(rand()%94+32));
}
}
void mutate_rule(rule& r)
{
int chance = rand()%100;
if(chance<33)
{
mutate_string(r.first);
}
else if(chance<66)
{
mutate_string(r.second);
}
else
{
mutate_string(r.first);
// cout< 1)
{
auto index = algo.begin()+rand()%algo.size();
algo.erase(index);
// return algo;
}
else
{
int index = rand()%algo.size();
mutate_rule(algo[index]);
// return algo;
}
}
algorithm random_algoritm()
{
int length = rand()%10+1;
algorithm ret;
for(int i=0; i& tests)
{
int length = 0;
for(int i=0; i& tests)
{
int ret = 0;
for(int i=0; i& tests)
{
int ret = 0;
for(int i=0; i& tests)
{
const int goal = max_fitness(tests);
int best = -10000;
vector population;
for(int i=0; i<100; i++)
population.push_back(random_algoritm());
int generation = 0;
int last_print = 0;
int start = time(NULL);
pair pop[100];
while(best != goal)
{
generation++;
for(int i=0; i<100; i++)
pop[i]=make_pair(population[i], fitness(population[i], tests));
sort(pop, pop+100,
[](const pair& a, const pair& b)
{return a.second > b.second;});
population[0] = pop[0].first;
for(int i=1; i<100; i++)
{
int chance=rand()%100;
if(chance>i)
{
mutate_algoritm(pop[0].first);
population[i] = pop[0].first;
}
else
population[i] = pop[0].first;
}
const int first = fitness(population[0], tests);
if(first>best)
{
best=first;
}
}
return population[0];
}
algorithm optimize_algorithm(const vector tests, algorithm algo)
{
vector population;
for(int i=0; i<100; i++)
population.push_back(algo);
int generation = 0;
int last_print = 0;
int best = -algo.size();
pair pop[100];
while(generation<10000)
{
generation++;
for(int i=0; i<100; i++)
pop[i]=make_pair(population[i], fitness_opt(population[i], tests));
sort(pop, pop+100,
[](const pair& a, const pair& b)
{return a.second > b.second;});
population[0] = pop[0].first;
for(int i=1; i<100; i++)
{
int chance=rand()%100;
if(chance>i)
{
mutate_algoritm(pop[0].first);
population[i] = pop[0].first;
}
else
population[i] = pop[0].first;
}
const int first = fitness_opt(population[0], tests);
if(first>best)
best=first;
}
return population[0];
}
int main()
{
// const vector tests = {{"||*||", "||||"},
// {"||*|||", "||||||"},
// {"||||*||", "||||||||"},
// {"||||*||||", "||||||||||||||||"}};
// const vector tests = {{"||+||", "||||"},
// {"|+||", "|||"},
// {"|||+|", "||||"}};
// const vector tests = {{"||-||", ""},
// {"|||-|", "||"},
// {"||-|", "|"}};
const vector tests = {{"||+||", "||||"},
{"|||+|", "||||"},
{"|+|", "||"}};
int start = time(NULL);
algorithm un_add = find_algorithm(tests);
cout<<"Found in "<
// в массив pop
for(int i=0; i<100; i++)
pop[i]=make_pair(population[i], fitness(population[i], tests));
// Сортируем массив pop по второму значению
sort(pop, pop+100,
[](const pair& a, const pair& b)
{return a.second > b.second;});
population[0] = pop[0].first;
for(int i=1; i<100; i++)
{
int chance=rand()%100;
if(chance>i)
{
// Алгоритм попадает в population
// либо после мутации
mutate_algoritm(pop[0].first);
population[i] = pop[0].first; //
}
else
population[i] = pop[0].first; // Либо без
}
Ответы
Ответ 1
Навскидку предлагаю такую оптимизацию:
Код вида
for(int i=0; i<100; i++)
pop[i]=make_pair(population[i], fitness(population[i], tests));
sort(pop, pop+100,
[](const pair& a, const pair& b)
{return a.second > b.second;});
population[0] = pop[0].first;
...
заменить на:
pair pop = make_pair(&population[0], fitness(population[0], tests));
for(int i=1; i<100; i++)
{
int ft = fitness(population[i], tests);
if(ft > pop.second)
pop = make_pair(&population[i], ft);
}
algorithm popalg = *pop.first;
population[0] = popalg;
...
Ибо, как я понял по коду, вам надо найти алгоритм с максимальным соответствием тестам.
Для этого достаточно простого поиска максимума, а полноценная сортировка ни к чему.
Кроме того я заменил вектора указателями на них.
А вообще в таких случаях желательно пользоваться профилировщиком. Ибо бывает сложно
без измерений оценить, какую выгоду даст то или иное изменение кода.
