Code-Live.ru

Портал о программировании

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

Возможно, дело в том, как ОС управляет распределением памяти.

Допустим, для решения задачи есть вот такой код:

#include <cstdlib>
#include <cstdio>

#define memory_block_size 10

template <typename type>
class mini_vector
{
    private:
        void _push_back();
        type *v;
        int _size;
        int _real_size;
    public:
        mini_vector( int s ): _size(s), _real_size(0)
        {
            if ( _size % memory_block_size  )
                _real_size += memory_block_size;
            _real_size +=  _size - _size % memory_block_size;
            v = (type*)malloc( sizeof( type ) * _real_size );
        }
        mini_vector(): _size(0), _real_size(0), v(NULL)
        {}
        ~mini_vector()
        {
            if( v )
                free( v );
        }
        void clear()
        {
            if ( v )
            {
                free( v );
                v = NULL;
                _size = 0;
                _real_size = 0;
            }
        }
        type &operator[]( int index )
        {
            if ( index < 0 || index > _size )
               exit( 1 );
            return v[index];
        }
        int size() const
        {
            return _size;
        }
        void push_back()
        {
            _push_back();
        }
        void push_back( type ob )
        {
            _push_back();
            v[_size-1] = ob;
        }
        type pop_back();        
};

template <typename type>
void mini_vector<type> :: _push_back()
{
    int free_memory = _real_size - _size;
    if ( !free_memory )
    {
        _real_size += memory_block_size;
        v = (type*)realloc( v, sizeof( type ) * _real_size );
        if ( !v )
           exit( 1 );
        ++_size;
    }
    else
        ++_size;
}

template <typename type>
type mini_vector<type> :: pop_back()
{
    type ret = v[_size-1];
    --_size;
    if ( !_size % memory_block_size && _size > memory_block_size )
    {
        _real_size -= memory_block_size;
        v = (type*)realloc( v, sizeof( type ) * _real_size );
        if ( !v )
           exit( 1 );
    }
    return ret;
}

template <typename type>
class stack
{
    private:
        mini_vector<type> st;
    public:
        ~stack()
        {
            if ( st.size() )
               st.clear();
        }
        void push( type ob )
        {
            st.push_back( ob );
        }
        type pop()
        {
            return st.pop_back();
        }
};

int main()
{
    register int i;
    stack<unsigned long> *st[1000];
    for ( i = 0; i < 1000; i++ )
        st[i] = NULL;
    short a;
    unsigned long b;
    char str[5];
    mini_vector<unsigned long> answers;
    int n;
    scanf( "%d", &n );
    for ( i = 0; i < n; i++ )
    {
        scanf( "%s%d", str, &a );
        switch( str[1] )
        {
            case 'U':
                {
                    a--;
                    scanf( "%u", &b );
                    if ( !st[a] )
                       st[a] = new stack<unsigned long>;
                    st[a]->push( b );
                };break;
            case 'O':
                {
                    a--;
                    answers.push_back( st[a]->pop() );
                };break;
            default:
                {
                    return 1;
                };break;
        }
    }
    for ( i = 0; i < answers.size(); i++ )
        printf( "%u\n", answers[i] );
    return 0;
}

Немного арифметики:

Если максимально возможное количество данных 100000, а максимально возможное кол-во стеков — 1000, то при самом худшем
варианте получаем:
1000(кол-во стеков) * ( (100 * 4)(в каждом стеке по 100 элементов, по 4 байта) + 4(_size) + 4(_real_size) ) + 4000(указатели на стэки), в итоге: 402,34375кБайта.

Но на шестом тесте:

    Roma    1220. Stacks    G++ 4.7.2 C++11 Memory limit exceeded   6   0.046   2 645 КБ

или 

Roma    1220. Stacks    Visual C++ 2010 Memory limit exceeded   6   0.14    4 660 КБ

Теперь один вопрос на обсуждение: где я туплю?

P.S.: G++ взял памяти в 1.7 раза меньше, чем Visual C++ 2010 o_0

Череп, а попробуй прогнать под G++ тот код, что на 12-м тест валился у тебя.

Прогнал под двумя G++:

1220. Stacks    G++ 4.7.2   Memory limit exceeded   12  0.25    925 КБ
1220. Stacks    G++ 4.7.2 C++11 Memory limit exceeded   12  0.328   949 КБ

porshe, последний код твой? Или взял чей-то?

Я не понял, зачем вся эта колбаса с шаблонами и классом мини-вектора. selevit уже предложил аналогичную идею, только в гораздо более компактной реализации.

Предлагаю более извращенный вариант решения. Выделяем изначально блок размером sizeof(unsigned int) * 100000, создаем карту использования памяти для стеков — массив указателей unsigned int* map[1000];.

Пишем примитивный «менеджер памяти», который будет выделять память и получать данные для стека с определенным номером.

Конечно, это костыль жуткий, но спортивное программирование — оно все такое :-) Вечером реализую описанное выше, если до меня никто не успеет.

Cranium, это был мой код, я пытался развить идею selevit'a, но вот только у меня не очень получилось. :(

selevit, перед тем, как пробовать реализовывать «более извращенный вариант решения», ещё раз просмотри мой пост.

Так ты же говоришь, что оно не все тесты проходит (вернее, не под всеми компиляторами). Кстати, чего не запостил решение?
Это задачу можно по разному решить, не думаю, что энтузиазм у ТС отобьешь публикацией своего кода.

Моё решение под Visual C++ 2010 проходит все тесты. Возможно, если ещё поколдовать над кодом, то будет проходить и под другими компиляторами. Но, если честно, уже не особо интересно.

В программировании любую задачу можно решить несколькими способами. В этом и прелесть программирования ))

Своё решение пока не стал постить по двум причинам:

  1. Боюсь сбить кураж, например у porshe. Когда на сайте ACM видишь, что у других получилось решить, а у тебя пока ещё нет, то есть стимул к решению. А когда ты видишь готовое решение — всё, шарик сдулся.
  2. Не хочу своим решением ограничивать возможности чужой фантазии. Например, использование realloc() мне в голову просто не пришло. Это потом, после твоего кода, я начал анализировать и пришёл к выводу, что библиотечный realloc() скорее всего не пройдёт по скорости. Лично мне было бы интересно посмотреть на решение (-ния), отличные от моего.

Sorry за нескромный вопрос...

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

Как в VSC++ или DEV C++ вывести это сообщение?
Заранее благодарен :)

Alf, ни как. Это сообщение тестирующей системы, а не компилятора.

А что если попробовать так:
— Создаём структуру element, которая хранит в себе значение, а так же номер стека, для которого это значение предназначено.

struct element
{
    unsigned long value;
    short stack_number;
};
  • Создаём массив — element memory[100000]( здесь, по-моему, неуместно, ведь так? )
  • Далее, при операции PUSH запихиваем в этот массив значение и номер стека переданные PUSH'у по адресу top++
  • При встреченной операции POP — с top'a идём до 0 по массиву memory , и если у очередного элемента номер стека подходит по описанию с нашим, выводим value данного элемента, а номер стека помечаем как UNUSED_ELEMENT = -1.

По памяти: 100000 * ( 4 + 2 ) / 1024 = 585,9375 кБайт, то есть проходим. Но вот я не уверен по поводу времени.
Как вам такая идея?

Вот реализация идеи, изложенной выше:

#include <cstdio>

#define UNUSED_ELEMENT -1

struct element
{
    unsigned long value;
    short stack_number;
};

int main()
{
    element *memory;
    unsigned long b;
    short a;
    char str[5];
    int n;
    scanf ( "%d", &n );
    register int i, j;
    unsigned long top = 0;
    memory = new element[n];
    for ( i = 0; i < n; i++ )
    {
        scanf ( "%s%d", str, &a );
        switch ( str[1] )
        {
            case 'U':
                {
                    scanf ( "%u", &b );
                    memory[top].value = b;
                    memory[top].stack_number = a;
                    top++;
                };break;
            case 'O':
                {
                    for ( j = top; j >= 0; j-- )
                        if ( a == memory[j].stack_number )
                        {
                            printf( "%u\n", memory[j].value );
                            memory[j].stack_number = UNUSED_ELEMENT;
                            break;
                        }
                };break;
            default:
                return 1;
                break;
        }
    }
    return 0;
}

Вроде всё хорошо, но:

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

Не могу понять — откуда 824кБ?

porshe, то, что мысль работает — это хорошо! ))

А вот с остальным я тебя огорчу.

Размер структуры element не 6 байт, а 8. Структура будет выравниваться по границе 32-битного слова, т.е. на границу 4 байт. В угоду быстроте доступа компилятором жертвуются сэкономленные тобой на short 2 байта. Итого, массив из 100тыс. element занимает 781.25Кб.

Причём, если ты делаешь массив из short, то выравнивание будет происходить для всего массива, а не для каждого элемента. Т.е. будет выравнено начало массива и начало следующего элемента данных, который расположен в памяти за концом массива.

Такое поведение компилятора вроде как-то можно обойти. То ли ключами компилятора, то ли прагмой — врать не буду, не помню.

Теперь по программе. Не компилировал и не тестировал. Но из текста видно следующее:

(1) Ты полагаешь, что массив memory после выделения из кучи инициализирован нулями? В общем случае, там должен быть мусор. Следовательно POP скорее всего будет работать неправильно.

(2) С PUSH тоже проблема. Что будет, если на вход подать 100тыс. PUSH, потом 50тыс. POP, а затем ещё 50тыс. PUSH? Ты не отслеживаешь UNUSED_ELEMENT. Значит нужно делать линейный поиск по массиву. Это опять время. И с top логика работы будет посложнее.

Не могу сказать точно, на чём основываюсь, но я бы посоветовал в данном случае избежать динамического выделения памяти. Т.е. объявить большой массив <чего-то> вне функций, в глобальной области видимости.

Ты полагаешь, что массив memory после выделения из кучи инициализирован нулями? В общем случае, там должен быть мусор. Следовательно POP скорее всего будет работать неправильно.

Что-то я не понял, POP ведь работает с индекса top, а начиная с индекса top и до 0 массив инициализирован(PUSH'ами), следовательно ошибок не будет.

И с top логика работы будет посложнее.

Можно попробовать удалять использованный элемент, например, так:

void delete_num ( unsigned long *A, int pos, int end )
{
    unsigned long temp = A[end-1];
        unsigned long temp2 = NOT_USED;
    A[end-1] = NOT_USED;
    for ( register int i = end -2; i >= pos; i-- )
    {
        if ( temp2 == NOT_USED )
        {
            temp2 = A[i];
            A[i] = temp;
            temp = NOT_USED;
        }
        else
        {
            temp = A[i];
            A[i] = temp2;
            temp2 = NOT_USED;
        }
    }
}

Итого, массив из 100тыс. element занимает 781.25Кб

Можно обойти это так:

unsigned long values[100000];
short stacks_num[100000];

Тогда компилятору ничего не остаётся, кроме как сделать так, как хотим мы :-).

Вот вариант немного улучшенный:

#include <cstdio>

#define UNUSED_STACK -1
#define NOT_USED UNUSED_STACK

unsigned long values[100000];
short stacks_num[100000];

void delete_num ( unsigned long *A, short *B, int pos, int end )
{
    unsigned long temp = A[end-1];
    unsigned long temp2 = NOT_USED;
    short temp_B = B[end-1];
    short temp2_B = NOT_USED;
    A[end-1] = NOT_USED;
    B[end-1] = NOT_USED;
    for ( register int i = end -2; i >= pos; i-- )
        if ( temp2 == NOT_USED )
        {
            temp2 = A[i];
            A[i] = temp;
            temp = NOT_USED;
            temp2_B = B[i];
            B[i] = temp_B;
            temp_B = NOT_USED;
        }
        else
        {
            temp = A[i];
            A[i] = temp2;
            temp2 = NOT_USED;
            temp_B = B[i];
            B[i] = temp2_B;
            temp2_B = NOT_USED;
        }
}

int main()
{
    unsigned int top = 0;
    unsigned long b;
    short a;
    char str[5];
    int n;
    scanf ( "%d", &n );
    register int i, j;
    for ( i = 0; i < n; i++ )
    {
        scanf ( "%s%d", str, &a );
        switch ( str[1] )
        {
            case 'U':
                {
                    scanf ( "%u", &b );
                    values[top] = b;
                    stacks_num[top++] = a;
                };break;
            case 'O':
                {
                    for ( j = top - 1; j >= 0; j-- )
                    {
                        if ( a == stacks_num[j] )
                        {
                            printf( "%u\n", values[j] );
                            delete_num( values, stacks_num, j, top-- );
                            break;
                        }
                    }
                };break;
            default:
                return 1;
                break;
        }
    }
    return 0;
}

Вердикт:

1220. Stacks    Visual C++ 2010 Time limit exceeded 19  0.531   716 КБ

А вот без функции delete_num:

1220. Stacks    Visual C++ 2010 Time limit exceeded 11  0.531   668 КБ

P.S.:идеи потихоньку кончаются...

Что-то я не понял, POP ведь работает с индекса top, а начиная с индекса top и до 0 массив инициализирован(PUSH'ами), следовательно ошибок не будет.

Согласен. Видимо я, когда это писал, уже начал думать об освобождённых элементах и поиске от конца массива.

unsigned long temp2 = NOT_USED; // = -1 (!) опасно и некрасиво.

И я не очень понял твою магию убирания элемента. Что-то больно сложно. А так не будет работать?

void delete_num( unsigned long *A, short *B, int pos, int end )
{
    for (int i = pos+1; i <= end; i++) {
        A[i-1] = A[i];
        B[i-1] = B[i];
    }
}

Но думаю, что по времени всё равно не уложишься в норматив. Для POP должны отработать два достаточно затратных for.

Для ускорения процесса, если подойдёт мой вариант ф-ции delete_num(), в ней вместо for можно использовать функцию memmove().

И я не очень понял твою магию убирания элемента

Да, согласен, замудрил :)

можно использовать функцию memmove().

Если заменить:

if ( a == stacks_num[j] )
{
        printf( "%u\n", values[j] );
        delete_num( values, stacks_num, j, top-- );
        break;
}

На:

if ( a == stacks_num[j] )
{
    printf( "%u\n", values[j] );
    memmove ( &values[j], &values[j+1], top - j );
    memmove ( &stacks_num[j], &stacks_num[j+1], top - j );
    top--;
    break;
}

Получается ошибка:

1220. Stacks    Visual C++ 2010 Wrong answer    3   0.015   136 КБ

Я как-то неправильно использую функцию memmove?

Я как-то неправильно использую функцию memmove?

Истинно так. memmove() перемещает байты. Поэтому операторы должны быть такие:

    memmove(&values[j], &values[j+1], (top - j) * sizeof(unsigned long));
    memmove(&stacks_num[j], &stacks_num[j+1], (top - j) * sizeof(short));

Впрочем это не спасает ситуацию:

1220. Stacks    Visual C++ 2010 Time limit exceeded 19  0.531   716 КБ

Есть ещё идеи?

Внимание! Это довольно старый топик, посты в него не попадут в новые, и их никто не увидит. Пишите пост, если хотите просто дополнить топик, а чтобы задать новый вопрос — начните новый.

Ответить

Вы можете использовать разметку markdown для оформления комментариев и постов. Используйте функцию предпросмотра для проверки корректности разметки.

Пожалуйста, оформляйте исходный код в соответствии с правилами разметки. Для того, чтобы вставить код в комментарий, скопируйте его в текстовое поле ниже, после чего выделите то, что скопировали и нажмите кнопку «код» в панели инструментов. Иначе ваш код может принять нечитаемый вид.

Либо производите оформление кода вручную, следующим образом:

``` #include <iostream> using namespace std; int main() { // ... } ```

Предпросмотр сообщения

Ваше сообщение пусто.