Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
 
Рейтинг 4.75/4: Рейтинг темы: голосов - 4, средняя оценка - 4.75
18 / 18 / 10
Регистрация: 19.05.2015
Сообщений: 704
1

Оптимизировать код

10.11.2016, 19:47. Просмотров 644. Ответов 21
Метки нет (Все метки)

Первое число входного потока - количество чисел
Дальше идут те самые числа
Надо найти кол-во пар чисел, для которых выполняется nums[i] <= nums[j] && nums[i] >= 0.9*nums[j] и наоборот
Код готов, работает, но не хватает времени на выполнение задачи с большими объемами входа (до 1 000 000 000)
Помогите оптимизировать
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
using namespace std;
 
int main()
{
    int count;
    long answer = 0;;
 
    cin >> count;
    int* nums = new int[count];
    for (int i = 0; i < count; i++) {
        cin >> nums[i];
        for (int j = 0; j < i; j++) {
            if ((nums[i] <= nums[j] && nums[i] >= 0.9*nums[j]) || (nums[j] <= nums[i] && nums[j] >= 0.9*nums[i])) {
                answer++;
            }
        }
    }
 
    cout << answer;
    cin >> count;
    return 0;
}
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
10.11.2016, 19:47
Ответы с готовыми решениями:

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

Нужно оптимизировать код
Нужно максимально сократить код #include &lt;iostream&gt; using namespace std; int main(int...

Нужно оптимизировать код
Вобщем код не принемает сайт, немного нагружает и по времени не проходит задание Август и...

Исправить и оптимизировать код
нужна помощь по исправлению ошибок Написал программу она работает все отлично но препод сказал...

21
2681 / 1853 / 552
Регистрация: 05.06.2014
Сообщений: 5,343
10.11.2016, 20:02 2
Предварительно отсортировать входной массив, заменить nums[i] <= nums[j] на i<j.
0
18 / 18 / 10
Регистрация: 19.05.2015
Сообщений: 704
10.11.2016, 20:26  [ТС] 3
Цитата Сообщение от Renji Посмотреть сообщение
Предварительно отсортировать входной массив
Как это можно реализовать с минимальным количеством действий в циклах?
Точнее, будет ли оптимальный такой вариант: найти в массиве место, куда вставить, до него не трогать, после него все сдвинуть через переменную?
0
2681 / 1853 / 552
Регистрация: 05.06.2014
Сообщений: 5,343
10.11.2016, 22:21 4
Цитата Сообщение от Игорь2001 Посмотреть сообщение
Как это можно реализовать с минимальным количеством действий в циклах?
std::sort(nums,nums+count). Или вдумчиво читать то же "Искусство Программирования" Дональда Кнута, где разбираются в том числе и методы сортировки.
1
18 / 18 / 10
Регистрация: 19.05.2015
Сообщений: 704
10.11.2016, 22:31  [ТС] 5
Цитата Сообщение от Renji Посмотреть сообщение
std::sort(nums,nums+count)
Прикол в том, что сортировать готовый массив - значит выходить сразу из всех циклов, потом еще сортировка время, а потом новые циклы, то есть логичнее делать это более динамически, сразу вставляя элемент куда надо
Но попробую, может сработает
0
2681 / 1853 / 552
Регистрация: 05.06.2014
Сообщений: 5,343
10.11.2016, 22:39 6
Цитата Сообщение от Игорь2001 Посмотреть сообщение
Прикол в том, что сортировать готовый массив - значит выходить сразу из всех циклов, потом еще сортировка время, а потом новые циклы, то есть логичнее делать это более динамически, сразу вставляя элемент куда надо
Прикол в том, что прежде чем рассуждать о логике, надо сесть и прикинуть на пальцах вычислительную сложность. Вставка элемента в середину массива - линейное время (потому что все что после вставки надо сдвинуть). Число вставок у вас растет опять-же линейно. Итого, время сожранное вашей "логичной" сортировкой растет по квадрату. Тогда как у нормальных людей оно N*log(N). Если же вдумчиво читать Кнута и (очень) щедро жертвовать память Богу-Машине, можно и линейное время попробовать выжать.
0
What a waste!
1576 / 1277 / 171
Регистрация: 21.04.2012
Сообщений: 2,677
10.11.2016, 22:40 7
Цитата Сообщение от Игорь2001 Посмотреть сообщение
Прикол в том, что сортировать готовый массив - значит выходить сразу из всех циклов, потом еще сортировка время, а потом новые циклы, то есть логичнее делать это более динамически, сразу вставляя элемент куда надо
У предложенного варианта с сортировкой асимптотическая сложность меньше, чем в оригинале, так что...
0
18 / 18 / 10
Регистрация: 19.05.2015
Сообщений: 704
10.11.2016, 22:40  [ТС] 8
Цитата Сообщение от Renji Посмотреть сообщение
i<j
а если там подряд пять единиц? Оно ж посчитает как 0 вообще
0
2681 / 1853 / 552
Регистрация: 05.06.2014
Сообщений: 5,343
10.11.2016, 22:44 9
Цитата Сообщение от Игорь2001 Посмотреть сообщение
а если там подряд пять единиц? Оно ж посчитает как 0 вообще
Какая разница сколько там единиц? Если массив отсортирован, элемент с меньшим индексом по определению не может быть больше элемента с большим индексом. И выражение nums[i] <= nums[j] эквивалентно выражению i<j. Дальше вас должно осенить что коли так, то for (int j = 0; можно заменить на for (int j = i+1;, а сравнение i<j вообще выкинуть.
0
18 / 18 / 10
Регистрация: 19.05.2015
Сообщений: 704
10.11.2016, 22:52  [ТС] 10
С учетом всего сказанного вышел такой код
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
#include <iostream>
using std::cin;
using std::cout;
#include <algorithm>
using std::sort;
 
int main()
{
    int count;
    int answer = 0;;
 
    cin >> count;
    int* nums = new int[count];
    for (int i = 0; i < count; i++) {
        cin >> nums[i];
    }
 
    sort(nums, nums + count);
 
    for (int i = 0; i < count; i++) {
        for (int j = i + 1; j < count; j++) {
            if (nums[i] >= 0.9*nums[j]) {
                answer++;
            }
        }
    }
 
    cout << answer;
    return 0;
}
Но максимальное время выполнения с большими числами все равно превышается
0
2681 / 1853 / 552
Регистрация: 05.06.2014
Сообщений: 5,343
10.11.2016, 22:54 11
Ох... for (int j = i + 1; j < count; j++) for (int j = i + 1; j < count && nums[i] >= 0.9*nums[j]; j++)
0
0 / 0 / 0
Регистрация: 10.11.2016
Сообщений: 12
10.11.2016, 22:58 12
Дан массив А(20). Найти максимальный элемент среди положительных элементов массива А и сформировать массив Р(20), у которого вначале расположены элементы массива А с нечетными индексами, затем с четными.
Как сделать на с++? голова не варит уже(((
0
18 / 18 / 10
Регистрация: 19.05.2015
Сообщений: 704
10.11.2016, 23:06  [ТС] 13
Цитата Сообщение от Renji Посмотреть сообщение
for (int j = i + 1; j < count && nums[i] >= 0.9*nums[j]; j++)
Ничего не изменилось....
Вопросик по-ходу: по быстродействию вложенные ифы дольше логического и?
0
What a waste!
1576 / 1277 / 171
Регистрация: 21.04.2012
Сообщений: 2,677
10.11.2016, 23:08 14
Игорь2001, можно так же заметить, что если nums[i] >= 0.9*nums[j], то и nums[i + 1] >= 0.9*nums[j]
0
18 / 18 / 10
Регистрация: 19.05.2015
Сообщений: 704
10.11.2016, 23:13  [ТС] 15
Цитата Сообщение от gray_fox Посмотреть сообщение
можно так же заметить
Чуть подробнее, я не вижу, откуда это вытекает
Цитата Сообщение от gray_fox Посмотреть сообщение
nums[i] >= 0.9*nums[j], то и nums[i + 1] >= 0.9*nums[j]
То есть внешний цикл можно не i++, а i +=2 ?
0
What a waste!
1576 / 1277 / 171
Регистрация: 21.04.2012
Сообщений: 2,677
10.11.2016, 23:25 16
Игорь2001, nums[i] <= nums[i + 1] && nums[i] >= 0.9*nums[j] => nums[i + 1] >= 0.9*nums[j].

Добавлено через 6 минут
Цитата Сообщение от Игорь2001 Посмотреть сообщение
То есть внешний цикл можно не i++, а i +=2 ?
Нет, можно j начинать не с i+1, а с предыдущего j.
0
18 / 18 / 10
Регистрация: 19.05.2015
Сообщений: 704
10.11.2016, 23:26  [ТС] 17
Цитата Сообщение от gray_fox Посмотреть сообщение
Нет, можно j не начинать с i+1, а с предыдущего j.
не понял
0
2681 / 1853 / 552
Регистрация: 05.06.2014
Сообщений: 5,343
10.11.2016, 23:30 18
Цитата Сообщение от Игорь2001 Посмотреть сообщение
Ничего не изменилось....
Ну, тады попробуйте:
C++
1
2
for (int i = 0; i < count; i++)
        answer+=std::upper_bound(nums,nums+count,nums[i]*10/9)-(nums+i);
0
What a waste!
1576 / 1277 / 171
Регистрация: 21.04.2012
Сообщений: 2,677
10.11.2016, 23:33 19
Игорь2001, примерно так
C++
1
2
3
4
for (int i = 0, j = 1; i < count - 1; ++i) {
   for ( ; j < count && nums[i] >= 0.9*nums[j]; ++j);
   answer += j - i - 1;
}
1
18 / 18 / 10
Регистрация: 19.05.2015
Сообщений: 704
10.11.2016, 23:46  [ТС] 20
Уже лучше, с большими числами успевает, сейчас еще с типами данных поработаю, вроде не влазит иногда...
А можете чуть-чуть логику объяснить, пожалуйста

Добавлено через 3 минуты
Да, для ответа надо было лонг

Добавлено через 3 минуты
Цитата Сообщение от gray_fox Посмотреть сообщение
C++
1
2
3
4
for (int i = 0, j = 1; i < count - 1; ++i) {
    for ( ; j < count && nums[i] >= 0.9*nums[j]; ++j);
    answer += j - i - 1;
}
Можете, пожалуйста примерно объяснить работу этого кода
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
10.11.2016, 23:46

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

Оптимизировать и минимализировать код
Cделал легкую прогу. Понимаю логики 0 в коде. Можете помочь оптимизировать код? А заодно и сделать...

Помогите оптимизировать код
Здравствуйте! Помогите, пожалуйста, оптимизировать его: main.cpp #include &quot;main.h&quot;...

Как оптимизировать код?
Как оптимизировать код, чтобы работала программа быстрее #include &lt;iostream&gt; #include &lt;fstream&gt;...

Помогите оптимизировать код
Помогите пожалуйста разобраться, хотелось бы чтобы это прграммка наконец-то заработала. Задача...


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

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2020, vBulletin Solutions, Inc.