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

Скорость выполнения, а так же работа с дв. файлами - C++

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 9, средняя оценка - 4.78
nexen
187 / 180 / 3
Регистрация: 27.01.2012
Сообщений: 1,335
24.06.2012, 22:07     Скорость выполнения, а так же работа с дв. файлами #1
Здравствуйте. У меня есть несколько вопросов, на которые я уже давненько ищу ответы, а именно :

1) Для таких классов, как vector/set/map и прочих, что быстрее - iterator или [] ?

2) Тот же вопрос, но для двумерного vector/set/map, ведь, если даже itearator быстрее [] для одномерного, то, чтобы получить доступ к элементу a[i+1][j+1] через итераторы, придется писать нечто подобное (и не иначе? есть ли возможность другого доступа к i+-N элементов?) :
*((i+1)->begin() + int(j - i->begin() + 1))
В данном случае [] будет гораздо быстрее, так ведь?

3) Есть ли различия в скорости между :
const int MAX = 1000*1000;
vector < vector <int> > a(MAX, vector<int>(MAX));
и
vector < vector <int> > a(MAX);
for (int i=0; i<MAX; i++)
a[i].resize(MAX);
?

4) Недавно работал с двоичными файлами и нужно было не считывая и не записывая ничего в файл (по неизвестному N, которое определяет кол-во элементов в файле), при помощи fseek пробежаться эти N раз с отступом по sizeof и, соответственно, определить его, но вот беда, fseek в упор не видел feof и EOF. Как ни старался, он его проходит и ничего путного о конце файла не говорит, причем не важно - прошел он его мимо или прямо-таки "наступил" на него.. Кто-нибудь сталкивался?

5) Слышал, что функции корня и возведения в степень можно заменить логарифмами и что это, якобы, быстрее, но сколько не шарюсь в гугле, найти чего-то путного по этому поводу не могу.. Можете сказать, как же произвести замену или хотя бы дать ссылку на статейку/заметку?

6) Быстрее ли inline-функция, чем обычная функция? Если да, то на сколько (примерно)? Есть хотя бы 100-200 тактов?

7) Недавно сталкивался с задачкой на оптимизацию и столкнулся с фактом, который не могу объяснить, а именно : цикл от 0 до N работает медленнее, чем цикл от N до 0, причем при больших данных, эта разница была огромной (Задача была в небольшой работе с массивом, был двойной цикл от 0 до (максимум) 2000. При максимальном значении, разница между 0->N и N->0 была в районе 0,3 секунд). Кто-нибудь может пояснить, откуда? Почему такая разница?
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
xADMIRALx
 Аватар для xADMIRALx
66 / 60 / 1
Регистрация: 09.06.2012
Сообщений: 291
24.06.2012, 22:10     Скорость выполнения, а так же работа с дв. файлами #2
Указатели всегда были быстрее...
но луче спросите у Evg он точна вам ответит... http://www.cyberforum.ru/members/18334.html
на счет inline уже писали,почитайте блог у него,много чего интересного на счет оптимизации...
Avazart
 Аватар для Avazart
6900 / 5140 / 252
Регистрация: 10.12.2010
Сообщений: 22,588
Записей в блоге: 17
24.06.2012, 22:33     Скорость выполнения, а так же работа с дв. файлами #3
1.
что быстрее - iterator или [] ?
iterator
2.
Цитата Сообщение от nexen Посмотреть сообщение
В данном случае [] будет гораздо быстрее, так ведь?
Нет
C++
1
*(  (v.begin()+i)->begin()+j )
3.
C++
1
2
const int MAX = 1000*1000;
 vector < vector <int> > a(MAX, vector<int>(MAX));
Быстрее
nexen
187 / 180 / 3
Регистрация: 27.01.2012
Сообщений: 1,335
25.06.2012, 09:18  [ТС]     Скорость выполнения, а так же работа с дв. файлами #4
Цитата Сообщение от nexen Посмотреть сообщение
Здравствуйте. У меня есть несколько вопросов, на которые я уже давненько ищу ответы, а именно :

4) Недавно работал с двоичными файлами и нужно было не считывая и не записывая ничего в файл (по неизвестному N, которое определяет кол-во элементов в файле), при помощи fseek пробежаться эти N раз с отступом по sizeof и, соответственно, определить его, но вот беда, fseek в упор не видел feof и EOF. Как ни старался, он его проходит и ничего путного о конце файла не говорит, причем не важно - прошел он его мимо или прямо-таки "наступил" на него.. Кто-нибудь сталкивался?

5) Слышал, что функции корня и возведения в степень можно заменить логарифмами и что это, якобы, быстрее, но сколько не шарюсь в гугле, найти чего-то путного по этому поводу не могу.. Можете сказать, как же произвести замену или хотя бы дать ссылку на статейку/заметку?

7) Недавно сталкивался с задачкой на оптимизацию и столкнулся с фактом, который не могу объяснить, а именно : цикл от 0 до N работает медленнее, чем цикл от N до 0, причем при больших данных, эта разница была огромной (Задача была в небольшой работе с массивом, был двойной цикл от 0 до (максимум) 2000. При максимальном значении, разница между 0->N и N->0 была в районе 0,3 секунд). Кто-нибудь может пояснить, откуда? Почему такая разница?
Значит остались только эти три вопроса. (К сожалению, не могу исправлять заголовок темы)
Evg
Эксперт С++Автор FAQ
 Аватар для Evg
16825 / 5246 / 321
Регистрация: 30.03.2009
Сообщений: 14,127
Записей в блоге: 26
25.06.2012, 14:03     Скорость выполнения, а так же работа с дв. файлами #5
Цитата Сообщение от nexen Посмотреть сообщение
4) Недавно работал с двоичными файлами и нужно было не считывая и не записывая ничего в файл (по неизвестному N, которое определяет кол-во элементов в файле), при помощи fseek пробежаться эти N раз с отступом по sizeof и, соответственно, определить его, но вот беда, fseek в упор не видел feof и EOF. Как ни старался, он его проходит и ничего путного о конце файла не говорит, причем не важно - прошел он его мимо или прямо-таки "наступил" на него.. Кто-нибудь сталкивался?
Пока нет конкретного исходника, предмет для разговора отсутствует

Цитата Сообщение от nexen Посмотреть сообщение
5) Слышал, что функции корня и возведения в степень можно заменить логарифмами и что это, якобы, быстрее, но сколько не шарюсь в гугле, найти чего-то путного по этому поводу не могу.. Можете сказать, как же произвести замену или хотя бы дать ссылку на статейку/заметку?
Вот тебе код функции pow из glibc
http://fossies.org/dox/glibc-2.15/ie...8c_source.html

Цитата Сообщение от nexen Посмотреть сообщение
6) Быстрее ли inline-функция, чем обычная функция? Если да, то на сколько (примерно)? Есть хотя бы 100-200 тактов?
Вопрос так неправильно поставлен. Сама по себе функция точно такая же. Но с учётом точки подстановки вызова - будет быстрее, если компилятор решит, что её нужно проинлайнить. Директива inline НЕ является обязательством с точки зрения inline-подстановки. Если inline произошёл тупо (т.е. операцию вызова заменили на внутренности inline-процедуры), то для intel'овских машин эффект будет сравнительно не большим - навскидку не более 10-20 тактов (примерно таковы накладные расходы на операцию вызова и возврата). Но бывают дополнительные эффекты, когда после inline-подстановки компилятор хорошо перемешает код вызвавшей и вызываемой процедуры и в итоге полученный код очень хорошо разляжется по нескольким конвейерам. В итоге ускорение может оказаться существенным. Но в абсолютных единицах тактов это нельзя выразить, т.к. надо знать длину inline-функции в тактах. В примеру, вполне может получиться так, что вызывающая функция сама по себе работает 100 тактов без учёта операции вызова. inline-функция работает 30 тактов, но после inline-подстановки итоговый код отработает за те же самые 100 тактов (за счёт хорошо спланированного конвейера)

Цитата Сообщение от nexen Посмотреть сообщение
7) Недавно сталкивался с задачкой на оптимизацию и столкнулся с фактом, который не могу объяснить, а именно : цикл от 0 до N работает медленнее, чем цикл от N до 0, причем при больших данных, эта разница была огромной (Задача была в небольшой работе с массивом, был двойной цикл от 0 до (максимум) 2000. При максимальном значении, разница между 0->N и N->0 была в районе 0,3 секунд). Кто-нибудь может пояснить, откуда? Почему такая разница?
Опять-таки без конкретного примера можно только гадать
nexen
187 / 180 / 3
Регистрация: 27.01.2012
Сообщений: 1,335
25.06.2012, 17:07  [ТС]     Скорость выполнения, а так же работа с дв. файлами #6
7) Цикл ищет максимальную тройку элементов в двумерном массиве, при этом эти элементы должны соприкосаться друг с другом (без рекурсии, тупо в лоб) :

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
for (int i=n-1; i >= -1 && maxSum != 300; --i)
    {
        for (int j=n-1; j >= 0 && maxSum != 300; --j)
        {
            if (i > -1)
                scanf("%d", &a[i][j]);
            if (i < n-1 && a[i+1][j] > maxSum-200)
            {
                if (i+3 < n)
                    if (a[i+1][j] + a[i+2][j] + a[i+3][j] > maxSum)
                        maxSum = a[i+1][j] + a[i+2][j] + a[i+3][j];
                
                if (j+2 < n)
                    if (a[i+1][j] + a[i+1][j+1] + a[i+1][j+2] > maxSum)
                        maxSum = a[i+1][j] + a[i+1][j+1] + a[i+1][j+2];
 
                if (i < n-2 && j != n-1)
                {
                    if (a[i+1][j] + a[i+2][j] + a[i+2][j+1] > maxSum)
                        maxSum = a[i+1][j] + a[i+2][j] + a[i+2][j+1];
                    if (a[i+1][j] + a[i+1][j+1] + a[i+2][j+1] > maxSum)
                        maxSum = a[i+1][j] + a[i+1][j+1] + a[i+2][j+1];
                }
 
                if (i < n-2 && j != 0)
                {
                    if (a[i+1][j] + a[i+2][j] + a[i+2][j-1] > maxSum)
                        maxSum = a[i+1][j] + a[i+2][j] + a[i+2][j-1];
                    if (a[i+1][j] + a[i+1][j-1] + a[i+2][j-1] > maxSum)
                        maxSum = a[i+1][j] + a[i+1][j-1] + a[i+2][j-1];
                }
            }
        }
    }
(здесь я совмести ввод и проверку, поэтому проверка идет от i+1 (а именно, мы даем считать одну строчку, а уже затем проверяем. После этого цикла есть ещё один, который проверяет последнюю строчку, но он не так важен для моего вопроса)
Этот цикл для N=2000 работает на порядок быстрее, чем цикл от 0 -> N.

4)
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
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <conio.h>
 
void IsEOF(FILE *v)
{
    printf("File is : ");
    if (feof(v))
        printf("End of File\n");
    else
        printf("Reading/Writing\n");
}
 
void main()
{
    freopen("input.dat", "wb", stdin);
    rewind(stdin);
    printf("Read from the file\n\n");
 
    int number = 777, temp;
    for (int i=0; i<10; i++)
        fwrite(&number, sizeof(number), 1, stdin);
 
    freopen("input.dat", "rb", stdin);
    rewind(stdin);
 
    printf("Read 10 numbers ");
    for (int i=0; i<10; i++)
    {
        fread(&temp, sizeof(temp), 1, stdin);
        //printf("%d ", temp);
    }
    printf("\n");
 
    IsEOF(stdin);
    printf("Read one more \n");
    fread(&temp, sizeof(temp), 1, stdin);
    IsEOF(stdin);
 
    rewind(stdin);
    printf("\nDon't read something now.\n\n");
 
    printf("'fseek'ing 10 numbers\n");
    fseek(stdin, 10*sizeof(number), SEEK_SET);
    IsEOF(stdin);
    printf("'fseek' one more\n");
    fseek(stdin, sizeof(number), SEEK_CUR);
    IsEOF(stdin);
    printf("'fseek' 11 numbers per command\n");
    fseek(stdin, 11*sizeof(number), SEEK_SET);
    IsEOF(stdin);
 
    _getch();
}

За inline и логарифмы спасибо, позже прочитаю ^^
p.s Жаль, что cpp не подгружается..
Shandr_71
13 / 13 / 1
Регистрация: 05.12.2011
Сообщений: 84
25.06.2012, 22:21     Скорость выполнения, а так же работа с дв. файлами #7
Насчет циклов: разница возникает из-за дополнительного сравнения в ассемберном цикле.
nexen
187 / 180 / 3
Регистрация: 27.01.2012
Сообщений: 1,335
26.06.2012, 07:21  [ТС]     Скорость выполнения, а так же работа с дв. файлами #8
Цитата Сообщение от Shandr_71 Посмотреть сообщение
Насчет циклов: разница возникает из-за дополнительного сравнения в ассемберном цикле.
Хм, а это можно как-то правилами логики объяснить? Или имеется ввиду лишняя проверка, созданная компилятором при трансляции?

При работе с дв. файлами постарался написать довольно четко, в чем проблема. Надеюсь, что всё понятно.

p.s Эм, да, что-то я забыл про теги кода :<
Deviaphan
Делаю внезапно и красиво
Эксперт C++
 Аватар для Deviaphan
1283 / 1217 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
26.06.2012, 07:34     Скорость выполнения, а так же работа с дв. файлами #9
Цитата Сообщение от Avazart Посмотреть сообщение
В данном случае [] будет гораздо быстрее, так ведь?
Нет
Код C++
1
*( (v.begin()+i)->begin()+j )
[] заменяются на точно такой же код. Итераторы эффективнее только при последовательном доступе, иначе они эквивалентны индексному доступу.



Цитата Сообщение от Avazart Посмотреть сообщение
2
const int MAX = 1000*1000;
vector < vector <int> > a(MAX, vector<int>(MAX));
Быстрее
С каких пор создание копий векторов эффективнее создания пустого вектора и изменения его размера без копирований?
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
26.06.2012, 08:13     Скорость выполнения, а так же работа с дв. файлами #10
Цитата Сообщение от nexen Посмотреть сообщение
) Для таких классов, как vector/set/map и прочих, что быстрее - iterator или [] ?
Для вектора эквивалентно.
В map оператор индексации работает за логарифм, а с итератором получается линейная сложность(т.е. намного хуже).
У set'a вообще нету оператора индексации.

Цитата Сообщение от nexen Посмотреть сообщение
Слышал, что функции корня и возведения в степень можно заменить логарифмами
О вещественных числах ничего не скажу, знаю, что есть бинарное возведение в степень, которое работает за логарифм. Тут есть подробнее.

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

Цитата Сообщение от nexen Посмотреть сообщение
Цикл ищет максимальную тройку элементов в двумерном массиве, при этом эти элементы должны соприкосаться друг с другом (без рекурсии, тупо в лоб)
Вы не об этой задаче случаем?
kazak
 Аватар для kazak
3029 / 2350 / 155
Регистрация: 11.03.2009
Сообщений: 5,401
26.06.2012, 09:57     Скорость выполнения, а так же работа с дв. файлами #11
Цитата Сообщение от nexen Посмотреть сообщение
но вот беда, fseek в упор не видел feof и EOF. Как ни старался, он его проходит и ничего путного о конце файла не говорит, причем не важно - прошел он его мимо или прямо-таки "наступил" на него.. Кто-нибудь сталкивался?
1. fseek возвращает результат своего выполнения, если все хорошо, fseek вернет ноль. О конце файла данная функция в принципе ничего рассказать не может, т.к. у нее несколько иное назначение.
2. Символа EOF в файле не существует, это просто некоторое условное значение, которое возвращают функции чтения, когда не могут считать данные по причине их отсутствия.
Evg
Эксперт С++Автор FAQ
 Аватар для Evg
16825 / 5246 / 321
Регистрация: 30.03.2009
Сообщений: 14,127
Записей в блоге: 26
26.06.2012, 10:11     Скорость выполнения, а так же работа с дв. файлами #12
Цитата Сообщение от nexen Посмотреть сообщение
7) Недавно сталкивался с задачкой на оптимизацию и столкнулся с фактом, который не могу объяснить, а именно : цикл от 0 до N работает медленнее, чем цикл от N до 0, причем при больших данных, эта разница была огромной (Задача была в небольшой работе с массивом, был двойной цикл от 0 до (максимум) 2000. При максимальном значении, разница между 0->N и N->0 была в районе 0,3 секунд). Кто-нибудь может пояснить, откуда? Почему такая разница?
Можешь показать мне нормальные два примера кода, которые бы отличались только направлением обхода в цикле и на которых бы видна была разница в скорости исполнения? То, что ты привёл - абсолютно не понятно к чему и зачем. Если хочешь получить ответ на вопрос - потрать своё драгоценное время на то, чтобы его внятно сформулировать
nexen
187 / 180 / 3
Регистрация: 27.01.2012
Сообщений: 1,335
26.06.2012, 11:44  [ТС]     Скорость выполнения, а так же работа с дв. файлами #13
Цитата Сообщение от diagon Посмотреть сообщение
В map оператор индексации работает за логарифм, а с итератором получается линейная сложность(т.е. намного хуже).
У set'a вообще нету оператора индексации.
Да.. это я немного не о том подумал :<

Цитата Сообщение от diagon Посмотреть сообщение
Вы не об этой задаче случаем?
Да, о ней.

Цитата Сообщение от Evg Посмотреть сообщение
Можешь показать мне нормальные два примера кода, которые бы отличались только направлением обхода в цикле и на которых бы видна была разница в скорости исполнения? То, что ты привёл - абсолютно не понятно к чему и зачем. Если хочешь получить ответ на вопрос - потрать своё драгоценное время на то, чтобы его внятно сформулировать
Не ну надо уж так критично ;(
Допустим так для N -> 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
46
47
48
49
50
#include <stdio.h>
#include <vector>
 
using namespace std;
 
int maxSum = -500, n;
int i, j;
vector < vector <int> > a;
 
void main()
{
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
 
    scanf("%d", &n);
    a.resize(n, vector<int>(n));
 
    for (i=n-1; i>=0; --i)
        for (j=n-1; j>=0; --j)
            scanf("%d", &a[i][j]);
 
    for (i=n-1; i>=0; --i)
        for (j=n-1; j>=0; --j)
            {
                if (i+2 < n)
                    if (a[i][j] + a[i+1][j] + a[i+2][j] > maxSum)
                        maxSum = a[i][j] + a[i+1][j] + a[i+2][j];
                
                if (j+2 < n)
                    if (a[i][j] + a[i][j+1] + a[i][j+2] > maxSum)
                        maxSum = a[i][j] + a[i][j+1] + a[i][j+2];
 
                if (i +1 < n && j + 1 < n)
                {
                    if (a[i][j] + a[i+1][j] + a[i+1][j+1] > maxSum)
                        maxSum = a[i][j] + a[i+1][j] + a[i+1][j+1];
                    if (a[i][j] + a[i][j+1] + a[i+1][j+1] > maxSum)
                        maxSum = a[i][j] + a[i][j+1] + a[i+1][j+1];
                }
 
                if (i + 1 < n && j != 0)
                {
                    if (a[i][j] + a[i+1][j] + a[i+1][j-1] > maxSum)
                        maxSum = a[i][j] + a[i+1][j] + a[i+1][j-1];
                    if (a[i][j] + a[i][j-1] + a[i+1][j-1] > maxSum)
                        maxSum = a[i][j] + a[i][j-1] + a[i+1][j-1];
                }
            }
    printf("%d", maxSum);
}
то же самое, только 0 -> N
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
#include <stdio.h>
#include <vector>
 
using namespace std;
 
int maxSum = -500, n;
int i, j;
vector < vector <int> > a;
 
void main()
{
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
 
    scanf("%d", &n);
    a.resize(n, vector<int>(n));
 
    for (i=0; i<n; ++i)
        for (j=0; j<n; ++j)
            scanf("%d", &a[i][j]);
 
    for (i=0; i<n; ++i)
        for (j=0; j<n; ++j)
            {
                if (i+2 < n)
                    if (a[i][j] + a[i+1][j] + a[i+2][j] > maxSum)
                        maxSum = a[i][j] + a[i+1][j] + a[i+2][j];
                
                if (j+2 < n)
                    if (a[i][j] + a[i][j+1] + a[i][j+2] > maxSum)
                        maxSum = a[i][j] + a[i][j+1] + a[i][j+2];
 
                if (i +1 < n && j + 1 < n)
                {
                    if (a[i][j] + a[i+1][j] + a[i+1][j+1] > maxSum)
                        maxSum = a[i][j] + a[i+1][j] + a[i+1][j+1];
                    if (a[i][j] + a[i][j+1] + a[i+1][j+1] > maxSum)
                        maxSum = a[i][j] + a[i][j+1] + a[i+1][j+1];
                }
 
                if (i + 1 < n && j != 0)
                {
                    if (a[i][j] + a[i+1][j] + a[i+1][j-1] > maxSum)
                        maxSum = a[i][j] + a[i+1][j] + a[i+1][j-1];
                    if (a[i][j] + a[i][j-1] + a[i+1][j-1] > maxSum)
                        maxSum = a[i][j] + a[i][j-1] + a[i+1][j-1];
                }
            }
    printf("%d", maxSum);
}
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
26.06.2012, 11:49     Скорость выполнения, а так же работа с дв. файлами #14
Цитата Сообщение от nexen Посмотреть сообщение
Да, о ней.
Во-первых, замените вектор векторов на обычный статический массив. Дело в том, что у них очень старый компилятор, который, к тому же, запускается в режиме без оптимизаций.
Во-вторых, там очень много ввода, даже scanf с таким не справится. Тут нужно писать свою функцию чтения.
В третьих, в этой задаче есть небольшой чит.
Можно поставить в начале условие
C++
1
2
if ( n > 700 )
   n = 700;
Это в ~3 раза ускорит программу.
Evg
Эксперт С++Автор FAQ
 Аватар для Evg
16825 / 5246 / 321
Регистрация: 30.03.2009
Сообщений: 14,127
Записей в блоге: 26
26.06.2012, 11:53     Скорость выполнения, а так же работа с дв. файлами #15
Цитата Сообщение от nexen Посмотреть сообщение
Допустим так для N -> 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
#include <stdio.h>
 
int main (void)
{
  int a[5] = { 2, 1, 3, 4, 5 };
  int i, max;
 
  max = a[0];
 
#if 1
  for (i = 0; i < 5; i++)
#else
  for (i = 4; i >= 0; i--)
#endif
  {
    if (a[i] > max)
    {
      printf ("Перезаписываем значение max\n");
      max = a[i];
    }
  }
 
  printf ("max=%d\n", max);
 
  return 0;
}
затем поменяй "#if 1" на "#if 0" (в результате чего цикл пойдёт в обратную сторону). Сравни результаты и попробуй сам ответить на вопрос
nexen
187 / 180 / 3
Регистрация: 27.01.2012
Сообщений: 1,335
26.06.2012, 12:57  [ТС]     Скорость выполнения, а так же работа с дв. файлами #16
Цитата Сообщение от diagon Посмотреть сообщение
...
Кстати, только что как раз ришал "Числовую последовательность", что у вас в блоге. Было бы интересно увидеть решение динамикой (во всяком случае в "обсуждении" задачи говорят, что есть нерекурсивное решение) или ещё чем-то.
Я, как идиот, забыл, что такое логарифм, и искал уровень двоичным поиском.. >_<"

Добавлено через 1 час 1 минуту
Цитата Сообщение от Evg Посмотреть сообщение
Запусти вот такой код:...
Хах, да уж, искал что-то глубокое, а ведь ответ был на поверхности, спасибо большое : D

Цитата Сообщение от diagon Посмотреть сообщение
Во-первых, замените вектор векторов на обычный статический массив. Дело в том, что у них очень старый компилятор, который, к тому же, запускается в режиме без оптимизаций.
Во-вторых, там очень много ввода, даже scanf с таким не справится. Тут нужно писать свою функцию чтения.
В третьих, в этой задаче есть небольшой чит.
Можно поставить в начале условие
C++
1
2
if ( n > 700 )
   n = 700;
Это в ~3 раза ускорит программу.
1) Т.е. если я использую вектор, то он (у них) быстрее статического массива, а при векторе векторов (и глубже) медленнее, так?
2) Если вы имеете ввиду в прямом смысле "функцию чтения", то странно, что требуется такой глубокий "анализ" на 35%, учитывая сложность таких задач, как "Шаблон" или та же "Числа в последовательности".
Если же вы имеете ввиду разверстку цикла, то разве не будет хуже? Ведь мне каждый раз придется проверять, не считываю ли я слишком много? (Т.е., если я разверну 100 scanf'ов, а у меня осталось 97, то каждую итерацию мне нужно будет проверять n-i <= 100 и уже от него скакать либо scanf'ом 100 к ряду, либо обычным циклом от 1 до 97 без разверстки.
p.s Где-то читал про "дв. разверстку", ту, где при помощи рекурсии каким-то образом можно считать, допустим 100 раз scanf'ом, осталось 97, уменьшили scanf'ы до 50, считали и так далее, но не видел реализации, да и странно это, ведь выделение памяти в рекурсии займет, как я думаю, больше времени, чем обычный цикл? Вы об этом что-нибудь знаете?
3) Не знаю почему, но "чит" не работает. Уже пробовал ;<
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
26.06.2012, 13:06     Скорость выполнения, а так же работа с дв. файлами #17
Цитата Сообщение от nexen Посмотреть сообщение
1) Т.е. если я использую вектор, то он (у них) быстрее статического массива, а при векторе векторов (и глубже) медленнее, так?
Вектор у них в любом случае медленнее статического массива, т.к. их компилятор не умеет инлайнить.
Итого, для одного обращения к элементу матрицы вызываются две функции, а это довольно сильно тормозит программу.

Цитата Сообщение от nexen Посмотреть сообщение
Если вы имеете ввиду в прямом смысле "функцию чтения", то странно, что требуется такой глубокий "анализ" на 35%
Если бы там стоял нормальный сервер, то сдать эту задачу было бы проще. Но сейчас там стоит какое-то корыто, поэтому приходится извращаться.

Как вариант, можно открыть файл как бинарный, и читать по много байт за раз.
Shandr_71
13 / 13 / 1
Регистрация: 05.12.2011
Сообщений: 84
26.06.2012, 16:35     Скорость выполнения, а так же работа с дв. файлами #18
Цитата Сообщение от nexen Посмотреть сообщение
Хм, а это можно как-то правилами логики объяснить? Или имеется ввиду лишняя проверка, созданная компилятором при трансляции?

p.s Эм, да, что-то я забыл про теги кода :<
Assembler
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//От 0 до n
    xor rcx, rcx
lo: 
    nop
    inc rcx
    cmp rcx, n
    jb lo
 
//От n до 0
    mov rcx, n
    dec rcx
lo:
    nop
    dec rcx
    jnz lo

Разницу здесь составляет команда
Assembler
1
cmp rcx, n
которая при нахождении n в памяти может занять 100-200 тактов.
Deviaphan
Делаю внезапно и красиво
Эксперт C++
 Аватар для Deviaphan
1283 / 1217 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
26.06.2012, 16:53     Скорость выполнения, а так же работа с дв. файлами #19
Цитата Сообщение от Shandr_71 Посмотреть сообщение
rcx
О_о
Это на какой архитектуре?
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
26.06.2012, 16:55     Скорость выполнения, а так же работа с дв. файлами
Еще ссылки по теме:

Как узнать скорость выполнения программы? C++
C++ Работа с файлами
Работа с файлами C++

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

Или воспользуйтесь поиском по форуму:
Shandr_71
13 / 13 / 1
Регистрация: 05.12.2011
Сообщений: 84
26.06.2012, 16:55     Скорость выполнения, а так же работа с дв. файлами #20
Цитата Сообщение от Deviaphan Посмотреть сообщение
О_о
Это на какой архитектуре?
Дык на х64.
Yandex
Объявления
26.06.2012, 16:55     Скорость выполнения, а так же работа с дв. файлами
Ответ Создать тему
Опции темы

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