Форум программистов, компьютерный форум CyberForum.ru

C++

Войти
Регистрация
Восстановить пароль
 
OlegRuno
2 / 2 / 0
Регистрация: 28.05.2012
Сообщений: 38
#1

Необходимо ускорить выполнение - C++

18.09.2012, 11:28. Просмотров 981. Ответов 9
Метки нет (Все метки)

Хеллоу эврибади. Проблема такая, имеется 2 вложенных цикла:
C++
1
2
3
4
5
6
7
8
for(int i=0;i<n;i++){
            for(int j=i;j<n;j++){
                flag=false;
                if(mass[j]>mass[i]){mass[i]=mass[j];flag=true; break;}
                
            }
            if (flag==false){mass[i]=0;}
        }
Он не проходит по времени выполнения, для ясности картины покажу условие всей задачи:

Входной файл: input.txt
Выходной файл: output.txt
Время на тест: 1 секунда
В массиве целых чисел необходимо заменить каждое число на другое из этого же массива, ближайшее большее по значению расположенное справа от заменяемого и большее заменяемого, или на ноль при отсутствии такового.

Формат входного файла:

В первой строке входного файла input.txt записано число - количество чисел в наборе. Во второй строке записаны сами числа через один пробел. Количество чисел в наборе не превосходит 100000. Значения всех чисел целые и по модулю не превосходят 2147483647. Гарантируется, что для предложенного набора чисел результат всегда существует. Каждая строка заканчивается переходом на новую строку.
Формат выходного файла:

В первую строку выходного файла output.txt необходимо вывести через один пробел получившиеся значения.

Пример ввода:

5
1 -2 8 3 5
Пример вывода:

8 8 0 5 0

Вот полностью рабочий код:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <stdio.h>
#include <fstream>
 
using namespace std;
 
int main()
{
    int n = 0;
    int *mass;
    mass = new int [100000];
 
    fstream F;
    F.open("input.txt", ios::in);
    F>>n;
    for(int i=0;i<n;i++)
    {
        F>>mass[i];
    }
    F.close();
 
    bool flag = false;
    for(int i=0;i<n;i++)
    {
        flag = false;
        for(int j=i;j<n;j++)
        {
        if(mass[j]>mass[i]) {mass[i]=mass[j]; flag = true; break;}
        }
        if (flag == false) {mass[i]=0;}
    }
 
    F.open("output.txt", ios::out);
    for(int i=0;i<n;i++)
    {
        F<<mass[i]<<" ";
    }
    F<<endl;
    F.close();
 
    return 0;
}
Жду ваши предложения по оптимизации!
Лучшие ответы (1)
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
yekka
384 / 148 / 8
Регистрация: 12.05.2011
Сообщений: 450
18.09.2012, 15:57     Необходимо ускорить выполнение #2
Добавлено через 3 часа 14 минут
попробовал поиграться с ускорением.
результат очень сильно зависит от набора данных.
в зависимости от способа заполнения массива результат различается принципиально:
http://liveworkspace.org/code/24a0f0...2cf2c05329df85
C++
1
array1[i] = array2[i] = rand() % 256 - 128;
Код
Время работы неопитимизированного алгоритма (сек): 5.36
Время работы оптимизированного алгоритма (сек):    0.09
Оба массива совпадают
http://liveworkspace.org/code/d4b70e...40e7922919d8d1
C++
1
array1[i] = array2[i] = rand();
Код
Время работы неопитимизированного алгоритма (сек): 0.06
Время работы оптимизированного алгоритма (сек):    0.13
Оба массива совпадают
Добавлено через 10 минут
т.е., если в массиве много повторов, то мой вариант оказывается на пару порядков быстрее, а если числа в основном уникальные, то время будет несколько больше (в приведенном примере в два раза)
mirror2u
0 / 0 / 0
Регистрация: 12.04.2012
Сообщений: 20
18.09.2012, 16:35     Необходимо ускорить выполнение #3
Цитата Сообщение от yekka Посмотреть сообщение
Добавлено через 3 часа 14 минут
попробовал поиграться с ускорением.
результат очень сильно зависит от набора данных.
в зависимости от способа заполнения массива результат различается принципиально:



Добавлено через 10 минут
т.е., если в массиве много повторов, то мой вариант оказывается на пару порядков быстрее, а если числа в основном уникальные, то время будет несколько больше (в приведенном примере в два раза)
Спасибо, а можно ли решить эту задачу без использования классов, но с той же скоростью выполнения?
yekka
384 / 148 / 8
Регистрация: 12.05.2011
Сообщений: 450
18.09.2012, 16:49     Необходимо ускорить выполнение #4
mirror2u, как-то так:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <ctime>
#include <iostream>
#include <algorithm>
 
const int Size = 500000;
int array1[Size];
int array2[Size];
 
int main() {
    srand(time(NULL));
    int cache[Size];
    int * top = cache;
    for(int i = 0; i < Size; ++i) {
        array1[i] = array2[i] = rand() % 8 - 4;
    }
 
    clock_t time1 = clock();
    for (int i = 0; i < Size; ++i) {
        bool flag = false;
        for (int j = i; j < Size; ++j) {
            if (array1[j] > array1[i]) {
                array1[i] = array1[j];
                flag = true;
                break;
            }
        }
        if (!flag) {
            array1[i] = 0;
        }
    }
    time1 = clock() - time1;
 
    clock_t time2 = clock();
    for (int i = Size - 1; i >= 0; --i) {
        int val = array2[i];
        int * edge = std::lower_bound(cache, top, val,
                [](int lhs, int rhs)-> bool { return lhs > rhs; });
        if (edge == cache) {
            array2[i] = 0;
        } else {
            array2[i] = *(edge - 1);
        }
        *edge = val;
        top = ++edge;
    }
    time2 = clock() - time2;
 
    bool correct = true;
    for (int i = 0; i < Size; ++i) {
        if (array1[i] != array2[i]) {
            correct = false;
            break;
        }
    }
 
    std::cout << "Время работы неопитимизированного алгоритма (сек): ";
    std::cout << ((double)time1)/CLOCKS_PER_SEC << std::endl;
    std::cout << "Время работы оптимизированного алгоритма (сек):    ";
    std::cout << ((double)time2)/CLOCKS_PER_SEC << std::endl;
    if (correct) {
        std::cout << "Оба массива совпадают" << std::endl;
    } else {
        std::cout << "Лажа" << std::endl;
    }
}
#pragma
Временно недоступен
 Аватар для #pragma
952 / 223 / 6
Регистрация: 12.04.2009
Сообщений: 921
18.09.2012, 20:56     Необходимо ускорить выполнение #5
Алгоритм
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
    for (int i = 0; i < Size; ++i) {
        bool flag = false;
        for (int j = i; j < Size; ++j) {
            if (array1[j] > array1[i]) {
                array1[i] = array1[j];
                flag = true;
                break;
            }
        }
        if (!flag) {
            array1[i] = 0;
        }
    }
работает неправильно.
Вот вывод нескольких запусков программы
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <ctime>
#include <iostream>
#include <algorithm>
#include <fstream>
 
const int Size = 10;
int array1[Size];
 
int main() {
    srand((unsigned)time(NULL));
 
    for(int i = 0; i < Size; ++i) {
        array1[i] =  rand();
    }
 
    clock_t time1 = clock();
    for (int i = 0; i < Size; ++i) {
        bool flag = false;
        for (int j = i; j < Size; ++j) {
            if (array1[j] > array1[i]) {
                array1[i] = array1[j];
                flag = true;
                break;
            }
        }
        if (!flag) {
            array1[i] = 0;
        }
    }
    time1 = clock() - time1;
 
    std::fstream F;
    F.open("output.txt", std::ios::out);
    for(int i=0;i<Size;i++)
    {
        F<<array1[i]<<"\n";
    }
    F<<std::endl;
    F.close();
 
 
    std::cout << "Время работы неопитимизированного алгоритма (сек): ";
    std::cout << ((double)time1)/CLOCKS_PER_SEC << std::endl;
 
}
(в столбик, чтобы удобнее читать было для больших массивов)
Код
0
1358406589
1786222289
889275314
1786222289
1786222289
0
1106820397
1106820397
0
Код
964432724
1078747914
1422710114
1422710114
1986008129
0
0
649280754
649280754
0
Вывод неверный, судя по условию (таких вариантов не должно быть вообще).

Добавлено через 2 минуты
yekka, кстати, какой у Вас компилятор? У меня на gcc 4.4.3 с включенной опцией -std=c++0x Ваш пример не компилится, видимо, из-за лямбда-функции.
yekka
384 / 148 / 8
Регистрация: 12.05.2011
Сообщений: 450
18.09.2012, 21:03     Необходимо ускорить выполнение #6
Сообщение было отмечено автором темы, экспертом или модератором как ответ
Цитата Сообщение от #pragma Посмотреть сообщение
Вывод неверный, судя по условию
не вижу ничего неверного

Код
gcc version 4.6.3
#pragma
Временно недоступен
 Аватар для #pragma
952 / 223 / 6
Регистрация: 12.04.2009
Сообщений: 921
18.09.2012, 21:05     Необходимо ускорить выполнение #7
Тогда я что-то не пойму, как большее число может быть после меньшего? Ведь оно должно быть крайним слева, и заполнять все позиции до следующего 0.
А, так
ближайшее большее по значению расположенное справа от заменяемого
это не значит самое большее справа, кажись, я опять условие проглядел ))

В таком случае неоптимизированный алгоритм на моей машине и 100000 элементов отрабатывает за 0.01 секунды, это если просто rand без интервала...
yekka
384 / 148 / 8
Регистрация: 12.05.2011
Сообщений: 450
18.09.2012, 21:10     Необходимо ускорить выполнение #8
#pragma,
Код
1 5 3 4 9 7
должно превратиться в
Код
5 9 4 9 0 0
mirror2u
0 / 0 / 0
Регистрация: 12.04.2012
Сообщений: 20
18.09.2012, 21:36     Необходимо ускорить выполнение #9
Цитата Сообщение от yekka Посмотреть сообщение
mirror2u, как-то так:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <ctime>
#include <iostream>
#include <algorithm>
 
const int Size = 500000;
int array1[Size];
int array2[Size];
 
int main() {
    srand(time(NULL));
    int cache[Size];
    int * top = cache;
    for(int i = 0; i < Size; ++i) {
        array1[i] = array2[i] = rand() % 8 - 4;
    }
 
    clock_t time1 = clock();
    for (int i = 0; i < Size; ++i) {
        bool flag = false;
        for (int j = i; j < Size; ++j) {
            if (array1[j] > array1[i]) {
                array1[i] = array1[j];
                flag = true;
                break;
            }
        }
        if (!flag) {
            array1[i] = 0;
        }
    }
    time1 = clock() - time1;
 
    clock_t time2 = clock();
    for (int i = Size - 1; i >= 0; --i) {
        int val = array2[i];
        int * edge = std::lower_bound(cache, top, val,
                [](int lhs, int rhs)-> bool { return lhs > rhs; });
        if (edge == cache) {
            array2[i] = 0;
        } else {
            array2[i] = *(edge - 1);
        }
        *edge = val;
        top = ++edge;
    }
    time2 = clock() - time2;
 
    bool correct = true;
    for (int i = 0; i < Size; ++i) {
        if (array1[i] != array2[i]) {
            correct = false;
            break;
        }
    }
 
    std::cout << "Время работы неопитимизированного алгоритма (сек): ";
    std::cout << ((double)time1)/CLOCKS_PER_SEC << std::endl;
    std::cout << "Время работы оптимизированного алгоритма (сек):    ";
    std::cout << ((double)time2)/CLOCKS_PER_SEC << std::endl;
    if (correct) {
        std::cout << "Оба массива совпадают" << std::endl;
    } else {
        std::cout << "Лажа" << std::endl;
    }
}
Большое спасибо yekka всё работает, ты как всегда выручаешь) Но если тебе не сложно, закомментируй пожалуйста строки, начиная с 34 и заканчивая 45. И ещё вопрос. У меня при компиляции функция clock() не выводит время выполнения: "преобразование "time_t" в "unsigned int", возможна потеря данных"? Подскажи пожалуйста в чём дело?
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
18.09.2012, 22:09     Необходимо ускорить выполнение
Еще ссылки по теме:

C++ Ускорить обход дерева
C++ Ускорить выполнение программы как минимум в два раза
Ускорить выполнение расчета CRC32 C++
C++ Ускорить работу программы
C++ Как ускорить цикл?

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
yekka
384 / 148 / 8
Регистрация: 12.05.2011
Сообщений: 450
18.09.2012, 22:09     Необходимо ускорить выполнение #10
При решении задачи в лоб мы перебираем массив слева направо и нам постоянно не хватает информации о его правом хвосте, поэтому нам постоянно приходится запускать еще внутренний цикл для поиска ближайшего числа больше данного. Идея моего подхода в том, чтобы обрабатывать массив справа налево в один проход. Для этого нам нужно как-то хранить информацию об уже обработанном участке массива. Нас интересуют достаточно большие значения, расположенные достаточно близко от рассматриваемой позиции. Поэтому будем сохранять информацию об уже пройденном участке в виде отсортированного по убыванию массива cache, в начале которого будут находиться большие, но далекие значения, а в конце -- близкие, но не очень большие. И в зависимости от того, чему равен текущий элемент массива, мы возьмем из кеша самый близкий из тех элементов, что больше текущего. При этом прежде чем переходить к следующим элементам, сам кеш тоже надо будет обновить: все элементы, которые меньше текущего, станут более не нужными, так как они будут меньше и дальше, чем только что обработанный элемент. Для этого мы присваиваем новое значение переменной top, указывающей на дальний конец кеша.
Т.е., если кеш представляет из себя что-то вроде
Код
10 4 0 -6 -10 -12
и нам на обработку приходит элемент -9, то мы ему присваиваем значение -6, а кеш превращается в
Код
10 4 0 -6 -9
если теперь получаем -20, то присваиваем -9 и кеш превращается в
Код
10 4 0 -6 -9 -20
если теперь получаем 15, то присваиваем 0 и кеш превращается в
Код
15
Yandex
Объявления
18.09.2012, 22:09     Необходимо ускорить выполнение
Ответ Создать тему
Опции темы

Текущее время: 22:53. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru