2020q3 第 13 週測驗題

tags: sysprog2020

目的: 檢驗學員對遞迴呼叫和記憶體管理的認知

作答表單

---

測驗 1

LeetCode 1239. Maximum Length of a Concatenated String with Unique Characters 題意：給定一個由 C 風格字串構成的陣列 arr，字串 s 是將 arr 某個字串連接所得的字串，若 s 中的每個字元都只出現一次，於是這會是個可能解。請提供所有可能解 s 中最大的長度。

範例 1

• 輸入

  arr = ["un", "iq", "ue"]

• 輸出

  4

• 解讀: 所有可能的字元串接組合是 "", "un", "iq", "ue", "uniq", "ique"，最大長度為 4

範例 2

• 輸入

  arr = ["cha", "r", "act", "ers"]

• 輸出

  6

• 解讀: 可能的解答有 "chaers" 和 "acters"，於是最大長度為 6

範例 3

• 輸入

  arr = ["abcdefghijklmnopqrstuvwxyz"]

• 輸出: 26
   
  提示：
• $1\le arr.length\le 16$
• $1\le arr[i].length\le 26$
• arr[i] 不算 null terminator (\0)，僅有小寫英文字母

本題用遞迴來思考：依序走訪每個單詞，對於目前的字串，若與之前連接的字串沒有相同的字串，那我們就可選擇將其串接或不串接。反之，若目前字串與之前串接的字串存在相同字元，那我們就無法串接。

針對 LeetCode 1239. Maximum Length of a Concatenated String with Unique Characters，以下 C 程式是對應的解法：

#include <string.h>
#define MAX(x, y) ((x) > (y) ? (x) : (y))

static void dfs(int *arr, int arr_size, int i, int temp, int *maxm)
{
    if (i > arr_size - 1)
        return;
    int c = temp;
    if ((c & arr[i]) == 0) {
        ASSIGN;
        ACT2;
        dfs(arr, arr_size, i + 1, c, maxm);
    }
    dfs(arr, arr_size, i + 1, temp, maxm);
}

int maxLength(char **arr, int arr_size)
{
    int a[arr_size];
    memset(a, 0, arr_size * sizeof(int));
    for (int i = 0; i < arr_size; i++) {
        int k = 0;
        int len = strlen(arr[i]);
        for (int j = 0; j < len; j++)
            k |= 1 << (arr[i][j] - 'a');
        ACT1;
        a[i] = k;
    }
    int maxm = 0;
    dfs(a, arr_size, 0, 0, &maxm);
    return maxm;
}

請補完程式碼，使得符合預期。

作答區

ACT1 = ?

• (a) if (k != len) continue
• (b) if (__builtin_popcount(k) != len) continue
• (c) if (k != len) break
• (d) if (__builtin_popcount(k) != len) break

ACT2 = ?

• (a) *maxm = MAX(c, *maxm)
• (b) *maxm = c
• (c) *maxm |= c
• (d) *maxm &= c
• (e) *maxm ^= c
• (f) *maxm = MAX(__builtin_popcount(c), *maxm)

ASSIGN = ?

• (a) c |= arr[i]
• (b) c &= arr[i]
• (c) c ^= arr[i]
• (d) c = arr[i]

延伸問題:

1. 解釋上述程式碼運作原理
2. 改寫程式碼，避免使用遞迴並尋求效率更高的實作

---

測驗 2

考慮以下透過 mmap 實作快速檔案複製的程式碼: mmap-filecopy.c

/* copy modified blocks of source file to destination file efficiently
 * using mmap.
 */

#include <assert.h>
#include <fcntl.h>
#include <stddef.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/mman.h>
#include <sys/stat.h>
#include <sys/types.h>
#include <sysexits.h>
#include <unistd.h>

int main(int argc, char *argv[])
{
    if (argc != 3) {
        printf("Usage: %s <source> <destination>\n", argv[0]);
        return EX_USAGE;
    }

    const char *src_name = argv[1];
    const char *dst_name = argv[2];
    int src_fd, dst_fd;
    struct stat dst_stat = {0};
    off_t src_len, dst_len;

    src_fd = open(src_name, O_RDONLY);
    if (src_fd == -1) {
        perror(src_name);
        return EX_DATAERR;
    }

    dst_fd = open(dst_name, O_RDWR | O_CREAT,
                  S_IRUSR | S_IWUSR | S_IRGRP | S_IWGRP | S_IROTH | S_IWOTH);
    if (dst_fd == -1 || fstat(dst_fd, &dst_stat) != 0) {
        perror(dst_name);
        return EX_DATAERR;
    }

    src_len = lseek(src_fd, 0, SEEK_END);
    if (src_len < 0) {
        perror(src_name);
        return EX_DATAERR;
    }

    dst_len = lseek(dst_fd, 0, SEEK_END);
    if (dst_len < 0) {
        perror(dst_name);
        return EX_DATAERR;
    }

    if (dst_len > src_len) {
        printf("Destination file is larger (%zd) than input file (%zd)\n",
               dst_len, src_len);
        return EX_DATAERR;
    }

    const size_t page_size =
        dst_stat.st_blksize > 0 ? dst_stat.st_blksize : BUFSIZ;
    const size_t len = src_len;

    if (ftruncate(dst_fd, len) != 0) {
        perror(dst_name);
        return EX_DATAERR;
    }

    size_t read_count = 0;
    size_t write_count = 0;

    if (len > 0) {
        const uint8_t *src;
        uint8_t *dst;

        src = mmap(NULL, len, PROT_READ, MAP_SHARED, src_fd, 0);
        if (src == NULL ||
            posix_madvise((void *) src, len, POSIX_MADV_SEQUENTIAL) != 0) {
            perror(src_name);
            return EX_UNAVAILABLE;
        }

        dst = mmap(NULL, len, PROP, MAP_SHARED, dst_fd, 0);
        if (dst == NULL ||
            posix_madvise(dst, len, POSIX_MADV_SEQUENTIAL) != 0) {
            perror(dst_name);
            return EX_UNAVAILABLE;
        }

        for (size_t i = 0; i < len; i += page_size) {
            size_t block_size = (len - i) >= page_size ? page_size : (len - i);

            if (memcmp(src + i, dst + i, block_size)) {
                memcpy(dst + i, src + i, block_size);
                write_count += block_size;
            }

            read_count += block_size;
        }

        if (munmap((void *) src, len) != 0) {
            perror(src_name);
            return EX_UNAVAILABLE;
        }

        if (msync(dst, len, MS_SYNC) != 0 || munmap(dst, len) != 0) {
            perror(dst_name);
            return EX_UNAVAILABLE;
        }
    }

    if (close(src_fd) != 0) {
        perror(src_name);
        return EX_UNAVAILABLE;
    }

    if (close(dst_fd) != 0) {
        perror(dst_name);
        return EX_UNAVAILABLE;
    }

    printf("%zu bytes read\n", read_count);
    printf("%zu bytes written\n", write_count);
    return EXIT_SUCCESS;
}

編譯方式:

$ gcc -std=c11 -D_POSIX_C_SOURCE=200809L -o mmap-filecopy mmap-filecopy.c

假設原本已有檔名為 in 的檔案，且 out 不存在目前的路徑，可執行以下命令:

$ ./mmap-filecopy in out

這樣即可達成快速的檔案複製。

請補完程式碼，使得符合預期。

作答區

PROP = ?

• (a) PROT_READ | PROT_WRITE
• (b) PROT_READ

延伸問題:

1. 解釋上述程式碼運作原理，並指出其缺失
2. 探討 sendfile 和 splice 等系統系統在上述程式的應用
   • 參見 以 sendfile 和 splice 系統呼叫達到 Zero-Copy