struct s1
{
vector < int > vec1;
vector < int > vec2;
}
...
vector < s1 > W1;
...
void func1()
{
long ws = W1.size();
for(long i=0; i<ws-1; i++)
{
for(long j=i+1; j<ws; j++)
{
if(func2(&(W1.vec1), &(W1[j].vec1)))
W1.vec2.push_back(j);
}
}
}
bool func2(vector < int >* v1, vector < int >* v2)
{
...
}
проблема с использованием класса vector
Если вектор не большой (10000-20000 элементов), то программа работает быстро. Если вектор увеличить примерно до 150000 элементов, то перебор начинает жутко тормозить.
С чем это связано? (это скорее особенности vector или косяк в проге)
Полторы сотни тысяч элементов - неслабо.
Первый вопрос в любом подобном случае - а нельзя ли упростить задачу?
Почти всегда, ежели это не "академическое" решение единственным требуемым способом, находится множество других путей.
Кстати, что значит "жутко тормозит"? Если сравнить приведённые тобоючисла (15 тысяч и 150 тысяч), то напрашивается мысль, что на большом "тормозить" должно раз в 10 сильнее, чем на малом. ;)
Цитата: .nornad
Ты бы хоть пример кода перебора привёл, что ли. Ну или сказал, как перебираешь. Для нормального перебора используют итераторы. Ежели ты вместо итератора перебираешь тупо через индексы, да ещё и количество элементов постоянно определяешь, то можно алгоритм соптимизировать.
Думаю, что тут наилучшей оптимизацией может быть использование другого контейнера, если автор подробнее расскажет задачу и покажет код.
Цитата: .nornad
Кстати, что значит "жутко тормозит"? Если сравнить приведённые тобоючисла (15 тысяч и 150 тысяч), то напрашивается мысль, что на большом "тормозить" должно раз в 10 сильнее, чем на малом. ;)
Ну если смотреть на слова автора "попарное сравнение элементов", то скорее, напрашивается мысль, что в 100 раз;)
Код выглядит примерно так:
O(n^2 * m) - это как минимум (n - размерность W1, m - размерность vec1 или vec2).
А проще никак нельзя было сделать?
Проблема не в векторе, даже не в реализации, а в самом алгоритме.
Что должен делать этот код?
Что делает func2, какое там сравнение?
Зачем сравнивать попарно?
идет сравнение( код ), и про структуры обьясни зачем?А так тебе
вряд ли помогут...
Задача - работа с путями в графе. Есть ориентированный граф. В нём выделяется вершина - корень. Из корня строятся всевозможные пути к остальным вершинам и загоняются в список. Список определённым образом сортируется. Для всех путей строится список ссылок вниз по списку на так называемые "совместимые". Совместимые пути - один не входит в дугой и взаимная проективность.
код подробнее:
struct way - структура-путь. Ways - список путей. MainFunc() - собственно функция с перебором. Func1() - проверка вхождения одного пути в другой. Func2() - проверка проективности.
Код:
struct way
{
vector < int > tops;
vector < int > neighbours;
...
};
...
vector < way > Ways;
...
void MainFunc()
{
if(Ways.size() == 0)
return;
long WS = Ways.size();
for(long i=0; i<WS-1; i++)
{
for(long j=i+1; j<WS; j++)
{
if(Func1(&(Ways.tops), &(Ways[j].tops))==0)
continue;
if(Func2(&(Ways.tops), &(Ways[j].tops)))
continue;
Ways.neighbours.push_back(j);
}
}
}
int Func1(vector <int>* way1, vector <int>* way2)
{
if(way1 == way2) return 0;
int res=0;
int iw1=0;
int iw2=0;
for(int i=0; i<(*way1).size(); i++)
{
for(int j=0; j<(*way2).size(); j++)
{
if((*way1) == (*way2)[j])
{
iw1 = i;
iw2 = j;
break;
}
}
if(j!=(*way2).size())
break;
}
if(iw1==0 || iw2==0)
{
int j1=0;
bool g1=true;
do
{
if((*way1)[j1+iw1]!=(*way2)[j1+iw2])
{
g1=false;
break;
}
j1++;
}
while(j1+iw1<(*way1).size() && j1+iw2<(*way2).size());
if(g1)
{
if (
j1+iw1 == (*way1).size()
&&
iw1>=iw2
)
{
res = -1;
}
if (
j1+iw2 == (*way2).size()
&&
iw2>=iw1
)
{
res = 1;
}
}
}
return res;
}
bool Func2(vector <int>* way1, vector <int>* way2)
{
int max1=0;
int min1=0;
int max2=0;
int min2=0;
for(int i=0; i<(*way1).size()-1; i++)
{
for(int j=0; j<(*way2).size()-1; j++)
{
if((*way1)<(*way1)[i+1])
{
min1=(*way1);
max1=(*way1)[i+1];
}
else
{
min1=(*way1)[i+1];
max1=(*way1);
}
if((*way2)[j]<(*way2)[j+1])
{
min2=(*way2)[j];
max2=(*way2)[j+1];
}
else
{
min2=(*way2)[j+1];
max2=(*way2)[j];
}
if (
(min1<min2 && min2<max1 && max1<max2)
||
(min2<min1 && min1<max2 && max2<max1)
)
{
return false;
}
}
}
return true;
}
{
vector < int > tops;
vector < int > neighbours;
...
};
...
vector < way > Ways;
...
void MainFunc()
{
if(Ways.size() == 0)
return;
long WS = Ways.size();
for(long i=0; i<WS-1; i++)
{
for(long j=i+1; j<WS; j++)
{
if(Func1(&(Ways.tops), &(Ways[j].tops))==0)
continue;
if(Func2(&(Ways.tops), &(Ways[j].tops)))
continue;
Ways.neighbours.push_back(j);
}
}
}
int Func1(vector <int>* way1, vector <int>* way2)
{
if(way1 == way2) return 0;
int res=0;
int iw1=0;
int iw2=0;
for(int i=0; i<(*way1).size(); i++)
{
for(int j=0; j<(*way2).size(); j++)
{
if((*way1) == (*way2)[j])
{
iw1 = i;
iw2 = j;
break;
}
}
if(j!=(*way2).size())
break;
}
if(iw1==0 || iw2==0)
{
int j1=0;
bool g1=true;
do
{
if((*way1)[j1+iw1]!=(*way2)[j1+iw2])
{
g1=false;
break;
}
j1++;
}
while(j1+iw1<(*way1).size() && j1+iw2<(*way2).size());
if(g1)
{
if (
j1+iw1 == (*way1).size()
&&
iw1>=iw2
)
{
res = -1;
}
if (
j1+iw2 == (*way2).size()
&&
iw2>=iw1
)
{
res = 1;
}
}
}
return res;
}
bool Func2(vector <int>* way1, vector <int>* way2)
{
int max1=0;
int min1=0;
int max2=0;
int min2=0;
for(int i=0; i<(*way1).size()-1; i++)
{
for(int j=0; j<(*way2).size()-1; j++)
{
if((*way1)<(*way1)[i+1])
{
min1=(*way1);
max1=(*way1)[i+1];
}
else
{
min1=(*way1)[i+1];
max1=(*way1);
}
if((*way2)[j]<(*way2)[j+1])
{
min2=(*way2)[j];
max2=(*way2)[j+1];
}
else
{
min2=(*way2)[j+1];
max2=(*way2)[j];
}
if (
(min1<min2 && min2<max1 && max1<max2)
||
(min2<min1 && min1<max2 && max2<max1)
)
{
return false;
}
}
}
return true;
}
Переменные и функции должны иметь значимые имена, чтоб посмотрев на название можно было понять для чего они.
Объясни описательно, для чего и что делают (внутри) функции Func1 и Func2? Подробно!
Сдается мне, что твоя проблема в непонимании или в неумении сформулировать того, что они должны делать.
Например, поиск пересечения двух путей (первая вложенность циклов в Func1) можно найти за O(n), а не за O(n^2).