Однострочники на Си/С++. Часть 2


    Ранее я уже публиковал статью о Однострочниках на С++. Так в этом посте я хочу упомянуть ещё несколько алгоритмов, а также несколько реализаций алгоритма обмена двух чисел(с вычислением времени работы).
    Всех заинтересовавшихся прошу под кат;)


    1. Проверка на простоту


    Для вызова этой функции надо написать prime(100, int(sqrt(100)));
    bool prime(int n, int div) {
      return ( div == 1) ? true : (n % div != 0) && (prime(n, div-1));
    }
    

    Чтобы этого избежать можно создать функцию-оболочку:
    bool prime(int n) {
      return ( n == 1 )? 0 : ( prime( n, int(sqrt(n))) ) ;
    }
    

    и тепер для вызова функции достаточно написать prime(100)

    2. Код Грея


    Кодом Грея называется такая система нумерования неотрицательных чисел, когда коды двух соседних чисел отличаются ровно в одном бите.
    int codeGrey (int n) {
     return n ^ (n >> 1);
    }
    

    А также нахождение обратного кода Грея
    int revCodeGrey (int g) { 
        int n;  
        for (n=0; g; n ^=g, g>>=1); 
        return n;
    }
    

    Коды Грея имеют несколько применений в различных областях:
    • битный код Грея соответствует гамильтонову циклу по n-мерному кубу
    • в решении задачи о Ханойских башнях
    • применение в теории генетических алгоритмов


    3. Вычисление биномиального коэффициента


    Биномиальный коэффициент — это коэффициент в разложении бинома Ньютона image по степеням x.
    int binomialCoefficient(int k, int n) {
        return (n==k || k==0)?1:binomialCoefficient(k-1,n-1)+binomialCoefficient(k,n-1);
    }
    


    4. Нахождение степени делителя факториала


    Даны два числа: [n] и [k]. Требуется посчитать, с какой степенью делитель [k] входит в число [n].
    int factPow(int n, int k) {
        return (n)? (n/k + factPow(n/k, k)):0;
    }
    


    5. Возведение числа [a] в степень [b] по модулю [p].


    nt powM(int a, int b, int p) {
        return b ? (a * powM(a-1, b, p) % p) : 1;
    }
    

    Также здесь можно использовать индийский алгоритм возведения в степень.
    int powM(int a, int b, int p) {
        return b ? ((b&1?a:1)*powM(a*a, b/2, p) % p) : 1;
    }
    





    Мое исследование SWAPa


    Вот мне пришла мысль исследовать разнообразные SWAPи, какой из них самый быстрый.
    Тест SWAPов будет вот такой программкой
        int a=1, b=2;
        for(int i=0; i<=300000000; i++) {
           swap(&a, &b);
        }
    

    где вместо swap, будут различные алгоритмы обмена двух значений.

    SWAP0

    Итак начнем пожалуй из STLивского, стандартного алгоритма:
    template <class T> void swap0 ( T& a, T& b ) {
        T c(a); a=b; b=c;
    }
    

    его показатели были таковы:
       1,996 sec.
       1,986 sec.
       1,996 sec.
    


    SWAP1

    Следующим SWAPом будет так называемый XOR SWAP:
    void swap1(int *a, int *b) {
        *a ^= ( *b ^= ( *a ^= *b ));
    }
    


    его показатели были таковы:
       3,603 sec.
       3,603 sec.
       3,608 sec.
    


    SWAP2

    void swap2(int *a, int *b) {
        *a += *b -= *a = *b - *a;
    }
    

    её показатели были таковы:
       3.728 sec.
       3.723 sec.
       3.728 sec.
    


    SWAP3

    void swap3(int *a, int *b) {
        *a /= *b = (*a= *a * (*b)) / (*b);
    }
    

    её показатели были таковы:
       7.878 sec.
       7.862 sec.
       7.862 sec.
    


    SWAP4

    void swap4(int *a, int *b) {
        *b= *a + *b - (*a = *b);
    }
    

    её показатели были таковы:
       2.012 sec.
       2.007 sec.
       2.012 sec.
    


    SWAP5

    void swap5(int *a, int *b) {
        *a=(*b=(*a=*b^*a)^*b)^*a;
    }
    

    её показатели были таковы:
      3.198 sec.
      3.213 sec.
      3.198 sec.
    


    SWAP6

    Ну, и ассемблерная вставка для компилятора GCC
    void swap7(int *a, int *b) {
         asm volatile(
            "XOR   %%EAX,  %%EBX;      \n\t"
            "XOR   %%EBX,  %%EAX;      \n\t"
            "XOR   %%EAX,  %%EBX;      \n\t"
            :"=a"(*a),"=b"(*b)
            :"a"(*a),"b"(*b)
        );
    }
    

    её показатели были таковы:
       2.199 sec.
       2.153 sec.
       2.167 sec.
    


    Как видим наша таблица исследований такова:
    1. SWAP0 -  1.992 sec.
      
    2. SWAP4 -  2.010 sec.
      
    3. SWAP6 -  2.173 sec.
      
    4. SWAP5 -  3.203 sec.
      
    5. SWAP1 -  3.604 sec.
      
    6. SWAP2 -  3.726 sec.
      
    7. SWAP3 -  7.867 sec.
      
    Поделиться публикацией
    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее
    Реклама

    Комментарии 23

      0
      Понимаете, любая функция должна быть хорошей. Нет, наверное, в качестве задачи для разминки мозгов «сделай XXXXX так, чтобы поместилось в одну строку» это подойдет. Вы рассматриваете их именно с этой точки зрения, правда?
      +4
      >> Ранее я уже публиковал статью о Однострочниках на С++.

      И, насколько я помню, с треском провалились?
        0
        Нет, это замена «Однострочников 2». Так сказать, «Однострочники 2.5»
        0
        Почему команду «xchg op1, op2» в ассемблерной вставке не используете?
          +1
          Потому что один из операндов должен быть регистром.
            0
            Полагаю, потому что xchg не имеет формы для обмена двух переменных в памяти.
              +2
              Да можно и так…
              void swap(int *a, int *b) {
                   asm volatile(
                      "XCHG   %0,  %1;      \n\t"
                      :"=a"(*a),"=b"(*b)
                      :"a"(*a),"b"(*b)
                  );
              }
              
                0
                И не забывайте, что если в аргументах XCHG есть память, то инструкция будет иметь префикс LOCK, что не значительно влияет на скорость исполнения.
                0
                Спасибо, Кэп)
                  0
                  Мне кажется, или данная реализация кода Грея для чисел вида 11...11 вернет 10...00?
                  11...11 ^ (01...11) = 10...00
                  • НЛО прилетело и опубликовало эту надпись здесь
                      0
                      clock_t start = clock();
                      ...
                      clock_t end = clock();
                      
                      –2
                      «индийский алгоритм»
                      return b? ((b&1?a:1)*powM(a*a, b/2, p) % p): 1;

                      Человек, который найдет это в какой-нить опенсурсной библиотеке, в которой нужно будет разобраться, прокленет ее автора.

                      Макконнелла не читали?
                        0
                        Почему? Алгоритм довольно простой и известный: если степень нечётная, умножь на основание предыдущую степень, а если чётная, возведи в квадрат вдвое меньшую степень. В одной строке разобраться не слишком сложно.
                          0
                          Это же не реальный рабочий код — это «разминка для мозгов». Естественно, никто не станет так делать. Я надеюсь, во всяком случае.
                            +1
                            В таком разобраться гораздо труднее:
                            main(Q,O)char**O;{if(--Q){main(Q,O);O[Q][0]^=0X80;for(O[0][0]=0;O[++O[0][0]]!=0;)if(O[O[0][0]][0]>0)puts(O[O[0][0]]);puts("----------");main(Q,O);}}
                            
                          0
                          При всём уважении к труду… я не совсем понимаю, зачем нужны «однострочники» на C++.
                          Одно дело какой-нибудь powershell, где нужно в командной строке набрать строчку и получить результат.
                          И совсем другое дело — компилируемый язык, где разницы между одной строчкой и десятью строчками нет.

                          У меня все программы состоят из однострочников примерно такого вида:

                          class X {
                          public: void f();
                          void g(int x);
                          int h(double a, double b);
                          };

                          А что находится в cpp-модуле — какая кому разница?
                            0
                            Спортивный интерес.
                              0
                              удалите все \n из текста программы :)
                            +3
                            > Сравнение 5 вариантов кода с undefined bahavior.

                            Fixed.
                              0
                              Где это оно fixed? Туплю.
                                0
                                Это предлагаемое исправление текста топика, чтобы тот соответствовал дейстительности.

                            Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                            Самое читаемое