Справочник функций

Ваш аккаунт

Войти через: 
Забыли пароль?
Регистрация
Информацию о новых материалах можно получать и без регистрации:

Почтовая рассылка

Подписчиков: -1
Последний выпуск: 19.06.2015

проблема с использованием класса vector

9.0K
30 января 2007 года
RedNN
33 / / 15.08.2006
Есть вектор (класс vector из std) небольших структур. Программа проводит попарное сравнение элементов вектора и ставит пометки (на элементах).
Если вектор не большой (10000-20000 элементов), то программа работает быстро. Если вектор увеличить примерно до 150000 элементов, то перебор начинает жутко тормозить.
С чем это связано? (это скорее особенности vector или косяк в проге)
309
30 января 2007 года
el scorpio
1.1K / / 19.09.2006
Косяк в проге естественно.
Полторы сотни тысяч элементов - неслабо.
Первый вопрос в любом подобном случае - а нельзя ли упростить задачу?
Почти всегда, ежели это не "академическое" решение единственным требуемым способом, находится множество других путей.
11K
30 января 2007 года
.nornad
125 / / 04.01.2007
Ты бы хоть пример кода перебора привёл, что ли. Ну или сказал, как перебираешь. Для нормального перебора используют итераторы. Ежели ты вместо итератора перебираешь тупо через индексы, да ещё и количество элементов постоянно определяешь, то можно алгоритм соптимизировать.
Кстати, что значит "жутко тормозит"? Если сравнить приведённые тобоючисла (15 тысяч и 150 тысяч), то напрашивается мысль, что на большом "тормозить" должно раз в 10 сильнее, чем на малом. ;)
63
30 января 2007 года
Zorkus
2.6K / / 04.11.2006
Цитата: .nornad
Ты бы хоть пример кода перебора привёл, что ли. Ну или сказал, как перебираешь. Для нормального перебора используют итераторы. Ежели ты вместо итератора перебираешь тупо через индексы, да ещё и количество элементов постоянно определяешь, то можно алгоритм соптимизировать.

Думаю, что тут наилучшей оптимизацией может быть использование другого контейнера, если автор подробнее расскажет задачу и покажет код.

Цитата: .nornad

Кстати, что значит "жутко тормозит"? Если сравнить приведённые тобоючисла (15 тысяч и 150 тысяч), то напрашивается мысль, что на большом "тормозить" должно раз в 10 сильнее, чем на малом. ;)


Ну если смотреть на слова автора "попарное сравнение элементов", то скорее, напрашивается мысль, что в 100 раз;)

9.0K
30 января 2007 года
RedNN
33 / / 15.08.2006
Код выглядит примерно так:
Код:
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)
{
    ...
}
3
30 января 2007 года
Green
4.8K / / 20.01.2000
Жуть...
O(n^2 * m) - это как минимум (n - размерность W1, m - размерность vec1 или vec2).
А проще никак нельзя было сделать?
Проблема не в векторе, даже не в реализации, а в самом алгоритме.
Что должен делать этот код?
Что делает func2, какое там сравнение?
Зачем сравнивать попарно?
320
31 января 2007 года
m_Valery
1.0K / / 08.01.2007
Выложи условие всей задачи.Я,например,тоже не понял что тут происходит. Это "реальная" задача или упражнение для ума?Как именно
идет сравнение( код ), и про структуры обьясни зачем?А так тебе
вряд ли помогут...
9.0K
31 января 2007 года
RedNN
33 / / 15.08.2006
Проект - реальный :)
Задача - работа с путями в графе. Есть ориентированный граф. В нём выделяется вершина - корень. Из корня строятся всевозможные пути к остальным вершинам и загоняются в список. Список определённым образом сортируется. Для всех путей строится список ссылок вниз по списку на так называемые "совместимые". Совместимые пути - один не входит в дугой и взаимная проективность.

код подробнее:
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;
}
3
31 января 2007 года
Green
4.8K / / 20.01.2000
Код - тихий ужас!
Переменные и функции должны иметь значимые имена, чтоб посмотрев на название можно было понять для чего они.
Объясни описательно, для чего и что делают (внутри) функции Func1 и Func2? Подробно!
Сдается мне, что твоя проблема в непонимании или в неумении сформулировать того, что они должны делать.
Например, поиск пересечения двух путей (первая вложенность циклов в Func1) можно найти за O(n), а не за O(n^2).
Реклама на сайте | Обмен ссылками | Ссылки | Экспорт (RSS) | Контакты
Добавить статью | Добавить исходник | Добавить хостинг-провайдера | Добавить сайт в каталог