c - 在 N 集中查找大小为 K 的子集

Question

关闭。此题需要 details or clarity 。目前不接受答案。

---

想要改进这个问题吗？通过 editing this post 添加详细信息并澄清问题.

已关闭 5 年前。

Improve this question

问题是。存在一个集合An，它由1到n之间的整数组成。

An={1, 2, 3, ..., n}

打印给定大小 K 的 An 的所有子集。并且它必须按照如下示例的顺序生成。

例如，n=5 k=3

{1, 2, 3} {1, 2, 4} {1, 2, 5} {1, 3, 4} {1, 3, 5} {1, 4, 5} {2, 3, 4} ... {3,4,5}

我不确定是否还有其他不使用递归的方法。我用递归做到了这一点，但问题是所有测试用例都应该在 1 秒内完成。当 N 和 K 类似于 5、3 和 12、6 时，没问题，但是当涉及到 50、48 或 100、95 时，时间就太长了。所有问题应在 1 秒内完成。我正在为这个问题苦苦挣扎。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

void subset(int n, int k, int arr[], int pos[], int index, int start){
    int i, j;

    if(index == k){
        for(j=0; j<k; j++){
            if(j==k-1)
                printf("%d\n", pos[j]);
            else{
                printf("%d ", pos[j]);
            }
        }
        return;
    }

    for(i=start; i<n; i++){
        pos[index] = arr[i]; 
        subset(n, k, arr, pos, index+1, i+1);
    }
}

int main(){
    int n, k, arr[100], index=0, start=0;

    scanf("%d %d", &n, &k);

    // 1<=n<=100 ; 1<=k<=n
    if(n>100||n<1 && k>n||k<1)
        return 0;

    int i;
    for(i=0; i<n; i++)
        arr[i]=i+1;

    int *pos = (int*)malloc(sizeof(int)*k);

    time_t clockstart=0, clockend=0;
    float gap;
    clockstart = clock();
    subset(n, k, arr, pos, index, start);
    clockend = clock();
    gap = (float)(clockend-clockstart)/(CLOCKS_PER_SEC);

    printf("%f\n", gap);

    return 0;
}

我认为我应该在 C++ 中使用尾递归或 vector 之类的东西。但我无法弄清楚这些。

Answer 1

在不触及“速度算法”的情况下提高“速度算法”的唯一方法是手动缓冲 printf。

printf 是一个函数，它将执行 system call有些时候。每个系统调用都是昂贵的，这就是为什么每个执行某种系统调用的函数通常都会进行“缓冲”。

对于 malloc，实际上，您分配的内存比您想象的要多得多(malloc(1) 最终不会分配 1 个八位字节，而是在幕后分配更多内存)，并且当您释放内存时，实际上它并没有真正释放(这样，如果您执行另一个 malloc，您将不会执行系统调用，而是重用释放的内存)。当然，它依赖于操作系统和实现(一切都在幕后)。您可以使用“strace”查看linux下的一些系统调用。

同样的事情也适用于“printf”:因为它会执行系统调用，所以有一个缓冲区可以保留您想要打印的内容，并且仅偶尔进行打印。

那么 printf 的缓冲区何时真正被打印？我们不知道，它是实现定义的(即使 printf 的手册页没有提到 printf 缓冲)，但通常情况下，它可能出现 3 次:

• 当缓冲区已满时
• 当您使用 fflush 强制刷新时
• 当您要打印的内容中有“\n”字符时。

由于您在每个子网中执行“\n”，因此 printf 可能每次都必须执行系统调用:这非常耗时。

通过使用缓冲区并在缓冲区中打印而不是标准输出，您可以加快代码速度:

#define BUF_LEN 2048

typedef struct mybuf {
    char   buffer[BUF_LEN];
    size_t len;
} mybuf;

// For convenience, I use global varaible, but it's BAD
mybuf buf = {.buffer = "", .len = 0};

void MyBuf_PrintOnStdout(void)
{
    write(1, buf.buffer, buf.len);
    buf.len = 0;
}

void MyBuf_Flush(void)
{
    MyBuf_PrintOnStdout();
    fflush(stdout);
}

void MyBuf_PrintInteger(int integer)
{
    int printedLen;

    // An 64bit integer take 20digit + 1 char for potential "-"
    // So 21 is the max len for an integer.
    // Of course, if your int is bigger than 64bit, this if is false.
    if (buf.len + 21 >= BUF_LEN) {
        MyBuf_PrintOnStdout();
    }
    printedLen = sprintf(buf.buffer + buf.len, "%d", integer);
    // Error check (printedLen < 0 == error)
    buf.len += printedLen;

}

void MyBuf_PrintCharacter(char character)
{
    if (buf.len + 1 >= BUF_LEN) {
        MyBuf_PrintOnStdout();
    }
    buf.buffer[buf.len] = character;
    ++buf.len;
}

void subset(int n, int k, int arr[], int pos[], int index, int start)
{   
    if (index == k) {
        for (int j = 0; j < k; ++j) {
            MyBuf_PrintInteger(pos[j]);
            MyBuf_PrintCharacter(j == k-1 ? '\n' : ' ');
        }
        return;
    }

    for(int i = start; i<n; i++){
        pos[index] = arr[i]; 
        subset(n, k, arr, pos, index+1, i+1);
    }
}

不要忘记在最后调用“MyBuf_Flush”，因为没有它你可能会错过一些打印。

编辑:使用完整的代码，我做了一些测试。虽然确实有改进(N = 30，k = 20，代码需要约 88 秒，写入需要约 78 秒)，但要在不到 1 秒的时间内完成这项工作确实太差了。没有 super 计算器是否可以解决您的问题？

<小时/>

另一个编辑:好的，我混淆了“应该”和“必须”的含义，抱歉。英语不是我的母语。 (我认为你必须使用递归)。

既然你可以不使用递归，这里有一些有趣的事情:我实现了递归，而不是 n=30、k=20 的递归。对于每个实现，我都启用和禁用了打印。

结果很明显:

• 递归，使用 printf 打印:~88s
• 递归，打印缓冲:~78s
• 递归，无打印:~7s

--

• 无递归，使用 printf 打印:~80s
• 无递归，打印缓冲:~70s
• 无递归，无打印:~0,47s

总之，打印部分比寻找解决方案本身更需要时间。

这里没有递归实现:

#define BUF_LEN 4096

typedef struct mybuf {
    char   buffer[BUF_LEN];
    size_t len;
} mybuf;

// For convenience, I use global varaible, but it's BAD
mybuf buf = {.buffer = "", .len = 0};

void MyBuf_PrintOnStdout(void)
{
    /*buf.buffer[buf.len] = '\0';
    printf("%s", buf.buffer);*/
    write(1, buf.buffer, buf.len);
    buf.len = 0;


}

void MyBuf_Flush(void)
{
    MyBuf_PrintOnStdout();
    fflush(stdout);
}

void MyBuf_PrintInteger(int integer)
{
    int printedLen;

    if (buf.len + 21 >= BUF_LEN) {
        MyBuf_PrintOnStdout();
    }
    printedLen = sprintf(buf.buffer + buf.len, "%d", integer);
    // Error check (printedLen < 0 == error)
    buf.len += printedLen;

}

void MyBuf_PrintCharacter(char character)
{
    if (buf.len + 1 >= BUF_LEN) {
        MyBuf_PrintOnStdout();
    }
    buf.buffer[buf.len] = character;
    ++buf.len;
}


void subset_no_recursion(int n, int k)
{
    int pos[k];

    for (int i = 0; i < k; ++i) {
        pos[i] = k - i;
    }

    for (;;) {
        // Last digit incrementation
        while (pos[0] <= n) {
            /* print
            for (int i = k - 1; i >= 0; --i) {
                MyBuf_PrintInteger(pos[i]);
                MyBuf_PrintCharacter(i == 0 ? '\n' : ' ');
            }*/

            ++pos[0];
        }

        // We find where we can increment the digit without overflow N
        int pivot = 1;
        while (pos[pivot] == n - pivot) {
            ++pivot;
        }
        if (pivot == k) {
            return;
        }
        ++pos[pivot];
        while (pivot) {
            pos[pivot - 1] = pos[pivot] + 1;
            --pivot;
        }
    }
}


void subset_recursion(int n, int k, int pos[], int index, int start)
{
    if (index == k) {
        for (int i = 0; i < k; ++i) {
            MyBuf_PrintInteger(pos[i]);
            MyBuf_PrintCharacter(i == k-1 ? '\n' : ' ');
        }
        return;
    }

    for (int i = start; i < n; i++) {
        pos[index] = i + 1;
        subset_recursion(n, k, pos, index + 1, i + 1);
    }
}



#define N 30
#define K 20

int main(void)
{
    int pos[K];
    time_t clockstart;
    time_t clockend;

    clockstart = clock();
    subset3(N, K);
    clockend = clock();


    printf("%f\n", ((float)(clockend - clockstart)) / CLOCKS_PER_SEC);

    return 0;
}