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

Парадокс - C++

Восстановить пароль Регистрация
 
alig007
1 / 1 / 0
Регистрация: 30.01.2013
Сообщений: 28
30.04.2013, 00:38     Парадокс #1
Назрел вопрос. Релизовывал сортировку слиянием, далее при тестировании, точнее при замерах времени работы, наткнулся на удивительную вещь:

вот код мейна номер один:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void main()
{
    const int N = 200000;
    int A[N];
 
    int F;
 
    for (int i = N-1; i>= 0; i--)
        A[i] = rand();
 
    int start = GetTickCount();
 
    merge_sort (A, 1, N);
 
    int end = GetTickCount();
 
    cout<<end - start;
 
    _getch();
}
время работы: см. изображение 1.

после чего сделал следующее:
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
#include "head.h"
 
void main()
{
    const int N = 200000;
    int A[N];
 
    int F;
 
    for (int i = N-1; i>= 0; i--)
        A[i] = rand();
 
    cout<<1<<endl;
 
    int start = GetTickCount();
 
    merge_sort (A, 1, N);
 
    int end = GetTickCount();
 
    cout<<end - start;
 
    _getch();
}
время работы см. картинку 2. Причем не обязательно cout, вообще, добавление любого действия, перед сортировкой дает такой результат.
Вопрос: КАК ???
Вот сама сортировка, как понимаю дело в ней, поскольку все остальное ведет себя нормально:
Кликните здесь для просмотра всего текста
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
void merge (int *Array, int p, int q, int r)
{
    int i = p - 1, j = q;
 
    int *result = new int[r - p + 1];
 
    int k = 0;
 
    while(i < q && j < r)
        if (Array[i] < Array[j])
            result[k++] = Array[i++];
        else
            result[k++] = Array[j++];
 
    while (i < q)
        result[k++] = Array[i++];
    while (j < r)
        result[k++] = Array[j++];
 
    for (int i = 0, j = p - 1 ; i<r - p + 1; i++, j++)
        Array[j] = result[i];
 
    delete[] result;
}
 
void merge_sort (int *Array, int Start, int End)
{
    if (Start < End)
    {
        int Split = (Start + End)/2;
        merge_sort (Array, Start, Split);
        merge_sort (Array, Split + 1, End);
        merge (Array, Start, Split, End);
    }
}
Миниатюры
Парадокс   Парадокс  
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
30.04.2013, 00:38     Парадокс
Посмотрите здесь:

C++ Парадокс: значение переменой равно её адресу. Помогите разобраться!
Парадокс
парадокс с ОЗУ
Парадокс Зенона ActionScript
Парадокс
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
MrGluck
Ворчун
Эксперт С++
 Аватар для MrGluck
4920 / 2663 / 243
Регистрация: 29.11.2010
Сообщений: 7,405
30.04.2013, 01:00     Парадокс #2
Возможно, дело в оптимизации компилятором, вызовы происходят в разное время.
alig007
1 / 1 / 0
Регистрация: 30.01.2013
Сообщений: 28
30.04.2013, 12:07  [ТС]     Парадокс #3
происходит только для этой сортировки, все остальные которые писал, работают независимо от того есть перед их запуском что-то или нету...

Добавлено через 10 часов 51 минуту
пробовал в онлайн компиляторах, разницы во времени никакой. Пробовал на другом компьютере, разница есть, но где-то в секунду для больших массивов. Может дело в Visual Studio 2012 ? И у себя и на другом компе компилировал в ней.
Croessmah
Модератор
Эксперт С++
 Аватар для Croessmah
11815 / 6794 / 769
Регистрация: 27.09.2012
Сообщений: 16,867
Записей в блоге: 2
Завершенные тесты: 1
30.04.2013, 12:26     Парадокс #4
Цитата Сообщение от alig007 Посмотреть сообщение
Может дело в Visual Studio 2012 ?
Можно запустить без отладчика - тогда время мало отличается.
Если линковать статически студийный рантайм, то результаты вообще резко меняются.
Ternsip
 Аватар для Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
30.04.2013, 14:48     Парадокс #5
alig007, Ссравнение делают на одинаковых тестах, не факт, что ваш компилятор не делает randomize, srand(GetTickcCount()) перед запуском

Добавлено через 8 минут
alig007, Вот такой код, всё окей работает, никаких оптимизаций или чудес (PS я грань кости не менял, всегда генерируется по одному и тому же распределению => массивы одинаковые)
Кликните здесь для просмотра всего текста
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 <iostream>
#include <set>
#include <vector>
#include <limits>
#include <queue>
#include <string>
#include <map>
#include <algorithm>
#include "Windows.h"
#include <conio.h>
 
using namespace std;
 
void merge (int *Array, int p, int q, int r)
{
    int i = p - 1, j = q;
 
    int *result = new int[r - p + 1];
 
    int k = 0;
 
    while(i < q && j < r)
        if (Array[i] < Array[j])
            result[k++] = Array[i++];
        else
            result[k++] = Array[j++];
 
    while (i < q)
        result[k++] = Array[i++];
    while (j < r)
        result[k++] = Array[j++];
 
    for (int i = 0, j = p - 1 ; i<r - p + 1; i++, j++)
        Array[j] = result[i];
 
    delete[] result;
}
 
void merge_sort (int *Array, int Start, int End)
{
    if (Start < End)
    {
        int Split = (Start + End)/2;
        merge_sort (Array, Start, Split);
        merge_sort (Array, Split + 1, End);
        merge (Array, Start, Split, End);
    }
} 
 
int main(){            
    freopen("input.txt", "rt", stdin);
    freopen("output.txt", "wt", stdout);
    const int N = 200000;
    int A[N];
 
    int F;
 
    for (int i = N-1; i>= 0; i--)
        A[i] = rand()%100000;
 
    int start = GetTickCount();
 
    merge_sort (A, 1, N);
    
    cout << GetTickCount() - start;
 
    return 0;
}
alig007
1 / 1 / 0
Регистрация: 30.01.2013
Сообщений: 28
30.04.2013, 18:43  [ТС]     Парадокс #6
кстати, если поменять debug на release то время сокращается, но по прежнему остается разрыв в несколько секунд
Ternsip
 Аватар для Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
30.04.2013, 18:51     Парадокс #7
alig007, я вам скинул код, в котором всё верно работает
ya_noob
_
200 / 144 / 9
Регистрация: 08.10.2011
Сообщений: 432
30.04.2013, 19:06     Парадокс #8
Цитата Сообщение от Ternsip Посмотреть сообщение
C++
1
A[i] = rand()%100000;
rand() умеет генерировать числа > 32767 ?
Tulosba
:)
Эксперт C++
4378 / 3221 / 297
Регистрация: 19.02.2013
Сообщений: 9,044
30.04.2013, 19:11     Парадокс #9
Цитата Сообщение от ya_noob Посмотреть сообщение
rand() умеет генерировать числа > 32767 ?
Зависит от реализации http://www.cplusplus.com/reference/cstdlib/RAND_MAX/
Ternsip
 Аватар для Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
30.04.2013, 20:44     Парадокс #10
ya_noob, нет, кто вам сказал ? я написал Mod для страховки

Добавлено через 1 минуту
ya_noob, я хотел показать, что нет никакого парадокса, есть невнимательность

Добавлено через 4 минуты
Tulosba, во всех стандартах с++, действительно, это 2 неполных байта
Tulosba
:)
Эксперт C++
4378 / 3221 / 297
Регистрация: 19.02.2013
Сообщений: 9,044
30.04.2013, 21:02     Парадокс #11
Ternsip, не во всех https://ideone.com/TPcbJD
Ternsip
 Аватар для Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
30.04.2013, 22:17     Парадокс #12
Tulosba, забавно, спасибо, кстати, в C++ builder от Embarcadero rand тоже большое число кидал, так что защита -- сила привычки

Добавлено через 5 минут
Tulosba, я проверил через http://codeforces.com/ GNU C++0x 4, разве gcc-4.7.2 не относится ? потому как выдаёт именно 32767, уж простите за придиру, я люблю мелкие шалости

Добавлено через 1 минуту
Tulosba, Просто, потом, на запросы пиши по ГОСТу, дорогой ГОСТЬ буду отвечать вот такими дерзкими вещами, как различия в спецификациях. В целом, это не плохой рычаг на защите своего софта.
alig007
1 / 1 / 0
Регистрация: 30.01.2013
Сообщений: 28
30.04.2013, 23:38  [ТС]     Парадокс #13
Ternsip, нихрена там не работает, точно так же как и в моем все. по крайней мере в VS 2012. Пробовал компилить в старом Билдере 6, и во-певых, сортирует быстрее чем ВС 2012, во-вторых, нету разницы между первым и вторым вариантами. все-таки дело в продукте майкрософта скорее всего.
Ternsip
 Аватар для Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
01.05.2013, 00:15     Парадокс #14
alig007, а вы точно моё решение собрали ? без всякой отсебятины ? у меня тоже MVS2012. Создайте новый проект с решением.

Добавлено через 1 минуту
alig007, попробуйте засекать через ctime clock
alig007
1 / 1 / 0
Регистрация: 30.01.2013
Сообщений: 28
01.05.2013, 15:10  [ТС]     Парадокс #15
Ternsip, проверил все заново, без изменений. да и вообще, чем отличается ваш код?) да и неважно чем засекать, разница между 20 секундами и 2 секундами и без таймера заметна)
Croessmah
Модератор
Эксперт С++
 Аватар для Croessmah
11815 / 6794 / 769
Регистрация: 27.09.2012
Сообщений: 16,867
Записей в блоге: 2
Завершенные тесты: 1
01.05.2013, 15:44     Парадокс #16
Запуск без отладчика? (ctrl+F5)
Ternsip
 Аватар для Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
01.05.2013, 16:05     Парадокс #17
alig007, тогда запускайте ваш код на http://codeforces.com/ там будет время исполнения

Добавлено через 46 секунд
alig007, http://codeforces.com/problemset/customtest
на этом сайте гарантированно верно показывеется время работы программы
alig007
1 / 1 / 0
Регистрация: 30.01.2013
Сообщений: 28
01.05.2013, 18:08  [ТС]     Парадокс #18
Croessmah, без отладчика, во первых - время одинаково для обоих случаев, во-вторых - время сортировки гораздо меньше чем с отладчиком. Так в чем же дело все-таки?

Добавлено через 1 минуту
блин, а если еще и в режиме Realese а не Debug то время вообще офигительно мало, для 200 000 елементов, 31 мс, по сравнению с 160 в режиме Debug
Ternsip
 Аватар для Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
01.05.2013, 18:10     Парадокс #19
alig007, запустите ваш код на http://codeforces.com/problemset/customtest и ваша проблема решится, правда, там потребуется регистрация. Вся ваша беда в том, что вы не можете разобраться со средой.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
01.05.2013, 18:34     Парадокс
Еще ссылки по теме:

Математический парадокс
Парадокс MySQL
Парадокс Бертрана

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

Или воспользуйтесь поиском по форуму:
alig007
1 / 1 / 0
Регистрация: 30.01.2013
Сообщений: 28
01.05.2013, 18:34  [ТС]     Парадокс #20
Ternsip, да я понял уже) ладно, спсибо всем)
Yandex
Объявления
01.05.2013, 18:34     Парадокс
Ответ Создать тему
Опции темы

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