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

Быстрый стек, с малым обьемом памяти - C++

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 17, средняя оценка - 4.65
outoftime
║XLR8║
 Аватар для outoftime
505 / 427 / 33
Регистрация: 25.07.2009
Сообщений: 2,297
10.01.2010, 15:23     Быстрый стек, с малым обьемом памяти #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
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
#include <iostream>
#include <sstream>
#include <string>
#include <algorithm>
 
#define FOR(i,a,b) for (int i(a), _b(b); i < _b; ++i)
#define ABS(a) ( (a) < 0 ? -(a) : a )
 
using namespace std;
 
class stack
{
public:
    stack()
    {
        sz = 0;
        a = (int *) calloc (sz, sizeof(int));
    }
    ~stack(){}
    void push(int n)
    {
        a = (int*) realloc(++sz, sizeof(int));
        a[sz-1] = n;
    }
    int pop()
    {
        int d = a[sz-1];
        a = (int *) realloc(--sz, sizeof(int));
        return d;
    }
private:
    int* a, sz;
};
 
int main()
{
    int n;
    cin >> n;
    stack a[1000];
    while (n--)
    {
        int d;
        string s;
        cin >> s >> d;
        if (s == "PUSH")
        {
            int dd;
            cin >> dd;
            a[d-1].push(dd);
        }
        else
            cout << a[d-1].pop() << endl;
    }
    return 0;
}
http://acm.timus.ru/problem.aspx?space=1&num=1220
нужно за 1 секунду и 0,75Мб памяти обработать 0 < N ≤ 100000 запросов к 1 ≤ A ≤ 1000 разным стекам, гарантируется что все запросы коректны, т.е. вывод елемента со стека не может быть раньше чем ввод.
Вроде написал, но компилятор упорно говорит что cannot convert parameter 1 from 'int' to 'void *', как видно a = (int *) realloc(--sz, sizeof(int)); я (int *) дописал, т.е. все верно, может я чего-то непонял, в чем ошибка, подскажите пожалуйста..

Добавлено через 3 минуты
немного доработал ввод, на сишный, т.к. он быстрее, но ошибка с выделением памяти осталась, вот
код
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
#include <iostream>
 
class stack
{
public:
    stack()
    {
        sz = 0;
        a = (int *) calloc (sz, sizeof(int));
    }
    ~stack(){}
    void push(int n)
    {
        a = (int*) realloc(++sz, sizeof(int));
        a[sz-1] = n;
    }
    int pop()
    {
        int d = a[sz-1];
        a = (int *) realloc(--sz, sizeof(int));
        return d;
    }
private:
    int* a, sz;
};
 
int main()
{
    int n;
    scanf("%d",&n);
    stack a[1000];
    while (n--)
    {
        int d;
        char* s;
        scanf("%s",&s);
        if (s == "PUSH")
        {
            int dd;
            scanf("%d",&dd);
            a[d-1].push(dd);
        }
        else
            printf("%d",a[d-1].pop());
    }
    return 0;
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
10.01.2010, 15:23     Быстрый стек, с малым обьемом памяти
Посмотрите здесь:

C++ Стек и освобождение памяти
C++ при работе рекурсивной функции заканчивается стек и программа соответственно; как сделать так, чтобы она писала "стек закончился"?
C++ Программа добавляет введенный массив 5*5 в стек и выводит полученный стек двумя столбцами
C++ Выделить в памяти 1024 ячейки по 8 байт и вывести их адреса(МИНИ менеджер памяти))
Структура стек (: добавить элемент в стек, удалить элемент из стека, получить значение с вершины стека, размер стека...) C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
odip
Эксперт C++
 Аватар для odip
7225 / 3287 / 58
Регистрация: 17.06.2009
Сообщений: 14,165
10.01.2010, 21:24     Быстрый стек, с малым обьемом памяти #21
C
1
2
3
4
5
6
struct block_t;
struct block_t {
    int value[MAX_BLOCK_SIZE];
    struct block_t *prev_blk;
};
typedef struct block_t block_t;
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
outoftime
║XLR8║
 Аватар для outoftime
505 / 427 / 33
Регистрация: 25.07.2009
Сообщений: 2,297
10.01.2010, 21:47  [ТС]     Быстрый стек, с малым обьемом памяти #22
int value[MAX_BLOCK_SIZE];
я запутался, а где тогда выделять malloc-ом память? или здесь надо просто указатель которому выделяем память?
odip
Эксперт C++
 Аватар для odip
7225 / 3287 / 58
Регистрация: 17.06.2009
Сообщений: 14,165
10.01.2010, 21:52     Быстрый стек, с малым обьемом памяти #23
в памяти выделяется одна структура типа block_t
block_t *pblk= malloc( sizeof(block_t) );
outoftime
║XLR8║
 Аватар для outoftime
505 / 427 / 33
Регистрация: 25.07.2009
Сообщений: 2,297
10.01.2010, 22:02  [ТС]     Быстрый стек, с малым обьемом памяти #24
Цитата Сообщение от odip Посмотреть сообщение
в памяти выделяется одна структура типа block_t
block_t *pblk= malloc( sizeof(block_t) );
извените коль что просто я и си++ не очень хорошо знаю, а чистый си вообще.. и кажется где-то читал что определять размер струкруры нельзя

Добавлено через 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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <stdio.h>
 
struct block_t;
struct block_t
{
    int val[19];
    struct block_t* prev;
};
 
typedef struct block_t block_t;
 
struct stack
{
    block_t* inf;
    int top;
    stack()
    {
        inf->prev = 0;
        top = 0;
    }
    ~stack(){}
    void push(int &n)
    {
        if (top == 19)
        {
            top = 0;
            block_t* tmp = malloc(sizeof(block_k));
        }
        else
        {
            inf->val[top++] = n;
        }
    }
};
 
int main()
{    
    return 0;
}
Добавлено через 11 секунд
куча ошибок:

Добавлено через 1 минуту
16 C:\Documents and Settings\Администратор\Рабочий стол\timus.c syntax error before "stack"

16 C:\Documents and Settings\Администратор\Рабочий стол\timus.c [Warning] no semicolon at end of struct or union
19 C:\Documents and Settings\Администратор\Рабочий стол\timus.c [Warning] data definition has no type or storage class
20 C:\Documents and Settings\Администратор\Рабочий стол\timus.c syntax error before '}' token
22 C:\Documents and Settings\Администратор\Рабочий стол\timus.c syntax error before '&' token

C:\Documents and Settings\Администратор\Рабочий стол\timus.c In function `push':

27 C:\Documents and Settings\Администратор\Рабочий стол\timus.c `block_k' undeclared (first use in this function)
(Each undeclared identifier is reported only once for each function it appears in.)
31 C:\Documents and Settings\Администратор\Рабочий стол\timus.c `inf' undeclared (first use in this function)
31 C:\Documents and Settings\Администратор\Рабочий стол\timus.c `n' undeclared (first use in this function)
At top level:
34 C:\Documents and Settings\Администратор\Рабочий стол\timus.c syntax error before '}' token
GRANDEATH
39 / 39 / 1
Регистрация: 13.09.2009
Сообщений: 108
10.01.2010, 22:20     Быстрый стек, с малым обьемом памяти #25
У меня другое решение. Я создаю массив определенного размера и массив дескрипторов на него. То есть грубо говоря - разбиваю массив на страницы (извиняюсь, за неправильный термин, но не знаю, как ещё можно сказать). Отдельно есть массив char, содержащий 0 - если данный блок свободен, 1 - если занят. Я думаю, что сдесь лучше сего было использовать биты, а не байты, то было бы лучше. Если объясните, как делать тоже самое, только с битами, скажу СПАСИБО.
Тут два класса Memory - описывающий функции allocate_block free_block - выделяющий память и помечающий блок, как свободный. Реализация стека через выделяемые блоки памяти.
Писал на С++, поэтому накладных расходов много.
Вот код. Извиняюсь за неструктурированнось, так классы были разбиты по файлам, которые я инклюдил.
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
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
// Task_2.cpp : Defines the entry point for the console application.
#include <stdio.h>
//#include <malloc.h>
 
 
 
#define BLOCK_SIZE 40
#define ARRAY_SIZE 400000
#define NUMBER_OF_POINTERS 10000 // = ARRAY_SIZE / BLOCK_SIZE
 
 
 
class Memory
{
public:
    //set_free();
    int* allocate_block(); //?????? ??????
    void free_block(int *p); // ???????? ??????
    Memory(void);
    ~Memory(void);
    void print(int a,int b);
 
private:
    int* data;
    char* indexes;
};
 
 
 
struct Descriptor
{
    int* position; //??????? ? ???? ????????
    Descriptor *next; //????????? ??????????
};
 
 
 
 
class stack
{
public:
    stack(void);
    ~stack(void);
    void push(int i);
    int pop();
    int debug_info_pos(); 
private:
    Descriptor root; //?????? ??????
    int pos; //?????? ???????
    int* local_pointer; // ????????? ?? ??????? ????. ???????? ????????.
};
 
 
int main()
{
 
        
        int n;
        scanf("%d",&n);
        stack *a = new stack[1000];
  
        char* temp = new char[20]; // 
        while (n--)
        {
                int d;
                scanf("%s",temp);
                //cin >> temp;
                scanf("%d",&d);
                //cin >> d;
                if (temp[1] == 'U') //
                {
                        int dd;
                        //cout << dd;
                        scanf("%d",&dd);
                        //cin >> dd;
                        a[d-1].push(dd);
                }
                else
                        //cout << a[d-1].pop() << endl;
                        printf("%d\n",a[d-1].pop());
        }
        
    
    //system("pause");
    
    return 0;
}
 
 
Memory my_memory;
 
stack::stack(void)
{
    local_pointer = root.position = my_memory.allocate_block(); //Âûäåëèòü áëîê ГЁГ§ "ГЄГіГ·ГЁ"
    root.next = NULL;
    pos = 0;
}
 
 
 
 
void stack::push(int i)
{
    if (pos == BLOCK_SIZE - 1) //Åñëè óæå Г*ГҐГІ ïÿìÿòè Гў ýòîé Г±ГІГ°Г*Г*èöå
    {
        Descriptor *temp = &root;
        while ( temp->next!= NULL)
        {
            temp = temp->next;
        }; //Èùåì Гў Г±ГЇГЁГ±ГЄГҐ Г*óëåâîé ГіГЄГ*Г§Г*òåëü
        
        
        temp->next = new Descriptor; // ÑîçäГ*ГҐГ¬ äåñêðèïòîð
        temp->next->position = my_memory.allocate_block();
        local_pointer = temp->next->position;
        temp->next->next = NULL; //Ñëåäóùåãî Г*ГҐГІ
        
        pos = 0; // Г‡Г*ïîëГ*ГїГІГј áëîê Г± 0-ГЈГ® ýëåìåГ*ГІГ*
        
    }
    *(local_pointer + pos) = i; //Г‡Г*ГЇГЁГёГЁ ГІГіГ¤Г* Г¤Г*Г*Г*ûå
    pos++; //Óâåëè÷ü ïîçèöèþ Г*Г* 1
}
 
int stack::pop()
{
    pos--; // ÓìåГ*ГјГёГј ГЁГ*äåêñ
    
    
    if (pos < 0) //Åñëè ГЁГ*äåêñ ìåГ*ГјГёГҐ 0. Г’Г® ГҐГ±ГІГј ГІГҐГЄГіГ№ГЁГ© áëîê ïóñòîé
    {
        Descriptor *temp = &root;
        if (temp->next != NULL) //Åñëè Г*ГҐ îäèГ* áëîê
        {   
            while ( temp->next->next!= NULL)
            {
                temp = temp->next;
            }; //Èùåì Гў Г±ГЇГЁГ±ГЄГҐ Г*äðåñ äåñêðèïòîðГ*, Г·ГҐГ© ñëåäóþùèé ýëåìåГ*ГІ Г± Г*óëåâûì ГіГЄГ*Г§Г*òåëåì
            
            my_memory.free_block(temp->next->position); //îñâîáîäèòü ýòîò áëîê
            temp->next = NULL; //Г“Г*è÷òîæèòü áëîê
            local_pointer = temp->position; //ÏðèñâГ*ГЁГўГ*ГҐГ¬ Г*äðåñ Г*Г* âåðõóøêó Г±ГІГҐГЄГ*
            pos = BLOCK_SIZE - 2; // ÏîñëåäГ*ГїГї ïîçèöèÿ Гў ýòîì áëîêå
        }
        else throw(1);
        
    }
    //int *p = (local_pointer + pos);
    int res = *(local_pointer + pos); //Èçâëåêè Г¤Г*Г*Г*ûå
    //cout << "pos = " << pos << " ";
    //if (res == 59) throw(2);
    /*static bool first = true;
    if (first)
    {
        my_memory.print(0,20);
        first = false;
    } */
    return res;
}
 
stack::~stack(void)
{
}
 
int stack::debug_info_pos()
{ 
    return pos;
};
 
Memory::Memory(void)
{
    data = new int[ARRAY_SIZE];
    indexes = new char[NUMBER_OF_POINTERS];
    for (int i = 0; i < NUMBER_OF_POINTERS; i++)
        indexes[i] = 0; //Âñå ñâîáîäГ*Г®
}
 
int* Memory::allocate_block()
{
    int i = 0;
    while (i++ < NUMBER_OF_POINTERS)
    {
        if (indexes[i] == 0) //Åñëè ýòîò áëîê ñâîáîäåГ*
        {
            indexes[i] = 1; //ÓñòГ*Г*îâèòü ГґГ«Г*ГЈ Г§Г*Г*ÿòîñòè
            return &data[BLOCK_SIZE*i]; //ÂåðГ*ГіГІГј ГіГЄГ*Г§Г*òåëü Г*Г* ýòîò áëîê. ÄëèГ*Г*Г* ГЄГ*æäîãî áëîêГ* BLOCK_SIZE
        }
    }
    
    return NULL; //ГЌГҐГІ ГІГ*êîé ГЇГ*ìÿòè
}
 
void Memory::free_block(int* p)
{
    int offset = (p - &data[0])/sizeof(int); //Îïðåäåëè ñìåùåГ*ГЁГҐ
    indexes[0] = 0; //ÓñòГ*Г*îâè ГґГ«Г*ГЈ ñâîáîäГ*îñòè
}
 
Memory::~Memory(void)
{
 
};
/*void Memory::print(int a,int b)
{
    for (int i = a; i < b; i++)
        cout << "memory[" << i << "] = " << data[i] << endl;
    cout << endl;
}*/
Выложил, вдруг кому-то станет интересен принцип.

Добавлено через 33 секунды
Результат:
1220 C++ Accepted 0.078 761 KB
Добавлено через 55 секунд
Извиняюсь за кодировку...
outoftime
║XLR8║
 Аватар для outoftime
505 / 427 / 33
Регистрация: 25.07.2009
Сообщений: 2,297
10.01.2010, 22:41  [ТС]     Быстрый стек, с малым обьемом памяти #26
Цитата Сообщение от GRANDEATH Посмотреть сообщение
как делать тоже самое, только с битами
кажется на си++ есть библиотека для работы с битмасками

Добавлено через 9 минут
подскажите как мне доделать свой вариант? катать ваш пример не хочу, толку будет мало, а так в голове останется..
GRANDEATH
39 / 39 / 1
Регистрация: 13.09.2009
Сообщений: 108
10.01.2010, 23:31     Быстрый стек, с малым обьемом памяти #27
Я так понимаю, что ты хочешь сделать через списки.
Тебе потребуется массив из 1000 структур, содержащие
1. Смещение внутри твоего 19-ти элементного блока
2. Указатель на начало списка

Список состоит из структур, котрые, как уже я увидел ты сделал.

Суть в чем - у тебя есть массив из структур, назови его своеобразной кучей
struct data_block
{
int data[19];
data_block *next;
}
и есть массив битов, которые показывают свободен ли этот блок.
1. Запись
Записывай в текущем блоке преременные, пока смещение не будет 18 (счет в си с 0 )
Если блок забит - найди по биту первый свободный блок и пристыкуй его к своему списку.
Установи смещение на 0.
2. Чтение.
Считывай, пока смещение не станет 0.Как только стало нулем отстыкуй блок. Пометь его как свободный (для дальнейшего использования). Установи смещение на 18 (последный элемент).

В целом - это примитивный алгоритм.
Я бы описал основные данные так:
struct data_block
{
int data[19];
data_block *next;
} - твоя единица памяти
data_block array[ Максимальное_ЧИСЛО_БЛОКОВ_В_СИСТЕМЕ];
byte access[Максимальное_ЧИСЛО_БЛОКОВ_В_СИСТЕМЕ]; // Здесь бы использовать битовое поле. Но я его не знаю.

struct stack_begin
{
int offset;
data_block* last; //Это излишне. Для того, что бы каждый раз тебе не пробегать по списку, для нахождения последнего элемента. Быстродействие увечилит в разы, а память сожрет только паку килобайт (ну или десятков)
data_block* first; //Указатель на первый блок
}

Теперь надо будет обьявить пару функций
1. Запихни в стек
2. Вытащи из стека
+ дополнит. функции
1. Верни свободный блок из кучи
2. Возвтрати блок в кучу.
3. Верни адрес предпоследнего блока в списке.
Ты так хотел делать?
outoftime
║XLR8║
 Аватар для outoftime
505 / 427 / 33
Регистрация: 25.07.2009
Сообщений: 2,297
11.01.2010, 09:55  [ТС]     Быстрый стек, с малым обьемом памяти #28
GRANDEATH, то как я хотел сделать я сделал, дальше я потерялся, просто у меня выходит, что выделяем мы память сразу всю, и при этом говорим две вещи:
1) каждому непустому стеку как минимум 1 блок
2) в каждом блоке 19 элементов
Вот эти две вещи меня и запутали, т.к. у нас каждый стек, который занимает больше N*19 элементов будет занимать на 18*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
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
#include <iostream>
 
#define FOR(i,a,b) for (int i(a), _n(b); i < _n; ++i)
 
//stack struct------------------------------------------------------------------
 
struct node;
struct node
{
public:
    int* val;
    node* prev;
};
typedef struct node node;
 
//const initialize--------------------------------------------------------------
 
const int heap_size = 60*1000,
          block_size = 19;
          
//memory class------------------------------------------------------------------
 
class Memory
{
public:
    Memory();
    ~Memory();
    int* find();
    void free(int *);
private:
    int* bit_set, //масив, для занятых/свободных блоков
       * heap; //блок на все стеки, или просто куча
};
 
//stack class-------------------------------------------------------------------
 
class stack
{
public:
    stack();
    ~stack();
    void push(int &);
    int pop();
private:
    node* head;
    int top; 
};
 
//main--------------------------------------------------------------------------
 
int main()
{
    int n, d;
    char* s = new char[5];
    scanf("%d", &n);
    stack* a = new stack[1000];
    while(n--)
    {
        scanf("%s%d", s, &d);
        if (s[1] == 'U')
        {
            int dd;
            scanf("%d", &dd);
            a[d-1].push(dd);
        }
        else printf("%d", a[d-1].pop());
    }
    return 0;
}
 
//class Memory------------------------------------------------------------------
 
Memory::Memory()
{
    bit_set = (int *) calloc (heap_size, sizeof(int)); // вделяем память на "битмаску" и "кучу"
    heap = (int *) malloc(heap_size * block_size * sizeof(int));
}
 
Memory::~Memory()
{
    bit_set = (int *) realloc (bit_set, 0); //освобождаем --||--
    heap = (int *) realloc (heap, 0);
}
 
int* Memory::find() //ищем и возвращаем указатель на ближайший свободный блок
{
    FOR(i,0,heap_size)
        if (!bit_set[i])
        {
            bit_set[i] = 1;
            return (heap + i*block_size);
        }
    return 0;
}
 
void Memory::free(int *n) //определяем блок как свободный
{
    bit_set[ (n - heap)/block_size ] = 0;
}
 
//class stack-------------------------------------------------------------------
 
Memory my_mem;
 
stack::stack() //выделяем память на корень стека
{
    top = 0;
    head = new node;
    head->prev = 0;
    head->val = my_mem.find();
}
 
stack::~stack() //освобождаем память
{
    delete head;
}
 
void stack::push(int &n)
{
    if (top == block_size) //если текущий блок забит ищем новый
    {
        top = 0;
        node* tmp = new node;
        tmp->prev = head;
        tmp->val = my_mem.find();
        head = tmp;
    }
    else head->val[top++] = n;
}
 
int stack::pop()
{
    if (top == 0) //если текущий блок пуст, переходим к предыдущему
    {
        node* tmp = head;
        my_mem.free(tmp->val);
        head = head->prev;
        delete tmp;
        top = block_size-1;
        return head->val[top--];
    }
    else return head->val[top--];
}
Есть проблемка: почему-то int stack :: pop() пашет неправельно, он достает элемент перед тем который надо достать

Добавлено через 39 минут
поисправлял ошибки, int stack :: pop() возвращала не предыдущий а следующий, вот верный код:
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
#include <iostream>
 
#define FOR(i,a,b) for (int i(a), _n(b); i < _n; ++i)
 
//stack struct------------------------------------------------------------------
 
struct node;
struct node
{
public:
    int* val;
    node* prev;
};
typedef struct node node;
 
//const initialize--------------------------------------------------------------
 
const int heap_size = 60*1000,
          block_size = 19;
          
//memory class------------------------------------------------------------------
 
class Memory
{
public:
    Memory();
    ~Memory();
    int* find();
    void free(int *);
private:
    int* bit_set,
       * heap;
};
 
//stack class-------------------------------------------------------------------
 
class stack
{
public:
    stack();
    ~stack();
    void push(int &);
    int pop();
private:
    node* head;
    int top;
};
 
//main--------------------------------------------------------------------------
 
int main()
{
    int n, d;
    char* s = new char[5];
    scanf("%d", &n);
    stack* a = new stack[1000];
    while(n--)
    {
        scanf("%s%d", s, &d);
        if (s[1] == 'U')
        {
            int dd;
            scanf("%d", &dd);
            a[d-1].push(dd);
        }
        else printf("%d\n", a[d-1].pop());
    }
    return 0;
}
 
//class Memory------------------------------------------------------------------
 
Memory::Memory()
{
    bit_set = (int *) calloc (heap_size, sizeof(int));
    heap = (int *) malloc(heap_size * block_size * sizeof(int));
}
 
Memory::~Memory()
{
    bit_set = (int *) realloc (bit_set, 0);
    heap = (int *) realloc (heap, 0);
}
 
int* Memory::find()
{
    FOR(i,0,heap_size)
        if (!bit_set[i])
        {
            bit_set[i] = 1;
            return (heap + i*block_size);
        }
    return 0;
}
 
void Memory::free(int *n)
{
    bit_set[ (n - heap)/block_size ] = 0;
}
 
//class stack-------------------------------------------------------------------
 
Memory my_mem;
 
stack::stack()
{
    top = 0;
    head = new node;
    head->prev = 0;
    head->val = my_mem.find();
}
 
stack::~stack()
{
    delete head;
}
 
void stack::push(int &n)
{
    if (top == block_size)
    {
        top = 0;
        node* tmp = new node;
        tmp->prev = head;
        tmp->val = my_mem.find();
        head = tmp;
        head->val[top++] = n;
    }
    else head->val[top++] = n;
}
 
int stack::pop()
{
    if (top == 0)
    {
        node* tmp = head;
        my_mem.free(tmp->val);
        head = head->prev;
        delete tmp;
        top = block_size-1;
        return head->val[top--];
    }
    else return head->val[--top];
}
Добавлено через 3 минуты
С++ Wrong answer 0.015сек 481 КБ

Добавлено через 5 минут
У меня вылетает последний елемент блока

Добавлено через 6 минут
нашел, исправил,
вот
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
#include <iostream>
 
#define FOR(i,a,b) for (int i(a), _n(b); i < _n; ++i)
 
//stack struct------------------------------------------------------------------
 
struct node;
struct node
{
public:
    int* val;
    node* prev;
};
typedef struct node node;
 
//const initialize--------------------------------------------------------------
 
const int heap_size = 60*1000,
          block_size = 19;
          
//memory class------------------------------------------------------------------
 
class Memory
{
public:
    Memory();
    ~Memory();
    int* find();
    void free(int *);
private:
    int* bit_set,
       * heap;
};
 
//stack class-------------------------------------------------------------------
 
class stack
{
public:
    stack();
    ~stack();
    void push(int &);
    int pop();
private:
    node* head;
    int top;
};
 
//main--------------------------------------------------------------------------
 
int main()
{
    int n, d;
    char* s = new char[5];
    scanf("%d", &n);
    stack* a = new stack[1000];
    while(n--)
    {
        scanf("%s%d", s, &d);
        if (s[1] == 'U')
        {
            int dd;
            scanf("%d", &dd);
            a[d-1].push(dd);
        }
        else printf("%d\n", a[d-1].pop());
    }
    return 0;
}
 
//class Memory------------------------------------------------------------------
 
Memory::Memory()
{
    bit_set = (int *) calloc (heap_size, sizeof(int));
    heap = (int *) malloc(heap_size * block_size * sizeof(int));
}
 
Memory::~Memory()
{
    bit_set = (int *) realloc (bit_set, 0);
    heap = (int *) realloc (heap, 0);
}
 
int* Memory::find()
{
    FOR(i,0,heap_size)
        if (!bit_set[i])
        {
            bit_set[i] = 1;
            return (heap + i*block_size);
        }
    return 0;
}
 
void Memory::free(int *n)
{
    bit_set[ (n - heap)/block_size ] = 0;
}
 
//class stack-------------------------------------------------------------------
 
Memory my_mem;
 
stack::stack()
{
    top = 0;
    head = new node;
    head->prev = 0;
    head->val = my_mem.find();
}
 
stack::~stack()
{
    delete head;
}
 
void stack::push(int &n)
{
    if (top == block_size)
    {
        top = 0;
        node* tmp = new node;
        tmp->prev = head;
        tmp->val = my_mem.find();
        head = tmp;
    }
    head->val[top++] = n;
}
 
int stack::pop()
{
    if (top == 0)
    {
        node* tmp = head;
        my_mem.free(tmp->val);
        head = head->prev;
        delete tmp;
        top = block_size;
    }
    return head->val[--top];
}


Добавлено через 1 минуту
Результат проверки № теста Время работы Выделено памяти
Memory limit exceeded 10 0.062 869 КБ
GRANDEATH
39 / 39 / 1
Регистрация: 13.09.2009
Сообщений: 108
11.01.2010, 15:41     Быстрый стек, с малым обьемом памяти #29
Memory limit exceeded 10 0.062 869 КБ
Вот оно и гадость( Попробуй выделить не 20, а 40?
+ сотри #icnclude <iostream>
Мало ли что системе в голову взбредет...
odip
Эксперт C++
 Аватар для odip
7225 / 3287 / 58
Регистрация: 17.06.2009
Сообщений: 14,165
11.01.2010, 15:45     Быстрый стек, с малым обьемом памяти #30
Memory limit exceeded 10 0.062 869 КБ
Да фигню какую-то в коде написал.
Например зачем вот это:
Memory::Memory()
{
bit_set = (int *) calloc (heap_size, sizeof(int));
heap = (int *) malloc(heap_size * block_size * sizeof(int));
}
GRANDEATH
39 / 39 / 1
Регистрация: 13.09.2009
Сообщений: 108
11.01.2010, 15:45     Быстрый стек, с малым обьемом памяти #31
C++
1
2
3
heap = (int *) malloc(heap_size * block_size * sizeof(int));
 
const int heap_size = 60*1000
а это ещё зачем.. Память под 60 * 19*1000 int'ов. Тебе столько не надо...
Тут она отрезает 60 000* 20 (размер блока) * 4 (занимает int) = 60 кб * 20 * 4 это дофига памяти. Что-то она больно мало показала
outoftime
║XLR8║
 Аватар для outoftime
505 / 427 / 33
Регистрация: 25.07.2009
Сообщений: 2,297
11.01.2010, 17:19  [ТС]     Быстрый стек, с малым обьемом памяти #32
Цитата Сообщение от GRANDEATH Посмотреть сообщение
Что-то она больно мало показала
так ведь процес до конца не завершился, они на этапе работы проверяют ограничения

Добавлено через 1 минуту
сколько тогда нужно выделить heap_size и block_size что-бы было норм?

Добавлено через 6 минут
Crash (access violation) 10 0.046 689 КБ
на этом коде:
C++
1
2
const int heap_size = 5*1000,
          block_size = 20;
odip
Эксперт C++
 Аватар для odip
7225 / 3287 / 58
Регистрация: 17.06.2009
Сообщений: 14,165
11.01.2010, 18:05     Быстрый стек, с малым обьемом памяти #33
сколько тогда нужно выделить heap_size и block_size что-бы было норм?
Нисколько.
По умолчанию НИЧЕГО не выделено.
Выделение памяти происходит по запросу - как требуется память.
outoftime
║XLR8║
 Аватар для outoftime
505 / 427 / 33
Регистрация: 25.07.2009
Сообщений: 2,297
11.01.2010, 19:29  [ТС]     Быстрый стек, с малым обьемом памяти #34
Цитата Сообщение от odip Посмотреть сообщение
По умолчанию НИЧЕГО не выделено.
Выделение памяти происходит по запросу - как требуется память.
Немного непонял к чему вы, ведь идея состояла в том, что-бы веделить часть памяти целиком, а потом распределять ее внутри програмы..

Добавлено через 4 минуты
Цитата Сообщение от odip Посмотреть сообщение
Еще вариант - вообще без блоков.
Выделяем 100000*7 байт
4 байта - число
3 байта - ссылка на предыдущий элемент
а как тогда на выделеной памяти созадать ссылки, т.е. присвоить указателю части выделеной памяти я понимаю как, а как указателю присвоить место в памяти, в котором будет хранится его значение?
odip
Эксперт C++
 Аватар для odip
7225 / 3287 / 58
Регистрация: 17.06.2009
Сообщений: 14,165
11.01.2010, 19:32     Быстрый стек, с малым обьемом памяти #35
Я уже отказался от этой идеи
Решил выделять блоками.
Прикол в том, что там неизвестно какой компилятор и трудно выделить ровно столько памяти чтобы ее хватило и в тоже время не перебрать.
Выделение делаю malloc(), не использую realloc() и никогда не делаю free().

Добавлено через 45 секунд
а как тогда на выделеной памяти созадать ссылки, т.е. присвоить указателю части выделеной памяти я понимаю как, а как указателю присвоить место в памяти, в котором будет хранится его значение?
Скорее всего ничего не получится - там похоже накладные расходы превышают 50Kb.

Ссылки очень просто - ссылка - это номер в массиве
То есть сразу выделяем 700000 байт одним куском.
Этого точно хватит на задачу.
outoftime
║XLR8║
 Аватар для outoftime
505 / 427 / 33
Регистрация: 25.07.2009
Сообщений: 2,297
11.01.2010, 20:05  [ТС]     Быстрый стек, с малым обьемом памяти #36
опять запутался, давайте я скажу на что у меня расходуется память а вы скажете где ее можно укротить?
я выделяю 2 блока, 1-ый для нужд самих стеков, он идет 400 Кб, 2-ой в качестве битмаски, он на 40 Кб
потом при создании стеков, каждые ил элементов имеет два указатели, 1 на значение, и 1 на предыдущий элемент, и того максимум 40 Кб + 4 Кб на текущие размеры стеков
+ 2 инта в мейне и масив 5 чаров, и того = 400+40+40+4+8+20 = 512 Кб

Добавлено через 11 секунд
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
#include <iostream>
 
#define FOR(i,a,b) for (int i(a), _n(b); i < _n; ++i)
 
//stack struct------------------------------------------------------------------
 
struct node;
struct node
{
public:
    int* val;
    node* prev;
};
typedef struct node node;
 
//const initialize--------------------------------------------------------------
 
const int heap_size = 10*1000,
          block_size = 10;
          
//memory class------------------------------------------------------------------
 
class Memory
{
public:
    Memory();
    ~Memory();
    int* find();
    void free(int *);
private:
    int* bit_set,
       * heap;
};
 
//stack class-------------------------------------------------------------------
 
class stack
{
public:
    stack();
    ~stack();
    void push(int &);
    int pop();
private:
    node* head;
    int top;
};
 
//main--------------------------------------------------------------------------
 
int main()
{
    int n, d, dd;
    char* s = new char[5];
    scanf("%d", &n);
    stack* a = new stack[1000];
    while(n--)
    {
        scanf("%s%d", s, &d);
        if (s[1] == 'U')
        {
            scanf("%d", &dd);
            a[d-1].push(dd);
        }
        else printf("%d\n", a[d-1].pop());
    }
    return 0;
}
 
//class Memory------------------------------------------------------------------
 
Memory::Memory()
{
    bit_set = (int *) calloc (heap_size, sizeof(int));
    heap = (int *) malloc(heap_size * block_size * sizeof(int));
}
 
Memory::~Memory()
{
    bit_set = (int *) realloc (bit_set, 0);
    heap = (int *) realloc (heap, 0);
}
 
int* Memory::find()
{
    FOR(i,0,heap_size)
        if (!bit_set[i])
        {
            bit_set[i] = 1;
            return (heap + i*block_size);
        }
    return 0;
}
 
void Memory::free(int *n)
{
    bit_set[ (n - heap)/block_size ] = 0;
}
 
//class stack-------------------------------------------------------------------
 
Memory my_mem;
 
stack::stack()
{
    top = 0;
    head = new node;
    head->prev = 0;
    head->val = my_mem.find();
}
 
stack::~stack()
{
    delete head;
}
 
void stack::push(int &n)
{
    if (top == block_size)
    {
        top = 0;
        node* tmp = new node;
        tmp->prev = head;
        tmp->val = my_mem.find();
        head = tmp;
    }
    head->val[top++] = n;
}
 
int stack::pop()
{
    if (top == 0)
    {
        node* tmp = head;
        my_mem.free(tmp->val);
        head = head->prev;
        delete tmp;
        top = block_size;
    }
    return head->val[--top];
}
в коде поменял только размер и количество блоков

где еще 300 Кб спрятано?
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
22.06.2010, 13:06     Быстрый стек, с малым обьемом памяти
Еще ссылки по теме:

Переменные в стеке. Где хранятся? Как обрабатываются? Есть ли программный стек или только стек процессора? C++
C++ Memory shift или самый быстрый способ перемещения блока памяти
Быстрый сплит C++

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

Или воспользуйтесь поиском по форуму:
Хохол
Эксперт C++
 Аватар для Хохол
475 / 443 / 13
Регистрация: 20.11.2009
Сообщений: 1,292
22.06.2010, 13:06     Быстрый стек, с малым обьемом памяти #37
Вот читерское решение.

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
#include <fstream>
#include <string>
 
using namespace std;
 
#ifndef ONLINE_JUDGE
ifstream cin("input.txt");
ofstream cout("output.txt");
#else
#include <iostream>
#endif
 
int size[1000] = {0}, n, x, y, *st[1000], ms[1000] = {0};
string str;
 
void prepare()
{
    cin >> n;
    for(int i = 0; i < n; i++)
    {
        cin >> str >> x;
        x--;
        if(str == "PUSH")
        {
            cin >> y;
            size[x]++;
            ms[x] = max(ms[x],size[x]);
        }
        else
            size[x]--;
    }
    for(int i = 0; i < 1000; i++)
        st[i] = new int[ms[i]];
    for(int i = 0; i < 1000; i++)
        size[i] = 0;
}
 
int main()
{
    prepare();
 
    #ifndef ONLINE_JUDGE
    ifstream cin("input.txt");
#else
    fseek(stdin,0,SEEK_SET);
#endif  
 
    cin >> n;
    for(int i = 0; i < n; i++)
    {
        cin >> str >> x;
        x--;
        if(str == "PUSH")
        {
            cin >> y;
            st[x][size[x]] = y;
            size[x]++;
        }
        else
        {
            size[x]--;
            cout << st[x][size[x]] << endl;
        }
    }
}
Но нормальное у меня тоже есть.
Yandex
Объявления
22.06.2010, 13:06     Быстрый стек, с малым обьемом памяти
Ответ Создать тему
Опции темы

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