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

нужна оптимизация приложения - C++

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 14, средняя оценка - 4.64
SpecBM
20 / 20 / 5
Регистрация: 16.01.2010
Сообщений: 61
06.04.2012, 14:26     нужна оптимизация приложения #1
Одной ночью коту Мурзику приснилось, что он судья на математических соревнованиях крыс. Соревнования проводятся среди N команд по K крыс в каждой. Соревнования проводятся в К раундов, в каждом из которых представитель команды называет число. Побеждает та команда, у которой произведение всех чисел наибольшее. Почему крысы не называют каждый раз максимально возможное число? На то они и крысы, что в отличии от Мурзика, обделены интеллектом. Но и Мурзик понимает, что сам подсчитать результат не сможет из-за недостачи математических способностей и поэтому просит вашей помощи.
Технические условия
Входные данные
Первая строка содержит два целых числа N и K (0 < N ≤ 20, 0 < K ≤ 100000). Следующие К строк содержат по N чисел, которые называют представители команд. Причем крысы, как представители образованного вида, знают только 32-битовые знаковые числа.
Выходные данные
Номер команды, выигравшей соревнования. Если несколько команд имеют одинаковые результаты, то побеждает та, у которой больше номер.

Лимит времени: 2 секунды
Лимит памяти: 64 MB


вот решение:
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
#include <iostream>
#include <fstream>
 
using namespace std; 
 
int main() {
   ifstream inf("input.txt");
   ofstream outf("output.txt");
   int k, n, i, j;
   float *a, t;
   inf >> n;
   inf >> k;
   a = new float[n];
   for(i = 0; i < n; i++) *(a + i) = 1;
   
   for (j = 0; j < k; j++)
       for (i = 0; i < n; i++){
           inf >> t;
           *(a + i) *= t;
       }
   t = *a;
   j = 1;
   cout << endl;
   for (i = 0; i < n; i++) 
       if (*(a + i) >= t) {
           t = *(a + i);
           j = i+1;
        }
   inf.close();
   outf<< j <<"\n";
   outf.close();
   return 0;
}
задача проходит 16 тестов из 20
на четырех тестах не хватает времени (2 сек). как решить эту проблему?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
06.04.2012, 14:26     нужна оптимизация приложения
Посмотрите здесь:

Оптимизация C++
C++ Оптимизация вычислений
оптимизация кода C++
Оптимизация программы C++
C++ Оптимизация кода (C++)
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Nekto
342 / 287 / 10
Регистрация: 23.03.2012
Сообщений: 838
06.04.2012, 14:31     нужна оптимизация приложения #2
через файл надо?
SpecBM
20 / 20 / 5
Регистрация: 16.01.2010
Сообщений: 61
06.04.2012, 14:39  [ТС]     нужна оптимизация приложения #3
Цитата Сообщение от Nekto Посмотреть сообщение
через файл надо?
да...
Nekto
342 / 287 / 10
Регистрация: 23.03.2012
Сообщений: 838
06.04.2012, 14:45     нужна оптимизация приложения #4
Цитата Сообщение от SpecBM Посмотреть сообщение
да...
Это на сайте каком-то?
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
#include <cstdio>
int main() 
{
   FILE *f=fopen("input.txt","r");
   int N, K;
   fscanf(f,"%d%d",&N,&K);
   long long a[20]={1};
   int temp;
   for (int i=0;i<K;i++)
    {
     for (int j=0;j<N;j++)
      {
       fscanf(f,"%d",&temp);
       a[j]*=temp;
      }
    }
   fclose(f);
   int max_i=0;
   long long max=a[0];
   for (int i=1;i<N;i++)
    if (a[i]>=max) { max=a[i]; max_i=i; }
   f=fopen("output.txt","w");
   fprintf(f,"%d",max_i+1);
   fclose(f);
   return 0;
}
Deviaphan
Делаю внезапно и красиво
Эксперт C++
 Аватар для Deviaphan
1283 / 1217 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
06.04.2012, 15:20     нужна оптимизация приложения #5
Цитата Сообщение от Nekto Посмотреть сообщение
a[j]*=temp;
При j > 0 расчёт не верен.

Добавлено через 58 секунд
Цитата Сообщение от Nekto Посмотреть сообщение
a[20]
При N > 20 расчёт не верен.

Добавлено через 2 минуты
Цитата Сообщение от Nekto Посмотреть сообщение
long long a
Не говоря о том, что достаточно трёх умножений, чтобы произошло переполнение даже такого большого числа.
castaway
Эксперт С++
4846 / 2985 / 368
Регистрация: 10.11.2010
Сообщений: 11,026
Записей в блоге: 10
Завершенные тесты: 1
06.04.2012, 15:20     нужна оптимизация приложения #6
Цитата Сообщение от Deviaphan Посмотреть сообщение
При N > 20 расчёт не верен.
Первая строка содержит два целых числа N и K (0 < N ≤ 20, ...
Deviaphan
Делаю внезапно и красиво
Эксперт C++
 Аватар для Deviaphan
1283 / 1217 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
06.04.2012, 15:20     нужна оптимизация приложения #7
Цитата Сообщение от SpecBM Посмотреть сообщение
N ≤ 20
Это я видел, но для количества всё-таки про константу упомянул.)
Kuzia domovenok
 Аватар для Kuzia domovenok
1883 / 1738 / 116
Регистрация: 25.03.2012
Сообщений: 5,907
Записей в блоге: 1
06.04.2012, 15:47     нужна оптимизация приложения #8
попробуй замени умножение на сложение степеней двойки
попробуй округлять вводимые числа, например
d00125=b01111101~=10000000=1<<7
d00070=b01000110~=01000000=1<<6
их произведение равно 1<<13
в среднем это не изменит победителя. максимальное произведение получит погрешность, но останется максимальным

правда тут про знаки надо помнить. знаки всё очень сильно портят.
Ну как? Разве не финт ушами?
Nekto
342 / 287 / 10
Регистрация: 23.03.2012
Сообщений: 838
06.04.2012, 16:00     нужна оптимизация приложения #9
Цитата Сообщение от Deviaphan Посмотреть сообщение
При j > 0 расчёт не верен.
Почему?
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
06.04.2012, 16:14     нужна оптимизация приложения #10
Можно просто С-шное чтение использовать, потоки долговато работают.
SpecBM
20 / 20 / 5
Регистрация: 16.01.2010
Сообщений: 61
06.04.2012, 16:32  [ТС]     нужна оптимизация приложения #11
Цитата Сообщение от Nekto Посмотреть сообщение
Это на сайте каком-то?
e-olimp.com.ua

Цитата Сообщение от Kuzia domovenok Посмотреть сообщение
попробуй замени умножение на сложение степеней двойки
попробуй округлять вводимые числа, например
d00125=b01111101~=10000000=1<<7
d00070=b01000110~=01000000=1<<6
их произведение равно 1<<13
нужно попробовать)
Deviaphan
Делаю внезапно и красиво
Эксперт C++
 Аватар для Deviaphan
1283 / 1217 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
06.04.2012, 17:19     нужна оптимизация приложения #12
Цитата Сообщение от SpecBM Посмотреть сообщение
нужно попробовать)
Не нужно. Считывай не по одному значению, а блоками. У тебя тормоза именно из-за обращения к диску.

Добавлено через 51 секунду
Цитата Сообщение от Nekto Посмотреть сообщение
Почему?
a[0] == 1, все последующие равны нулю.
Nekto
342 / 287 / 10
Регистрация: 23.03.2012
Сообщений: 838
06.04.2012, 17:20     нужна оптимизация приложения #13
Цитата Сообщение от Deviaphan Посмотреть сообщение
При j > 0 расчёт не верен.
Мой код прошел 50% тестов Добавил только \n при выводе.
Deviaphan
Делаю внезапно и красиво
Эксперт C++
 Аватар для Deviaphan
1283 / 1217 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
06.04.2012, 17:30     нужна оптимизация приложения #14
Цитата Сообщение от Nekto Посмотреть сообщение
Мой код прошел 50% тестов
Не заданные явно элементы инициализируются конструктором по умолчанию. Для чисел это 0. Если твой компилятор поступает иначе - удали его, отформатируй винт и сожги монитор. С мышью тоже что-нибудь можешь сделать, она тоже в этом замешана.
Nekto
342 / 287 / 10
Регистрация: 23.03.2012
Сообщений: 838
06.04.2012, 17:32     нужна оптимизация приложения #15
Цитата Сообщение от Deviaphan Посмотреть сообщение
Не заданные явно элементы инициализируются конструктором по умолчанию. Для чисел это 0. Если твой компилятор поступает иначе - удали его, отформатируй винт и сожги монитор. С мышью тоже что-нибудь можешь сделать, она тоже в этом замешана.
да, с конструктором ты прав, исправил ту строчку, уже 85% тестов проходит

Не по теме:

Не будь таким агрессивным

Если писать арифметику через стринг, разве это будет быстрее 2 секунд для почти 2 миллионов умножений?
Deviaphan
Делаю внезапно и красиво
Эксперт C++
 Аватар для Deviaphan
1283 / 1217 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
06.04.2012, 17:56     нужна оптимизация приложения #16

Не по теме:

Цитата Сообщение от Nekto Посмотреть сообщение
Не будь таким агрессивным
Вот если бы я сказал, что по IP тебя вычислю и мышке провод перегрызу, то вот это была бы агрессия.)




Цитата Сообщение от Nekto Посмотреть сообщение
Если писать арифметику через стрин
Нет!
Сейчас ты считываешь ОДНО значение. А нужно считывать сразу всю строку в массив и потом уже из этого массива брать значения. Только считывать не в цикле, а при помощи read. 100000 значений это всего лишь 400 килобайт, так что в лимит памяти легко войдёт.
SpecBM
20 / 20 / 5
Регистрация: 16.01.2010
Сообщений: 61
06.04.2012, 17:56  [ТС]     нужна оптимизация приложения #17
Цитата Сообщение от Kuzia domovenok Посмотреть сообщение
попробуй замени умножение на сложение степеней двойки
попробуй округлять вводимые числа, например
d00125=b01111101~=10000000=1<<7
d00070=b01000110~=01000000=1<<6
их произведение равно 1<<13
а можно по подробней?



если поставить
int a[20];
for (int i = 0; i<N; i++) a[i] = 1; // забыли))

проходит 95% тестов
Deviaphan
Делаю внезапно и красиво
Эксперт C++
 Аватар для Deviaphan
1283 / 1217 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
06.04.2012, 17:57     нужна оптимизация приложения #18
Стоп! Файл же текстовый, а не бинарный... Read не поможет...
SpecBM
20 / 20 / 5
Регистрация: 16.01.2010
Сообщений: 61
06.04.2012, 18:10  [ТС]     нужна оптимизация приложения #19
со скоростью уже все норм.
осталось решить как оперировать с большимы числами.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
06.04.2012, 18:12     нужна оптимизация приложения
Еще ссылки по теме:

C++ Оптимизация памяти
C++ Запустить параллельного приложения / Запуск приложения в новом консольном окне
Оптимизация робота C++

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

Или воспользуйтесь поиском по форуму:
Deviaphan
Делаю внезапно и красиво
Эксперт C++
 Аватар для Deviaphan
1283 / 1217 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
06.04.2012, 18:12     нужна оптимизация приложения #20
Цитата Сообщение от SpecBM Посмотреть сообщение
как оперировать с большимы числами.
Умножать в double.
Yandex
Объявления
06.04.2012, 18:12     нужна оптимизация приложения
Ответ Создать тему
Опции темы

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