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

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

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 17, средняя оценка - 4.65
outoftime
║XLR8║
506 / 428 / 33
Регистрация: 25.07.2009
Сообщений: 2,297
#1

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

10.01.2010, 15:23. Просмотров 2148. Ответов 36
Метки нет (Все метки)

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++ при работе рекурсивной функции заканчивается стек и программа соответственно; как сделать так, чтобы она писала "стек закончился"?
C++ Программа добавляет введенный массив 5*5 в стек и выводит полученный стек двумя столбцами
C++ быстрый xor
Переменные в стеке. Где хранятся? Как обрабатываются? Есть ли программный стек или только стек процессора? C++
Быстрый поиск C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
GRANDEATH
39 / 39 / 1
Регистрация: 13.09.2009
Сообщений: 108
10.01.2010, 16:14     Быстрый стек, с малым обьемом памяти #2
C++
1
2
3
4
void *realloc(
   void *memblock,
   size_t size 
);
Parameters
memblock
Pointer to previously allocated memory block.

size
New size in bytes.

Посмотри на входные параметры. В частности параметр 1

Требуется тип void* , a ты ему суешь sz, что int. Вот он и противится тебе.

Добавлено через 18 минут
Надо подумать... 100000 вызовов функций по работе с паматью... Не уверен, что программа уложится в секунду...
outoftime
║XLR8║
506 / 428 / 33
Регистрация: 25.07.2009
Сообщений: 2,297
10.01.2010, 17:02  [ТС]     Быстрый стек, с малым обьемом памяти #3
Цитата Сообщение от GRANDEATH Посмотреть сообщение
Надо подумать... 100000 вызовов функций по работе с паматью... Не уверен, что программа уложится в секунду...
есть предложения? пямяти тоже нет..

Добавлено через 17 минут
scanf("%s",&s);
if (s == "PUSH")
эти строки, они коректны?
GRANDEATH
39 / 39 / 1
Регистрация: 13.09.2009
Сообщений: 108
10.01.2010, 17:52     Быстрый стек, с малым обьемом памяти #4
Я решил сделать так:
1. Не использовать string (едять память)
2. Не делать сравнение строк, а сравнивать только одну букву
3. Выделать память блоками
4. Убрать cout, cin

Я приложу код. Но он работает плохо. Я не знаю откуда он есть столько памяти!!!
Даже на этапе ИНИЦИАЛИЗАЦИИ
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
#include <stdio.h>
#include <malloc.h>
 
//#include <iostream>
//#include <sstream>
//#include <string>
//#include <algorithm>
 
#define BLOCK_SIZE 20
const int BLOCK_INT_SIZE = BLOCK_SIZE * sizeof(int);
 
//using namespace std;
 
class stack
{
public:
        stack()
        {
                pos = 0;
                length = 1; //ÎäèГ* áëîê âûäåëåГ*
                a = (int *) calloc (BLOCK_SIZE, sizeof(int));
        }
        ~stack(){}
        void push(int n)
        {
                if (pos == BLOCK_SIZE - 1)
                {
                     length ++; //ÄîáГ*âèëè ГҐГ№Вё îäèГ* áëîê
                     a = (int*)realloc( (void*)a, BLOCK_INT_SIZE*length); // Âûäåëèëè ГЇГ*ìÿòü
                     pos = 0; //Ïîçèöèÿ Г*Г* Г*Г*Г·Г*ëî
                }
                a[(length - 1)*BLOCK_SIZE + pos] = n;
                pos++; //Óâåëè÷èëè ïîçèöèþ Г*Г* 1
        }
        int pop()
        {
                if (pos == -1)
                {
                     length --; //ÓäГ*Г«Г*ГҐГ¬ áëîê
                     a = (int*)realloc( (void*)a, BLOCK_INT_SIZE*length); // ГђГ*ñïðåäåëèòü ГЇГ*ìÿòü
                     pos = BLOCK_SIZE - 1; //Ïîçèöèÿ Г*Г* Г*Г*Г·Г*ëî
                }
                pos--; //ÓìåГ*ГјГёГ*ГҐГ¬ ïîçèöèþ Г*Г* 1
                
                return a[(length - 1)*BLOCK_SIZE + pos];
        }
private:
        int* a; //ГЌГ*Г·Г*ëî Г¬Г*Г±Г±ГЁГўГ*
        int pos; //Г’ГҐГЄГіГ№Г*Гї ïîçèöèÿ
        int length; // ÄëèГ*Г*
};
 
int main()
{
        int n;
        scanf("%d",&n);
        stack a[1000];
        
        char temp[20]; // ÂðåìåГ*Г*Г*Гї ïåðåìåГ*Г*Г*Гї
        while (n--)
        {
                int d;
                scanf("%s",temp);
                scanf("%d",&d);
                if (temp[1] == 'U') // temp[1] ñîäåðæèò 'U' äëÿ pUsh èëè 'O' äëÿ pOp
                {
                        int dd;
                        scanf("%d",&dd);
                        a[d-1].push(dd);
                }
                else
                        //cout << a[d-1].pop() << endl;
                        printf("%d\n",a[d-1].pop());
        }
        
        
        system("pause"); //Error
        return 0;
}
Добавлено через 3 минуты
Говоря блоками я имею ввиду выделение на 20 чисел. Это уменьшит частоту вызова функций где-то на 1000 процентов. (Так она вызывалась на 20 чисел 10 раз (в среднем), теперь она вызывается один раз). Согласен, идет не очень удачный расход памяти.
По идее, я теряю максимум 20 чисел * 4 байта на число * 1000 кол-во стеков. Это 80 килобайт.
но откуда у меня такие потери памяти - не знаю((

Добавлено через 1 минуту
Как вообще отследить сколько памяти жрет прога?? Кроме диспетчера задач, котрый ахинею несет.
odip
Эксперт С++
7153 / 3293 / 59
Регистрация: 17.06.2009
Сообщений: 14,164
10.01.2010, 18:03     Быстрый стек, с малым обьемом памяти #5
А что - N<=100000.
Даже если все операции будут PUSH, то памяти потребуется 100000*4 байт, то есть 0.4Mb

Скорее всего в данной задаче realloc() вообще нельзя использовать.
Потому что realloc() может тупо выделять память из системы и не возвращать ее обратно системе никогда (только по завершении программы ).
То есть программа использует скажем 0.5Mb памяти, но сам размер кучи давно превысил 1Mb.

Я думаю хранить данные нужно не в 1000 отдельных стеках, а в одном большом массиве.
Причем массив можно сразу выделить весь
Осталось продумать как записывать/извлекать быстро

Если же они будут делать половину PUSH, а половину POP
тогда памяти потребуется всего 0.2Mb.
GRANDEATH
39 / 39 / 1
Регистрация: 13.09.2009
Сообщений: 108
10.01.2010, 18:09     Быстрый стек, с малым обьемом памяти #6
Мне приходила в голову такая идея. Но надо рассмотреть операции ограничения. То есть мы попытаемся сами смоделировать realloc. То есть разбить наш массив на части и отслеживать их. Я вот только понять не могу
realloc returns a void pointer to the reallocated (and possibly moved) memory block.

If there is not enough available memory to expand the block to the given size, the original block is left unchanged, and NULL is returned.

If size is zero, then the block pointed to by memblock is freed; the return value is NULL, and memblock is left pointing at a freed block.

The return value points to a storage space that is guaranteed to be suitably aligned for storage of any type of object. To get a pointer to a type other than void, use a type cast on the return value.
по идее он должен возвращать память куче.
odip
Эксперт С++
7153 / 3293 / 59
Регистрация: 17.06.2009
Сообщений: 14,164
10.01.2010, 18:13     Быстрый стек, с малым обьемом памяти #7
по идее он должен возвращать память куче.
Да он и возвращает память куче.
Только куча это что ?
Это кусок памяти выделенный системой для программы.
А вот его уже никто системе возвращать не собирается
А именно этот размер памяти и проверяется системой как занятая память.
То есть я например выделю 1000 кусков по 1000 байт, а потом все разом освобожу.
И что ?
У меня все равно будет написано - занято 1000000 байт.

Добавлено через 58 секунд
То есть разбить наш массив на части и отслеживать их.
Либо разбить на части.

Но мне больше нравится идея - не разбивать на части.
То есть один большой массив
GRANDEATH
39 / 39 / 1
Регистрация: 13.09.2009
Сообщений: 108
10.01.2010, 18:16     Быстрый стек, с малым обьемом памяти #8
Если же они будут делать половину PUSH, а половину POP
тогда памяти потребуется всего 0.2Mb.
Вот я и подумал, а почему бы не выделять блоками. Есть алгорит передвижение блоков. Но я не очень уверен, что он окажется удачным. Хотя с другой стороны почему бы не разбить массив на "страницы". Нам придется создать массив указателей на эти блоки, что не очень хорошо. И представь, сколько ошибок памяти у нас будет .
Нет. Надо усовершенствоавать realloc, я верю в команду разработчков этой функции

Добавлено через 2 минуты
Да он и возвращает память куче.
Только куча это что ?
Это кусок памяти выделенный системой для программы.
А вот его уже никто системе возвращать не собирается
А именно этот размер памяти и проверяется системой как занятая память.
То есть я например выделю 1000 кусков по 1000 байт, а потом все разом освобожу.
И что ?
У меня все равно будет написано - занято 1000000 байт.

Значит придется массив.
odip
Эксперт С++
7153 / 3293 / 59
Регистрация: 17.06.2009
Сообщений: 14,164
10.01.2010, 18:16     Быстрый стек, с малым обьемом памяти #9
Нам придется создать массив указателей на эти блоки, что не очень хорошо.
Нормально будет.
И представь, сколько ошибок памяти у нас будет
Ни одной не будет
outoftime
║XLR8║
506 / 428 / 33
Регистрация: 25.07.2009
Сообщений: 2,297
10.01.2010, 18:23  [ТС]     Быстрый стек, с малым обьемом памяти #10
проблему предоставляет то что стеков 1000 и в каждом максимум 100000 элементов, сколько у нас теперь памяти получится? (можно вести отдельный масив top[i], который указывает на верхний элемент стека i, он размером 1000 интов) и того 1000*100000+1000 = 1000001000 интов ~ 100*1000*1000 = 10 млн интов
GRANDEATH
39 / 39 / 1
Регистрация: 13.09.2009
Сообщений: 108
10.01.2010, 18:24     Быстрый стек, с малым обьемом памяти #11
По скольку будет разбивать?
Предлагаю по 50 чисел.
То есть max размер = 100 000 * 4 байта + 1000* 200 байт = 400 + 200 = 600 килов. Это много
+ нам потребуется массив указателей.

Добавлено через 37 секунд
Цитата Сообщение от outoftime Посмотреть сообщение
1000 и в каждом максимум 100000 элементов
Нет. В общем случае 100 000 элементов
odip
Эксперт С++
7153 / 3293 / 59
Регистрация: 17.06.2009
Сообщений: 14,164
10.01.2010, 18:25     Быстрый стек, с малым обьемом памяти #12
Нет. В общем случае 100 000 элементов
Ну так я о чем говорю уже полчаса !
Там в худшем случае 100000 элементов ВСЕГО.
GRANDEATH
39 / 39 / 1
Регистрация: 13.09.2009
Сообщений: 108
10.01.2010, 18:27     Быстрый стек, с малым обьемом памяти #13
Мы разобъем весь массив на блоки. И будем выделять из них. То есть сначала у кажного 50 чисел. Если какой-то становится больше - находим свободный блок и пишем туда. А к указателям в этом стеке добавляем указатель на еще один блок.

Добавлено через 1 минуту
Цитата Сообщение от odip Посмотреть сообщение
Ну так я о чем говорю уже полчаса !
Там в худшем случае 100000 элементов ВСЕГО.
Я согласен с тобой. Надо уже взять и написать эту задачу!!!
outoftime
║XLR8║
506 / 428 / 33
Регистрация: 25.07.2009
Сообщений: 2,297
10.01.2010, 18:38  [ТС]     Быстрый стек, с малым обьемом памяти #14
код вышел типа:
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
#include <iostream>
#define FOR(i,a,b) for (int i(a), _n(b); i < _n; ++i)
 
int main()
{
    int n;
    scanf("%d",&n);
    stack** a = (int **) malloc (1000 * sizeof(int *)),
        * top = (int *) calloc (1000, sizeof(int));
    FOR(i,0,1000)
        a[i] = (int *) malloc (100*1000 * sizeof(int));
    while (n--)
    {
        int d;
        char s[10];
        scanf("%s%d",&s,&d);
        if (s == "PUSH")
        {
            int dd;
            scanf("%d",&dd);
            a[d-1][top[d-1]++] = dd;
        }
        else
            printf("%d",a[d-1][top[d-1]--]);
    }
    return 0;
}
Добавлено через 7 минут
можно попутно вопрос: что если сделать 1000 стеков вручную, на указателях?
GRANDEATH
39 / 39 / 1
Регистрация: 13.09.2009
Сообщений: 108
10.01.2010, 18:44     Быстрый стек, с малым обьемом памяти #15
Идея то неплохая. Вот только вопрос? Чем память рубить будешь? alloc или new? Но вот главный вопрос - как освобождать будешь - free? И ответ - почему мы не можем использовать функцию realloc?
Да он и возвращает память куче.
Только куча это что ?
Это кусок памяти выделенный системой для программы.
А вот его уже никто системе возвращать не собирается
А именно этот размер памяти и проверяется системой как занятая память.
То есть я например выделю 1000 кусков по 1000 байт, а потом все разом освобожу.
И что ?
У меня все равно будет написано - занято 1000000 байт.
Результат будет тот же
outoftime
║XLR8║
506 / 428 / 33
Регистрация: 25.07.2009
Сообщений: 2,297
10.01.2010, 19:00  [ТС]     Быстрый стек, с малым обьемом памяти #16
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>
#define FOR(i,a,b) for (int i(a), _n(b); i < _n; ++i)
 
struct node
{
    node(){prev = 0; inf = 0;}
    ~node(){}
    int inf;
    node* prev;
};
 
class stack
{
public:
    stack(){head = 0;}
    ~stack(){}
    void push(int &n)
    {
        node* tmp = new node;
        tmp->inf = n;
        tmp->prev = head;
        head = tmp;
    }
    int pop()
    {
        int d = head->inf;
        node* tmp = head;
        head = head->prev;
        delete tmp;
        return d;
    }
private:
    node* head;
};
 
int main()
{
    int n;
    scanf("%d",&n);
    stack a[1000];
    while (n--)
    {
        int d;
        char s[10];
        scanf("%s%d",&s,&d);
        if (s == "PUSH")
        {
            int dd;
            scanf("%d",&dd);
            a[d-1].push(dd);
        }
        else printf("%d",a[d-1].pop());
    }
    return 0;
}
неверное сравнение строк, можете помочь?

Добавлено через 2 минуты
GRANDEATH, я просто не могу понять как делать линковку, какому стеку отвечает какой элемент + нам нужет top..

Добавлено через 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
#include <iostream>
#define FOR(i,a,b) for (int i(a), _n(b); i < _n; ++i)
 
struct node
{
    node(){prev = 0; inf = 0;}
    ~node(){}
    int inf;
    node* prev;
};
 
class stack
{
public:
    stack(){head = 0;}
    ~stack(){}
    void push(int &n)
    {
        node* tmp = new node;
        tmp->inf = n;
        tmp->prev = head;
        head = tmp;
    }
    int pop()
    {
        int d = head->inf;
        node* tmp = head;
        head = head->prev;
        delete tmp;
        return d;
    }
private:
    node* head;
};
 
int main()
{
    int n;
    scanf("%d",&n);
    stack a[1000];
    while (n--)
    {
        int d;
        char s[10];
        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;
}
Добавлено через 1 минуту
кто знает сколько мугут потянуть указатели между элементами стека?

Добавлено через 2 минуты
этот код не канает, 10-ий тест - выделено пямяти: 1 653 КБ
GRANDEATH
39 / 39 / 1
Регистрация: 13.09.2009
Сообщений: 108
10.01.2010, 19:01     Быстрый стек, с малым обьемом памяти #17
Дай 20 мин подумать
outoftime
║XLR8║
506 / 428 / 33
Регистрация: 25.07.2009
Сообщений: 2,297
10.01.2010, 19:24  [ТС]     Быстрый стек, с малым обьемом памяти #18
я думал так: если вы говорите, что для програмы выделяется куча, и даже если мы освобождаем память в систем она не возвращается, тогда нет другого пути как сделать все элементы статическими, что со стороны полный бред, но..
если мы запишем все 100000 операций в масив, после записи будем идти по нему, соответственно давая ответы на запросы?

Добавлено через 12 минут
и еще один вопрос: можно каким-то образом сново заполнять память которую мы освободили?
odip
Эксперт С++
7153 / 3293 / 59
Регистрация: 17.06.2009
Сообщений: 14,164
10.01.2010, 21:03     Быстрый стек, с малым обьемом памяти #19
Вообщем сдал я эту задачу.
Блок состоит из 19 чисел и одного указателя на предыдущий блок.
Для прикола сделал еще список свободных блоков.
Блок, когда освобождается, не отдается в систему, а записывается в список свободных блоков.
Когда нужен блок, то он сначала берется из этого списка,
а если список пуст, тогда уже берется из системы.

Я думаю что вообщем освобождение блоков не нужно,
но проверять это уже лень.

Добавлено через 1 минуту
Да - блоки выделяются обычным malloc().

Добавлено через 3 минуты
Еще вариант - вообще без блоков.
Выделяем 100000*7 байт
4 байта - число
3 байта - ссылка на предыдущий элемент ( 2-ух байт на 100000 не хватит )
Если 50 Kбайт хватит для работы программы то влезем
Но похоже накладные расходы больше.
У меня при сдаче получилось 725Kb
А я выделял блоками по 19+1 значение.
То есть там еще дофига должно было остаться.
Хитрая задача.

Добавлено через 39 секунд
Еще - не делайте на C++.
У С++ накладные расходы по памяти сильно большие !
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
10.01.2010, 21:23     Быстрый стек, с малым обьемом памяти
Еще ссылки по теме:

C++ Memory shift или самый быстрый способ перемещения блока памяти
Быстрый сплит C++
C++ Быстрый аллокатор
C++ Наиболее быстрый способ сортировки файла в 1 Тб при ограниченном объёме оперативной памяти
C++ Стек. Нехватка памяти. Числа в тексте

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

Или воспользуйтесь поиском по форуму:
outoftime
║XLR8║
506 / 428 / 33
Регистрация: 25.07.2009
Сообщений: 2,297
10.01.2010, 21:23  [ТС]     Быстрый стек, с малым обьемом памяти #20
Цитата Сообщение от odip Посмотреть сообщение
Блок состоит из 19 чисел и одного указателя на предыдущий блок.
Для прикола сделал еще список свободных блоков.
Блок, когда освобождается, не отдается в систему, а записывается в список свободных блоков.
Когда нужен блок, то он сначала берется из этого списка,
а если список пуст, тогда уже берется из системы.
вы описывали стек как структуру которая выделяет память блоками по 19 елементов?
Yandex
Объявления
10.01.2010, 21:23     Быстрый стек, с малым обьемом памяти
Ответ Создать тему
Опции темы

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