Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
alig007
1 / 1 / 0
Регистрация: 30.01.2013
Сообщений: 28
#1

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

30.04.2013, 00:38. Просмотров 701. Ответов 19
Метки нет (Все метки)

Назрел вопрос. Релизовывал сортировку слиянием, далее при тестировании, точнее при замерах времени работы, наткнулся на удивительную вещь:

вот код мейна номер один:
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);
    }
}
0
Миниатюры
Парадокс   Парадокс  
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
30.04.2013, 00:38
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Парадокс (C++):

Парадокс выбора - C++
Имеет ли смысл напрочь забыть о всех функциях прямиком из Си? Существует ли полная замена в Си++ всему, что есть в стандартной библиотеке...

Парадокс: значение переменной равно её адресу - C++
Друзья! Вот код, в нём всё понятно. Выводятся одинаковые значения. Но ведь этого не может быть! Хотя бы потому не может, что по адресу,...

Парадокс - Логика и множества
Математический парадокс Допустим я у друга взял 100 рублей ,пошел в магазин и потерял их, встретил подругу, взял у неё 50 рублей ,купил...

If else парадокс) - PHP
if (!isset($fupload) or empty($fupload) or $fupload =='') { $avatar = &quot;avatars/net-avatara.jpg&quot;; } else { //код...

Парадокс - MySQL
ситуация в следующем есть цмс но это не важно, на лакалке к базе данных цмс добавил еще три своих таблице. так вот на локалке все ок,...

Парадокс - Оперативная память
Здравствуйте! Вот моя машина- материнка Foxconn NF4SK8AA-8KRS SLI nForse4, 4DDR, 2xPCL-Ex, процессор Socket 939 2.4ГГц, ОЗУ DDR1...

19
MrGluck
Модератор
Эксперт CЭксперт С++
7490 / 4605 / 691
Регистрация: 29.11.2010
Сообщений: 12,589
30.04.2013, 01:00 #2
Возможно, дело в оптимизации компилятором, вызовы происходят в разное время.
0
alig007
1 / 1 / 0
Регистрация: 30.01.2013
Сообщений: 28
30.04.2013, 12:07  [ТС] #3
происходит только для этой сортировки, все остальные которые писал, работают независимо от того есть перед их запуском что-то или нету...

Добавлено через 10 часов 51 минуту
пробовал в онлайн компиляторах, разницы во времени никакой. Пробовал на другом компьютере, разница есть, но где-то в секунду для больших массивов. Может дело в Visual Studio 2012 ? И у себя и на другом компе компилировал в ней.
0
Croessmah
Ушел
Эксперт CЭксперт С++
13553 / 7704 / 872
Регистрация: 27.09.2012
Сообщений: 19,006
Записей в блоге: 3
Завершенные тесты: 1
30.04.2013, 12:26 #4
Цитата Сообщение от alig007 Посмотреть сообщение
Может дело в Visual Studio 2012 ?
Можно запустить без отладчика - тогда время мало отличается.
Если линковать статически студийный рантайм, то результаты вообще резко меняются.
0
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;
}
0
alig007
1 / 1 / 0
Регистрация: 30.01.2013
Сообщений: 28
30.04.2013, 18:43  [ТС] #6
кстати, если поменять debug на release то время сокращается, но по прежнему остается разрыв в несколько секунд
0
Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
30.04.2013, 18:51 #7
alig007, я вам скинул код, в котором всё верно работает
0
ya_noob
_
202 / 146 / 9
Регистрация: 08.10.2011
Сообщений: 432
30.04.2013, 19:06 #8
Цитата Сообщение от Ternsip Посмотреть сообщение
C++
1
A[i] = rand()%100000;
rand() умеет генерировать числа > 32767 ?
0
Tulosba
:)
Эксперт С++
4396 / 3232 / 297
Регистрация: 19.02.2013
Сообщений: 9,045
30.04.2013, 19:11 #9
Цитата Сообщение от ya_noob Посмотреть сообщение
rand() умеет генерировать числа > 32767 ?
Зависит от реализации http://www.cplusplus.com/reference/cstdlib/RAND_MAX/
0
Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
30.04.2013, 20:44 #10
ya_noob, нет, кто вам сказал ? я написал Mod для страховки

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

Добавлено через 4 минуты
Tulosba, во всех стандартах с++, действительно, это 2 неполных байта
0
Tulosba
:)
Эксперт С++
4396 / 3232 / 297
Регистрация: 19.02.2013
Сообщений: 9,045
30.04.2013, 21:02 #11
Ternsip, не во всех https://ideone.com/TPcbJD
1
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, Просто, потом, на запросы пиши по ГОСТу, дорогой ГОСТЬ буду отвечать вот такими дерзкими вещами, как различия в спецификациях. В целом, это не плохой рычаг на защите своего софта.
0
alig007
1 / 1 / 0
Регистрация: 30.01.2013
Сообщений: 28
30.04.2013, 23:38  [ТС] #13
Ternsip, нихрена там не работает, точно так же как и в моем все. по крайней мере в VS 2012. Пробовал компилить в старом Билдере 6, и во-певых, сортирует быстрее чем ВС 2012, во-вторых, нету разницы между первым и вторым вариантами. все-таки дело в продукте майкрософта скорее всего.
0
Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
01.05.2013, 00:15 #14
alig007, а вы точно моё решение собрали ? без всякой отсебятины ? у меня тоже MVS2012. Создайте новый проект с решением.

Добавлено через 1 минуту
alig007, попробуйте засекать через ctime clock
0
alig007
1 / 1 / 0
Регистрация: 30.01.2013
Сообщений: 28
01.05.2013, 15:10  [ТС] #15
Ternsip, проверил все заново, без изменений. да и вообще, чем отличается ваш код?) да и неважно чем засекать, разница между 20 секундами и 2 секундами и без таймера заметна)
0
01.05.2013, 15:10
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
01.05.2013, 15:10
Привет! Вот еще темы с ответами:

Сетевой парадокс - Сети
Добрый день Ребят, помогите, такая вот проблемка. Несколько ноутбуков никак не реагируют на сеть, сетевая карта выдает &quot;нет подключения&quot;....

Парадокс Зенона - ActionScript
Переместил с исходников Добавлено через 4 минуты а можно в пародоксе зенона сделать чтобы Ball двигался не к мышке а к другому...

парадокс с ОЗУ - Оперативная память
небольшие непоняткиО_о есть 3 динозавра, условно будем их называть: 1-512мб озу, 2-1г озу, 3-256 мб озу. Вся озу - DDR DIMM. 3ий комп...

Математический парадокс - Алгебра
Математический парадокс: Допустим я у друга взял 100 рублей, пошел в магазин и потерял их, встретил подругу, взял у нее 50 рублей,...


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

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

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