Об оптимизации комбинаторных алгоритмов

Не знаю, стоило ли делать отдельную заметку по оптимизации уже опубликованных алгоритмов или нужно было просто добавить в старую статью revised code. Я решил, что все же новенькое будет интереснее. Сразу должен сказать, что данная заметка предназначена не для профессиональных программистов.Речь, с одной стороны, пойдет о приеме оптимизации кода на языке С для генерации всех перестановок, с другой стороны, о видимых скоростных улучшениях, которые удалось получить по сравнению с кодом на С из моей покрывшейся пылью статьи. Основная задача: объяснить некоторые приемы сокращения кода неспециалистам, которым приходится сталкиваться с алгоритмизацией.

О первом

В алгоритме генерации всех перестановок после обмена значений в массиве необходимо обернуть часть этого массива — хвост. В первой реализации для этого используются 4 довольно затратных приема, которые сводятся к: а) разбиению массива на два — 2 операции, б) переворачиванию одного из полученных массивов. с) склеиванию массивов в один.

Если выразить это, например, на языке PHP, то получится следующая конструкция:

$a=array_merge(array_reverse(array_slice($a, 0, $i)),array_slice($a, $i));

Если читатель познакомился со статьей по ссылке, то наверное заметил, что эта строчка кода фактически является полным аналогом тех операций, которые используются в коде на языке С.
Однако там операции разнесены в функции, что сильно запутывает.

Это выражение на PHP также довольно трудно читается (это не относится к программистам на языке haskell), но у нее есть один важный плюс — это однозначность в понимании необходимых действий для оптимизации. После непродолжительного медитативного созерцания этой строки она начинает осмысляться как одна операция, для которой можно попытаться найти более простой аналог, а главное более быстрый. Для PHP у меня получилось следующее:

$c=$a;
$z=0;
for ($i-=1; $i > -1; $i--) $a[$z++]=$c[$i];

Пришлось ввести в алгоритм еще одну копию массива и относительно простой цикл для переопределения части массива, также добавилась одна переменная z.

Прокомментирую этот участок: 1) после обмена элементов массив С равен А; 2) цикл for начинает работать от индекса, на котором осуществлен обмен (i) к нулевому индексу, i уменьшается.

Переменная z наоборот увеличивается и части массива А присваиваются элементы из массива С, но в обратном порядке. Таким образом получаем нужный результат — массив А с перевернутой частью. В реализации из переменной i вычитается 1, чтобы не выйти за пределы.

Мы получили метод оптимизации из трех шагов, который заключается: 1) в кодировании полного алгоритма, т.е. как он мыслится и выводится на бумаге, со всеми избыточными операциями; 2) в поиске и сведении некоторых разрозненных операций в одну строку 3) к поиску более простых аналогов для операций в этой строке, если это возможно.

Код на Си получился достаточно компактным:

Смотреть
#include <stdio.h>
#include <string.h>
int main() {
        char a[] = "4321";
        char d[5];
        int fact = 24; 
           int i, j, z;
           int y=0;
            char c;
          while (y != fact) {
          printf("%s\n", a);
          i=1;
          while(a[i] > a[i-1]) {
          i++;
          }
          j=0;
          while(a[j] < a[i]) {
          j++;    
          }
      c=a[j];
      a[j]=a[i];
      a[i]=c;
    strcpy(d, a);
	z=0;
	for (i-=1; i > -1; i--) a[z++]=d[i];	
y++;  
   }
}


Получилось 4 цикла и условие выхода — когда переменная достигнет факториала числа всех перестановок для n. Я нарочно выбросил сравнение массивов, чтобы немного ускорить работу.

Update
Как правильно заметил в комментариях wataru, конструкция оборота части массива также может быть заменена на более простую, в итоге имеем код в 4 цикла на Си только с использованием основной библиотеки:

Отредактированный код
#include <stdio.h>
int main() {
        char a[] = "4321";
        int fact = 24; 
           int i, j;
           int y=0;
           char c;
          while (y != fact) {
          printf("%s\n", a);
          i=1;
          while(a[i] > a[i-1]) i++;
          j=0;
          while(a[j] < a[i])j++;         
      c=a[j];
      a[j]=a[i];
      a[i]=c;
i--;
for (j = 0; j < i; i--, j++) {
  c = a[i];
  a[i] = a[j];
  a[j] = c;
      }
y++;  
   }
}



О скорости работы

Ранее я проводил сравнение своей первой реализации с рекурсивным алгоритмом по данной ссылке и результат был такой:

Рекурсивный алгоритм выдал время работы для n=11:

real 2m9.213s
user 0m2.920s
sys 0m26.290s

Алгоритм из первой статьи выдал для n=11:

real 2m15.510s
user 0m19.750s
sys 0m34.300s

Текущая версия для n=11

real 1m46.459s
user 0m3.130s
sys 0m24.000s

Similar posts

AdBlock has stolen the banner, but banners are not teeth — they will be back

More
Ads

Comments 15

    +2
    однако странный стиль написания кода у Вас
      –1
      индусский: )
        +1
        Код прошедший автоформатирование
        #include <stdio.h>
        #include <string.h>
        int main() {
          char a[] = "4321";
          char d[5];
          int fact = 24;
          int i, j, z;
          int y = 0;
          char c;
          while (y != fact) {
            printf("%s\n", a);
            i = 1;
            while (a[i] > a[i - 1]) {
              i++;
            }
            j = 0;
            while (a[j] < a[i]) {
              j++;
            }
            c = a[j];
            a[j] = a[i];
            a[i] = c;
            strcpy(d, a);
            z = 0;
            for (i -= 1; i > -1; i--) a[z++] = d[i];
            y++;
          }
        }
      0
      А можно без кода, для дибилов, вроде меня, что всё-таки было сделано, помимо изначальной рекурсивной перестановки? Особенно мне не понравились слова «ешё одна копия массива» в контекстве «оптимизация алгоритма»
        0
        А разве Алгоритм индуса является самым эффективным для генерации всех перестановок?

        Простой перебор без сравнений и реверса должен быть в разы быстрее.
          0

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

            0
            Для n = 13 проверял без вывода, рекурсивный и данный. Рекурсивный быстрее все равно на доли секунд.
              0

              Итеративный метод правильно реализован, без копирования? Последний этап разворота части массива у автора сделан весьма не оптимально. Не нужно никакого d и strcopy, а нужно:


              j--;
              for (i = 0; i < j; i++, j--) {
                c = a[i];
                a[i] = a[j];
                a[j] = c;
              }

              Итеративный метод сразу в 2 раза ускоряется почти.

                0
                Спасибо. Думал об этом, уже после написания. Как четвертый шаг сокращения алгоритма.
                  0
                  Да, все верно. Просто переменные переназначены по другому.
                  #include <stdio.h>
                  #include <string.h>
                  int main() {
                          char a[] = "4321";
                          char d[9];
                          int fact = 24; 
                             int i, j, z;
                             int y=0;
                              char c;
                            while (y != fact) {
                            printf("%s\n", a);
                            i=1;
                            while(a[i] > a[i-1]) {
                            i++;
                            }
                            j=0;
                            while(a[j] < a[i]) {
                            j++;    
                            }
                        c=a[j];
                        a[j]=a[i];
                        a[i]=c;
                  
                  i--;
                  for (j = 0; j < i; i--, j++) {
                    c = a[i];
                    a[i] = a[j];
                    a[j] = c;
                  }
                  y++;  
                     }
                  }
                   
                  
                  
                  0

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


                  Итеративный:
                  #include <iostream>
                  #include <vector>
                  #include <ctime>
                  
                  using namespace std;
                  
                  int n;
                  char a[15];
                  int nn;
                  int count;
                  
                  void Gen() {
                      int i, j;
                      nn = n-1;
                      for (i = 0; i < n; i++)
                      a[i] = i;
                      char c;
                      while (true) {
                          // Output;
                          //for (i = 0; i < n; i++)
                          //    cout << (int)a[i] << ' ';
                          //cout << '\n';
                          count++;
                          i = nn;
                          while ((i > 0) && (a[i] < a[i-1])) 
                              i--;
                          if (i == 0) break;
                          j = nn;
                          i--;
                          while (a[j] < a[i]) 
                              j--;
                          c = a[j];
                          a[j] = a[i];
                          a[i] = c;
                          i++;
                          j = nn;
                          while (i < j) {
                              c = a[i];
                              a[i] = a[j];
                              a[j] = c;
                              i++;
                              j--;
                          }
                      }
                      cout << count << "\n";
                  }
                  
                  int main() {
                      clock_t beg = clock();
                      n = 12;
                      Gen();
                      clock_t total = clock() - beg;
                      cout << float(total) / CLOCKS_PER_SEC << "\n";
                  }

                  Рекурсивный
                  #include <iostream>
                  #include <vector>
                  #include <ctime>
                  
                  using namespace std;
                  
                  int n;
                  char a[15];
                  bool fr[15];
                  int count;
                  
                  void Gen(int i) {
                      if (i == n) {
                  /*        for (int k = 0; k < n; k++)
                              cout << (int)a[k] << " ";
                          cout << "\n";*/
                          count++;
                          return;
                      }
                      for (int j = 0; j < n; j++) {
                          if (fr[j]) {
                              fr[j] = false;
                              a[i] = j;
                              Gen(i+1);
                              fr[j] = true;
                          }
                      }
                  }
                  
                  int main() {
                      clock_t beg = clock();    
                      n = 12;
                      for (int i = 0; i < n; i++)
                          fr[i] = true;
                      Gen(0);
                      cout << count << "\n";
                      clock_t total = clock() - beg;
                      cout << float(total) / CLOCKS_PER_SEC << "\n";
                  }

                  Результаты n=12
                  perm-recursive.exe
                  479001600
                  9.93

                  perm-iterative.exe
                  479001600
                  1.392
                    0
                    Рекурсивный брал отсюда.
                    http://www.geeksforgeeks.org/write-a-c-program-to-print-all-permutations-of-a-given-string/
                    Похоже с вашим вариантом оборота будет быстрее. Завтра проверю.
                      0

                      Отличный метод! Никаких проверок лишних элементов вообще. Это просто гениально. Но все-равно, он в 2 раза медленнее итеративной реализации. С учетом лишнего копирования, как раз они и будут примерно равны, как у вас.


                      Результат
                      >iterative
                      479001600
                      1.392
                      >recursive2
                      479001600
                      3.727

                      Код для тестирования
                      #include <iostream>
                      #include <vector>
                      #include <ctime>
                      
                      using namespace std;
                      
                      int n;
                      char a[15];
                      int count;
                      
                      void Gen(int i) {
                          if (i == n) {
                      /*        for (int k = 0; k < n; k++)
                                  cout << (int)a[k] << " ";
                              cout << "\n";*/
                              count++;
                              return;
                          }
                          char c;
                          for (int j = i; j < n; j++) {
                              c = a[j];
                              a[j] = a[i];
                              a[i] = c;
                              Gen(i+1);
                              c = a[j];
                              a[j] = a[i];
                              a[i] = c;
                          }
                      }
                      
                      int main() {
                          clock_t beg = clock();    
                          n = 12;
                          for (int i = 0; i < n; i++)
                              a[i] = i;
                          Gen(0);
                          cout << count << "\n";
                          clock_t total = clock() - beg;
                          cout << float(total) / CLOCKS_PER_SEC << "\n";
                      }
                        0
                        Увы! Удаление strcpy ничего дало, даже небольшие потери, хотя это с выводом на терминал.
                        real 1m51.157s
                        user 0m4.060s
                        sys 0m24.410s

                        Но без вывода ваша правда
                        для n=12
                        С вашим вариантом оборота
                        real 0m8.763s
                        user 0m8.730s
                        sys 0m0.010s

                        Со strcpy
                        real 0m13.756s
                        user 0m13.720s
                        sys 0m0.000s

                        Прирост сразу существенный.
                        Я, правда, признаюсь считал, что прироста не будет, так как по идее strcpy также копирует посимвольно в цикле, если не ошибаюсь.


                          0
                          Увы! Удаление strcpy ничего дало, даже небольшие потери, хотя это с выводом на терминал.

                          Вывод в терминал вообще очень тормознутый. Ничего с ним мерять нельзя.


                          Я, правда, признаюсь считал, что прироста не будет, так как по идее strcpy также копирует посимвольно в цикле, если не ошибаюсь.

                          Там еще каждую итерацию проверка на терминальный нулевой символ. Какой-нибудь memcpy() с фиксированным размером будет заметно быстрее. Вот тут бы никакого прироста почти и не было бы от удалиения.

            Only users with full accounts can post comments. Log in, please.