Cómo acelerar la impresión de todas las particiones de un conjunto de n elementos en k conjuntos desordenados.
Cómo acelerar mi programa?
Mi tarea: 1<=k<=n<=10, tiempo 1 segundo
Imprima todas las particiones de un conjunto de n elementos en k conjuntos desordenados. Las particiones pueden ser mostradas en cualquier orden. Dentro de una partición, los conjuntos pueden ser mostrados en cualquier orden. Dentro del conjunto, los números deben ser mostrados en orden ascendente. Siga el formato del ejemplo.
Ejemplo:
example
Mi solución:
“`cpp
#include <iostream>
#include <vector>
using namespace std;
int n;
int num(vector<><int>> sets) {
int res = 0;
for (int i = 0; i < sets.size(); i++)
for (int j = 0; j < sets[i].size(); j++)
if (sets[i][j] != 0)
res++;
return res;
}
bool testSets(vector<><int>> sets) {
for (int i = 0; i < sets.size(); i++) {
if (sets[i].size() == 0) {
return false;
} else {
for (int j = 0; j < sets[i].size() – 1; j++)
if (sets[i][j] >= sets[i][j + 1])
return false;
}
}
if (num(sets) == n)
return true;
else
return false;
}
void out(vector<><int>> a) {
for (int i = 0; i < a.size(); i++) {
for (int j = 0; j < a[i].size(); j++)
cout << a[i][j] << " ";
cout << endl;
}
}
void func(vector<><int>> sets, vector<int> a, vector<bool> used) {
if (num(sets) == n) {
if (testSets(sets)) {
out(sets);
cout << endl;
} else {
return;
}
} else {
int i, x;
for (i = 0; i < used.size(); i++) {
if (used[i] == false)
break;
}
if (i == used.size())
i–;
<pre><code>for (x = 0; x < sets.size(); x++) {
if (sets[x].size() == 0)
break;
}
if (x == sets.size())
x–;
used[i] = true;
for (int j = 0; j <= x; j++) {
sets[j].push_back(a[i]);
func(sets, a, used);
sets[j].pop_back();
}
used[i] = false;
</code></pre>
}
}
int main() {
int k;
cin >> n >> k;
vector<int> a(n);
vector<><int>> sets;
vector<bool> used(n, false);
for (int i = 0; i < a.size(); i++)
a[i] = i + 1;
sets.resize(k);
func(sets, a, used);
return 0;
}
“`
davy.ai
Hay varias formas de acelerar un programa, pero las más comunes son mejorar el algoritmo, optimizar el código y utilizar la paralelización.
En cuanto a mejorar el algoritmo, un enfoque consiste en buscar un algoritmo mejor que tenga una mayor complejidad temporal. La complejidad temporal es una medida de cuánto tiempo tarda un algoritmo en ejecutarse a medida que aumenta el tamaño de entrada. Por ejemplo, un algoritmo que tarda O(n^2) tiempo tiene una mayor complejidad temporal que uno que tarda O(n log n) tiempo.
En el caso de este problema, puede ser posible encontrar un algoritmo mejor que tenga una menor complejidad temporal que el actual. Sin embargo, esta tarea ya tiene un límite de tiempo de 1 segundo para el tamaño de entrada dado, lo que significa que el algoritmo actual ya es relativamente rápido para las restricciones dadas.
Por lo tanto, optimizar el código puede ser un enfoque más práctico. Micro-optimizaciones como desenrollar bucles, inlinear funciones y utilizar operaciones a nivel de bits pueden mejorar la velocidad del programa. En este caso específico, hay varias micro-optimizaciones que se pueden hacer:
Además, utilizar optimizaciones del compilador como “-O3” puede acelerar significativamente el programa. Sin embargo, esto puede dificultar la lectura y depuración del código.
Finalmente, utilizar la paralelización puede mejorar la velocidad del programa utilizando múltiples procesadores o núcleos. Esto podría implicar el uso de multi-threading o aceleración de GPU. Sin embargo, implementar la paralelización puede ser desafiante y puede requerir cambios significativos en el código.