Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
 
Рейтинг 4.57/7: Рейтинг темы: голосов - 7, средняя оценка - 4.57
nexen
187 / 180 / 25
Регистрация: 27.01.2012
Сообщений: 1,335
#1

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

24.06.2012, 22:07. Просмотров 1346. Ответов 20
Метки нет (Все метки)

Здравствуйте. У меня есть несколько вопросов, на которые я уже давненько ищу ответы, а именно :

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 секунд). Кто-нибудь может пояснить, откуда? Почему такая разница?
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
24.06.2012, 22:07
Ответы с готовыми решениями:

Работа с файлами в С++. Подскажите , что не так , сам пробую разобраться и никак не получается
#include &lt;iostream&gt; #include &lt;fstream&gt; #include &lt;windows.h&gt; #include...

Скорость выполнения.
Есть консольное приложение, работающее с огромными текстовыми файлами,...

Скорость выполнения delete
Всем привет! Интересует почему скорость выполнения деструктора зависит...

Скорость выполнения операторов
Привет всем. У меня есть задачка с которой не могу справится, она очень простая...

Скорость выполнения программы
Здравствуйте, уважаемые форумчане. Решил задаться таким вопросом. Какой из...

20
xADMIRALx
67 / 61 / 5
Регистрация: 09.06.2012
Сообщений: 291
24.06.2012, 22:10 #2
Указатели всегда были быстрее...
но луче спросите у Evg он точна вам ответит... http://www.cyberforum.ru/members/18334.html
на счет inline уже писали,почитайте блог у него,много чего интересного на счет оптимизации...
1
Avazart
Эксперт С++
7703 / 5612 / 545
Регистрация: 10.12.2010
Сообщений: 25,206
Записей в блоге: 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));
Быстрее
1
nexen
187 / 180 / 25
Регистрация: 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 секунд). Кто-нибудь может пояснить, откуда? Почему такая разница?
Значит остались только эти три вопроса. (К сожалению, не могу исправлять заголовок темы)
0
Evg
Эксперт CАвтор FAQ
19134 / 6976 / 522
Регистрация: 30.03.2009
Сообщений: 19,628
Записей в блоге: 30
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 секунд). Кто-нибудь может пояснить, откуда? Почему такая разница?
Опять-таки без конкретного примера можно только гадать
1
nexen
187 / 180 / 25
Регистрация: 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 не подгружается..
0
Shandr_71
13 / 13 / 6
Регистрация: 05.12.2011
Сообщений: 84
25.06.2012, 22:21 #7
Насчет циклов: разница возникает из-за дополнительного сравнения в ассемберном цикле.
1
nexen
187 / 180 / 25
Регистрация: 27.01.2012
Сообщений: 1,335
26.06.2012, 07:21  [ТС] #8
Цитата Сообщение от Shandr_71 Посмотреть сообщение
Насчет циклов: разница возникает из-за дополнительного сравнения в ассемберном цикле.
Хм, а это можно как-то правилами логики объяснить? Или имеется ввиду лишняя проверка, созданная компилятором при трансляции?

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

p.s Эм, да, что-то я забыл про теги кода :<
0
Deviaphan
Делаю внезапно и красиво
Эксперт С++
1306 / 1221 / 72
Регистрация: 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));
Быстрее
С каких пор создание копий векторов эффективнее создания пустого вектора и изменения его размера без копирований?
1
diagon
Higher
1937 / 1203 / 120
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
26.06.2012, 08:13 #10
Цитата Сообщение от nexen Посмотреть сообщение
) Для таких классов, как vector/set/map и прочих, что быстрее - iterator или [] ?
Для вектора эквивалентно.
В map оператор индексации работает за логарифм, а с итератором получается линейная сложность(т.е. намного хуже).
У set'a вообще нету оператора индексации.

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

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

Цитата Сообщение от nexen Посмотреть сообщение
Цикл ищет максимальную тройку элементов в двумерном массиве, при этом эти элементы должны соприкосаться друг с другом (без рекурсии, тупо в лоб)
Вы не об задаче случаем?
1
kazak
3057 / 2378 / 255
Регистрация: 11.03.2009
Сообщений: 5,438
Завершенные тесты: 1
26.06.2012, 09:57 #11
Цитата Сообщение от nexen Посмотреть сообщение
но вот беда, fseek в упор не видел feof и EOF. Как ни старался, он его проходит и ничего путного о конце файла не говорит, причем не важно - прошел он его мимо или прямо-таки "наступил" на него.. Кто-нибудь сталкивался?
1. fseek возвращает результат своего выполнения, если все хорошо, fseek вернет ноль. О конце файла данная функция в принципе ничего рассказать не может, т.к. у нее несколько иное назначение.
2. Символа EOF в файле не существует, это просто некоторое условное значение, которое возвращают функции чтения, когда не могут считать данные по причине их отсутствия.
1
Evg
Эксперт CАвтор FAQ
19134 / 6976 / 522
Регистрация: 30.03.2009
Сообщений: 19,628
Записей в блоге: 30
26.06.2012, 10:11 #12
Цитата Сообщение от nexen Посмотреть сообщение
7) Недавно сталкивался с задачкой на оптимизацию и столкнулся с фактом, который не могу объяснить, а именно : цикл от 0 до N работает медленнее, чем цикл от N до 0, причем при больших данных, эта разница была огромной (Задача была в небольшой работе с массивом, был двойной цикл от 0 до (максимум) 2000. При максимальном значении, разница между 0->N и N->0 была в районе 0,3 секунд). Кто-нибудь может пояснить, откуда? Почему такая разница?
Можешь показать мне нормальные два примера кода, которые бы отличались только направлением обхода в цикле и на которых бы видна была разница в скорости исполнения? То, что ты привёл - абсолютно не понятно к чему и зачем. Если хочешь получить ответ на вопрос - потрать своё драгоценное время на то, чтобы его внятно сформулировать
1
nexen
187 / 180 / 25
Регистрация: 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);
}
0
diagon
Higher
1937 / 1203 / 120
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
26.06.2012, 11:49 #14
Цитата Сообщение от nexen Посмотреть сообщение
Да, о ней.
Во-первых, замените вектор векторов на обычный статический массив. Дело в том, что у них очень старый компилятор, который, к тому же, запускается в режиме без оптимизаций.
Во-вторых, там очень много ввода, даже scanf с таким не справится. Тут нужно писать свою функцию чтения.
В третьих, в этой задаче есть небольшой чит.
Можно поставить в начале условие
C++
1
2
if ( n > 700 )
   n = 700;
Это в ~3 раза ускорит программу.
1
Evg
Эксперт CАвтор FAQ
19134 / 6976 / 522
Регистрация: 30.03.2009
Сообщений: 19,628
Записей в блоге: 30
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" (в результате чего цикл пойдёт в обратную сторону). Сравни результаты и попробуй сам ответить на вопрос
2
nexen
187 / 180 / 25
Регистрация: 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) Не знаю почему, но "чит" не работает. Уже пробовал ;<
0
diagon
Higher
1937 / 1203 / 120
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
26.06.2012, 13:06 #17
Цитата Сообщение от nexen Посмотреть сообщение
1) Т.е. если я использую вектор, то он (у них) быстрее статического массива, а при векторе векторов (и глубже) медленнее, так?
Вектор у них в любом случае медленнее статического массива, т.к. их компилятор не умеет инлайнить.
Итого, для одного обращения к элементу матрицы вызываются две функции, а это довольно сильно тормозит программу.

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

Как вариант, можно открыть файл как бинарный, и читать по много байт за раз.
1
Shandr_71
13 / 13 / 6
Регистрация: 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 тактов.
1
Deviaphan
Делаю внезапно и красиво
Эксперт С++
1306 / 1221 / 72
Регистрация: 22.03.2011
Сообщений: 3,744
26.06.2012, 16:53 #19
Цитата Сообщение от Shandr_71 Посмотреть сообщение
rcx
О_о
Это на какой архитектуре?
0
Shandr_71
13 / 13 / 6
Регистрация: 05.12.2011
Сообщений: 84
26.06.2012, 16:55 #20
Цитата Сообщение от Deviaphan Посмотреть сообщение
О_о
Это на какой архитектуре?
Дык на х64.
0
26.06.2012, 16:55
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
26.06.2012, 16:55

Скорость выполнения запросов в SQLite
Здравствуйте! Собственно, мне нужно осуществлять динамическую запись в журнал...

От чего зависит скорость выполнения программы?
от чего больше всего зависит скорость выполнения программы?

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


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

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

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