Не знаю, стоило ли делать отдельную заметку по оптимизации уже опубликованных алгоритмов или нужно было просто добавить в старую статью 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 b[] = "1234";
char a[] = "4321";
char d[8];
int fact = 24;
int i;
int j;
char c;
int z;
int y=0;
while (y != fact) {
printf("%sn", 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. Я нарочно выбросил сравнение массивов, чтобы немного ускорить работу.
О скорости работы
Ранее я проводил сравнение своей первой реализации с рекурсивным алгоритмом по данной ссылке и результат был такой:
Рекурсивный алгоритм выдал время работы для 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
Автор: Iv Gavryushin
