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

в 18:24, , рубрики: Алгоритмы, оптимизация алгоритмов, метки:

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

Источник

Поделиться

* - обязательные к заполнению поля