Не знаю, стоило ли делать отдельную заметку по оптимизации уже опубликованных алгоритмов или нужно было просто добавить в старую статью revised code. Я решил, что все же новенькое будет интереснее. Сразу должен сказать, что данная заметка предназначена не для профессиональных программистов.Речь, с одной стороны, пойдет о приеме оптимизации кода на языке С для генерации всех перестановок, с другой стороны, о видимых скоростных улучшениях, которые удалось получить по сравнению с кодом на С из моей покрывшейся пылью статьи. Основная задача: объяснить некоторые приемы сокращения кода неспециалистам, которым приходится сталкиваться с алгоритмизацией.
О первом
В алгоритме генерации всех перестановок после обмена значений в массиве необходимо обернуть часть этого массива — хвост. В первой реализации для этого используются 4 довольно затратных приема, которые сводятся к: а) разбиению массива на два — 2 операции, б) переворачиванию одного из полученных массивов. с) склеиванию массивов в один.
Если выразить это, например, на языке PHP, то получится следующая конструкция:
Если читатель познакомился со статьей по ссылке, то наверное заметил, что эта строчка кода фактически является полным аналогом тех операций, которые используются в коде на языке С.
Однако там операции разнесены в функции, что сильно запутывает.
Это выражение на PHP также довольно трудно читается (это не относится к программистам на языке haskell), но у нее есть один важный плюс — это однозначность в понимании необходимых действий для оптимизации. После непродолжительного медитативного созерцания этой строки она начинает осмысляться как одна операция, для которой можно попытаться найти более простой аналог, а главное более быстрый. Для PHP у меня получилось следующее:
Пришлось ввести в алгоритм еще одну копию массива и относительно простой цикл для переопределения части массива, также добавилась одна переменная z.
Прокомментирую этот участок: 1) после обмена элементов массив С равен А; 2) цикл for начинает работать от индекса, на котором осуществлен обмен (i) к нулевому индексу, i уменьшается.
Переменная z наоборот увеличивается и части массива А присваиваются элементы из массива С, но в обратном порядке. Таким образом получаем нужный результат — массив А с перевернутой частью. В реализации из переменной i вычитается 1, чтобы не выйти за пределы.
Мы получили метод оптимизации из трех шагов, который заключается: 1) в кодировании полного алгоритма, т.е. как он мыслится и выводится на бумаге, со всеми избыточными операциями; 2) в поиске и сведении некоторых разрозненных операций в одну строку 3) к поиску более простых аналогов для операций в этой строке, если это возможно.
Код на Си получился достаточно компактным:
Получилось 4 цикла и условие выхода — когда переменная достигнет факториала числа всех перестановок для n. Я нарочно выбросил сравнение массивов, чтобы немного ускорить работу.
Update
Как правильно заметил в комментариях wataru, конструкция оборота части массива также может быть заменена на более простую, в итоге имеем код в 4 цикла на Си только с использованием основной библиотеки:
О скорости работы
Ранее я проводил сравнение своей первой реализации с рекурсивным алгоритмом по данной ссылке и результат был такой:
Рекурсивный алгоритм выдал время работы для 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
О первом
В алгоритме генерации всех перестановок после обмена значений в массиве необходимо обернуть часть этого массива — хвост. В первой реализации для этого используются 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
