Форум программистов, компьютерный форум, киберфорум
Наши страницы
CoderHuligan
Войти
Регистрация
Восстановить пароль
Рейтинг: 2.00. Голосов: 4.

Уроки программинга. Урок № 7. Ещё один пример разберём.

Запись от CoderHuligan размещена 03.06.2019 в 19:00
Обновил(-а) CoderHuligan 03.06.2019 в 19:53
Метки goto

Давайте закрепим предыдущий урок ещё одним примером.
В главе 1.9 КР находится такое задание: "Напишите программу копирования ввода на вывод, заменяющая каждую строку из одного или более пробелов единственным пробелом."
Открываем ответ из книги ТГ(Тонго, Гимпал. "Книга ответов".) и видим там код:
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
#include <stdio.h>
 
#define NONBLANK 'a'
 
int main(void) 
{
 
    int c, lastc=NONBLANK;
    while((c=getchar())!=EOF)
    {
        if(c!=' ')
        {
            putchar(c);
        }
        else if(lastc!=' ')
        {
            putchar(c);     
        }
        
        lastc=c;        
    }
    
    return 0;
}
Функция getchar() принимает по одному символу с клавиатуры(в данном случае), а функция putchar() выводит символы в консоль. Переменная lastc вначале инициализируется любым непробельным символом, в данном случае символом 'a'. Данная переменная будет содержать предыдущий входной символ.
Преобразуем также как и прошлый пример, но только в данном случае мы будем результат копировать в другую строку - ss.
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
#include <stdio.h>
#define N 255
#define NONBLANK 'a'
char s[N]="  Lorem    ipsum   j   "; 
int main(void) 
{
 
    int lastc=NONBLANK, i=0, j=0;
    char ss[N];
    while(s[i])
    {
        if(s[i]!=' ')
        {
            ss[j]=s[i]; ++j;
        }
        else if(lastc!=' ')
        {
            ss[j]=s[i]; ++j;        
        }
        
        lastc=s[i];
        ++i;
                
    }
    ss[j]='\0';
    printf("%s", ss);
    return 0;
}*/
Алгоритм полностью сохранён. Просто результат будет содержаться в другой строке.
Есть ли в данном алгоритме лишние действия? Да, есть. Это присваивание
C
1
lastc=c;
Опять мы встречаемся со школьной информатикой, которой пичкают бедных деток, которые потом вырастают с уже неизлечимым сознанием.. Надо с детских лет приучать детей мыслить категориями состояний. В данной задаче можно выделить 2-3 состояния.
1) на входе не-пробельный символ;
2) на входе пробельный символ;
Это два основных состояния.
Третье вспомогательное получается тогда, когда мы встречаем конец не-пробельных символов/а с началом пробельных. Это будет третье состояние. Давайте отобразим их в нашем коде:
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
#include <stdio.h>
#define N 255
 
char s[N]="  Lorem    ipsum   j   "; 
int main(void) 
{
    int  i=0, j=0;
    char ss[N];
    L1:
        if(!s[i])
            goto EXIT;
        if(s[i]==' ')
            goto L10;
        ss[j]=s[i]; ++j; ++i; 
            goto L1;
    L10:
        ss[j]=s[i]; ++j; 
            goto L20;
    L20:
        ++i;
        if(!s[i])
            goto EXIT;
        if(s[i]==' ')
            goto L20;
        ss[j]=s[i]; ++j; ++i; 
            goto L1;
    EXIT:
    ss[j]='\0';
    printf("%s", ss);
    return 0;
}*/
Код выглядит несколько длиннее, так как я специально переводами строк и отступами выделил поток управления. Выровнены, как метки, так и операторы goto, чтобы легко можно было охватывать алгоритм целиком.
Почему я не придаю осмысленные имена меткам? Потому что это ещё не вся программа. Документация на программу предполагает ещё три документа. Один документ должен на чистом русском языке описать все состояния программы, все входные и выходные действия.
Например:
L1 - состояние "на входе не-пробельный символ";
L20 - состояние "на входе пробельный символ";
L10 - состояние "на входе первый пробельный символ после не-пробельного";
Теперь всё понятно - нам не нужно выдумывать, тратя на это занятие много времени, различные имена меткам, переменным, функциям и пр. Достаточно иметь отдельный документ, в котором, ещё раз повторяю, мы на чистом русском языке, внятно и понятно описываем происходящее. Если нужно на английском описываем на английском и т.д.
Второй документ должен описать весь алгоритм в общих чертах: цели , что на входе, что на выходе и т.д. общее описание.
Третий документ должен описать граф переходов. К этому важному моменту мы ещё вернёмся.
Ещё раз взгляните на данные алгоритмы. В последнем случае состояния разделены и мы не совершаем никаких лишних действий, а значит эффективность последнего алгоритма выше.
Понимать такой код нужно не читая сам код, а читая соответствующую документацию. Позже мы всё это рассмотрим боле подробно. Главное, что сейчас мы должны привыкнуть к необычности кода, который раньше был обычным.
Глаза должны привыкнуть к этому. Конечно, многие просто не читают такой код, считая его "говнокодом", но думаю, что "говнокод" это такой код, который делает лишние вещи, много лишних вещей. А совершенный код, это такой код, который делает только то, что необходимо.
Наш код делает только необходимые вещи ("делай, что должен, и будь, что будет" - Лев Толстой).
Размещено в Без категории
Просмотров 438 Комментарии 26
Всего комментариев 26
Комментарии
  1. Старый комментарий
    Аватар для Croessmah
    Она не делает то что должна.
    Запись от Croessmah размещена 03.06.2019 в 21:37 Croessmah на форуме
  2. Старый комментарий
    Аватар для Usaga
    Цитата:
    Преобразуем также как и прошлый пример, но только в данном случае мы будем результат копировать в другую строку - ss.
    Зачем?

    Цитата:
    Алгоритм полностью сохранён.
    Нет. Оригинальный алгоритм работал с входными данными произвольного размера и не потребляем памяти. Ваш вариант требует буфер (хорошо, что хоть в стеке поместился), логику проверки не выхода за пределы буфера, а так же ограничен размерами этого буфера. Этот вариант тупо хуже.

    Цитата:
    пичкают бедных деток, которые потом вырастают с уже неизлечимым сознанием.. Надо с детских лет приучать детей мыслить категориями состояний. В данной задаче можно выделить 2-3 состояния.
    Молодчина. Был простой и наглядный алгоритм с минимальным состоянием (единственная переменная lastc), теперь получилась злющая каша из безусловных переходов, с буфером, выход за пределы которого это дерьмище даже не пытается проверить.

    Что в итоге: ваш пример значительно больше, совершенно нечитабельный, больше ветвлений (if) -> выше цикломатическая сложность, обладает большим количеством состояний, ненадёжный, ибо не контролирует работу с буфером.

    В чём преимущества этого... "кода" перед оригиналом?

    Цитата:
    Глаза должны привыкнуть к этому.
    Нет, не должны. Это - говно.
    Запись от Usaga размещена 04.06.2019 в 06:08 Usaga вне форума
  3. Старый комментарий
    Аватар для Croessmah
    Usaga, а чтобы выглядело короче, нафигачим всё в одну строчку.
    Запись от Croessmah размещена 04.06.2019 в 07:40 Croessmah на форуме
  4. Старый комментарий
    Цитата:
    L1 - состояние "на входе не-пробельный символ";
    L20 - состояние "на входе пробельный символ";
    Если на входе не пробельный символ, то почему он снова на пробельность проверяется? Описание не соответствует действительности.
    Запись от TopLayer размещена 04.06.2019 в 10:18 TopLayer вне форума
  5. Старый комментарий
    Аватар для Croessmah
    Ребята! Я достиг просветления.
    C
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    
    #include <stdio.h>
    #define N 255
    #define IF(x, y) if((x))goto y
    #define $(x) goto x
     
    char s[N]="  Lorem    ipsum   j   "; 
     
    int main(void) 
    {
        char ss[N];
        int i = 0, j = 0;
        L1:
            IF(!(ss[j++] = s[i]), done);
            IF(s[i] == ' ', L2);
            ++i;
            $(L1);
        L2:
            IF(s[++i] == ' ', L2);
            $(L1);
        done:
            printf("[%s]", ss);
        return 0;
    }
    И поговнокодить тоже надо:
    C
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    
    #include <stdio.h>
     
     
    int main(void) 
    { 
        int c;
        while((c=getchar()) != EOF)
        {
            putchar(c);
            while((c=getchar()) == ' ');
            if (c != EOF) putchar(c);   
        }
        return 0;
    }
    Запись от Croessmah размещена 04.06.2019 в 12:19 Croessmah на форуме
    Обновил(-а) Croessmah 04.06.2019 в 12:26
  6. Старый комментарий
    Цитата:
    И поговнокодить тоже надо:
    Говнокод с ошибкой
    Запись от TopLayer размещена 04.06.2019 в 13:02 TopLayer вне форума
  7. Старый комментарий
    Аватар для CoderHuligan
    Цитата:
    Сообщение от Croessmah Просмотреть комментарий
    Она не делает то что должна.
    Она убирает лишние символы пробела. Укажите где ошибка если она есть.
    Цитата:
    Сообщение от Usaga Просмотреть комментарий
    Зачем?
    Зачем преобразуем? Для того, чтобы удобнее проводить бенчмарки. Помоему уже обьяснял.

    Цитата:
    Сообщение от Usaga Просмотреть комментарий
    Нет. Оригинальный алгоритм работал с входными данными произвольного размера и не потребляем памяти. Ваш вариант требует буфер (хорошо, что хоть в стеке поместился), логику проверки не выхода за пределы буфера, а так же ограничен размерами этого буфера. Этот вариант тупо хуже.
    Это чисто учебный пример. Размер обоих строк одинаков.
    Цитата:
    Сообщение от Usaga Просмотреть комментарий
    Молодчина. Был простой и наглядный алгоритм с минимальным состоянием (единственная переменная lastc), теперь получилась злющая каша из безусловных переходов, с буфером, выход за пределы которого это дерьмище даже не пытается проверить.
    Выход за пределы второй строки не требуется проверять, так как длина данной строки идентична первой.
    Ваш простой и наглядный("ненаглядный мой") пример не имеет явных состояний, а это значит, что при модификации данного алгоритма придётся переписывать весь код, в то время как в моём придётся модифицировать лишь конкретное состояние не трогая другие.
    Цитата:
    Сообщение от Usaga Просмотреть комментарий
    В чём преимущества этого... "кода" перед оригиналом?
    В разделении его на явные состояния.
    Если вы не понимаете преимуществ этого, то , ну, не сошлось, что-ж..
    Цитата:
    Сообщение от Usaga Просмотреть комментарий

    Нет, не должны. Это - говно.
    Данным продуктом можно назвать код который делает много-много лишних вещей - особенно у вас в шарпах на выходе вот такой код. Жаль что им нельзя удобрять огороды.

    Цитата:
    Сообщение от TopLayer Просмотреть комментарий
    Если на входе не пробельный символ, то почему он снова на пробельность проверяется? Описание не соответствует действительности.
    Для того, чтобы в случае пробельности перейти в другое состояние.
    Запись от CoderHuligan размещена 04.06.2019 в 13:22 CoderHuligan на форуме
    Обновил(-а) CoderHuligan 04.06.2019 в 13:29
  8. Старый комментарий
    Аватар для CoderHuligan
    Цитата:
    Сообщение от Croessmah Просмотреть комментарий
    Ребята! Я достиг просветления.
    Смотрите - не втянитесь.. Это как наркотик достаточно один раз курнуть..
    Запись от CoderHuligan размещена 04.06.2019 в 13:25 CoderHuligan на форуме
  9. Старый комментарий
    Аватар для Croessmah
    Цитата:
    Она убирает лишние символы пробела. Укажите где ошибка если она есть.
    Она выполняет не ту задачу, которую выполняет код оригинала. См. пост Usaga.
    Поэтому не ясно, как минимум, зачем було притягивать сюда этот пример?
    Это можно было найти сумму чисел в массиве тогда.
    А че, какая разница, всё равно задача уже не та.
    Цитата:
    Зачем преобразуем? Для того, чтобы удобнее проводить бенчмарки. Помоему уже обьяснял.
    Бенчмарки таких программ бесполезны.
    Цитата:
    Это чисто учебный пример. Размер обоих строк одинаков.
    Почему оригинальный пример не зависит от размеров строки?
    Запись от Croessmah размещена 04.06.2019 в 13:25 Croessmah на форуме
    Обновил(-а) Croessmah 04.06.2019 в 13:31
  10. Старый комментарий
    Аватар для Croessmah
    Цитата:
    Смотрите - не втянитесь.. Это как наркотик достаточно один раз курнуть..
    Тяжелый у Вас случай...
    Запись от Croessmah размещена 04.06.2019 в 13:27 Croessmah на форуме
    Обновил(-а) Croessmah 04.06.2019 в 13:30
  11. Старый комментарий
    Аватар для CoderHuligan
    Цитата:
    Сообщение от Croessmah Просмотреть комментарий
    Бенчмарки таких программ бесполезны.
    Не бесполезны. Мы тестируем именно эффективность алгоритма, как такового.
    Цитата:
    Сообщение от Croessmah Просмотреть комментарий
    Она выполняет не ту задачу, которую выполняет код оригинала. См. пост Usaga.
    А че, какая разница, всё равно задача уже не та.
    Смысл задачи в удалении лишних пробелов. Смысл алгоритма. А каким способом мы получаем на вход поток исмволов неважно.
    Цитата:
    Сообщение от Croessmah Просмотреть комментарий
    Она выполняет не ту задачу, которую выполняет код оригинала. См. пост Usaga
    Почему оригинальный пример не зависит от размеров строки?
    Какое отношение это имеет к самому алгоритму удаления лишних пробелов?
    Запись от CoderHuligan размещена 04.06.2019 в 13:45 CoderHuligan на форуме
  12. Старый комментарий
    У меня больше состояний, я победил?
    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
    
    #include <stdio.h>
    #define IF(x, y) if(x) goto y
    #define $(x) goto x
     
    int main(void) 
    { 
        int ch;
        
        L1: // предыдущий не пробельный, текущий неизвестен
            ch = getchar();
            IF(ch == ' ', L3);
            IF(ch == EOF, EXIT);
        L2: // предыдущий не пробельный, текущий не пробельный
            putchar(ch);
            $(L1);
        L3: // предыдущий не пробельный, текущий пробельный
            putchar(ch);
        L4: // предыдущий пробельный, текущий неизвестен
            ch = getchar();
            IF(ch == ' ', L6);
            IF(ch == EOF, EXIT);
        L5: // предыдущий пробельный, текущий не пробельный
            putchar(ch);
            $(L1);
        L6: // предыдущий пробельный, текущий пробельный
            $(L4);
        EXIT:
            return 0;
    }
    Запись от TopLayer размещена 04.06.2019 в 13:59 TopLayer вне форума
  13. Старый комментарий
    Аватар для Croessmah
    Цитата:
    Мы тестируем именно эффективность алгоритма, как такового.
    Так Вы тестируете степень оптимизации компилятором. В режиме без оптимизаций тестирование не актуально, так же как и тестирование на одной платформе и одном компиляторе.
    Цитата:
    А каким способом мы получаем на вход поток исмволов неважно.
    Важно! Это разные алгоритмы. Например, в оригинальном алгоритме происходит только одно обращение к буферу с данными за итерацию. Собственно, с этим и связанно введение переменной lastc. Ваш же код имеет совершенно другие требования к входным данным и не умеет работать с входными данными оригинального алгоритма.
    Цитата:
    Какое отношение это имеет к самому алгоритму удаления лишних пробелов?
    Самое прямое - оригинальный алгоритм работает с данными, к которым нельзя обращаться дважды. Ваш код такого не умеет. Как при этом их можно сравнивать - не ясно.
    Запись от Croessmah размещена 04.06.2019 в 14:00 Croessmah на форуме
  14. Старый комментарий
    Аватар для Croessmah
    Цитата:
    Сообщение от TopLayer Просмотреть комментарий
    У меня больше состояний, я победил?
    Можно еще добавить состояний!
    Запись от Croessmah размещена 04.06.2019 в 14:06 Croessmah на форуме
  15. Старый комментарий
    Аватар для CoderHuligan
    Цитата:
    Сообщение от TopLayer Просмотреть комментарий
    У меня больше состояний, я победил?
    Зачем больше если можно обойтись тремя? Короче пошёл неадекват. Я удаляюсь..
    Запись от CoderHuligan размещена 04.06.2019 в 14:28 CoderHuligan на форуме
    Обновил(-а) CoderHuligan 04.06.2019 в 14:35
  16. Старый комментарий
    Аватар для bedvit
    Цитата:
    Сообщение от Croessmah Просмотреть комментарий
    И поговнокодить тоже надо:
    C
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    
    #include <stdio.h>
     
     
    int main(void) 
    { 
        int c;
        while((c=getchar()) != EOF)
        {
            putchar(c);
            while((c=getchar()) == ' ');
            if (c != EOF) putchar(c);   
        }
        return 0;
    }
    Да, затея удалась - нормально не работает!

    Вообще это две разные задачи, разобрать строку или ловить символы при вводе.
    По строке, можно же проще?
    К примеру
    C
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    
    #include "stdafx.h"
    #include <stdio.h>
     
    char s[] = "  Lorem    ipsum   j   ";
     
    int main(void)
    {
        int j=1;
        for (int i=1 ; i <= sizeof(s); i++)
        {
            if (s[i] != s[i - 1] || s[i] != ' ')
            {
                s[j] = s[i]; 
                j++;
            }
        }
        printf("%s", s);
        return 0;
    }
    Запись от bedvit размещена 04.06.2019 в 14:48 bedvit вне форума
    Обновил(-а) bedvit 04.06.2019 в 14:50
  17. Старый комментарий
    Аватар для bedvit
    Ого сколько накидали, пока писал.
    Запись от bedvit размещена 04.06.2019 в 14:49 bedvit вне форума
  18. Старый комментарий
    Цитата:
    Сообщение от CoderHuligan Просмотреть комментарий
    Зачем больше если можно обойтись тремя?
    Так можно и двумя обойтись. Для чего 3 тогда сделали?
    C
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    
    #include <stdio.h>
    #define IF(x, y, z) if(x) { z; goto y;}
    #define $(x) goto x
     
    int main(void) 
    { 
        int ch;
        
        L1: // предыдущий непробельный
            ch = getchar();
            IF(ch == EOF, EXIT,);
            putchar(ch);
            IF(ch != ' ', L1,);
        L2: // предыдущий пробельный
            ch = getchar();
            IF(ch == EOF, EXIT,);
            IF(ch != ' ', L1, putchar(ch));
            $(L2);
        EXIT:
            return 0;
    }
    Запись от TopLayer размещена 04.06.2019 в 14:58 TopLayer вне форума
  19. Старый комментарий
    Аватар для Croessmah
    Цитата:
    Сообщение от bedvit Просмотреть комментарий
    По строке, можно же проще?
    Или так:
    C
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    
    #include <stdio.h>
     
    char s[] = "  Lorem  ipsum   j   ";
     
    int main(void)
    {
        for (int j = 0, i = 0; s[j] = s[i]; ++j)
            if (s[i++] == ' ')
                while (s[i] == ' ') 
                    ++i;
        printf("[%s]", s);
        return 0;
    }
    Запись от Croessmah размещена 04.06.2019 в 15:02 Croessmah на форуме
  20. Старый комментарий
    Аватар для CoderHuligan
    Эдгар Дейкстра как-то сказал знаменитую фразу: "Те, кто начал программировать с goto, практически невозможно переучить программировать по новому." Можно перефразировать это и сказать: Тех кто начал учится программировать со структурной парадигмы практически невозможно переучить создавать программы как-то иначе. Это болезнь..
    Запись от CoderHuligan размещена 04.06.2019 в 16:58 CoderHuligan на форуме
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.
Рейтинг@Mail.ru