Форум программистов, компьютерный форум 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++)
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
SpecBM
20 / 20 / 5
Регистрация: 16.01.2010
Сообщений: 61
06.04.2012, 18:17  [ТС]     нужна оптимизация приложения #21
Цитата Сообщение от Deviaphan Посмотреть сообщение
Умножать в double.
даже в long double не проходит тестов.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Nekto
342 / 287 / 10
Регистрация: 23.03.2012
Сообщений: 838
06.04.2012, 18:26     нужна оптимизация приложения #22
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
#include <cstdio>
#include <vector>
using namespace std;
typedef vector<int> lnum;
const int base = 1000*1000*1000;
 
lnum mult (lnum a, int b)
{
int carry = 0;
for (size_t i=0; i<a.size() || carry; ++i)
 {
  if (i == a.size())
   a.push_back (0);
  long long cur = carry + a[i] * 1ll * b;
  a[i] = int (cur % base);
  carry = int (cur / base);
}
while (a.size() > 1 && a.back() == 0)
   a.pop_back();
return a;
}
 
int main()
{
 FILE *f=fopen("input.txt","r");
 int N, K;
 fscanf(f,"%d%d",&N,&K);
 lnum* a=new lnum[N];
 for (int i=0;i<N;i++)
  a[i].push_back(1);
 int temp;
 for (int i=0;i<K;i++)
  {
   for (int j=0;j<N;j++)
    {
     fscanf(f,"%d",&temp);
     a[j]=mult(a[j],temp);
    }
  }
 fclose(f);
 int max_i=0;
 lnum 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\n",max_i+1);
 fclose(f);
 return 0;
}
70%, по времени не успеваю
Deviaphan
Делаю внезапно и красиво
Эксперт C++
 Аватар для Deviaphan
1283 / 1217 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
06.04.2012, 18:29     нужна оптимизация приложения #23
Цитата Сообщение от SpecBM Посмотреть сообщение
даже в long double не проходит тестов.
Тогда попробуй, как тебе уже советовали, считать не по честному. Сделай для каждого загруженного целого сдвиг на 24 бита вправо и умножай получившиеся числа. Они будут не больше 255. Может и хватит даблов.
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
06.04.2012, 19:08     нужна оптимизация приложения #24
Ну там тема на длинную арифметику, так что придется ее написать.
Я за 2 минуты накидал решение с double, максимальное время работы - 0.6 секунд, но на 6 тестах валится где-то.
Тут длинную арифметику нужно неплохо так реализовать, если хранить 9 знаков в одном элементе массива, то все равно будет не особо быстро. Вроде можно по 17-18 хранить, но тогда нужно будет контролировать переполнение через asm-вставки. Где-то читал про такое, но не уверен, что даже на ассемблере можно умножить 2 64битных числа.
SpecBM
20 / 20 / 5
Регистрация: 16.01.2010
Сообщений: 61
06.04.2012, 19:16  [ТС]     нужна оптимизация приложения #25
нужна оптимизация приложения

хз что не так
Nekto
342 / 287 / 10
Регистрация: 23.03.2012
Сообщений: 838
06.04.2012, 20:51     нужна оптимизация приложения #26
быдлокод :)
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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
#include <cstdio>
#include <vector>
using namespace std;
typedef vector<int> lnum;
const int base = 1000*1000*1000;
 
lnum mult (lnum a, int b)  //ÓìГ*îæåГ*ГЁГҐ äëèГ*Г*îãî Г*Г* êîðîòêîå
//ÓìГ*îæГ*ГҐГІ äëèГ*Г*îå a Г*Г* êîðîòêîå b (b < (base)) 
//ГЁ ñîõðГ*Г*ГїГҐГІ ðåçóëüòГ*ГІ Гў a:
{
 int carry = 0;
 for (size_t i=0; i<a.size() || carry; ++i) 
  {
   if (i == a.size())
    a.push_back (0);
   long long cur = carry + a[i] * 1ll * b;
   a[i] = int (cur % base);
   carry = int (cur / base);
}
while (a.size() > 1 && a.back() == 0)
    a.pop_back();
return a;
}
 
bool checks(lnum a, lnum b)  // a>=b 
{
 if (a.size()>b.size()) return true;
 if (a.size()<b.size()) return false;
 for (size_t i=a.size()-1;i>=0;--i)
  {
   if (a[i]>b[i]) return true;
   if (a[i]<b[i]) return false;
  }
 return true;
} 
 
int main()
{
  FILE *f=fopen("input.txt","r");
  int N, K;
  fscanf(f,"%d%d",&N,&K);
  lnum* a=new lnum[N];
  bool* sign=new bool[N]; //Г¬Г*Г±Г±ГЁГў õðГ*Г*ГҐГ*ГЁГї Г§Г*Г*ГЄГ*
  int **inp=new int*[N];
  for (int i=0;i<N;i++)
   inp[i]=new int[K];
  int temp;
  for (int i=0;i<N;i++)
   {
    a[i].push_back(1); //äëÿ ГіГ¬Г*îæåГ*ГЁГї
    sign[i]=true;      //+
   }
  for (int i=0;i<K;i++)
   {
    for (int j=0;j<N;j++)
     {
      fscanf(f,"%d",&temp);
      if (temp<0) { sign[j]=!sign[j]; inp[j][i]=-temp; } //åñëè "-", ГІГ® ìåГ*ГїГҐГ¬ Г§Г*Г*ГЄ
       else inp[j][i]=temp;
     }
   }
  fclose(f);
  int max_i=0;
  bool all_minus=true; //ïðîâåðêГ* ГҐГ±ГІГј ëè ïîëîæèòåëüГ*ûå Г·ГЁГ±Г«Г*
  for (int i=0;i<N;i++)
   if (!sign[i]) { all_minus=false; break; } 
  if (!all_minus)
   {
    for (int i=0;i<N;i++)
     {
      if (sign[i]) //åñëè ïëþñ
       {
        for (int j=0;j<K;j++) //ïðîâîäèì ГіГ¬Г*îæåГ*ГЁГї
         a[i]=mult(a[i],inp[j][i]);
        max_i=i; //Г§Г*ïîìèГ*Г*ГҐГ¬ ГЁГ*äåêñ äëÿ Г¬Г*êñèìóìГ*
       }
     }
    lnum max=a[max_i];  
    for (int i=0;i<N;i++)
     {
      if (sign[i]) //åñëè ïëþñ
       {
        if (i!=max_i) //åñëè Г*ГҐ òîò æå ýëåìåГ*ГІ
        if (checks(a[i],max)) //Г*[i]>=max
         { 
          max_i=i; 
          max=a[i]; 
         }
       }
     }    
   } 
  else
   {
    for (int i=0;i<N;i++)
     {
      if (!sign[i])
       {
        for (int j=0;j<K;j++)
         a[i]=mult(a[i],inp[j][i]);
        max_i=i;
       }
     }
    lnum max=a[max_i]; 
    for (int i=0;i<N;i++)
     {
      if (!sign[i])
       {
        if (i!=max_i)
        if (!checks(a[i],max)) 
         { 
          max_i=i; 
          max=a[i]; 
         }
       }
     }    
   } 
  f=fopen("output.txt","w");
  fprintf(f,"%d\n",max_i+1);
  fclose(f);
  delete [] a;
  delete [] sign;
  return 0;
}
Подскажите, а в моём быдло-коде что не так? Процедурку умножения стырил, там по идее всё правильно должно быть.

Добавлено через 49 минут
С умножением что-то не так... Проверил - в конце выводит то, что задал в начале (пробовал другие числа любой длины кроме 1 начальным значением).
castaway
Эксперт С++
4841 / 2980 / 367
Регистрация: 10.11.2010
Сообщений: 11,013
Записей в блоге: 10
Завершенные тесты: 1
06.04.2012, 21:18     нужна оптимизация приложения #27
Nekto, нужна оптимизация по скорости - не используй С++, используй Си.
Любой алгоритм на С++ можно переписать на Си, который будет выполняться быстрее. Классы, STL и т.д. и т.п. только замедляют выполнение программы.
Nekto
342 / 287 / 10
Регистрация: 23.03.2012
Сообщений: 838
06.04.2012, 21:19     нужна оптимизация приложения #28
Цитата Сообщение от lazybiz Посмотреть сообщение
Nekto, нужна оптимизация по скорости - не используй С++, используй Си.
Любой алгоритм на С++ можно переписать на Си, который будет выполняться быстрее. Классы, STL и т.д. и т.п. только замедляют выполнение программы.
В последнем коде надо найти ошибку Он ошибочные результаты выдаёт
castaway
Эксперт С++
4841 / 2980 / 367
Регистрация: 10.11.2010
Сообщений: 11,013
Записей в блоге: 10
Завершенные тесты: 1
06.04.2012, 21:21     нужна оптимизация приложения #29
Цитата Сообщение от Nekto Посмотреть сообщение
В последнем коде надо найти ошибку Он ошибочные результаты выдаёт
Это не решит твоей проблемы. Я сильно сомневаюсь что программа пройдет все тесты.
Kuzia domovenok
 Аватар для Kuzia domovenok
1882 / 1737 / 116
Регистрация: 25.03.2012
Сообщений: 5,907
Записей в блоге: 1
06.04.2012, 22:45     нужна оптимизация приложения #30
Да ладно вам, считайте приближённо, складывая только порядки величин.
Вот: как вам это? Не уверен, правда, что будет быстрее.

а можно по подробней?
Вот: набросал поподробней. Сплошные битовые операции, ни одного умножения. Правда, не уверен, что операция
C++
1
while(!(num&mask)){mask=mask>>1;cnt--;}
быстрее умножения. Совсем не уверен. Зато оптимизация! И никаких крестопроблем, характерных для ООП и крестоплюсов.
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
#include <iostream>
#include <fstream>
#include <limits>
using namespace std;
//MAXINT32=1<<31-1
int main(){
    ifstream inf("input.txt");
    ofstream outf("output.txt");
    int n, k, num;
    int i, j;
    const int hbit=1<<30;
    int mask;
    int result, cnt;
    int sign;
    int max, max_i;
    inf >> n;
    inf >> k;
    max=1<<31;//MIN_INT32
    max_i=-1;
    sign=1;//positive
    for (i=0; i<k; i++){
        result=0;//резалт хранит сумму порядков всех чисел, сами числа не хранятся.
        for (j=0; j<n; j++){
            mask=hbit;
            inf>>num;
            if (num<0){
                cnt=30;
                while(!(num&mask)){mask=mask>>1;cnt--;}//число положительное, подсчитываем число нулевых битов в 
//начале, чтобы определить ближайшую степень двойки
                if (num&(mask>>1))result+=cnt+1;//если второй по старшинству бит - единица, округляем в большую сторону
                else
                result+=cnt;
            }
            else{
                sign=sign^1; //if (sign==0) sign=1; else sign=0;
                cnt=30;
                while(num&mask){mask=mask>>1; cnt--;}//число отрицательное, подсчитываем число единичных битов в 
//начале, чтобы определить ближайшую степень двойки
                if (num&(mask>>1))result+=cnt;//если второй по старшинству бит - единица, округляем в большую сторону
                else 
                result+=(cnt+1);
            }
        }
        if ((result>max)&&(sign)){//работает если хоть одно произведение положительно. и если нет крайне близких по значению произведений
            result=max;
            max_i=i;
        }
        //else if result==max && sign , то считаем вручную оба произведения.
        //и всё равно все расчёты были приблизительными, но зато сверх быстрыми.
    }
    inf.close();
    outf<< max_i <<"\n";
    outf.close();
    return 0;
}
castaway
Эксперт С++
4841 / 2980 / 367
Регистрация: 10.11.2010
Сообщений: 11,013
Записей в блоге: 10
Завершенные тесты: 1
06.04.2012, 22:53     нужна оптимизация приложения #31
Не хочу пирожков! Хочу Вотрушек!!! (произносится с акцентом)
Kuzia domovenok, я думаю что она и 10-й тест не пройдет..., а если пройдет 10-й, то не пройдет 11-й!...
Kuzia domovenok
 Аватар для Kuzia domovenok
1882 / 1737 / 116
Регистрация: 25.03.2012
Сообщений: 5,907
Записей в блоге: 1
06.04.2012, 23:11     нужна оптимизация приложения #32
Как известно положительный int32 выглядит так
5=00000000000000000000000000000101
мы считаем нули сначала
бит.маска mask=1<<30=01000000000000000000000000000000
(старший бит - знак)
мы двигаем маску вправо, чтобы определить порядок числа, пока не доберёмся до старшей единицы.
cnt=2; mask=00000000000000000000000000000100
если видим, что следующий бит=0 (как в примере), то округляем число до 1<<mask=4,
если бы число было 7=00000000000000000000000000000111, то округляем число до 1<<mask+1=8,
Но значение чисел нам не важны и мы эту операцию (1<<mask=)
даже не выполняем вместо этого мы суммируем в переменной result все показатели, т.к 2^n*2^m=2^(n+m)

Как известно ОТРИЦАТЕЛЬНЫЙ int32 выглядит так
-5=11111111111111111111111111111011
мы считаем нули сначала
бит.маска mask=1<<30=01000000000000000000000000000000
(старший бит - знак)
мы двигаем маску вправо, чтобы определить порядок числа, но теперь наоборот: перебираем все единицы, пока не получим старший нуль
Далее аналогично

Добавлено через 5 минут
Цитата Сообщение от lazybiz Посмотреть сообщение
Не хочу пирожков! Хочу Вотрушек!!! (произносится с акцентом)
Kuzia domovenok, я думаю что она и 10-й тест не пройдет..., а если пройдет 10-й, то не пройдет 11-й!...
Ну а как иначе предлагаешь оценить произведение 100000 чисел, каждое 32 разряда, не вызвав переполнение?
Суммировать их порядки - идеальный вариант. Да, проблема - операция получения порядка числа, если кто знает более оптимальный вариант - отзовитесь.
Возможно можно как-то вытащить порядок битовыми операциями c float

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
#include <iostream>
#include <fstream>
#include <limits>
using namespace std;
//MAXINT32=1<<31-1
int main(){
    ifstream inf("input.txt");
    ofstream outf("output.txt");
    int n, k, num;
    int i, j;
    const int hbit=1<<30;
    int mask;
    int result, cnt;
    int sign;
    int max, max_i;
    inf >> n;
    inf >> k;
    max=1<<31;//MIN_INT32
    max_i=-1;
    sign=1;//positive
    for (i=0; i<k; i++){
        result=0;//резалт хранит сумму порядков всех чисел, сами числа не хранятся.
        for (j=0; j<n; j++){
            mask=hbit;
            inf>>num;
            if (num<0){
                cnt=30;
                while(!(num&mask)){mask=mask>>1;cnt--;}//число положительное, подсчитываем число нулевых битов в 
//начале, чтобы определить ближайшую степень двойки
                if (num&(mask>>1))result+=cnt+1;//если второй по старшинству бит - единица, округляем в большую сторону
                else
                result+=cnt;
            }
            else{
                sign=sign^1; //if (sign==0) sign=1; else sign=0;
                cnt=30;
                while(num&mask){mask=mask>>1; cnt--;}//число отрицательное, подсчитываем число единичных битов в 
//начале, чтобы определить ближайшую степень двойки
                if (num&(mask>>1))result+=cnt;//если второй по старшинству бит - единица, округляем в большую сторону
                else 
                result+=(cnt+1);
            }
        }
        if ((result>max)&&(sign)){//работает если хоть одно произведение положительно. и если нет крайне близких по значению произведений
            result=max;
            max_i=i;
        }
        //else if result==max && sign , то считаем вручную оба произведения.
        //и всё равно все расчёты были приблизительными, но зато сверх быстрыми.
    }
    inf.close();
    outf<< max_i <<"\n";
    outf.close();
    return 0;
}
Nekto
342 / 287 / 10
Регистрация: 23.03.2012
Сообщений: 838
07.04.2012, 02:30     нужна оптимизация приложения #33
нужна оптимизация приложения Так что, никто не знает, в чем ошибка? Посмотрите хотя бы первую функцию (mult). Она правильно должна работать?

Добавлено через 3 минуты
Цитата Сообщение от Kuzia domovenok Посмотреть сообщение
Ну а как иначе предлагаешь оценить произведение 100000 чисел, каждое 32 разряда, не вызвав переполнение?
В моём варианте числа хранятся в векторе. На тестовых вариантах получается максимальное время 1375 ms, память 8.5 mb. Но умножение почему-то вообще не меняет изначальное число. Наверное в синтаксисе где-то ошибка, потому что внутренности копировал из статьи про арифметику длинных чисел.

Добавлено через 1 час 44 минуты
Оптимизировал немного, нашел ошибку. Проходит 70% тестов. На одном неверный ответ, на остальных не хватает времени
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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
#include <cstdio>
#include <vector>
using namespace std;
typedef vector<int> lnum;
const int base = 1000*1000*1000;
  lnum a[20];
  int sign[20]; //Г¬Г*Г±Г±ГЁГў õðГ*Г*ГҐГ*ГЁГї Г§Г*Г*ГЄГ*
  int inp[20][100000];
 
lnum mult (lnum a, int b)  //ÓìГ*îæåГ*ГЁГҐ äëèГ*Г*îãî Г*Г* êîðîòêîå
//ÓìГ*îæГ*ГҐГІ äëèГ*Г*îå a Г*Г* êîðîòêîå b (b < (base)) 
//ГЁ ñîõðГ*Г*ГїГҐГІ ðåçóëüòГ*ГІ Гў a:
{
 int carry = 0;
 for (size_t i=0; i<a.size() || carry; ++i) 
  {
   if (i == a.size())
    a.push_back (0);
   long long cur = carry + a[i] * 1ll * b;
   a[i] = int (cur % base);
   carry = int (cur / base);
  }
while (a.size() > 1 && a.back() == 0)
    a.pop_back();
return a;
}
 
bool checks(lnum a, lnum b)  // a>=b 
{
 if (a.size()>b.size()) return true;
 if (a.size()<b.size()) return false;
 for (size_t i=(int)a.size()-1;i>=0;i--)
  {
   if (a[i]>b[i]) return true;
   if (a[i]<b[i]) return false;
  }
 return true;
} 
 
int main()
{
  FILE *f=fopen("input.txt","r");
  int N, K;
  fscanf(f,"%d%d",&N,&K);
  for (int i=0;i<N;i++)
   {
    a[i].push_back(1); //äëÿ ГіГ¬Г*îæåГ*ГЁГї
    sign[i]=1;      //+
   }
  for (int i=0;i<K;i++)
   {
    for (int j=0;j<N;j++)
     {
      fscanf(f,"%d",&inp[j][i]);
      if (inp[j][i]<0) { sign[j]=-sign[j]; inp[j][i]=-inp[j][i]; } //åñëè "-", ГІГ® ìåГ*ГїГҐГ¬ Г§Г*Г*ГЄ
       else 
        if (inp[j][i]==0) sign[j]=0;
     }
   }
  fclose(f);
  int max_i=0;
  bool all_minus=true; //ïðîâåðêГ* ГҐГ±ГІГј ëè Г·ГЁГ±Г«Г* >=0
  for (int i=0;i<N;i++)
   if (sign[i]!=-1) { all_minus=false; break; } 
  if (!all_minus)
   {
    for (int i=0;i<N;i++)
     {
      if (sign[i]==1) //åñëè ïëþñ
       {
        for (int j=0;j<K;j++) //ïðîâîäèì ГіГ¬Г*îæåГ*ГЁГї
         {
          a[i]=mult(a[i],inp[i][j]);
         } 
        max_i=i; //Г§Г*ïîìèГ*Г*ГҐГ¬ ГЁГ*äåêñ äëÿ Г¬Г*êñèìóìГ*
       }
     else if (sign[i]==0) { a[i].clear(); a[i].push_back(0); max_i=i; }
    }
    lnum max=a[max_i];  
    for (int i=0;i<N;i++)
     {
      if (sign[i]!=-1) //åñëè ïëþñ
       {
        if (i!=max_i) //åñëè Г*ГҐ òîò æå ýëåìåГ*ГІ
        if (checks(a[i],max)) //Г*[i]>=max
         { 
          max_i=i; 
          max=a[i]; 
         }
       }
     }    
   } 
  else
   {
    for (int i=0;i<N;i++)
     {
      for (int j=0;j<K;j++) //ïðîâîäèì ГіГ¬Г*îæåГ*ГЁГї
       {
        a[i]=mult(a[i],inp[i][j]);
       } 
     }
    lnum max=a[max_i]; 
    for (int i=0;i<N;i++)
     {
      if (i!=max_i)
      if (!checks(a[i],max)) 
       { 
        max_i=i; 
        max=a[i]; 
       }
    }
  }    
  f=fopen("output.txt","w");
  fprintf(f,"%d\n",max_i+1);
  fclose(f);
  return 0;
}
Kuzia domovenok
 Аватар для Kuzia domovenok
1882 / 1737 / 116
Регистрация: 25.03.2012
Сообщений: 5,907
Записей в блоге: 1
07.04.2012, 12:59     нужна оптимизация приложения #34
Цитата Сообщение от Nekto Посмотреть сообщение
В моём варианте числа хранятся в векторе. На тестовых вариантах получается максимальное время 1375 ms, память 8.5 mb. Но умножение почему-то вообще не меняет изначальное число. Наверное в синтаксисе где-то ошибка, потому что внутренности копировал из статьи про арифметику длинных чисел.
Добавлено через 1 час 44 минуты
Оптимизировал немного, нашел ошибку. Проходит 70% тестов. На одном неверный ответ, на остальных не хватает времени
Ну так скажи, ты всё ещё хочешь в лоб умножать или прислушаешься к моему варианту?
Обрати внимание: в задаче тебя не просят сказать, с каким конкретно счётом команда выиграла соревнования. Тебе нужно просто назвать победителя, а мой метод приближённого умножения, как раз позволяет это быстро оценить!
Зачем изобретать методы длинного умножения? Зачем вычислять точно мантиссу произведения всех чисел, когда нам достаточно лишь знать порядок? Зачем эти пляски с векторами, которые только замедляют алгоритм?
Ты точно понял суть моего предложения алгоритма?
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
07.04.2012, 13:07     нужна оптимизация приложения #35
Цитата Сообщение от Kuzia domovenok Посмотреть сообщение
Ну так скажи, ты всё ещё хочешь в лоб умножать
По хорошему другого варианта нет, т.к. остальные методы неточные.
Я попробовал набросать длинку на С, но жрется 106% времени все равно.
Можно попробовать распараллелить вычисления, или хранить цифры в 64битном числе и умножать через asm-вставки.
Еще вариант - можно слегка оптимизировать, если брать за основание не степень десятки, а степень двойки, тогда будет работать немного быстрее и есть меньше памяти, правда будет сложновато выводить такие числа, но в данной задаче это и не требуется.

P.S. Nekto, имхо, плохая оптимизация, т.к. в худшем случае время только увеличиться.
Kuzia domovenok
 Аватар для Kuzia domovenok
1882 / 1737 / 116
Регистрация: 25.03.2012
Сообщений: 5,907
Записей в блоге: 1
07.04.2012, 13:27     нужна оптимизация приложения #36
Цитата Сообщение от diagon Посмотреть сообщение
По хорошему другого варианта нет, т.к. остальные методы неточные.
Нет, есть. Считать результаты крысиных команд, как сумму ближайших степеней двойки, а когда выяснится, что у пары команд одинаковые результаты, можно и поточнее для них пересчитать.
Но вот о скорости надо думать в первую очередь. А значит, никакой длинной арифметики.

К тому же в моём решении берётся не просто порядок старшего бита числа, а в зависимости от следующего за ним бита, округляется в ближайшую сторону, то есть в среднем ошибка накапливаться не должна.
Я думаю, составитель задания хотел именно это проверить. А не то, что задачу можно перемножить в лоб длинной арифметикой. К тому же вектора - зло.

Ты только представь, на сколько это
C++
1
2
3
4
5
6
7
8
 for (size_t i=0; i<a.size() || carry; ++i) 
  {
   if (i == a.size())
    a.push_back (0);  //потрясающе, ещё и работа с vector идёт, а 
   long long cur = carry + a[i] * 1ll * b;
   a[i] = int (cur % base);    ///   о! а ещё деление на 10
   carry = int (cur / base);  /// а вы удивляетесь, почему медленно????
  }
медленнее этого!!!
C++
1
while(!(num&mask)){mask=mask>>1;cnt--;}
К тому же, отрицательные числа в дополнительном коде тоже проверяются.единственное, я кажется забыл учесть ноль.
Присутствие нуля должно отменять весь подсчёт произведения и переходить к следующей команде.
Nekto
342 / 287 / 10
Регистрация: 23.03.2012
Сообщений: 838
07.04.2012, 14:04     нужна оптимизация приложения #37
Цитата Сообщение от Kuzia domovenok Посмотреть сообщение
Нет, есть. Считать результаты крысиных команд, как сумму ближайших степеней двойки, а когда выяснится, что у пары команд одинаковые результаты, можно и поточнее для них пересчитать.
Но вот о скорости надо думать в первую очередь. А значит, никакой длинной арифметики.
А если окажется, что 20 команд с одинаковыми степенями?

Добавлено через 8 минут
Цитата Сообщение от Kuzia domovenok Посмотреть сообщение
a[i] = int (cur % base); /// о! а ещё деление на 10
Деление на миллиард идёт
Kuzia domovenok
 Аватар для Kuzia domovenok
1882 / 1737 / 116
Регистрация: 25.03.2012
Сообщений: 5,907
Записей в блоге: 1
07.04.2012, 14:29     нужна оптимизация приложения #38
Цитата Сообщение от Nekto Посмотреть сообщение
Деление на миллиард идёт
Естественным желанием при оптимизации было бы.
1) Заменить деление на сдвиг, основание на степень двойки.
2) Использовать вместо вектора статический массив.

А если окажется, что 20 команд с одинаковыми степенями?
Ну вот тогда и использовать твой алгоритм. При этом на одном тесте, где "20 команд с одинаковыми степенями" будет тормозить, а остальные пулей отсеются.
Nekto
342 / 287 / 10
Регистрация: 23.03.2012
Сообщений: 838
07.04.2012, 14:40     нужна оптимизация приложения #39
Цитата Сообщение от Kuzia domovenok Посмотреть сообщение
Естественным желанием при оптимизации было бы.
1) Заменить деление на сдвиг, основание на степень двойки.
2) Использовать вместо вектора статический массив.
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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
#include <cstdio>
#include <vector>
using namespace std;
typedef vector<unsigned long long> lnum;
const unsigned long long base = 140737488355328ULL;
 lnum a[20];
 int sign[20]; //Г¬Г*Г±Г±ГЁГў õðГ*Г*ГҐГ*ГЁГї Г§Г*Г*ГЄГ*
 int inp[20][100000];
 
lnum mult (lnum a, int b)  //ÓìГ*îæåГ*ГЁГҐ äëèГ*Г*îãî Г*Г* êîðîòêîå
//ÓìГ*îæГ*ГҐГІ äëèГ*Г*îå a Г*Г* êîðîòêîå b (b < (base))
//ГЁ ñîõðГ*Г*ГїГҐГІ ðåçóëüòГ*ГІ Гў a:
{
int carry = 0;
for (size_t i=0; i<a.size() || carry; ++i)
 {
  if (i == a.size())
   a.push_back (0);
  long long cur = carry + a[i] * 1ll * b;
  carry = cur << 47;
  a[i] = cur-carry*base;
 }
while (a.size() > 1 && a.back() == 0)
   a.pop_back();
return a;
}
 
bool checks(lnum a, lnum b)  // a>=b
{
if (a.size()>b.size()) return true;
if (a.size()<b.size()) return false;
for (size_t i=(int)a.size()-1;i>=0;i--)
 {
  if (a[i]>b[i]) return true;
  if (a[i]<b[i]) return false;
 }
return true;
}
 
int main()
{
 FILE *f=fopen("input.txt","r");
 int N, K;
 fscanf(f,"%d%d",&N,&K);
 for (int i=0;i<N;i++)
  {
   a[i].push_back(1); //äëÿ ГіГ¬Г*îæåГ*ГЁГї
   sign[i]=1;      //+
  }
 for (int i=0;i<K;i++)
  {
   for (int j=0;j<N;j++)
    {
     fscanf(f,"%d",&inp[j][i]);
     if (inp[j][i]<0) { sign[j]=-sign[j]; inp[j][i]=-inp[j][i]; } //åñëè "-", ГІГ® ìåГ*ГїГҐГ¬ Г§Г*Г*ГЄ
      else
       if (inp[j][i]==0) sign[j]=0;
    }
  }
 fclose(f);
 int max_i=0;
 bool all_minus=true; //ïðîâåðêГ* ГҐГ±ГІГј ëè Г·ГЁГ±Г«Г* >=0
 for (int i=0;i<N;i++)
  if (sign[i]!=-1) { all_minus=false; break; }
 if (!all_minus)
  {
   for (int i=0;i<N;i++)
    {
     if (sign[i]==1) //åñëè ïëþñ
      {
       for (int j=0;j<K;j++) //ïðîâîäèì ГіГ¬Г*îæåГ*ГЁГї
        {
         a[i]=mult(a[i],inp[i][j]);
        }
       max_i=i; //Г§Г*ïîìèГ*Г*ГҐГ¬ ГЁГ*äåêñ äëÿ Г¬Г*êñèìóìГ*
      }
    else if (sign[i]==0) { a[i].clear(); a[i].push_back(0); max_i=i; }
   }
   lnum max=a[max_i];  
   for (int i=0;i<N;i++)
    {
     if (sign[i]!=-1) //åñëè ïëþñ
      {
       if (i!=max_i) //åñëè Г*ГҐ òîò æå ýëåìåГ*ГІ
       if (checks(a[i],max)) //Г*[i]>=max
        {
         max_i=i;
         max=a[i];
        }
      }
    }    
  }
 else
  {
   for (int i=0;i<N;i++)
    {
     for (int j=0;j<K;j++) //ïðîâîäèì ГіГ¬Г*îæåГ*ГЁГї
      {
       a[i]=mult(a[i],inp[i][j]);
      }
    }
   lnum max=a[max_i];
   for (int i=0;i<N;i++)
    {
     if (i!=max_i)
     if (!checks(a[i],max))
      {
       max_i=i;
       max=a[i];
      }
   }
 }    
 f=fopen("output.txt","w");
 fprintf(f,"%d\n",max_i+1);
 fclose(f);
 return 0;
}
Я правильно сдвиг сделал? 18 правильных, 1 неправильный, 1 нехватка времени.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
08.04.2012, 18:22     нужна оптимизация приложения
Еще ссылки по теме:

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

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

Или воспользуйтесь поиском по форуму:
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
08.04.2012, 18:22     нужна оптимизация приложения #40
вот так проходит все тесты:
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
66
67
68
#include <stdio.h> 
double mas[100000][20];
int N, K;
bool zn[20], null[20];
 
bool func(int a, int b)
{
    if(null[a] && null[b])
        return false;
    if(null[a] && zn[b])
        return false;
    if(zn[a] && null[b])
        return true;
    if(zn[a] && !zn[b])
        return true;
    if(!zn[a] && zn[b])
        return false;
    int l=0, r=0, k;
    double tmp=1.;
    while(true)
    {
        while(r<K && tmp<=1.)
        {
            tmp*=mas[r++][b];
            k=0;
        }
        while(l<K && tmp>=1.)
        {
            tmp/=mas[l++][a];
            k=0;
        }
        if(k==0)
            k++;
        else
        {
            if(zn[b] && tmp<1.)
                return true;
            if(!zn[b] && tmp>1.)
                return true;
            return false;
        }       
    }
}
 
int main() 
{
    scanf("%d%d",&N, &K);
    int i, j, res;
    for(i=0; i<K; i++)
        for(j=0; j<N; j++)
        {
            scanf("%lf", &mas[i][j]);
            if(mas[i][j]<0)
            {
                mas[i][j]*=-1.;
                zn[j]=!zn[j];
            }
            else
                if(mas[i][j]==.0)
                    null[j]=true;
        }
    res=N-1;
    for(i=N-2; i>=0; i--)
        if(func(res, i))
            res=i;
    printf("%d\n", res+1);
    return 0; 
}
Yandex
Объявления
08.04.2012, 18:22     нужна оптимизация приложения
Ответ Создать тему
Опции темы

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