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