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

Сложности распределения памяти - C++

Восстановить пароль Регистрация
 
BlackDay28
0 / 0 / 0
Регистрация: 12.12.2013
Сообщений: 8
12.12.2013, 20:51     Сложности распределения памяти #1
Ребят, никогда не писал под студию, всё время на Dev C++, там проблем с изначальным кодом не было, программа работала прекрасно, а вот в студии ругается на то что переменная в массиве, только с динамическими массивами пока как то не очень получается, ругается на неверное распределение памяти
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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
#include <stdio.h>
#include <ctime>
#include <stdlib.h>
#include <iostream>
#include <conio.h>
#define A  10000
using namespace std;
int arr[10000];
void Quick(int l,int r,int*arr);
void Random(int*arr,int num)
{
            for (int n=0; n<num ; n++) arr[n]=0+rand()%10;
}
int Time(int t1,int t2)
{
    return t2-t1;
}
void Scaler(int  &num)
{
    num*=10;
}
int Bubble(int num)
{
    int t1=clock();
    for (int p=0;p<A;p++)
    {
         int *arr = new int[num];
    Random(arr,num);
    
    int temp;
            for (int i=1; i<=num ; i++)
              {
                for (int j=1; j<=num-i; j++) 
                    {
                        if (arr[j]>arr[j+1]) 
                            {
                                 temp=arr[j]; 
                                 arr[j]=arr[j+1];
                                 arr[j+1]=temp;
                            }
                    }
               }
                delete [] arr;
               }
    
               int t2=clock();
                return Time(t1,t2);
}
int Shell(int num)
{
int t1=clock();
    for (int p=0;p<A;p++)
    {
         int *arr = new int[num];
                Random(arr,num);
        int step = num / 2;
        while (step > 0)
    {
      for (int i = 0; i < (num - step); i++)
                {
                    int j = i;
                    while (j >= 0 && arr[j] > arr[j + step])
                    {
                        int temp = arr[j];
                        arr[j] = arr[j + step];
                        arr[j + step] = temp;
                        j--; 
                    }
                }
                step = step / 2;
                delete[] arr;   
            }
         
}
    
   int t2=clock();
               return   Time(t1,t2);
}
int QuickTime(int l,int r,int num)
{
    
        int t1=clock();
            for (int o=0;o<A;o++)
{   
    int *arr = new int[num];
    Random(arr,num);
        Quick(0,num-1,arr);
        delete [] arr;
    }
                
         int t2=clock();
   return Time(t1,t2);
}
void Quick(int l,int r,int*arr)
{   
    int x = arr[l + (r - l) / 2];
    int i = l;
    int j = r;
    while(i <= j)
    {
        while(arr[i] < x) i++;
        while(arr[j] > x) j--;
        if(i <= j)
        {
            swap(arr[i], arr[j]);
            i++;
            j--;
        }
    }
    if (i<r)
                Quick(i, r,arr);
    
    if (l<j)    
        Quick(l, j,arr);   
}
 
void Merge(int l, int r,int num) {
 
   
    if (r == l)
        return;
    if (r - l == 1) { 
        if (arr[r] < arr[l])
            swap(arr[r], arr[l]);
        return;
    }
    int m = (r + l) / 2;
    Merge(l, m, num);
    Merge(m + 1, r, num);
   int *buf = new int[num];
    int xl = l;
    int xr = m + 1;
    int cur = 0;
    while (r - l + 1 != cur) {
        if (xl > m)
            buf[cur++] = arr[xr++];
        else if (xr > r)
            buf[cur++] = arr[xl++];
        else if (arr[xl] > arr[xr])
            buf[cur++] = arr[xr++];
        else buf[cur++] = arr[xl++];
 
    }
    for (int i = 0; i < cur; i++) arr[i + l] = buf[i];
}
 
int MergeTime(int l,int r,int num)
{
    
 
    int t1=clock();
        for (int o=0;o<A;o++)
{
        Random(arr,num);
    Merge(0,num-1,num);
    
    delete [] &arr;
}
        int t2=clock();
        return Time(t1,t2);
}
int main()
{
    
    cout << "\\\Cycles ="<<A<<"///";
    int num=10;
    for(int i=0;i<4;i++)
    {
     int *arr = new int[num];
cout << "\n///Bubble Sort/// \n--------------------\nNumber of elements = "<<num<<"\nTime of work = " << Bubble(num)<<"ms\n-------------------";
cout << "\n///Shell Sort/// \n--------------------\nNumber of elements = "<<num<<"\nTime of work = " << Shell(num)<<"ms\n-------------------";
cout << "\n///Merge Sort/// \n--------------------\nNumber of elements = "<<num<<"\nTime of work = " << MergeTime(0,num-1,num)<<"ms\n-------------------";      
cout << "\n///Quick Sort/// \n--------------------\nNumber of elements = "<<num<<"\nTime of work = " << QuickTime(0,num-1,num)<<"ms\n-------------------";      
Scaler(num);
}
cout << "\\\END///";
return 0;
}
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
zss
Модератор
Эксперт С++
 Аватар для zss
5950 / 5555 / 1786
Регистрация: 18.12.2011
Сообщений: 14,195
Завершенные тесты: 1
12.12.2013, 21:13     Сложности распределения памяти #2
Так вроде все нормально.
У меня компилятор VS 2008 выдает только предупреждение на строки типа
C++
1
cout << "\\\END///";
Неизвестная escape - последовательность.
Не хватает обратных слашей, надо
C++
1
cout << "\\\\\\END///";
BlackDay28
0 / 0 / 0
Регистрация: 12.12.2013
Сообщений: 8
12.12.2013, 21:20  [ТС]     Сложности распределения памяти #3
выдаёт heap corruption detected

Добавлено через 3 минуты
вероятно он думает что arr уже удалён, но я вроде как его пересоздаю же
Croessmah
Модератор
Эксперт С++
 Аватар для Croessmah
11841 / 6820 / 771
Регистрация: 27.09.2012
Сообщений: 16,911
Записей в блоге: 2
Завершенные тесты: 1
12.12.2013, 21:23     Сложности распределения памяти #4
C++
1
2
3
            for (int i=1; i<=num ; i++)
              {
                for (int j=1; j<=num-i; j++)
уверены в правильности индексации?

и утечки памяти
BlackDay28
0 / 0 / 0
Регистрация: 12.12.2013
Сообщений: 8
12.12.2013, 21:26  [ТС]     Сложности распределения памяти #5
да, это конечно ошибка, да только вылетает он на функции Shell
alsav22
5282 / 4801 / 442
Регистрация: 04.06.2011
Сообщений: 13,587
12.12.2013, 21:46     Сложности распределения памяти #6
Цитата Сообщение от BlackDay28 Посмотреть сообщение
только вылетает он на функции Shell
Виснет в Bubble(), после delete [] arr. В циклах где-то выход за пределы (в arr, в одном из элементов, мусор).
Миниатюры
Сложности распределения памяти  
alsav22
5282 / 4801 / 442
Регистрация: 04.06.2011
Сообщений: 13,587
12.12.2013, 21:51     Сложности распределения памяти #7
И зачем эта функция, если потом массив удаляется?
BlackDay28
0 / 0 / 0
Регистрация: 12.12.2013
Сообщений: 8
12.12.2013, 21:57  [ТС]     Сложности распределения памяти #8
мне нужно исключительно замерить время сортировки

Добавлено через 3 минуты
и дело не в этом, уже поправил, останавливает не из за этого
alsav22
5282 / 4801 / 442
Регистрация: 04.06.2011
Сообщений: 13,587
12.12.2013, 22:00     Сложности распределения памяти #9
Цитата Сообщение от BlackDay28 Посмотреть сообщение
уже поправил
Если поправили, то и код было бы неплохо увидеть (что поправили? как поправили?). Ясновидящих тут нет.
BlackDay28
0 / 0 / 0
Регистрация: 12.12.2013
Сообщений: 8
12.12.2013, 22:09  [ТС]     Сложности распределения памяти #10
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
      int Bubble(int num)
{
    int t1=clock();
    for (int p=0;p<A;p++)
    {
   int *arr = new int[num];
    Random(arr,num);
            for (int i=0; i<num ; i++)
              {
                for (int j=0; j<num-i; j++) 
                    {
                        if (arr[j]>arr[j+1]) 
                            {
                                 swap(arr[j],arr[j+1]);
                            }
                    }
               }
                delete [] arr;
               }
    
               int t2=clock();
                return Time(t1,t2);
}
Добавлено через 2 минуты
я о счётчике, баг остался

Добавлено через 1 минуту
сомневаюсь что теперь он хоть как то способен выйти из пределов

Добавлено через 3 минуты
а нет, сортировка неправильная, счётчик второй точно, но всё же не работает даже после правки
alsav22
5282 / 4801 / 442
Регистрация: 04.06.2011
Сообщений: 13,587
12.12.2013, 22:11     Сложности распределения памяти #11
Всё равно выход в Bubble (j = 9, а значит j + 1 = 10 - выход за пределы), и зависание при delete [] arr.
Миниатюры
Сложности распределения памяти  
BlackDay28
0 / 0 / 0
Регистрация: 12.12.2013
Сообщений: 8
12.12.2013, 22:25  [ТС]     Сложности распределения памяти #12
теперь выводит это... _Block_Type_Is_Valid (pHead->nBlockUse)

Добавлено через 51 секунду
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int Bubble(int num)
{
    int t1=clock();
    for (int p=0;p<A;p++)
    {
         int *arr = new int[num];
    Random(arr,num);
            for (int i=0; i<num ; i++)
              {
                for (int j=num-1; j>i; j--) 
                    {
                        if (arr[j]<arr[j-1]) 
                            {
                                 swap(arr[j],arr[j-1]);
                            }
                    }
               }
                delete [] arr;
               }
    
               int t2=clock();
                return Time(t1,t2);
}
вот верный алгоритм он то точно не глючит
alsav22
5282 / 4801 / 442
Регистрация: 04.06.2011
Сообщений: 13,587
12.12.2013, 22:40     Сложности распределения памяти #13
Вы в Shell(), в while(), delete[] arr делаете? И что потом в этом цикле делать?

Добавлено через 2 минуты
А это что (в MergeTime): delete [] &arr? Освобождение памяти под массивом на стеке?
BlackDay28
0 / 0 / 0
Регистрация: 12.12.2013
Сообщений: 8
12.12.2013, 22:44  [ТС]     Сложности распределения памяти #14
тот баг я уже заметил, но зависает всё ещё в bubble

Добавлено через 4 минуты
а всё, вроде теперь всё в норме хотя на 1000 элементов вылет, кажется я не прописал удаление buf
DU
1477 / 1053 / 45
Регистрация: 05.12.2011
Сообщений: 2,279
12.12.2013, 22:54     Сложности распределения памяти #15
замерять время сортировки и при этом учитывать время на создание и удаление диманического массива - это неправильно. динамическое выделение может быть сильно больше времени сортировки маленького массива.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
12.12.2013, 23:16     Сложности распределения памяти
Еще ссылки по теме:

C++ модель распределения памяти разделами переменного размера с общей очередью со стратегией «наименее подходящий»
Можно ли разместить переменную в нужную ячейку памяти и реально ли хранить данные, разбросанными по памяти? C++
Как работает strcpy с точки зрения распределения памяти? C++

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

Или воспользуйтесь поиском по форуму:
BlackDay28
0 / 0 / 0
Регистрация: 12.12.2013
Сообщений: 8
12.12.2013, 23:16  [ТС]     Сложности распределения памяти #16
там массив в 10к элементов который сортируется 10к раз, меня намного больше пугает что для слияния приходится глобальный массив делать, вот это реально пакость

Добавлено через 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
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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
#include <stdio.h>
#include <ctime>
#include <stdlib.h>
#include <iostream>
#include <conio.h>
#define A  10000
using namespace std;
void Quick(int l,int r,int*arr);
void Random(int*arr,int num)
{
            for (int n=0; n<num ; n++) arr[n]=0+rand()%10;
}
int Time(int t1,int t2)
{
    return t2-t1;
}
void Scaler(int  &num)
{
    num*=10;
}
int Bubble(int num)
{
    int t1=clock();
     int *arr = new int[num];
    for (int p=0;p<A;p++)
    {
        
    Random(arr,num);
            for (int i=0; i<num ; i++)
              {
                for (int j=num-1; j>i; j--) 
                    {
                        if (arr[j]<arr[j-1]) 
                            {
                                 swap(arr[j],arr[j-1]);
                            }
                    }
               }
               
               }
     delete [] arr;
               int t2=clock();
                return Time(t1,t2);
}
int Shell(int num)
{
int t1=clock();
int  *arr = new int[num];
    for (int p=0;p<A;p++)
    {
                Random(arr,num);
        int step = num / 2;
        while (step > 0)
    {
      for (int i = 0; i < (num - step); i++)
                {
                    int j = i;
                    while (j >= 0 && arr[j] > arr[j + step])
                    {
                        int temp = arr[j];
                        arr[j] = arr[j + step];
                        arr[j + step] = temp;
                        j--; 
                    }
                }
                step = step / 2;
   
            }
            
}
     delete [] arr;
   int t2=clock();
               return   Time(t1,t2);
}
int QuickTime(int l,int r,int num)
{
    
        int t1=clock();
            for (int o=0;o<A;o++)
{   
    int *arr = new int[num];
    Random(arr,num);
        Quick(0,num-1,arr);
        delete [] arr;
    }
                
         int t2=clock();
   return Time(t1,t2);
}
void Quick(int l,int r,int*arr)
{   
    int x = arr[l + (r - l) / 2];
    int i = l;
    int j = r;
    while(i <= j)
    {
        while(arr[i] < x) i++;
        while(arr[j] > x) j--;
        if(i <= j)
        {
            swap(arr[i], arr[j]);
            i++;
            j--;
        }
    }
    if (i<r)
                Quick(i, r,arr);
    
    if (l<j)    
        Quick(l, j,arr);   
}
    int arr1[10000];
void Merge(int l, int r,int num) {
 
   
    if (r == l)
        return;
    if (r - l == 1) { 
        if (arr1[r] < arr1[l])
            swap(arr1[r], arr1[l]);
        return;
    }
    int m = (r + l) / 2;
    Merge(l, m, num);
    Merge(m + 1, r, num);
   int *buf = new int[num];
    int xl = l;
    int xr = m + 1;
    int cur = 0;
    while (r - l + 1 != cur) {
        if (xl > m)
            buf[cur++] = arr1[xr++];
        else if (xr > r)
            buf[cur++] = arr1[xl++];
        else if (arr1[xl] > arr1[xr])
            buf[cur++] = arr1[xr++];
        else buf[cur++] = arr1[xl++];
 
    }
    for (int i = 0; i < cur; i++) arr1[i + l] = buf[i];
    delete [] buf;
}
int MergeTime(int l,int r,int num)
{
    
 
    int t1=clock();
        for (int o=0;o<A;o++)
{
     int *arr = new int[num];
        Random(arr,num);
    Merge(0,num-1,num);
    
    delete [] arr;
}
        int t2=clock();
        return Time(t1,t2);
}
int main()
{
    
    cout << "\\\\\\Cycles ="<<A<<"///\n";
    cout << "___________________________";
    int num=10;
    for(int i=0;i<4;i++)
    {
     int *arr = new int[num];
cout << "\n///Bubble Sort/// \n--------------------\nNumber of elements = "<<num<<"\nTime of work = " << Bubble(num)<<"ms\n-------------------";
cout << "\n///Shell Sort/// \n--------------------\nNumber of elements = "<<num<<"\nTime of work = " << Shell(num)<<"ms\n-------------------";
cout << "\n///Merge Sort/// \n--------------------\nNumber of elements = "<<num<<"\nTime of work = " << MergeTime(0,num-1,num)<<"ms\n-------------------";      
cout << "\n///Quick Sort/// \n--------------------\nNumber of elements = "<<num<<"\nTime of work = " << QuickTime(0,num-1,num)<<"ms\n-------------------";      
Scaler(num);
}
cout << "\\\\\\END///";
return 0;
}
Добавлено через 4 минуты
если есть какие то дополнения, или подсказки в плане того как оптимизировать, хотел бы увидеть ваше мнение, а в общем спасибо всем , кто помог, сам бы долго копался
Yandex
Объявления
12.12.2013, 23:16     Сложности распределения памяти
Ответ Создать тему
Опции темы

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