Часто встречающаяся задача на оптимизацию.
Есть два шарика и небоскрёб в 100 этажей. Если бросать шарики из окон небоскрёба, то начиная с какого-то этажа они будут разбиваться вдребезги (и после этого разбившийся шарик уже нельзя будет использовать). Нужно предложить алгоритм, который поможет найти этот роковой этаж за оптимальное число итераций. Шарики не обязательно сохранять целыми к концу алгоритма.
...программисты, как известно, славятся тем, что очень плохо находят узкие места в своих собственных программах. Если вы не использовали профайлер и у вас нет некоторых эмпирических данных, которыми вы можете руководствоваться, вы можете потратить целые дни, оптимизируя то, что оптимизировать не требуется и что заметно не повлияет ни на размер, ни на время выполнения программы. Ситуация может оказаться хуже, когда вы не понимаете, что требует оптимизации, и своими действиями непреднамеренно ухудшаете программу.
Вот правила, которыми я призываю вас руководствоваться:
1. Не оптимизируйте преждевременно.
2. Не оптимизируйте до тех пор, пока не убедитесь в том, что это необходимо.
3. Даже в этом случае не оптимизируйте до тех пор, пока не будете точно знать, что и где надо оптимизировать.
int main ()
{
int c = 0;
int size = 10000;
int *a = new int[size * size];
for (int i = 0; i < size; ++i)
{
for (int j = 0; j < size; ++j)
{
a[j * size + i] = c++;
}
}
delete [] a;
return 0;
}
0 10 20 30 40 50 60 70 80 90
1 11 21 31 41 51 61 71 81 91
2 12 22 32 42 52 62 72 82 92
3 13 23 33 43 53 63 73 83 93
4 14 24 34 44 54 64 74 84 94
5 15 25 35 45 55 65 75 85 95
6 16 26 36 46 56 66 76 86 96
7 17 27 37 47 57 67 77 87 97
8 18 28 38 48 58 68 78 88 98
9 19 29 39 49 59 69 79 89 99
g++ и sunCC:-fast в suncc анализирует окружение и подбирает набор опций компилятора для максимального быстродействия. Видно, что sunCC в режиме оптимизации дает результаты в разы лучше, чем g++. А именно — в 5 раз. Хм...Цель данной статьи совсем не в том, чтобы принизить возможности GCC. Для замеров использовался GCC версии 4.1. На данный момент существуют более новые версии этого компилятора, которые могут показать лучшие результаты оптимизации этого кода.
-g0. Эта опция сохраняет в объектном файле отладочную информацию (в том числе и комментарии компилятора), но не запрещает инлайнить функции. Для просмотра комментариев нужно использовать программу er_src, которая также поставляется с Sun Studio.
$ sunCC -g0 -fast a.cpp
$ er_src a.o
Source file: ./a.cpp
Object file: ./a.o
Load Object: ./a.o
1. int main ()
2. {
3. int c = 0;
4. int size = 10000;
5. int *a = new int[size * size];
6.
Source loop below has tag L1
Induction variable substitution performed on L1
L1 interchanged with L2
7. for (int i = 0; i < size; ++i)
8. {
Source loop below has tag L2
Induction variable substitution performed on L2
L2 interchanged with L1
9. for (int j = 0; j < size; ++j)
10. {
11. a[j * size + i] = c++;
12. }
13. }
14.
15. delete [] a;
16. return 0;
17. }
a[j * size + i] = c++;a[j * size + i] = i * size + j;
int main ()
{
int c = 0;
int size = 10000;
int *a = new int[size * size];
for (int j = 0; j < size; ++j)
{
for (int i = 0; i < size; ++i)
{
a[j * size + i] = i * size + j;
}
}
delete [] a;
return 0;
}