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

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

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

11.06.2017 18:24

dcc0 15 4700 Источник

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

Поделиться с друзьями

-->

Комментарии (15)

xEpozZ

12.06.2017 00:07

#10260244

однако странный стиль написания кода у Вас

dcc0

12.06.2017 00:08

#10260248

-1

индусский: )

AngReload

12.06.2017 17:45

#10260870

Код прошедший автоформатирование

#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++;
  }
}

VaalKIA
12.06.2017 01:17
#10260274
А можно без кода, для дибилов, вроде меня, что всё-таки было сделано, помимо изначальной рекурсивной перестановки? Особенно мне не понравились слова «ешё одна копия массива» в контекстве «оптимизация алгоритма»

Siemargl
12.06.2017 02:28
#10260298
А разве Алгоритм индуса является самым эффективным для генерации всех перестановок?

Простой перебор без сравнений и реверса должен быть в разы быстрее.
1. wataru
  12.06.2017 13:46
  #10260594
  Не совсем. Рекурсивный перебор довольно медленнее. Ассимптотика точно такая же, но при переборе есть накладные расходы на рекурсию, а главное, на поиск следующего не использованного элемента.
  1. dcc0
    12.06.2017 21:48
    #10261034
    Для n = 13 проверял без вывода, рекурсивный и данный. Рекурсивный быстрее все равно на доли секунд.
    
    wataru
    12.06.2017 21:54
    #10261036
    Итеративный метод правильно реализован, без копирования? Последний этап разворота части массива у автора сделан весьма не оптимально. Не нужно никакого d и strcopy, а нужно:
    
    j--; for (i = 0; i < j; i++, j--) { c = a[i]; a[i] = a[j]; a[j] = c; }
    
    Итеративный метод сразу в 2 раза ускоряется почти.
    
    dcc0
    12.06.2017 22:26
    #10261054
    Спасибо. Думал об этом, уже после написания. Как четвертый шаг сокращения алгоритма.
    
    dcc0
    12.06.2017 23:03
    #10261086
    Да, все верно. Просто переменные переназначены по другому.
    
    #include <stdio.h> #include <string.h> int main() { char a[] = "4321"; char d[9]; 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; i--; for (j = 0; j < i; i--, j++) { c = a[i]; a[i] = a[j]; a[j] = c; } y++; } }
    
    wataru
    12.06.2017 22:37
    #10261066
    Вы скажите, как вы рекурсивный делали, а то он у меня в 10 раз медленее итеративного. Хотя код получился сильно короче, это правда.
    
    Итеративный:
    #include <iostream> #include <vector> #include <ctime> using namespace std; int n; char a[15]; int nn; int count; void Gen() { int i, j; nn = n-1; for (i = 0; i < n; i++) a[i] = i; char c; while (true) { // Output; //for (i = 0; i < n; i++) // cout << (int)a[i] << ' '; //cout << '\n'; count++; i = nn; while ((i > 0) && (a[i] < a[i-1])) i--; if (i == 0) break; j = nn; i--; while (a[j] < a[i]) j--; c = a[j]; a[j] = a[i]; a[i] = c; i++; j = nn; while (i < j) { c = a[i]; a[i] = a[j]; a[j] = c; i++; j--; } } cout << count << "\n"; } int main() { clock_t beg = clock(); n = 12; Gen(); clock_t total = clock() - beg; cout << float(total) / CLOCKS_PER_SEC << "\n"; }
    
    dcc0
    12.06.2017 22:55
    #10261080
    Рекурсивный брал отсюда.
    http://www.geeksforgeeks.org/write-a-c-program-to-print-all-permutations-of-a-given-string/
    Похоже с вашим вариантом оборота будет быстрее. Завтра проверю.
    
    wataru
    12.06.2017 23:14
    #10261096
    Отличный метод! Никаких проверок лишних элементов вообще. Это просто гениально. Но все-равно, он в 2 раза медленнее итеративной реализации. С учетом лишнего копирования, как раз они и будут примерно равны, как у вас.
    
    Результат
    >iterative 479001600 1.392 >recursive2 479001600 3.727
    
    dcc0
    13.06.2017 11:44
    #10261552
    Увы! Удаление strcpy ничего дало, даже небольшие потери, хотя это с выводом на терминал.
    real 1m51.157s
    user 0m4.060s
    sys 0m24.410s
    
    Но без вывода ваша правда
    для n=12
    С вашим вариантом оборота
    real 0m8.763s
    user 0m8.730s
    sys 0m0.010s
    
    Со strcpy
    real 0m13.756s
    user 0m13.720s
    sys 0m0.000s
    
    Прирост сразу существенный.
    Я, правда, признаюсь считал, что прироста не будет, так как по идее strcpy также копирует посимвольно в цикле, если не ошибаюсь.
    
    wataru
    13.06.2017 11:49
    #10261578
    Увы! Удаление strcpy ничего дало, даже небольшие потери, хотя это с выводом на терминал.
    Вывод в терминал вообще очень тормознутый. Ничего с ним мерять нельзя.
    
    Я, правда, признаюсь считал, что прироста не будет, так как по идее strcpy также копирует посимвольно в цикле, если не ошибаюсь.
    Там еще каждую итерацию проверка на терминальный нулевой символ. Какой-нибудь memcpy() с фиксированным размером будет заметно быстрее. Вот тут бы никакого прироста почти и не было бы от удалиения.