Моя производительность в написании программ

[Zealint]

allchemist в сообщении #357070 писал(а):

Цитата:

мой новый конкурс

а что это?

Да я конкурсы делаю для программистов. Но задачи даю не совсем такие как на олимпиаде, а убойные. Первый был попроще: про перемножение матриц. Второй про ферзей (ссылку давал выше). Третий будет ещё сложнее.

Кстати, написал код интерпретатора. Надо кому? Заняло 16 минут (старею):

Используется синтаксис C++

#include <stdio.h>

const int MAX_LEN = 1024;

char Str [ MAX_LEN ];
int lenOfStr;

double strToNum ( char * Str, int i, int j ) {
        double x = 0.0;
        for ( ; i <= j; i ++ ) {
                x *= 10.0;
                x += double ( Str [ i ] - '0' );
        }
        return x;
}

int Find ( char * Str, int i, int j, char c1, char c2 ) {
        int b = 0, k;
        for ( k = j; k >= i; k -- ) {
                if ( Str [ k ] == '(' )  b ++;
                else if ( Str [ k ] == ')' ) b --;
                else if ( b == 0 && ( Str [ k ] == c1 || Str [ k ] == c2 ) )
                        return k;
        }
        return -1;
}

double Calc ( char * Str, int i, int j ) {
        int k;
        double a, b;
        if ( i > j ) 
                return 0.0;
        if ( ( k = Find ( Str, i, j, '+', '-' ) ) >= 0 ) {              
                a = Calc ( Str, i, k - 1 );
                b = Calc ( Str, k + 1, j );             
                if ( Str [ k ] == '+' )
                        return a + b;
                else 
                        return a - b;
        }
        if ( ( k = Find ( Str, i, j, '*', '/' ) ) >= 0 ) {              
                a = Calc ( Str, i, k - 1 );
                b = Calc ( Str, k + 1, j );             
                if ( Str [ k ] == '*' )
                        return a * b;
                else 
                        return a / b;
        }
  /* Остались только скобки */
  if ( Str [ i ] == '(' ) 
                return Calc ( Str, i + 1, j - 1 );
  /* Или голое число */
  return strToNum ( Str, i, j );
}

int main ( ) {
        gets ( Str );
        for ( lenOfStr = 0; Str [ lenOfStr ] != '\0'; lenOfStr ++ );
        printf ( "Answer is %.8lf\n", Calc ( Str, 0, lenOfStr - 1 ) );
        return 0;
}
 

Получилось длиннее, чем было заявлено мной вначале. Вроде работает. Но раньше я как-то короче умел... Там смысл был в том, что умножение и сложение искались одновременно, а не по очереди. Сейчас думать не хочется.

[arseniiv]

allchemist в сообщении #357034 писал(а):

Отличный вариант, осталось только язык придумать позаковыристей. Brainfuck пойдет? :)

Он же для головы трудный, а вот для кодирования почти нет. Может, парсер подмножества BBCode? Конечно, не нужно ничего отображать, достаточно, чтобы текст поделился на фрагменты, в каждой части указание свойств (начертание, цвет), например, "1[ i]23[ b]45[/b][/i]6" (123456) поделится на 4 куска.

Zealint в сообщении #357067 писал(а):

Ещё модно стало с длинной арифметикой делать, это усложняет кодирование минут на 10-15.

Как у вас получается такое время? Или вы храните в массиве, представляющем число, цифры не по основанию, скажем, 256, а по основанию 10? Тогда, конечно, не так трудно.

[Maslov]

arseniiv в сообщении #357094 писал(а):

allchemist в сообщении #357034 писал(а):

Отличный вариант, осталось только язык придумать позаковыристей. Brainfuck пойдет? :)

Он же для головы трудный, а вот для кодирования почти нет. Может, парсер подмножества BBCode? Конечно, не нужно ничего отображать, достаточно, чтобы текст поделился на фрагменты, в каждой части указание свойств (начертание, цвет), например, "1[ i]23[ b]45[/b][/i]6" (123456) поделится на 4 куска.

Если есть желание написать компилятор/интерпретатор, то самое правильное, на мой взгляд, -- начать с чтения Dragon Book (Ахо, Лам, Сети, Ульман. Компиляторы: принципы, технологии и инструментарий.).

[Zealint]

arseniiv в сообщении #357094 писал(а):

Как у вас получается такое время? Или вы храните в массиве, представляющем число, цифры не по основанию, скажем, 256, а по основанию 10? Тогда, конечно, не так трудно.

Основание $10^8$ для сложения и вычитания. Если есть умножение и деление, берём $10^4$, чтобы не переполнялось. 10 минут - это тупая (чисто олимпиадная) длинная арифметика без деления. Деление, как сейчас помню, я писал в 6 строк, но совершенно не помню как. Когда есть отрицательные числа - ещё плюс 5 минут. Разумеется, код всей арифметики был выучен наизусть. Конечно, такая арифметика работала раз в 10 хуже, чем написанная для практически полезных нужд. Но практически полезную лучше не писать, а взять готовую GMP.

Короче, я хочу сказать, что натасканный человек все простые классические задачи умеет решать за считанные минуты. Поэтому нечестно сравнивать уровень на тривиальной классике. А на не тривиальных задачах тоже нечестно, поскольку каждому своё.

То есть

Цитата:

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

Это верно ещё и потому, что кто-то уже решил сотни подобных задач.

Цитата:

Позитивный результат. Дык значит все просто - преимущества получает более опытный (что-то подобное видел, делал, слышал ...). А как набраться опыта?

Сидеть и решать задачи. Например, в своё время я решил здесь всё. Потом там начали появляться другие тома с задачами. Там я уже не так активно решал, завязал с этим. Еще здесь есть хорошие задачи. Когда там было только три тома, я решил штук 150 или 200 задач. Это я дал ссылки на два самых лучших в России сайта с задачами по программированию.

Но учтите, что данные задачи НИКАКОГО отношения не имеют к формированию навыка решения жизненных задач. Вы получите только скил и умение писать кучу всяких алгоритмов.

[y_nikolaenko]

Zealint писал(а):

... Да я конкурсы делаю для программистов. Но задачи даю не совсем такие как на олимпиаде, а убойные. Первый был попроще: про перемножение матриц. Второй про ферзей (ссылку давал выше). Третий будет ещё сложнее...

Вообще говоря, не имеет смысла сравнивать перемножение матриц со второй задачей. Сама по себе задача перемножения матриц элементарна, но для ее грамотного решения необходимо владеть современными компьютерными технологиями перемножения матриц. А вторая задача в основном алгоритмическая.

[Zealint]

y_nikolaenko в сообщении #357225 писал(а):

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

Ну так а я и не говорю, что они одинаковые. Просто для первого раза мне нужен был кое-какой опыт, и было некоторое любопытство по части оптимизации программ. Я не могу сказать, что разбираюсь в этом. Вторая задача просто не давала покоя - я хотел найти формулу.

Цитата:

А вторая задача в основном алгоритмическая.

Это действительно так. Но вот задача про 7 ферзей требует для своего решения кое-какой теории. Одним известным алгоритмом её взять нельзя. Ну, если только на петафлопсной машине. В таком случае, 8 ферзей без данное теории решить будет невозможно. Мне поэтому и нравится решать задачи, которые ещё никто не решил - в них и алгоритм надо придумать и теорию подвести. То есть мне нравится комбинировать разные подходы, делая из них что-то более мощное.

[creative]

arseniiv в сообщении #356964 писал(а):

creative, а вы можете привести пример рассуждений при решении какой-нибудь задачи, где вы видите, что решаете слишком долго? Может, станет понятно, что не так.

Решил я тоже написать интерпретатор brainfuck'a. Хронология:

* Час кодирования.
* В первой половине второго часа, проверка и отладка на простых случаях типа:

 +++++++++++++++++++++++++++++++++++++++++++++
 +++++++++++++++++++++++++++.+++++++++++++++++
 ++++++++++++.+++++++..+++.-------------------
 ---------------------------------------------
 ---------------.+++++++++++++++++++++++++++++
 ++++++++++++++++++++++++++.++++++++++++++++++
 ++++++.+++.------.--------.------------------
 ---------------------------------------------
 ----.-----------------------.

* Во второй половине второго часа простые случаи со скобками [] работали
* Прошло два часа, код заработал на примере:

 ++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++
 .>+.+++++++..+++.>++.<<+++++++++++++++.>.+++.
 ------.--------.>+.>.

* В течении третьего, четвёртого часов упорно пытался понять через отладчик, почему не работает следующий код:

>>>>>++++++++[<+++++++++>-]<+[>>[>]+[<]<-]>++++++++++[<+++++
+++++>-]<[>>[+>]<[<]<-]<++++++++[>++++++++[>>->->->>>>>>>>>>
>->>>->>>>>>->->->->>->>>->>>>->>>>>->->>>>>>->>>>->>>>>->->
>>>>->>>->>>>>>>->-[<]<-]>>++>++>->>+>++>++>+>>>>++>>->+>>->
>>>++>>+>+>+>--->>->+>+>->++>>>->++>>+>+>+>--->>-->>+>>->+>+
>>->>+>++>+>+>->+>>++>++>->>++>->>++>+>++>+>>+>---[<]<<-]>>>
++++>++++>+++>--->++>->->->>[-]>->-->[-]>+++>++>+>+++>--->>>
--->[-]>+>+>+>--->[-]>+++>++>+>+++>->+++>>+++>++>---->->->+>
--->[-]>->---->-->>+++>++>+>>+++>->++>++>+>->+++>+++>---->--
>-->+++>++++>->+++>---->--->++>>+>->->---[[<]<]+++++++++[<+<
+++++++++++>>-]<<[>>>>>[<]>[.>]>--[>.>]<[<<]>++>>>[.>]>[>]>[
.>]<[[<]<]>>[.>]>--[>.>]<[<<]>++>>>[.>]>[.>]>[>]>[.>]<[[<]<]
<<[<]>>>+<[>-]>[>]<[+++++++++[<+<->>>>>+<<<-]+<<[>>-]>>>[<]<
<<++++++++++>>[>>[-]+<<-]>>-<<]>>>-[>]>-<<[<]>[.>]>--[>.>]<[
<<]>++>>>[.>]>[>]>[.>]<.[[<]<]<<[<]>>-<-]

* в конце четвёртого часа окончательно понял, что написанный код слишком не надёжен и просто удалил его полностью
* с конца четвёртого часа и весь пятый час полностью писал и отлаживал следующий код, на этот раз ошибок почти не было, через несколько попыток код заработал корректно (серил с выводом готового интерпретатора)

Итого: четыре часа проб и ошибок над кривым кодом в отладчике и осознание того как правильней решать эту задачу и ещё час на получение правильного решения.

Используется синтаксис C

#include <stdio.h>
#include <stdlib.h>

#define MAX_SIZE 4096

unsigned char *mem;
int            mpt;

void scope(unsigned char *tape)
{
    int n, c;
    int tpt = 0;

    while (tape[tpt]) {
        switch (tape[tpt]) {
        case '<':
            mpt--; //case '<'
            tpt++;
            break;
        case '>':
            mpt++; //case '>'
            tpt++;
            break;
        case '+':
            mem[mpt]++; //case '+'
            tpt++;
            break;
        case '-':
            mem[mpt]--; //case '-'
            tpt++;
            break;
        case '.':
            printf("%c", mem[mpt]); //case '.'
            tpt++;
            break;
        case ',':
            scanf("%c", &mem[mpt]); //case ','
            tpt++;
            break;
        case '[':
            c = 1; //case '['
            n = ++tpt;
            while (c) {
                if (tape[n] == ']') c--;
                if (tape[n] == '[') c++;
                n++;
            }
            if (mem[mpt]) {
                scope(&tape[tpt]);
            }
            tpt = n;
            break;
        case ']':
            if (mem[mpt] == 0) return; //case ']'
            tpt = 0;
            break;
        }
    }
}

int main()
{
    unsigned char  *tape;
    int             tpt;
    unsigned char   ch;
    int             ret;

    mem = calloc(MAX_SIZE, 1);
    tape = calloc(MAX_SIZE, 1);

    tpt = 0;
    do {
        ret = scanf("%c", &ch);
        if (ch == '<' || ch == '>' || ch == '+' || ch == '-' 
            || ch == '.' || ch == ',' || ch == '[' || ch == ']') {
            tape[tpt++] = ch;
        }
    } while (ret > 0);

    scope(tape);
    //printf("\n");

    return 0;
}
 

Вопрос: Нужно пытаться сразу написать правильный код? Если да, то обычно я так не могу, в голове всё расплывается. Если нет, то после долгих проб и ошибок над кривым кодом, я его удаляю и пишу работающий код, так как в процессе проб и ошибок я уже начинаю представлять как оно должно работать. Но если так, то это очень и очень долго. Каким образом Вам удаётся всё сразу удержать в голове и за 10-20 минут написать такой же рабочий код?

P.S. Кстати классный пример на brainfuck, он у меня в интерпретаторе тоже заработал :)

[venco]

35 минут с перерывами и изучением языка.

Используется синтаксис C

#include <stdio.h>
#include <string.h>

void run(char* cmd)
{
    char data[99999] = {}, *ptr = data;
    while ( *cmd ) {
        switch ( *cmd++ ) {
        case '>': ++ptr; break;
        case '<': --ptr; break;
        case '+': ++*ptr; break;
        case '-': --*ptr; break;
        case '.': putchar(*ptr); break;
        case ',': *ptr = getchar(); break;
        case '[':
            if ( !*ptr ) {
                int lvl = 1;
                while ( lvl ) {
                    switch ( *cmd++ ) {
                    case '[': ++lvl; break;
                    case ']': --lvl; break;
                    }
                }
            }
            break;
        case ']':
            if ( *ptr ) {
                int lvl = 0;
                do {
                    switch ( *--cmd ) {
                    case '[': --lvl; break;
                    case ']': ++lvl; break;
                    }
                } while ( lvl );
            }
            break;
        }
    }
}

int main(int argc, char**argv)
{
    while ( --argc > 0 ) {
        char* arg = *++argv;
        if ( strcmp(arg, "file") == 0 ) {
            --argc;
            char prg[99999];
            FILE* in = fopen(*++argv, "rt");
            prg[fread(prg, 1, sizeof(prg), in)] = 0;
            fclose(in);
            run(prg);
        }
        else {
            run(arg);
        }
    }
}
 

[Maslov]

(Оффтоп)

Забавно было бы попробовать написать компилятор какого-нибудь простенького pascal-подобного языка в этот самый brainfuck :)

[Zealint]

Цитата:

Вопрос: Нужно пытаться сразу написать правильный код? Если да, то обычно я так не могу, в голове всё расплывается. Если нет, то после долгих проб и ошибок над кривым кодом, я его удаляю и пишу работающий код, так как в процессе проб и ошибок я уже начинаю представлять как оно должно работать. Но если так, то это очень и очень долго. Каким образом Вам удаётся всё сразу удержать в голове и за 10-20 минут написать такой же рабочий код?

Нужно ли писать сразу? - ответ не может быть однозначным. Все индивидуально. Например, если сразу есть чёткое представление о задаче, то пишется сразу. При этом представление настолько чёткое, чтобы написанная программа сразу работала правильно. Без отладки. Чтобы добиться этого, я раньше писал программы в windows-блокноте (правда не удобно без автоотступа было). Потом делал так: если программа не компилируется или затем не работает правильно, код удаляется и пишется заново. После этих упражнений мысли становятся более чёткими, а все программы пишутся практически без отладки... правда, спустя годы, навык немного теряется, приходится прибегать к отладочному выводу.

Если представления о решении задачи нет (как Вы говорите, "все расплывается"), планируете свой код/алгоритм заранее. Планируете и думаете до тех пор, пока не придёт чёткого понимания. Как это тренировать? Берёте штук 10 задач и отмеряете 6-7 часов (это как Вам удобно). Первые 5 часов Вы эти задачи решаете ИСКЛЮЧИТЕЛЬНО на бумаге или в голове. За остальные 2 часа Вы должны набрать работающий код для всех решённых задач. На архивы автоматических тестирующих систем с задачами я давал ссылки выше. Надо просто решить пару сотен штук - проблемы начнут исчезать.

-- Чт сен 30, 2010 04:45:26 --

Maslov в сообщении #357501 писал(а):

(Оффтоп)

Забавно было бы попробовать написать компилятор какого-нибудь простенького pascal-подобного языка в этот самый brainfuck :)

(Оффтоп)

Да, а потом из полученного кода можно делать неплохие обои в коридор. Или туалетную бумагу с таким кодом. Представляете как популярно будет?

[creative]

Zealint в сообщении #357555 писал(а):

Нужно ли писать сразу? - ответ не может быть однозначным. Все индивидуально. Например, если сразу есть чёткое представление о задаче, то пишется сразу. При этом представление настолько чёткое, чтобы написанная программа сразу работала правильно. Без отладки. Чтобы добиться этого, я раньше писал программы в windows-блокноте (правда не удобно без автоотступа было). Потом делал так: если программа не компилируется или затем не работает правильно, код удаляется и пишется заново. После этих упражнений мысли становятся более чёткими, а все программы пишутся практически без отладки... правда, спустя годы, навык немного теряется, приходится прибегать к отладочному выводу.

Мне нравится эта идея.

Zealint в сообщении #357555 писал(а):

Если представления о решении задачи нет (как Вы говорите, "все расплывается"), планируете свой код/алгоритм заранее. Планируете и думаете до тех пор, пока не придёт чёткого понимания. Как это тренировать? Берёте штук 10 задач и отмеряете 6-7 часов (это как Вам удобно). Первые 5 часов Вы эти задачи решаете ИСКЛЮЧИТЕЛЬНО на бумаге или в голове. За остальные 2 часа Вы должны набрать работающий код для всех решённых задач. На архивы автоматических тестирующих систем с задачами я давал ссылки выше. Надо просто решить пару сотен штук - проблемы начнут исчезать.

Хорошая идея, но программы могут быть большими и на бумаге их не охватить или охватить но очень долго. Как на счёт поиска решения при написании мини протатипов различных частей задачи. Например, придумал какую нибудь конструкцию рекурсивного вызова и написал 10 - 20 строчную тестовую программку с пару printf, чтобы проверить результат.
Или это всё равно неправильно и надо абсолютно полностью на бумаге моделировать любую программу независимо от размера?

venco в сообщении #357495 писал(а):

35 минут с перерывами и изучением языка.

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

[Maslov]

creative в сообщении #357580 писал(а):

Хорошая идея, но программы могут быть большими и на бумаге их не охватить или охватить но очень долго. Как на счёт поиска решения при написании мини протатипов различных частей задачи. Например, придумал какую нибудь конструкцию рекурсивного вызова и написал 10 - 20 строчную тестовую программку с пару printf, чтобы проверить результат.

При таком подходе Вы рискуете потом затратить огромные усилия на прилаживание друг к другу разрозненных и плохо стыкующихся кусков кода. Более предпочтительным обычно является нисходящее проектирование/программирование: пишете модуль (метод/процедуру) верхнего уровня, не углубляясь в детали, несущественные на данном уровне абстракции, и заменяя подчинённые модули заглушками. Отладив в первом приближении модули верхнего уровня, переходите к реализации подчинённых модулей по той же схеме. Ну и так далее...

[Zealint]

creative в сообщении #357580 писал(а):

Хорошая идея, но программы могут быть большими и на бумаге их не охватить или охватить но очень долго. Как на счёт поиска решения при написании мини протатипов различных частей задачи. Например, придумал какую нибудь конструкцию рекурсивного вызова и написал 10 - 20 строчную тестовую программку с пару printf, чтобы проверить результат.
Или это всё равно неправильно и надо абсолютно полностью на бумаге моделировать любую программу независимо от размера?

Не могу знать. Я в разные периоды работы программировал по-разному. Иногда экстремально (называется, "думать пальцами"): сразу пишется код-прототип. Не работает? Пишется заново. Опять не работает? ... Опять пишется заново и т. д. После десятого повтора все работает, дописываются различные мелкие детали и программа готова. Второй подход - полное моделирование, потом кодирование. Моделировать, как мне кажется, нужно начинать от головы: ничего не пишем, лежим и смотрим в потолок, мысленно собирая куски желаемого результата в единое целое, иной раз на это уходит до 5 часов подряд (в один заход, а таких может быть несколько). Только потом записываем на бумагу и кодим. Сколько я не сравнивал эти два подхода, второй всегда оказывался быстрее, точнее и результативнее. Но я никогда не писал больше 10 тыс. строк в одной программе, поэтому не могу утверждать, что сразу записывать - плохо. Каждому своё. При участии в олимпиадах, например, надо сразу рисовать, записывать, кодировать что попало и отсылать. Там мечтать некогда и эффективность вместе с надёжностью и удобством никого не интересует.

Удивительно, но любом жизненном деле надо сначала думать, а потом делать. Это неизбежно. Опыт приходит с опытом.

[creative]

Maslov в сообщении #357586 писал(а):

При таком подходе Вы рискуете потом затратить огромные усилия на прилаживание друг к другу разрозненных и плохо стыкующихся кусков кода. Более предпочтительным обычно является нисходящее проектирование/программирование: пишете модуль (метод/процедуру) верхнего уровня, не углубляясь в детали, несущественные на данном уровне абстракции, и заменяя подчинённые модули заглушками. Отладив в первом приближении модули верхнего уровня, переходите к реализации подчинённых модулей по той же схеме. Ну и так далее...

Нет, я говорил не о самой программе с подходом разработки снизу вверх. Я говорил о прототипах, то есть маленьких тестовых програмках. Например, пишу я модуль к какому-нибудь приложению и паралельно пишу маленькие 10-20 строчные тестовые программки, которые демонстрируют или проверяют работу того или иного API или алгоритма (т.е. програмки только для теста, я не буду их код копировать в основную программу).
Мне кажется как-то неправильным без эмпирической проверки сразу лепить незнакомые API в главную программу, чтобы потом погрязнуть в отладке.

[Maslov]

creative в сообщении #357922 писал(а):

Я говорил о прототипах, то есть маленьких тестовых програмках. Например, пишу я модуль к какому-нибудь приложению и паралельно пишу маленькие 10-20 строчные тестовые программки, которые демонстрируют или проверяют работу того или иного API или алгоритма

Ну если так, то возражение снимается :)