Мой вариант разминки для мозгов: оптимизация кода

Как известно, на acm.timus.ru есть множество интересных заданий. Вот одно из них. Мой код:

#include <iostream>
#include <vector>

using namespace std;

class STACK
{
    private:
        vector<unsigned int> st;
    public:
        short int number;
        void push( unsigned int val ) 
        {
            st.push_back( val );
        }
        unsigned int pop()
        {
            unsigned int y;
            y = st[st.size()-1];
            st.pop_back();
            return y;
        }
        ~STACK()
        {
            st.clear();
        }
};

int main()
{
    int n;
    cin >> n;
    vector<unsigned int> r;
    vector<STACK> st(0);
    char str[5];
    short int a;
    bool find;
    unsigned int b;
    register int i, j;
    for ( i = 0; i < n; i++ )
    {
        cin >> str;
        if ( str[1] == 'U' )
        {
            cin >> a >> b;
            find = false;
            for ( j = st.size() - 1; j >= 0; j-- )
            {
                if ( st[j].number == a )
                {
                    find = true;
                    st[j].push( b );
                    break;
                }
            }
            if ( !find )
            {
                STACK t;
                t.push( b );
                t.number = a;
                st.push_back( t );
            }
        }
        else
        {
            cin >> a;
            for ( j = st.size() - 1; j >= 0; j-- )
                if ( st[j].number == a )
                {
                    r.push_back( st[j].pop() );
                    break;
                }
        }

    }
    for ( i = 0; i < r.size(); i++ )
        cout << r[i] << endl;
    return 0;
}

Первые 9 тестов программа проходит на Ура, но на 10ом получает вердикт: Закончилась память. Я уже оптимизировал её как смог, в результате выиграл около 300кБ. Но дальше ничего не могу придумать. А как бы вы оптимизировали этот код? Или может у вас есть своё решение?

Для того, что бы что-то посоветовать, пришлось самому решить это задание. Общие впечатления от процесса:

1. Решение неочевидное.
2. «Правильность» решения зависит от компилятора, которому подсовываешь программу на проверку: Visual C++ 2010 — Accepted, G++ 4.7.2 — Memory limit exceeded для одной и той же программы. Так же можно получить и Compilation error.
3. Компилятор G++ 4.7.2 делает более объёмный код по сравнению с Visual C++ 2010.
4. Самые «правильные» решения народ получал на компиляторе Intel C++ 7, который сейчас вообще убрали.

Задание было бы простым, если бы не два очень жёстких ограничения: по объёму памяти и по времени выполнения.

Давай немного посчитаем расходы по памяти:
1. Хранить 100000 значений типа unsighed int: 100000 x 4байта = 400Кб (грубо).
2. Хранить для этих 100000 значений информацию о порядке их следования в стеках. Если использовать указатели — это по 8 байт на значение. Если использовать целочисленный индекс в массиве — это по 4 байта на значение. Итого ещё 400Кб.
3. Хранить информацию по 1000 стекам. Ещё минимум 4Кб.

Итого уже получается 400 + 400 + 4 > 750Кб.

Отсюда два следствия:
1. STL со своими прекрасными контейнерами нервно курит в сторонке.
2. Всё равно по памяти не проходим (( Надо что-то изобретать.

Пока не буду тебе ломать кайф от самостоятельного поиска решения ;-)

Пара советов по «оптимизации»:
1. Используй компилятор Visual C++ 2010.
2. Не используй библиотеку потокового ввода-вывода C++. Пользуйся stdio.h. Это сэкономит порядка 76Кб памяти.
3. Программу, приведённую выше, можно выкинуть с чистой совестью: никакая оптимизация ей не поможет.

PS. «Безумству храбрых поём мы песню...»

Cranium, одно только подскажи — надо ли использовать класс — STACK ? его ведь ничем не заменить...
Да и если его использовать, а от STL придётся отказаться, то придётся делать размер стека фиксированным, а это неизбежные потери памяти(( Как быть?

Может, если нельзя использовать STL, то попробовать что-то типа вот этого:

struct Q
{
    unsigned long data;
    Q *next;
    Q *back;    
};

class STACK
{
    private:
        Q a;
        Q *ptr;
    public:
        STACK();
        unsigned long pop();
        void push( unsigned long );
        ~STACK();
};

STACK :: STACK()
{
    a.back = NULL;
    a.next = NULL;
    ptr = a.next;
}

void STACK :: push( unsigned long n )
{
    ptr->next = new Q;
    ptr->next->back = ptr;
    ptr = ptr->next;
    ptr->data = n;
    ptr->next = NULL;
}

unsigned long STACK ::  pop()
{
    unsigned long ret = ptr->data;
    Q *t = ptr;
    ptr = ptr->back;
    ptr->next = NULL;
    delete t;
    return ret;
}

STACK :: ~STACK()
{
    while ( ptr->back )
    {
        Q *t = ptr;
        ptr = ptr->back;
        delete t;
    }
}

Правда этот код не работает, не знаете почему?

Компилятор G++ 4.7.2 делает более объёмный код по сравнению с Visual C++ 2010.

С какими флагами компилировал в GCC? Включал ли -O2 и -DNDebug?

А, оно у них в облаке собирается. Понял.

Porshe, ты можешь управлять размером стека без STL. Это не C++-Way, но для такой задачи вполне сойдет.

#include <cstdio>
#include <cstdlib>

class stack {

public:
    stack()
    {
        size = 0;
        elements = NULL;
    }

    ~stack()
    {
        if (elements != NULL) {
            free(elements);
        }
    }

    void push(unsigned short int element)
    {
        unsigned int memsize = sizeof(unsigned short int) * ++size;
        unsigned short int* more_elements = (unsigned short int*) realloc(elements, memsize);
        if (more_elements != NULL) {
            elements = more_elements;
            elements[size-1] = element;
        } else {
            free(elements);
            puts("Error (re)allocating memory");
            exit(1);
        }
    }

    unsigned short int pop()
    {
        if (elements == NULL) {
            puts("stack is empty");
            exit(1);
        }
        unsigned short int _ret = elements[size-1];
        unsigned int memsize = sizeof(unsigned short int) * --size;
        if (memsize > 0) {
            unsigned short int* less_elements = (unsigned short int*) realloc(elements, memsize);
            if (less_elements != NULL) {
                elements = less_elements;
            } else {
                free(elements);
                puts("Error (re)allocating memory");
                exit(1);
            }
        }
        return _ret;
    }

private:
    unsigned int size;
    unsigned short int* elements;
};


int main()
{
    stack st;

    st.push(10);
    st.push(12);
    st.push(100);

    printf("%d\n", st.pop());
    printf("%d\n", st.pop());
    printf("%d\n", st.pop());

    return 0;
}

Selevit, правда, а я совсем про realloc то забыл... :)

Коллеги, вы, наверное, не очень внимательно прочитали мой предыдущий пост в этой теме.

Задание было бы простым, если бы не два очень жёстких ограничения: по объёму памяти и по времени выполнения.

porshe, твой последний код, если бы он даже работал, при 100 тыс. элементов типа unsigned int, не говоря уже про long, будет кушать 100000 * (8 + 8 + 4) = 2000000 байт, т.е. почти 2Мб. А надо уложиться в 750Кб.

Код selevit не лишён здравого безумия, но даю 99,99%, что он не пройдёт по скорости. Выделение и освобождение динамической памяти всегда были затратными операциями. А тем более realloc(), который будет вызываться при каждом чихе. Впрочем можете проверить.

porshe, по поводу класса STACK. Тут как бы «хоть горшком назови, только в печь не ставь». Если, конечно, ты не имеешь ввиду шаблон stack<> из STL, от которого придётся отказаться однозначно. И вообще, можно решить задачу с классами, а можно и без классов — не принципиально. Например у меня получился класс, который, с одной стороны, стеком назвать ни как нельзя, но, с другой стороны, он реализует стековые операции. Потом, ради интереса, я переписал программу на чистом C (естественно без классов). Не упирайся так в терминологию.

Некорректная постановка вопроса: если «делать размер стека фиксированным, а это неизбежные потери памяти». В данном случае, размер стека фиксированным делать ни как нельзя, поскольку по условию задачи все 100 тыс. значений вполне могут быть помещены в один стек. Т.е. тогда для каждого из 1000 стеков надо резервировать... ну ты понял. А вот объём памяти, где будут размещаться эти 1000 стеков может и должен быть фиксированным, поскольку, по условию, 100 тыс. значений типа unsigned int (int, не long!) — это верхний предел.

PS. Кстати, porshe, при реализации стека с использованием указателей, вполне хватает одного указателя на следующий элемент (у тебя в struct Q). А в class STACK лишний член Q a: хватит Q *ptr, который будет указывать на верхний элемент стека (или NULL, если стек пуст).

Выделение и освобождение динамической памяти всегда были затратными операциями.

Затратными с точки зрения процессорного времени, включая задержки системной шины.

При более грамотном подходе, realloc можно вызывать при заполнении блока определенного размера. Например, при инициализации стека, выделять сразу 16 байт для хранения данных, потом еще 16, и т. д.

selevit, я высказал только своё мнение по поводу использования realloc(). Попробуй написать полноценную программу по этой задаче и прогнать её на acm.timus.ru. Будет интересно узнать результат.

Cranium, хорошо, а как тогда хранить эти 100тыс.*1000 значений? Нет разницы какая структура данных, всё равно память выйдет...

типа unsigned int (int, не long!)

В 32битной системе unsigned long и unsigned int одинаковы, а значит и разницы нет. А вдруг у них там 16ти или 64х битная система? :)

А вот объём памяти, где будут размещаться эти 1000 стеков может и должен быть фиксированным, поскольку, по условию, 100 тыс. значений типа unsigned int (int, не long!) — это верхний предел.

Что-то я не совсем понял, зачем нужно использовать фиксированный объём памяти под стеки, ведь это затраты памяти, и при чём тут верхний предел?

Так весь смысл этой задачи в том, что бы впихнуть в ограниченный объём памяти то, что на первый взгляд туда ни как не поместится. Я же тебе написал в Следствии №2: "Всё равно по памяти не проходим (( Надо что-то изобретать". Читай внимательнее.

На счёт int и long — согласен. Но соломку лучше подстелить ;-)

Что-то я не совсем понял, зачем нужно использовать фиксированный объём памяти под стеки, ведь это затраты памяти, и при чём тут верхний предел?

Либо ты невнимательно читаешь, либо я косноязычно объясняю ((

По условию задачи, максимальный объём данных, которые ты должен разместить 100 тыс. значений типа unsigned int (по 4 байта на каждое значение) — 390.625Кб. Этот объём памяти можно совершенно спокойно зафиксировать.

Плюс к этому, должны быть организованы максимум 1000 стеков. Для каждого стека нужно хранить, как минимум, либо указатель (адрес) на вершину стека (это 4-8 байт в зависимости от системы 32/64-битная), либо индекс в массиве из 100 тыс. элементов (это 4 байта, точнее 17 бит). Итого, считая по минимуму, 1000 * 4 = 3.91Кб. Тоже можно фиксировать, но это мелочь.

Остаётся совсем немного: придумать способ как организовать сам механизм стека. Т.е. как и где хранить информацию о следующем элементе стека.

Кстати, я проверил предложение selevit по организации стека с использованием realloc(). Единственно, что пришлось подправить unsigned short int -> unsigned int — иначе просто Wrong answer на тесте 3. Как я и ожидал:

1220. Stacks компилятор: Visual C++ 2010 Time limit exceeded тест: 11 время: 0.531 память: 516 КБ

Оно, конечно, заманчиво, что бы элементы каждого стека сразу лежали в массиве по порядку — не надо хранить информацию о следующем элементе. Но затраты времени на realloc() оказываются слишком велики ((

У нас максимальное количество операций со стекам — 100 тысяч. Максимальное количество самих стеков — 1000.

Но 100 тысяч — это общее количество операций, а не для каждого из 1000 отдельных стеков.

Т.е. максимальный размер выделяемой памяти на стек (при отсутствии POP-операций) — 100000 * sizeof(unsigned short int). Или 200 килобайт.

UPD: да, невнимательно прочитал предыдущий пост.

Череп, попробуй делать realloc не для каждого изменения стека, а поблочно. Т.е. выделяешь изначально какой-либо блок памяти, когда он заполняется, выделяешь другой. Так работает std::vector, кстати.

selevit, unsigned short int — это который 16 бит? — не катит. По условию задачи, числа в стеках до 10^9 — это 30 бит. Т.е. однозначно 4-х битный unsigned int. И, см. мой предыдущий пост, ошибка на тесте 3 это подтвердила.

Если ты переделаешь свой класс stack под выделение памяти поблочно — я проверю на acm.timus.ru.

Ну вот, топорный вариант.
(обновлено)

class stack {

public:
    stack() {
        size = 0;
        real_size = 0;
        free_elements = 0;
        elements = NULL;
        reserve_free_elements = 16;
    }

    ~stack() {
        if (elements != NULL) {
            free(elements);
        }
    }

    void push(unsigned int element)
    {
        if (free_elements > 0) {
            elements[size] = element;
        } else {
            add_memory_block(reserve_free_elements);
            elements[size] = element;
        }
        ++size;
        free_elements = real_size - size;
    }

    unsigned int pop()
    {
        if (elements == NULL) {
            puts("stack is empty");
            exit(1);
        }
        unsigned int _ret = elements[size-1];
        --size;
        free_elements = real_size - size;
        if (free_elements >= reserve_free_elements) {
            remove_memory_block(reserve_free_elements);
        }
        free_elements = real_size - size;
        return _ret;
    }

private:
    void remove_memory_block(unsigned int _size)
    {
        real_size -= _size;
        unsigned int memsize = sizeof(unsigned int) * real_size;
        unsigned int *new_elements = (unsigned int*) realloc(elements, memsize);
        elements = new_elements;
    }

    void add_memory_block(unsigned int _size)
    {
        real_size += _size;
        unsigned int memsize = sizeof(unsigned int) * real_size;
        unsigned int *new_elements = (unsigned int*) realloc(elements, memsize);
        if (new_elements != NULL) {
            elements = new_elements;
        } else {
            puts("Error allocating memory");
            exit(1);
        }
    }

    unsigned int size;
    unsigned int free_elements;
    unsigned int real_size;
    unsigned int* elements;
    unsigned int reserve_free_elements;
};

Результат «топорного варианта»:

1220. Stacks Visual C++ 2010 Memory limit exceeded тест: 12 время: 0.234 память: 852 КБ

Честно говоря, я затрудняюсь прокомментировать результат :-0

Ну это нормально, небольшой оверхед по памяти, зато по времени вышло куда быстрее. Попробуй изменить значение reserve_free_elements на 10.

1220. Stacks Visual C++ 2010 Memory limit exceeded 10 0.109 872 КБ

Как ни странно, стало ещё хуже.

Вообще-то, теоретически твой вариант должен кушать 100000 * 4 = 400Кб на хранение данных, 32 * 1000 = 32Кб на хранение объектов типа stack и 15 * 4 * 1000 = 60Кб — самый неудачный вариант перерасхода памяти при размере блока 16. Итого чуть меньше 492Кб.

Откуда 872Кб — непонятно.