Как стать автором
Обновить

FizzBuzz по-пенсионерски

Время на прочтение3 мин
Количество просмотров9.1K

Статья коллеги @qrdl про собеседование с написанием вариантов FizzBuzz очень понравилась.

Но очень не понравился код, совсем не понравился. И после публикации технотекстов пришлось внимательно изучить https://habr.com/ru/post/540136/ и понять, разобраться в своем неприятии, ну и потренироваться самому.

Мне >60 лет и первую часть своей карьеры я зарабатывал на более чем 20 языках, из которых пяток только ассемблеров. Но С среди них не было, а те, что были тогда, умерли все. Так что повод отличный.

Итак, начнем.


Для сравнения выбрал код https://github.com/qrdl/fizzbuzz/blob/main/customprint2.c так как с интринсиками что-то мой нотбук дает ошибку и лень разбираться. Да и не везде они есть и прекрасно можно обойтись без них.

Чтобы сравнить чисто код вычислений, в программе customprint2.c убрал 60 строку. Это вывод fwrite(cur, wrkbuf + CHUNK_SIZE - cur, 1, stdout);

Замеры проводил вот так:

#!/usr/bin/bash
gcc -O3 -march=native src/customprint2.c -o customprint2
basetime=$(date +%s%N)
./customprint2 > /dev/null
echo "runtime: $(echo "scale=3;($(date +%s%N) - ${basetime})/(1*10^09)" | bc) seconds"

Если оставить fwrite runtime: 6.954 seconds.

Если убрать fwrite runtime: 4.443 seconds.

Т.е. в сеньорской программе собственно расчеты составляют 4.4 сек. Ну норм, наверно, для сеньора.

Теперь запустим пенсионерский вариант:

/* ============================================================================
 Name        : fizzbuzz.c
 Author      : Peter Che 7210208@gmail.com
 Version     :
 Copyright   : Your copyright notice
 Description : FizzBuzz in C, Ansi-style
 ============================================================================*/

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

#define LIMIT 1000000000
#define CHUNK_SIZE  330 //??

int main(void) {
        int i;
        int ii;
        int carry;

        const char* buff;
        buff = "11\nFizz\n13\n14\nFizzBuzz\n16\n17\nFizz\n19\nBuzz\nFizz\n22\n23\nFizz\nBuzz\n26\nFizz\n28\n29\nFizzBuzz\n31\n32\nFizz\n34\nBuzz\nFizz\n37\n38\nFizz\nBuzz\n";
        int buff_len = 126;
        int l[30];
        char* s;
        char* ss;
        char* t_ss;
        char* buf_s;
        int l0;
        char* src;
        char* dst;
        char buf[CHUNK_SIZE];
        char *buf_0;
        buf_0 = "1\n2\nFizz\n4\nBuzz\nFizz\n7\n8\nFizz\nBuzz\n";


        l[0] = 3;
        l[1] = -5;
        l[2] = 3;
        l[3] = 3;
        l[4] = -9;
        l[5] = 3;
        l[6] = 3;
        l[7] = -5;
        l[8] = 3;
        l[9] = -5;
        l[10] = -5;
        l[11] = 3;
        l[12] = 3;
        l[13] = -5;
        l[14] = -5;
        l[15] = 3;
        l[16] = -5;
        l[17] = 3;
        l[18] = 3;
        l[19] = -9;
        l[20] = 3;
        l[21] = 3;
        l[22] = -5;
        l[23] = 3;
        l[24] = -5;
        l[25] = -5;
        l[26] = 3;
        l[27] = 3;
        l[28] = -5;
        l[29] = -5;

        fwrite(buf_0, 35, 1, stdout);

        memcpy(buf + CHUNK_SIZE - buff_len, buff, buff_len);
        buf_s = buf + CHUNK_SIZE -buff_len;

        fwrite(buf_s, buff_len, 1, stdout);

        l0 = 115;
        for (int j = 0; j < 33333332; j++) {
//
                ss = buf + CHUNK_SIZE - 10;
                i = 27;
                while (i >= 0)
                {
                        if (l[i] < 0) {
                                ss = ss + l[i--];
                                continue;
                        }
                        carry = 0;
                        s = ss - 3;
                        *s = *s + 3;
                        ss = ss - l[i];
                        do {
                                *s = *s + carry;
                                if (*s > '9') {
                                        carry = 1;
                                        *s = *s - 10;
                                        s--;
                                }
                                else {
                                        carry = 0;
                                        break;
                                }
                        } while (s >= ss);

                        if (carry > 0) {
                                src = buf_s--;
                                dst = buf_s;
                                l[i] = l[i] + carry;
                                l0++;
                                while (dst < s)
                                        *dst++ = *src++;
                                *(--ss) = '1';
                        }
                        i--;
                }
                fwrite(buf_s, buf + CHUNK_SIZE - buf_s, 1, stdout);
        }
        return EXIT_SUCCESS;
}

Если оставить fwrite ( это 68, 73 и 114 строки) runtime: 2.777 seconds.

Если убрать fwrite runtime: .001 seconds. (UPD ниже. Проглядел)

Всё это на машине:

model name: Intel(R) Core(TM) i5-9400T CPU @ 1.80GHz

Так что, вот так получается, что нынешние сеньоры супротив пенсионеров слабоваты. Опыта маловато, нет глубокого понимания основы основ нашего дела.

Суть разницы в скорости в том, что операции "%" и "/" очень дорогие. Но по сути это одна и та же операция, но почему-то выполнена дважды. Причем в каждом цикле, где считается число, вызываются по количеству десятичных разрядов. Это структурно лишняя операция, инкремент можно делать и без этих дорогих операций.

Ну и то, что все данные и код уместились во втором/первом кэше, конечно позволило считать очень быстро.

Ну и распараллеливать тут нечего, создание потоков съест больше времени процессора, чем собственно вычисления.

P.S. Коллега @qrdl Вы уж извините меня за такой стиль. Это ведь тоже статья шутошная, почти.

P.P.S. я больше чем уверен, что и мой код можно улучшить. Подождем других сеньоров ))

P.P.P.S. не успел опубликовать, но уже понял, что массив l и его использование не оптимально. Наверно остался от какой-то другой идеи ))

UPD. Очень дельное замечание про оптимизацию. При -О3 выбрасывает. Спасибо.

Результат, если убрать fwrite, но использовать буфер, будет 1.417 сек.

Теги:
Хабы:
Всего голосов 36: ↑31 и ↓5+37
Комментарии17

Публикации

Истории

Работа

Программист С
39 вакансий

Ближайшие события

25 – 26 апреля
IT-конференция Merge Tatarstan 2025
Казань