Существуют фундаментальные проблемы с вашим подходом:
Чего вы пытаетесь достичь?
Если вы хотите перечислить перестановки размером 10 обычного алфавита , ваша программа имеет недостатки, поскольку она перечисляет все комбинации из 10 букв алфавита. Ваша программа будет производить 26 10 комбинаций, огромное количество 141167095653376 , 141,167 миллиарда! Игнорирование нумерации, которая будет превышать диапазон типа int, это более 1,5 петабайта, вряд ли уместится на вашем пространстве хранения. Запись этого с максимальной скоростью 100 МБ / с займет более 20 дней.
Количество перестановок, то есть комбинаций различных букв из 26 букв алфавита, не так велико: 26! / 16! который все еще велик: 19275223968000 , в 7 раз меньше, чем предыдущий результат. Это по-прежнему более 212 терабайт памяти и 3 дня при скорости 100 МБ / с.
Хранение этих перестановок нецелесообразно. Вы можете изменить свою программу, чтобы просто подсчитать перестановки и измерить, сколько времени потребуется, если это ожидаемое значение. Первым шагом курса является исправление вашей программы для получения правильного набора.
Тест на меньших наборах для проверки правильности
Учитывая ожидаемый Размер проблемы, вы должны сначала проверить для меньших значений, таких как перечисление перестановок букв 1, 2 и 3, чтобы убедиться, что вы получите ожидаемое количество результатов.
Один раз у вас есть правильность, только тогда сосредоточьтесь на производительности
Выбирая различные методы вывода, от printf("%d %s\n", ++count, prefix); до ++count; puts(prefix); до ++count;, вы увидите, что большую часть времени тратится на создание вывод. Как только вы прекратите производить вывод, вы можете увидеть, что strlen() потребляет значительную часть времени выполнения, что бесполезно, поскольку вы можете передавать длину префикса из вызывающей стороны. Дальнейшие улучшения могут быть связаны с использованием общего массива для текущего префикса, что исключает необходимость копирования на каждом рекурсивном шаге.
Использование нескольких потоков, каждый из которых создает свой собственный вывод, например, каждый с другой начальной буквой, не будет улучшить общее время, поскольку узким местом является пропускная способность выходного устройства. Но если вы сведете программу к простому перечислению и подсчету перестановок, вы можете получить более быстрое выполнение с несколькими потоками, по одному на ядро, увеличивая тем самым загрузку ЦП. Но это должен быть последний шаг в вашей разработке.
Использование памяти не является мерой производительности
Использование как можно большего объема памяти не является цель сама по себе. Некоторые проблемы могут потребовать компромисса между памятью и временем, когда более быстрое время решения достигается с использованием большего количества памяти ядра, но это не так. 8 МБ на самом деле намного больше, чем фактические потребности вашей программы: это количество включает в себя все пространство стека, назначенное программе, из которых будет использоваться только крошечная доля.
Фактически, использование меньшего количества памяти может улучшить Общая производительность, поскольку ЦП будет лучше использовать свои различные кэши.
Вот модифицированная программа:
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
static unsigned long long count;
void print_permutations(char arr[], int n, char used[], char prefix[], int pos, int k) {
if (pos == k) {
prefix[k] = '\0';
++count;
//printf("%llu %s\n", count, prefix);
//puts(prefix);
return;
}
for (int i = 0; i < n; i++) {
if (!used[i]) {
used[i] = 1;
prefix[pos] = arr[i];
print_permutations(arr, n, used, prefix, pos + 1, k);
used[i] = 0;
}
}
}
int main(int argc, char *argv[]) {
int n = 26, k = 10;
char arr[27] = "abcdefghijklmnopqrstuvwxyz";
char used[27] = { 0 };
char perm[27];
unsigned long long expected_count;
clock_t start, elapsed;
if (argc >= 2)
k = strtol(argv[1], NULL, 0);
if (argc >= 3)
n = strtol(argv[2], NULL, 0);
start = clock();
print_permutations(arr, n, used, perm, 0, k);
elapsed = clock() - start;
expected_count = 1;
for (int i = n; i > n - k; i--)
expected_count *= i;
printf("%llu permutations, expected %llu, %.0f permutations per second\n",
count, expected_count, count / ((double)elapsed / CLOCKS_PER_SEC));
return 0;
}
Без вывода эта программа перечисляет 140 миллионов комбинаций в секунду на моем медленном ноутбуке потребовалось бы 1,5 дня , чтобы перечислить 19275223968000 10-буквенные перестановки из 26-буквенного алфавита. Он использует почти 100% одного ядра, но процессор все еще на 63% простаивает, поскольку у меня двухъядерный гиперпоточный процессор Intel Core i5. Использование нескольких потоков должно повысить производительность, но программа должна быть изменена, чтобы больше не использовать глобальную переменную count.