dcc0 Jun 11 2017 at 21:24

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

3 min

7.5K

Algorithms*

Recovery Mode

Comments 15

xEpozZ Jun 12 2017 at 00:07

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

dcc0 Jun 12 2017 at 00:08

индусский: )

-1

AngReload Jun 12 2017 at 17:45

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

#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 Jun 12 2017 at 01:17

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

Siemargl Jun 12 2017 at 02:28

А разве Алгоритм индуса является самым эффективным для генерации всех перестановок?

Простой перебор без сравнений и реверса должен быть в разы быстрее.

wataru Jun 12 2017 at 13:46

Не совсем. Рекурсивный перебор довольно медленнее. Ассимптотика точно такая же, но при переборе есть накладные расходы на рекурсию, а главное, на поиск следующего не использованного элемента.

dcc0 Jun 12 2017 at 21:48

Для n = 13 проверял без вывода, рекурсивный и данный. Рекурсивный быстрее все равно на доли секунд.

wataru Jun 12 2017 at 21:54

Итеративный метод правильно реализован, без копирования? Последний этап разворота части массива у автора сделан весьма не оптимально. Не нужно никакого d и strcopy, а нужно:

j--;
for (i = 0; i < j; i++, j--) {
  c = a[i];
  a[i] = a[j];
  a[j] = c;
}

Итеративный метод сразу в 2 раза ускоряется почти.

dcc0 Jun 12 2017 at 22:26

Спасибо. Думал об этом, уже после написания. Как четвертый шаг сокращения алгоритма.

dcc0 Jun 12 2017 at 23:03

Да, все верно. Просто переменные переназначены по другому.

#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 Jun 12 2017 at 22:37

Вы скажите, как вы рекурсивный делали, а то он у меня в 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";
}

Рекурсивный

#include <iostream>
#include <vector>
#include <ctime>

using namespace std;

int n;
char a[15];
bool fr[15];
int count;

void Gen(int i) {
    if (i == n) {
/*        for (int k = 0; k < n; k++)
            cout << (int)a[k] << " ";
        cout << "\n";*/
        count++;
        return;
    }
    for (int j = 0; j < n; j++) {
        if (fr[j]) {
            fr[j] = false;
            a[i] = j;
            Gen(i+1);
            fr[j] = true;
        }
    }
}

int main() {
    clock_t beg = clock();    
    n = 12;
    for (int i = 0; i < n; i++)
        fr[i] = true;
    Gen(0);
    cout << count << "\n";
    clock_t total = clock() - beg;
    cout << float(total) / CLOCKS_PER_SEC << "\n";
}

Результаты n=12

perm-recursive.exe
479001600
9.93

perm-iterative.exe
479001600
1.392

dcc0 Jun 12 2017 at 22:55

Рекурсивный брал отсюда.
http://www.geeksforgeeks.org/write-a-c-program-to-print-all-permutations-of-a-given-string/
Похоже с вашим вариантом оборота будет быстрее. Завтра проверю.

wataru Jun 12 2017 at 23:14

Отличный метод! Никаких проверок лишних элементов вообще. Это просто гениально. Но все-равно, он в 2 раза медленнее итеративной реализации. С учетом лишнего копирования, как раз они и будут примерно равны, как у вас.

Результат

>iterative
479001600
1.392
>recursive2
479001600
3.727

Код для тестирования

#include <iostream>
#include <vector>
#include <ctime>

using namespace std;

int n;
char a[15];
int count;

void Gen(int i) {
    if (i == n) {
/*        for (int k = 0; k < n; k++)
            cout << (int)a[k] << " ";
        cout << "\n";*/
        count++;
        return;
    }
    char c;
    for (int j = i; j < n; j++) {
        c = a[j];
        a[j] = a[i];
        a[i] = c;
        Gen(i+1);
        c = a[j];
        a[j] = a[i];
        a[i] = c;
    }
}

int main() {
    clock_t beg = clock();    
    n = 12;
    for (int i = 0; i < n; i++)
        a[i] = i;
    Gen(0);
    cout << count << "\n";
    clock_t total = clock() - beg;
    cout << float(total) / CLOCKS_PER_SEC << "\n";
}

dcc0 Jun 13 2017 at 11:44

Увы! Удаление 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 Jun 13 2017 at 11:49

Увы! Удаление strcpy ничего дало, даже небольшие потери, хотя это с выводом на терминал.

Вывод в терминал вообще очень тормознутый. Ничего с ним мерять нельзя.

Я, правда, признаюсь считал, что прироста не будет, так как по идее strcpy также копирует посимвольно в цикле, если не ошибаюсь.

Там еще каждую итерацию проверка на терминальный нулевой символ. Какой-нибудь memcpy() с фиксированным размером будет заметно быстрее. Вот тут бы никакого прироста почти и не было бы от удалиения.

Show the best of all time