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

Уроки программинга. Урок № 6. Машина Тьюринга и КР.

Запись от CoderHuligan размещена 31.05.2019 в 16:32
Обновил(-а) CoderHuligan 01.06.2019 в 18:23

Важные замечания о машине Тьюринга.

Как хорошо известно, Алан Тьюринг, выдающийся английский математик(https://habr.com/ru/post/304244/), создал универсальную модель вычислительного устройства, так называемую, "машину Тьюринга". То есть был создан универсальный вычислитель, способны вычислить всё, что способно быть вычислимым в принципе. С тех пор данная модель считается эталоном полноты того или иного ЯП (Языка Программирования) Это называется полнотой по Тьюрингу . Машина Тьюринга (МТ) способна эмулировать любой алгоритм, любую вычислительную машину. По сути она представляет из себя частный случай конечного автомата, математическая теория которого хорошо развита. На ней можно эмулировать алгорифмы Маркова, машину Поста, любой компьютер, любой алгоритм и т.п. Всё что угодно. Более того: на этом принципе и построены процессоры компьютеров. Любая другая машина будет ограничена. Модель универсального вычислителя это основа будущего ИИ (Искуственного Интелекта), основа робототехники и пр.
К сожалению, "благодаря" революционным изменениям, которые произошли в комп-индустрии в 60-70 годы, МТ так и осталась недооценённым артефактом, чисто теоретической вещью, хотя и использовалась во время Великой Отечественной Войны в криптографии. А в практическом плане, наука программирования ещё даже не смогла осознать важность МТ, как ему уже всучили в зубы кость пожирнее, видимо для отвлечения внимания..
МТ состоит из двух основных устройств:

1) Управляющего устройства (головки считывания).
2) Бесконечной ленты с ячейками, в каждой из которых может находится одно единственное значение так называемого "входного алфавита".
До некоторой степени ленту можно сопоставить с ячейками ОЗУ компьютера.
Лента может двигаться вправо или влево или оставаться на месте (нейтральное положение). При этом головка считывания может считывать это значение, либо записывать его в ячейку. Это механическая её часть.
Работа МТ обуславливается тремя сущностями:
1) Набором значений входного алфавита конкретной МТ;
2) Набором явно заданных конечных состояний МТ;
3) Набором команд, которые специфизируют правила перехода из одного состояния в другое и действия машины в каждом конкретном состоянии.
Так как МТ это машина абстрактная, то она имеет бесконечную ленту с ячейками. В реальных вычислительных системах она конечна, так как конечна сама память машины. Однако это не приводит к каким-либо осложнениям когда мы пытаемся "натянуть" на реальный вычислитель, абстракцию в виде МТ.
Алгоритм работы задаётся таблицей, в которой ряды задаются отдельными значениями алфавита, а колонки состояниями данного алгоритма. В ячейках, которые образуются пересечениями данного ряда и колонки записываются команды переходов. В МТ всегда есть стартовое состояние и конечное состояние. То есть она состоит из минимум двух состояний.
Подробно с работой МТ можно ознакомится в сети, например: https://ru.wikipedia.org/wiki/%D0%9C...BD%D0%B3%D0%B0
Или даже поиграться на онлайн симуляторах, коих много в сети.

Первый пример.

Откроем первую главу КР, если кто забыл, то так мы согласились именовать книгу Кернигана и Ритчи "Язык программирования Си".
Давайте разберём небольшой пример, который к тому же позволит нам изучить некоторые особенности языка Си.
Данный пример из главы 1.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
#include <stdio.h> 
 
#define IN 1 /* внутри слова */ 
#define OUT 0 /* вне слова */ 
 
/* подсчет строк, слов и символов */ 
main () 
{ 
     int с, nl, nw, nc, state; 
     state = OUT; 
     nl = nw = nc = 0; 
     while ((c = getchar()) != EOF)
     { 
          ++nc; 
          if (c == '\n' ) 
               ++nl;
          if (c == " " || c == '\n' || с == '\t') 
               state = OUT; 
          else if (state == OUT)
          { 
                state = IN; 
                ++nw; 
          } 
     printf ("%d %d %d\n", nl, nw, nc); 
}
Что касается подсчёта строк, то тут всё просто: считаем количество \n. Количество символов также: считаем каждый введённый символ.
Примечателен алгоритм подсчёта слов. Его и разберём.
Прежде всего удалим из данного кода подсчёт строк и символов, чтобы сильнее сосредоточиться на основном алгоритме подсчёта слов, сохранив при этом сам алгоритм подсчёта слов. Также избавимся от getchar() с тем, чтобы было возможно работать с готовой примерной строкой, а в дальнейшем выполнить и некоторые бенчмарки. Преобразовав, получим данный код:
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 IN 1 /* внутри слова */ 
#define OUT 0 /* вне слова */ 
 
char s[N]="Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed";
 
int main(void) 
{ 
     int nw, state; 
     char *p=s;
     state = OUT; 
     nw = 0; 
     while (*p)
     {
          if(*p == ' ' || *p == '\n' || *p == '\t') 
               state = OUT; 
          else if (state == OUT)
          { 
                state = IN; 
                ++nw; 
          }
          ++p;
     } 
     printf ("%d\n", nw);
    return 0; 
}
Здесь мы в точности воспроизвели исходный алгоритм. Что тут примечательного? Во-первых, здесь мы наблюдаем чистый структурный код. Переменная-флаг - state призвана отмечать находимся ли мы в слове или вне слова. Слова разделяются (в данном коде) символами пробела, конца строк, и табуляции. Здесь мы встречаем новый для нас оператор инкремента ++, который просто увеличивает свой аргумент на единицу. В языке Си есть и противоположенный ему оператор декремента --, который уменьшает аргумент на единицу. На единицу можно увеличивать и так:
C
1
a = a+1;
или сокращённо так:
C
1
a +=1;
однако раньше компиляторы оптимизировали операции декремента и инкремента. К тому же отличие ещё в том, что если инкриментировать ПОСЛЕ аргумента:
C
1
a++;
то операция инкремента произойдёт ПОСЛЕ того, как выполнятся другие операторы выражения, в котором используется данный оператор. Это надо помнить. Вообще же из-за этой особенности данный оператор рекомендуется использовать с особой осторожностью или совсем отказаться от его употребления.
Препроцессорная директива #define позволяет определить макросы, то есть сокращённую запись некоторого выражения или константы, что позволяет сделать программу более поддерживаемой из-за того, что мы заменяем макросами так называемые "магические числа" в программе. В данном случае макросами мы заменили две числовые константы 1 и 0, дав им осмысленные имена. Теперь если нам потребуется изменить их значения мы можем это сделать в одном единственном месте не перелопачивая код всей программы. Препроцессор всю работу сделает за нас!
Сила, брат, не только в адресной арифметике, но и в макросах!
Указатель p, который мы настроили на первый элемент строки s, будет перемещаться по массиву строки и возвращать нам (разыменованием при помощи звёздочки - *) разыменованное значение элемента строки. Как видим , использование указателя сильно упростило как сам код, так и его понимание, так как отсутствует индексация. Привыкаем к указателям!.
Обратите внимание, если мы инкрементируем указатель так:
C
1
++p;
то будет увеличен адрес, который хранит указатель (указатель будет указывать на следующую по номеру ячейку памяти). А если вот так:
C
1
++*p;
то будет увеличено значение по адресу, который хранит указатель.
Также здесь мы видим логический оператор - ||. Он выполняет операцию ИЛИ над операндами, которые стоят по левую и правую стороны от него. А также оператор ==, который выполняет логическую операцию сравнения двух операндов слева и справа от него. Так как приоритет сравнения выше, чем операции ИЛИ, сначала будет выполнено сравнение, результат будет подставлен заместо данной операции, а затем уже будет выполнена операция ИЛИ.То есть строка:
C
1
if(*p == ' ' || *p == '\n' || *p == '\t')
означает следующее: если *p равно пробелу, или *p равно переводу строки, или *p равно табулятору.
Обратите внимание, что если к примеру первое выражение ИЛИ вернёт ДА (1), то остальные операции выполнятся не будут!
Имя переменной state в переводе означает "состояние", однако в данном коде нет явно выделенных состояний! Данная переменная просто хранит логическое значение в слове ли мы находимся в данный момент или нет. Цикл один.
Вроде как решение оптимальное и выглядит достойно, но давайте подумаем: а правильный ли это алгоритм? Можно ли тут выделить какие-то состояния, как в машине тьюринга?


Что такое "состояние"?

Попробую показать на примере, что такое состояние и с чем его едят..
В каждой квартире есть выключатель освещения. Довольно простой прибор - в каждом доме их может быть много. Входим на кухню включаем свет, выходим - выключаем.
Выключатель - устройство, которое имеет два состояния:
1) Включен;
2) Выключен;
В каждом из этих двух состояний он может находиться продолжительное время, и переключаться из одного состояния в другое по событию. Событие вызывается человеком, который нажимает на кнопку переключателя. Таким образом, такая машина (автомат) имеет 2 состояния, а его входной алфавит состоит из одного события - нажатия на кнопку.

Состояния есть у каждого мало-мальски сложного обьекта. Например человек - может находится в разных состояниях - сна, приёма пищи, прогулки, чтения и т.д. В каждом из них он может находится некоторое время.
Мыслить в терминах состояний довольно естественней, чем в терминах объектов. Состояние сна это не объект, а состояние, поэтому не всё в мире можно представить в терминах объектов.

Преобразование примера подсчёта слов.

Давайте преобразуем пример из КР в машину Тьюринга или автомат, и посмотрим что из этого выйдет, и какие плюсы мы можем из этого извлечь.
Данный алгоритм можно преобразовать в два независимых состояния, в каждом из которых автомат может находиться некоторое время. Из природы решаемой задачи сразу видно, что тут имеется как минимум 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
#include <stdio.h>
#define N 255
char s[N]="Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed";
int main(void)
{
 
    int nw = 0;
    
    char *p=s;
        --p;
    OUT:
        ++p;
        if(!*p)
            goto K;
        if(*p == ' ' || *p == ',' || *p == '\n')
            goto OUT;
        nw++; 
            goto IN;
    IN:
        if(!*p)
            goto K;
        if(*p == ' ' || *p == ',' || *p == '\n')
            goto OUT;
        ++p; 
            goto IN;
    K:
    printf ("%d \n",  nw);
    return 0;
}
Данный алгоритм переходит из одного независимого "цикла" в другой, что абсолютно неприемлемо(даже невозможно) в структурной парадигме.
Проведённые бенчмарки показали, что хотя код последнего примера длиннее, однако выполняется он на 30-40% быстрее приведённого в книге КР.
Домашнее задание: попытайтесь без потери эффективности выполнить тот же самый алгоритм в структурном стиле.
Не спешите. Внимательно изучите оба примера, и попытайтесь понять почему последний на треть эффективнее первого, и что первый делал всё это время..
Давайте немного поиграемся, и избавимся от назойливых "goto", в последнем примере:
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 <stdio.h>
#define N 255
#define IF(x, y) if((x))goto y
#define $(x) goto x
char s[N]="Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed";
int main(void)
{
 
    int nw = 0;
    
    char *p=s;
        --p;
    OUT:
        ++p;
        IF(!*p, K);
        IF(*p == ' ' || *p == ',' || *p == '\n', OUT);
             nw++; 
         $(IN);
    IN:
        IF(!*p, K);
        IF(*p == ' ' || *p == ',' || *p == '\n', OUT);
             ++p; 
         $(IN);
    K:
    printf ("%d\n",  nw);
    return 0;
}
Символ $ хорошо подходит для обозначения прямого безусловного перехода - вертикальная черта пересекает извилистый путь, то есть прямой путь всегда эффективнее кривого..
Продолжение следует...
Размещено в Без категории
Просмотров 1379 Комментарии 87
Всего комментариев 87
Комментарии
  1. Старый комментарий
    Аватар для bedvit
    По-моему здесь где-то ошибка/и
    C
    1
    
    if (c == " " || c == '\n' || с '\t')
    Запись от bedvit размещена 31.05.2019 в 18:20 bedvit на форуме
  2. Старый комментарий
    Аватар для liv
    А теперь посмотрим на такой код:
    C
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    
    #include <stdio.h>
    #define N 255
    char s[N] = "Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed";
    int main(void)
    {
        int nw;
        bool prev = true;
        bool curr = true;
        char *p = s;
     
        for (nw=0; *p; p++)
        {
            prev = curr;
            curr = (*p == ' ' || *p == ',' || *p == '\n');
            nw += prev && !curr;
        }
        printf ("%d\n", nw);
        return 0;
    }
    Запись от liv размещена 31.05.2019 в 18:21 liv на форуме
  3. Старый комментарий
    Аватар для CoderHuligan
    Цитата:
    Сообщение от bedvit Просмотреть комментарий
    По-моему здесь где-то ошибка/и
    C
    1
    
    if (c == " " || c == '\n' || с '\t')
    Копипастил из русского перевода КР, а там эта опечатка.
    Запись от CoderHuligan размещена 31.05.2019 в 18:27 CoderHuligan вне форума
  4. Старый комментарий
    Аватар для bedvit
    По скорости - слишком короткая строка, не удалось определить победителя
    Запись от bedvit размещена 31.05.2019 в 18:28 bedvit на форуме
  5. Старый комментарий
    Аватар для CoderHuligan
    Цитата:
    Сообщение от bedvit Просмотреть комментарий
    По скорости - слишком короткая строка, не удалось определить победителя
    Надо вкладывать во внешний цикл. Позже проведу проверку.
    Запись от CoderHuligan размещена 31.05.2019 в 18:41 CoderHuligan вне форума
  6. Старый комментарий
    Аватар для liv
    CoderHuligan, ну и чем Ваш код лучше?
    То, что читается хуже, так это однозначно... А работает ничуть не быстрее...
    Запись от liv размещена 31.05.2019 в 18:41 liv на форуме
  7. Старый комментарий
    Аватар для rerf2010rerf
    Ещё и дублирование кода, вот это вот, два куска практически одинаковые
    C
    1
    2
    3
    4
    5
    6
    
     if(!*p)
                goto K;
            if(*p == ' ' || *p == ',' || *p == '\n')
                goto OUT;
            nw++; 
                goto IN;
    C
    1
    2
    3
    4
    5
    6
    
            if(!*p)
                goto K;
            if(*p == ' ' || *p == ',' || *p == '\n')
                goto OUT;
            ++p; 
                goto IN;
    Запись от rerf2010rerf размещена 31.05.2019 в 18:54 rerf2010rerf на форуме
  8. Старый комментарий
    Аватар для CoderHuligan
    Цитата:
    Сообщение от liv Просмотреть комментарий
    CoderHuligan, ну и чем Ваш код лучше?
    Помните я в первом уроке писал что утрём носик отцам основателям? Он лучше тем, что работает быстрее кода отцов-основателей. Он просто эффективнее, если вам вообще что-то говорит это слово.
    Цитата:
    Сообщение от liv Просмотреть комментарий
    То, что читается хуже, так это однозначно...
    Кому как..
    Цитата:
    Сообщение от liv Просмотреть комментарий
    А работает ничуть не быстрее...
    Проверим.
    Запись от CoderHuligan размещена 31.05.2019 в 18:54 CoderHuligan вне форума
  9. Старый комментарий
    Аватар для liv
    Цитата:
    Сообщение от CoderHuligan Просмотреть комментарий
    Кому как..
    Подавлющему большинству программистов
    Запись от liv размещена 31.05.2019 в 18:56 liv на форуме
  10. Старый комментарий
    Кликните здесь для просмотра всего текста
    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
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    
    #include <stdio.h>
    #include <Windows.h>
    #define N 1000
    #define IF(x, y) if((x))goto y
    #define $(x) goto x
    char s[N] = "Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed ";
     
    double get_time()
    {
        LARGE_INTEGER t, f;
        QueryPerformanceCounter(&t);
        QueryPerformanceFrequency(&f);
        return (double)t.QuadPart / (double)f.QuadPart;
    }
     
    void bench(int func(char*), int count, const char* description)
    {
        double start_time = get_time();
        double sum = 0;
     
        for (int i = 0; i < count; i++)
        {
            sum += func(s);
        }
     
        double time = get_time() - start_time;
     
        printf("%s: %f sum=%f\n", description, time, sum);
    }
     
    int calc_words_by_CoderHuligan(char* s)
    {
        int nw = 0;
     
        char* p = s;
    OUTWORD:
        ++p;
        IF(!*p, K);
        IF(*p == ' ' || *p == ',' || *p == '\n', OUTWORD);
        nw++;
        $(INWORD);
    INWORD:
        IF(!*p, K);
        IF(*p == ' ' || *p == ',' || *p == '\n', OUTWORD);
        ++p;
        $(INWORD);
    K:
     
        return nw;
    }
     
    int calc_words_by_TopLayer(char* s)
    {
        int inWord = 0;
        int count = 0;
     
        for (char* curr = s; 1; ++curr)
        {
            switch (*curr)
            {
            case ' ':
            case ',':
            case '\n':
                inWord = 0;
                break;
            case '\0':
                return count;
            default:
                count += 1 - inWord;
                inWord = 1;
                break;
            }
        }
    }
     
    int calc_words_by_CR(char* s)
    {
        int nw, state;
        char* p = s;
        state = 0;
        nw = 0;
        while (*p)
        {
            if (*p == ' ' || *p == '\n' || *p == '\t')
                state = 0;
            else if (state == 0)
            {
                state = 1;
                ++nw;
            }
            ++p;
        }
        return nw;
    }
     
    int main(void)
    {
        int count = 50 * 1000 * 1000;
     
        for (int i = 0; i < 5; i++)
        {
            bench(calc_words_by_TopLayer, count, "TopLayer\t");
            bench(calc_words_by_CoderHuligan, count, "CoderHuligan\t");
            bench(calc_words_by_CR, count, "CR\t\t");
            printf("\n");
        }
    }

    Результаты x86
    Кликните здесь для просмотра всего текста
    Код:
    TopLayer        : 12.917347 sum=1350000000.000000
    CoderHuligan    : 14.812625 sum=1350000000.000000
    CR              : 12.661899 sum=1350000000.000000
    
    TopLayer        : 12.802429 sum=1350000000.000000
    CoderHuligan    : 16.617118 sum=1350000000.000000
    CR              : 12.346018 sum=1350000000.000000
    
    TopLayer        : 12.718622 sum=1350000000.000000
    CoderHuligan    : 14.780174 sum=1350000000.000000
    CR              : 12.028693 sum=1350000000.000000
    
    TopLayer        : 12.303113 sum=1350000000.000000
    CoderHuligan    : 15.288510 sum=1350000000.000000
    CR              : 12.544408 sum=1350000000.000000
    
    TopLayer        : 12.637029 sum=1350000000.000000
    CoderHuligan    : 14.957522 sum=1350000000.000000
    CR              : 11.901372 sum=1350000000.000000

    Результаты x64
    Кликните здесь для просмотра всего текста
    Код:
    TopLayer        : 10.847556 sum=1350000000.000000
    CoderHuligan    : 13.810305 sum=1350000000.000000
    CR              : 14.043269 sum=1350000000.000000
    
    TopLayer        : 10.784305 sum=1350000000.000000
    CoderHuligan    : 13.125637 sum=1350000000.000000
    CR              : 13.482344 sum=1350000000.000000
    
    TopLayer        : 10.542314 sum=1350000000.000000
    CoderHuligan    : 13.152043 sum=1350000000.000000
    CR              : 14.088173 sum=1350000000.000000
    
    TopLayer        : 10.998437 sum=1350000000.000000
    CoderHuligan    : 13.457013 sum=1350000000.000000
    CR              : 13.632453 sum=1350000000.000000
    
    TopLayer        : 10.612615 sum=1350000000.000000
    CoderHuligan    : 13.171614 sum=1350000000.000000
    CR              : 13.673943 sum=1350000000.000000
    Запись от TopLayer размещена 31.05.2019 в 19:15 TopLayer вне форума
  11. Старый комментарий
    Аватар для liv
    Вот мой результат сравнения таким несложным образом:
    Кликните здесь для просмотра всего текста
    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
    
    #include <time.h>
    #include <stdio.h>
    #define N 255
    char s[N] = "Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed";
    int main(void)
    {
        clock_t time = clock();
     
        for (int i = 0; i < 10000000; i++)
        {
            int nw;
     
            bool prev = true;
            bool curr = true;
            char *p = s;
     
            nw = 0; 
            while(*p)
            {
                prev = curr;
                curr = (*p == ' ' || *p == ',' || *p == '\n');
                nw += prev && !curr;
                p++;
            }
        }
     
        printf("%f\n", (double)(clock() - time) / CLOCKS_PER_SEC);
        
    #define IF(x, y) if((x))goto y
    #define $(x) goto x
            time = clock();
            
            for (int i = 0; i < 10000000; i++)
            {
                    int nw = 0;
     
                    char *p = s;
                OUT:
                    ++p;
                    IF(!*p, K);
                    IF(*p == ' ' || *p == ',' || *p == '\n', OUT);
                    nw++;
                    $(IN);
                IN:
                    IF(!*p, K);
                    IF(*p == ' ' || *p == ',' || *p == '\n', OUT);
                    ++p;
                    $(IN);
                K:;
            }
            printf("%f\n", (double)(clock() - time) / CLOCKS_PER_SEC);
            return 0;
    }
    Результат сильно зависит от того Debug версия или Release
    Вот что выдала Release программа:

    0.673000
    3.010000

    В 4.5 (!) раз мой фрагмент работает быстрее!
    В Debug версии правда в 2 раза медленнее... Но Debug есть Debug...
    Кому-то тут известно слово "эффективность"...
    Запись от liv размещена 31.05.2019 в 19:28 liv на форуме
    Обновил(-а) liv 31.05.2019 в 19:59
  12. Старый комментарий
    Цитата:
    В 4.5 (!) раз моя подпрограммка работает быстрее!
    На моем ноуте только в 3 раза при компиляции под x86, и в 2,5 раза при компиляции под x64.
    А вот если перенести на C, то уступит всем вариантам. Может у меня бенч с ошибкой?
    C
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    
    int calc_words_by_liv(char* s)
    {
        int nw;
     
        int prev = 1;
        int curr = 1;
        char* p = s;
     
        nw = 0;
        while (*p)
        {
            prev = curr;
            curr = (*p == ' ' || *p == ',' || *p == '\n');
            nw += prev && !curr;
            p++;
        }
     
        return nw;
    }
    Запись от TopLayer размещена 31.05.2019 в 20:01 TopLayer вне форума
  13. Старый комментарий
    Аватар для Croessmah
    Твой код имеет поведение, отличное от первого кода из КР.
    Дооптимизировался.
    https://rextester.com/RCS2118
    https://rextester.com/CQEPC95958
    Запись от Croessmah размещена 31.05.2019 в 20:07 Croessmah на форуме
  14. Старый комментарий
    Аватар для liv
    TopLayer, ничего не скажу... А по мне, так и 3, и 2.5 раза говорят, что все, что пытается нам донести уважаемый ТС, мягко скажем, не дает никаких преимуществ, а только значительно усложняет понимание... И ради чего?
    Мое мнение только углубилось...
    Запись от liv размещена 31.05.2019 в 20:11 liv на форуме
  15. Старый комментарий
    Неужели главной характеристикой кода является его быстродействие?
    Для меня например нет разницы...
    работает программа 0,001 секунды или 1 секунду. Всё-равно это ничего программисту не даст.
    Время - деньги.
    Более медленная программа как правило будет создана скорее. Вот где экономится время! Или я не прав? Тут собрались умные люди. И я полагаю, что они не фанатики, целью которых - "быстрая программа любой ценой"
    Запись от нтч размещена 01.06.2019 в 11:23 нтч вне форума
  16. Старый комментарий
    Аватар для Croessmah
    Цитата:
    работает программа 0,001 секунды или 1 секунду.
    Разница в тысячу раз?
    Цитата:
    Или я не прав? Тут собрались умные люди. И я полагаю, что они не фанатики, целью которых - "быстрая программа любой ценой"
    Вам разницы нет, а если эта программа, которая работает на сервере и обрабатывает миллионы запросов?
    Или это часть алгоритма рендера в видеоредакторе?
    Ждать окончания рендеринга час и десять часов - разница ощутимая.
    НО! Прежде чем оптимизировать нормальный код, нужно доказать необходимость этой оптимизации.
    Упарываться две недели, чтобы получить выполнение на две секунды быстрее в функции,
    которая вызывается раз в десять минут - хреновый результат.
    Цитата:
    Время - деньги.
    В данном случае можно попробовать просто "пустить" цикл оригинального кода в обратном порядке.
    Скорее всего он будет работать быстрее, чем велосипед автора.
    Запись от Croessmah размещена 01.06.2019 в 11:34 Croessmah на форуме
  17. Старый комментарий
    Аватар для Avazart
    Это было сказано к тому что приоритеты (эффективность, ясность кода, скорость разработки итд.) сильно зависят от задачи.

    И очевидно что хочется оптимизировать пиши на асме или делай асм вставки (с соответствующими последтвиями), а не страдай как автор фигней с goto.
    Запись от Avazart размещена 01.06.2019 в 12:09 Avazart на форуме
    Обновил(-а) Avazart 01.06.2019 в 12:12
  18. Старый комментарий
    Аватар для Croessmah
    Ну так, пока чай пил.
    Обратный проход
    C
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    
    void foo(void) 
    { 
        int nw = 0;
        int state = OUT; 
        char * p = s + strlen(s);
        while (p != s)
        {
            --p;
            if(IS_SPACE(*p)) {
                state = OUT; 
            }
            else if (state == OUT) { 
                state = IN; 
                ++nw; 
            }
        } 
        X = nw;
    }

    Запустил синтетические тесты.
    Выполнялось 100000 прогонов на данных из файла в ~494 Кб.
    Показало такой результат:

    x64 - clang -O3 -DNDEBUG
    Код:
    Оригинальный код
    Чтение файла...
    Прочитано 494126 байт.
    Результат: 71244
    Время выполнения: 113.029847
    
    Код от liv
    Чтение файла...
    Прочитано 494126 байт.
    Результат: 70902
    Время выполнения: 151.892191
    
    Код от CoderHuligan
    Чтение файла...
    Прочитано 494126 байт.
    Результат: 70902
    Время выполнения: 97.843284
    
    Код от Croessmah
    Чтение файла...
    Прочитано 494126 байт.
    Результат: 71244
    Время выполнения: 89.648194

    x64 - gcc -O3 -DNDEBUG

    Код:
    Оригинальный код
    Чтение файла...
    Прочитано 494126 байт.
    Результат: 71244
    Время выполнения: 104.988702
    
    Код от liv
    Чтение файла...
    Прочитано 494126 байт.
    Результат: 70902
    Время выполнения: 101.691142
    
    Код от CoderHuligan
    Чтение файла...
    Прочитано 494126 байт.
    Результат: 70902
    Время выполнения: 114.833246
    
    Код от Croessmah
    Чтение файла...
    Прочитано 494126 байт.
    Результат: 71244
    Время выполнения: 105.545979


    x32 - clang -m32 -O3 -DNDEBUG
    Код:
    Оригинальный код
    Чтение файла...
    Прочитано 494126 байт.
    Результат: 71244
    Время выполнения: 148.357867
    
    Код от liv
    Чтение файла...
    Прочитано 494126 байт.
    Результат: 70902
    Время выполнения: 137.317979
    
    Код от CoderHuligan
    Чтение файла...
    Прочитано 494126 байт.
    Результат: 70902
    Время выполнения: 103.277272
    
    Код от Croessmah
    Чтение файла...
    Прочитано 494126 байт.
    Результат: 71244
    Время выполнения: 104.967851


    x32 - gcc -m32 -O3 -DNDEBUG
    Код:
    Оригинальный код
    Чтение файла...
    Прочитано 494126 байт.
    Результат: 71244
    Время выполнения: 100.925051
    
    Код от liv
    Чтение файла...
    Прочитано 494126 байт.
    Результат: 70902
    Время выполнения: 89.601795
    
    Код от CoderHuligan
    Чтение файла...
    Прочитано 494126 байт.
    Результат: 70902
    Время выполнения: 107.555324
    
    Код от Croessmah
    Чтение файла...
    Прочитано 494126 байт.
    Результат: 71244
    Время выполнения: 108.041254

    Как и ожидалось, все "оптимизации", в общем случае, бесполезны.
    Ну и да, автор накосячил с алгоритмом, поэтому он выдает неправильный результат.
    Код liv тоже этим грешит, видимо, переделывал не из оригинального кода.
    Запись от Croessmah размещена 01.06.2019 в 12:17 Croessmah на форуме
    Обновил(-а) Croessmah 01.06.2019 в 12:34
  19. Старый комментарий
    Аватар для CoderHuligan
    Да... Повеселили меня.. Оптимизацию не забыли случаем отключить? А? Почему-то об этом умолчали.. О том, что цикл for оптимизирован на уровне регистров тоже. В любом случае мои бенчмарки показывают несколько иной результат.
    Тестировались два случая. Один через цикл, который выполняется 30000000 раз (тридцать милионов). Второй на длинной строке длиной 1 гигабайт при единичном цикле.
    Оптимизация естественно отключена полностью, чтобы тестировать ИМЕННО алгоритм, а не оптимизатор вашего компилятора.
    Первый случай показал такие результаты:
    1) Код КР - 14 секунд.
    2) Код Liv - 13 секунд.
    3) Код на goto - 11 секунд.
    Тестовые условия:
    C
    1
    
    #define M 300000000
    и раскомментируйте строку s. Закомментируйте выделение памяти и заполнение строки s.

    Второй случай показал более удивительный результат на длинной строке длиной 1 гигабайт:
    1) Код КР - 7 секунд.
    2) Код Liv - 8 секунд.
    3) Код на goto - 4 секунды.
    Тестовые условия:
    C
    1
    2
    
    #define B 1000000000
    #define M 1
    Как я и писал на 30-50% быстрее мой вариант.

    Вот код:
    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
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    
    #include <stdio.h>
    #include <stdlib.h> 
    #include <time.h>
     
    #define B 1000000000
    #define M 1
    #define N 255
    //#define GOTO
    #define KR
    //#define LIV
    #ifdef KR
        #define IN 1 
        #define OUT 0 
    #endif
     
    //char s[N]="Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed";
     
    int main(void) 
    { 
        time_t st, en;
        //ДЛЯ длинной строки!
        // создаём и заполняем строку в куче( последовательность  - три пробела/6 букв а)
        char *s = (char*)malloc(sizeof(char)*B);
        char *f = s;
        long i;
        int c=0;
        for(i=0; i<B-1; ++i, ++c)
        {
            if(c<=6)
                f[i]='a';
            else
            {
                f[i]=' ';
                if(c>=9)c=0;
            }
        }
        f[B-1] = '\0';
     
        st=time(NULL);
        int state, nw = 0;
        char *p;
        int curr, prev;
    #ifdef GOTO
        for(i=0; i<M; ++i)
        {
            nw = 0;
            p=s;
     
            OUT:
                ++p;
                if(!*p)
                    goto K;
                if(*p == ' ' || *p == ',' || *p == '\n')
                    goto OUT;
                nw++; 
                    goto IN;
            IN:
                if(!*p)
                    goto K;
                if(*p == ' ' || *p == ',' || *p == '\n')
                    goto OUT;
                ++p; 
                    goto IN;
            K:;
        }
    #endif
    #ifdef KR
        for(i=0; i<M; i++)
        {
            p=s;
            state = OUT; 
            nw = 0;
            while(*p)
            {
                if(*p == ' ' || *p == ',' || *p == '\n') 
                    state = OUT; 
                else if (state == OUT)
                { 
                    state = IN; 
                    ++nw; 
                }
                ++p;
            }
        }
    #endif
    #ifdef LIV
        for(i=0; i<M; i++)
        {
            prev = 1;
            curr = 1;
            p = s;
            for (nw=0; *p; p++)
            {
                prev = curr;
                curr = (*p == ' ' || *p == ',' || *p == '\n');
                nw += prev && !curr;
            }
        }
    #endif 
     
        en=time(NULL); 
        printf("Rezult: %ld sec.\n", en - st); 
        return 0;
    }
    Или я что-то не понимаю, или кто-то из нас пытается ввести в заблуждение.. У меня нехорошие мысли по этому поводу, друзья..

    Я-то прекрасно осознаю, что мой алгоритм правильный, то есть оптимизирован на уровне самого алгоритма. Лучше уже не сделаешь. Поэтому вы не сможете приблизится к данной эффективности применяя структурный код. Просто признайте это.
    Запись от CoderHuligan размещена 01.06.2019 в 14:29 CoderHuligan вне форума
    Обновил(-а) CoderHuligan 01.06.2019 в 15:17
  20. Старый комментарий
    Аватар для Avazart
    Что бы оценивать эффективность алгоритма вообще тестировать не нужно.

    А вот как раз писать код и тестировать без учета оптимизации настоящее время как глупо.
    Запись от Avazart размещена 01.06.2019 в 16:55 Avazart на форуме
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.
Рейтинг@Mail.ru