2020q3 sysprog Homework13 (quiz13)

tags: sysprog

contributed by < sciyen >

• 2020q3 sysprog Homework13 (quiz13)
  • Q1 LeetCode 1239. Maximum Length of a Concatenated String with Unique Characters
  • Q2

作答表單

Q1 LeetCode 1239. Maximum Length of a Concatenated String with Unique Characters

for (int i = 0; i < arr_size; i++) {
    int k = 0;
    int len = strlen(arr[i]);
    for (int j = 0; j < len; j++)
        // Translate characters into bitwise composition
        k |= 1 << (arr[i][j] - 'a');
    if (__builtin_popcount(k) != len) continue;
    // Add into potential list (a[])
    a[i] = k;
}

Example of translating characters into bitwise composition:

   a -> 0b00000000000000000000000001
   z -> 0b10000000000000000000000000
char -> 0b00000000100000000010000101

Note，重複的字串無法符合題目條件的字串描述，因此無法加入參考選項。當 1 的個數比 字元數量 還少，表示字元內容有重複。因此跳過下一行的

a[i] = k;

Q2

該程式碼利用 mmap() 將檔案映射到記憶體，實現高效率的檔案複製。

src = mmap(NULL, len, PROT_READ, MAP_SHARED, src_fd, 0);

將 destination 映射到記憶體

dst = mmap(NULL, len, PROP_READ | PROP_WRITE, MAP_SHARED, dst_fd, 0);

檔案複製原本是 low level IO 操作，變成記憶體複製，可以利用例如

• memcpy
• SIMD

等方式做資料複製。

for (size_t i = 0; i < len; i += page_size) {
    size_t block_size = (len - i) >= page_size ? page_size : (len - i);
    // if content is different
    if (memcmp(src + i, dst + i, block_size)) {
        // copy them with memcpy()
        memcpy(dst + i, src + i, block_size);
        write_count += block_size;
    }
    read_count += block_size;
}