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

Не знаю, стоило ли делать отдельную заметку по оптимизации уже опубликованных алгоритмов или нужно было просто добавить в старую статью 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