║XLR8║
1210 / 907 / 270
Регистрация: 25.07.2009
Сообщений: 4,354
Записей в блоге: 5
1

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

10.01.2010, 15:23. Показов 3421. Ответов 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;
}
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
10.01.2010, 15:23
Ответы с готовыми решениями:

Стек, куча, хранение в памяти, динамическое выделение памяти, указатели в чем отличие?
Здравствуйте. Прочитал кучу определений но никак не пойму вообще что к чему. 1)Стек - это якобы...

Memory shift или самый быстрый способ перемещения блока памяти
int* dataField = new int{0}; for (int i = 0; i &lt; 50; i++) dataField = 777; //тут должен быть...

Наиболее быстрый способ сортировки файла в 1 Тб при ограниченном объёме оперативной памяти
Привет! Какой есть наиболее быстрый способ сортировки файла, содержащего int-ы (по одному int-у на...

Стек и освобождение памяти
Пишу класс стека, реслизую в виде односвязного списка. stack.h #ifndef STACK_H_INCLUDED #define...

36
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 вызовов функций по работе с паматью... Не уверен, что программа уложится в секунду...
1
║XLR8║
1210 / 907 / 270
Регистрация: 25.07.2009
Сообщений: 4,354
Записей в блоге: 5
10.01.2010, 17:02  [ТС] 3
Цитата Сообщение от GRANDEATH Посмотреть сообщение
Надо подумать... 100000 вызовов функций по работе с паматью... Не уверен, что программа уложится в секунду...
есть предложения? пямяти тоже нет..

Добавлено через 17 минут
scanf("%s",&s);
if (s == "PUSH")
эти строки, они коректны?
0
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 минуту
Как вообще отследить сколько памяти жрет прога?? Кроме диспетчера задач, котрый ахинею несет.
1
Эксперт С++
7175 / 3234 / 79
Регистрация: 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.
1
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.
по идее он должен возвращать память куче.
1
Эксперт С++
7175 / 3234 / 79
Регистрация: 17.06.2009
Сообщений: 14,164
10.01.2010, 18:13 7
по идее он должен возвращать память куче.
Да он и возвращает память куче.
Только куча это что ?
Это кусок памяти выделенный системой для программы.
А вот его уже никто системе возвращать не собирается
А именно этот размер памяти и проверяется системой как занятая память.
То есть я например выделю 1000 кусков по 1000 байт, а потом все разом освобожу.
И что ?
У меня все равно будет написано - занято 1000000 байт.

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

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

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

Значит придется массив.
1
Эксперт С++
7175 / 3234 / 79
Регистрация: 17.06.2009
Сообщений: 14,164
10.01.2010, 18:16 9
Нам придется создать массив указателей на эти блоки, что не очень хорошо.
Нормально будет.
И представь, сколько ошибок памяти у нас будет
Ни одной не будет
2
║XLR8║
1210 / 907 / 270
Регистрация: 25.07.2009
Сообщений: 4,354
Записей в блоге: 5
10.01.2010, 18:23  [ТС] 10
проблему предоставляет то что стеков 1000 и в каждом максимум 100000 элементов, сколько у нас теперь памяти получится? (можно вести отдельный масив top[i], который указывает на верхний элемент стека i, он размером 1000 интов) и того 1000*100000+1000 = 1000001000 интов ~ 100*1000*1000 = 10 млн интов
0
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 элементов
1
Эксперт С++
7175 / 3234 / 79
Регистрация: 17.06.2009
Сообщений: 14,164
10.01.2010, 18:25 12
Нет. В общем случае 100 000 элементов
Ну так я о чем говорю уже полчаса !
Там в худшем случае 100000 элементов ВСЕГО.
1
39 / 39 / 1
Регистрация: 13.09.2009
Сообщений: 108
10.01.2010, 18:27 13
Мы разобъем весь массив на блоки. И будем выделять из них. То есть сначала у кажного 50 чисел. Если какой-то становится больше - находим свободный блок и пишем туда. А к указателям в этом стеке добавляем указатель на еще один блок.

Добавлено через 1 минуту
Цитата Сообщение от odip Посмотреть сообщение
Ну так я о чем говорю уже полчаса !
Там в худшем случае 100000 элементов ВСЕГО.
Я согласен с тобой. Надо уже взять и написать эту задачу!!!
1
║XLR8║
1210 / 907 / 270
Регистрация: 25.07.2009
Сообщений: 4,354
Записей в блоге: 5
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 стеков вручную, на указателях?
1
39 / 39 / 1
Регистрация: 13.09.2009
Сообщений: 108
10.01.2010, 18:44 15
Идея то неплохая. Вот только вопрос? Чем память рубить будешь? alloc или new? Но вот главный вопрос - как освобождать будешь - free? И ответ - почему мы не можем использовать функцию realloc?
Да он и возвращает память куче.
Только куча это что ?
Это кусок памяти выделенный системой для программы.
А вот его уже никто системе возвращать не собирается
А именно этот размер памяти и проверяется системой как занятая память.
То есть я например выделю 1000 кусков по 1000 байт, а потом все разом освобожу.
И что ?
У меня все равно будет написано - занято 1000000 байт.
Результат будет тот же
1
║XLR8║
1210 / 907 / 270
Регистрация: 25.07.2009
Сообщений: 4,354
Записей в блоге: 5
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 КБ
0
39 / 39 / 1
Регистрация: 13.09.2009
Сообщений: 108
10.01.2010, 19:01 17
Дай 20 мин подумать
1
║XLR8║
1210 / 907 / 270
Регистрация: 25.07.2009
Сообщений: 4,354
Записей в блоге: 5
10.01.2010, 19:24  [ТС] 18
я думал так: если вы говорите, что для програмы выделяется куча, и даже если мы освобождаем память в систем она не возвращается, тогда нет другого пути как сделать все элементы статическими, что со стороны полный бред, но..
если мы запишем все 100000 операций в масив, после записи будем идти по нему, соответственно давая ответы на запросы?

Добавлено через 12 минут
и еще один вопрос: можно каким-то образом сново заполнять память которую мы освободили?
0
Эксперт С++
7175 / 3234 / 79
Регистрация: 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++.
У С++ накладные расходы по памяти сильно большие !
1
║XLR8║
1210 / 907 / 270
Регистрация: 25.07.2009
Сообщений: 4,354
Записей в блоге: 5
10.01.2010, 21:23  [ТС] 20
Цитата Сообщение от odip Посмотреть сообщение
Блок состоит из 19 чисел и одного указателя на предыдущий блок.
Для прикола сделал еще список свободных блоков.
Блок, когда освобождается, не отдается в систему, а записывается в список свободных блоков.
Когда нужен блок, то он сначала берется из этого списка,
а если список пуст, тогда уже берется из системы.
вы описывали стек как структуру которая выделяет память блоками по 19 елементов?
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
10.01.2010, 21:23

Стек. Нехватка памяти. Числа в тексте
Здравствуйте, у меня возникла проблема, и как я понял, именно в нехватке памяти. Программа должна...

Ошибка сегментирования (стек памяти сброшен на диск)
Здравствуйте. Я новичок в Ассемблере, и мне надо решить следующую задачу: есть массив из 12...

Прочитать последовательность из файла и создать стек в памяти
В файл записывается последовательность целых чисел. Прочитать последовательность из файла и создать...

Ошибка сегментирования (стек памяти сброшен на диск)
Помогите найти ошибку в коде. Ошибка сегментирования выскакивает после ввода трех строк. section...


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

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

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