Try   HackMD

2020q3 Homework1 (lab0)

contributed by < kevin30292 >
code GitHub

function 功能

queue.c 僅提供介面但尚未有完整程式實作，需要補完並逐步精進，包含以下：

  1. q_new: 建立新的「空」佇列;
  2. q_free: 釋放佇列所佔用的記憶體;
  3. q_insert_head: 在佇列開頭 (head) 加入 (insert) 給定的新元素 (以 LIFO 準則);
  4. q_insert_tail: 在佇列尾端 (tail) 加入 (insert) 給定的新元素 (以 FIFO 準則);
  5. q_remove_head: 在佇列開頭 (head) 移除 (remove) 給定的元素。
  6. q_size: 計算佇列中的元素數量。
  7. q_reverse: 以反向順序重新排列鏈結串列，該函式不該配置或釋放任何鏈結串列元素，換言之，它只能重排已經存在的元素;
  8. q_sort: 「進階電腦系統理論與實作」課程所新增，以遞增順序來排序鏈結串列的元素，可參閱 Linked List Sort 得知實作手法

開發紀錄

q_size

由於要在 O(1) 的常數時間內執行完成，所以也不可能走訪整個鏈結串列，以取得佇列的容積。
新增 size 值紀錄 queue 的大小，又提示

Return 0 if q is NULL or empty





int q_size(queue_t *q)
{
    return (q == NULL) ? 0 q->size
}

new_q

TODO: What if malloc returned NULL?

malloc 回傳 NULL 可能為記憶體不足，因此失敗。
加入檢查機制：





if(q == NULL){
            printf("Error! Allocation was failed. \n");
            return 1;
    }

q_free

需逐一 free 所有queue中的值及字串














void q_free(queue_t *q)
{
    if (q != NULL) {
        list_ele_t *next;
        while (q->head != NULL) {
            next = q->head->next;
            free(q->head->value);
            free(q->head);
            q->head = next;
        }
        free(q);
    }
}

q_insert_head

第19行需要 free(newh) 因為第10行的 malloc 失敗，但第6行的malloc是有成功的































bool q_insert_head(queue_t *q, char *s)
{
    list_ele_t *newh;
    if (q != NULL) {
        list_ele_t *newh;
        newh = malloc(sizeof(list_ele_t));
        if (newh != NULL) {
            int length;
            length = strlen(s);
            newh->value = malloc(length * sizeof(char));
            if (newh->value != NULL) {
                memcpy(newh->value, s, length);
                newh->next = q->head;
                q->head = newh;
                q->size++;
                return true;
            }
            else {
                free(newh);
                return false
            }
        }
        else {
            return false;
        }
    }
    else {
        return false;
    }
}

q_insert_tail

  • 要在 O(1) 的常數時間內執行完成

不能從 head 慢慢找 tail

加入 tail 性質
queue.h 加入：

list_ele_t *tail;

需修改 code 以維護此參數
new_q 加入：

q->tail = NULL;  // Add for the q_insert_tail

q_insert_head 加入：




if (q->size == 0) {
    q->tail = newh;
}

12-16行，避免 head 缺失情況
































bool q_insert_tail(queue_t *q, char *s)
{
    if (q != NULL) {
        list_ele_t *newt;
        newt = malloc(sizeof(list_ele_t));
        if (newt != NULL) {
            int length;
            length = strlen(s) + 1;
            newt->value = malloc(length * sizeof(char));
            if (newt->value != NULL) {
                memcpy(newt->value, s, length);
                if (q->size == 0) {
                    q->head = newt;
                } else {
                    q->tail->next = newt;
                }
                q->tail = newt;
                newt->next = NULL;
                q->size++;
                return true;
            } else {
                free(newt);
                return false;
            }
        } else {
            return false;
        }
    } else {
        return false;
    }
}

Debug

測試時發現亂碼及 Segmentation fault

q = [gerbil▒▒▒ bear▒▒▒ dolphin▒▒▒]
cmd> # Now at the tail
cmd> it meerkat
Segmentation fault occurred.  You dereferenced a NULL or invalid pointer
make: *** [Makefile:51: check] Aborted (core dumped)

Segmentation fault 部分，檢查發現 new_q 沒有：

  1. initialize q->size
  2. 檢查 q 是否為 NULL

改寫 q_new














queue_t *q_new()
{
    queue_t *q = malloc(sizeof(queue_t));
    if (q == NULL) {
        printf("Error! Allocation was failed. \n");
        return q;
    } else {
        q->head = NULL;
        q->tail = NULL;  // Add for the q_insert_tail
        q->size = 0;
        return q;
    }
}

亂碼部分，檢查發現 q_insert_head length 值錯誤

length = strlen(s);

改為：

length = strlen(s) + 1;

q_reverse

用兩個 pointer 紀錄，過程中的 head 及 tail 命名為 tmph 及 tmpt
從舊 head 開始反轉，head->next 指回 head 以此類推。
維持 q->head 指向尚未反轉的佇列的首項


















void q_reverse(queue_t *q)
{
    if (q != NULL && q->size > 1) {
        list_ele_t *tmph, *tmpt;
        tmpt = q->head;
        tmph = q->head->next;
        q->tail = q->head;
        while (q->head->next != NULL) {
            q->head = tmph->next;
            tmph->next = tmpt;
            tmpt = tmph;
            tmph = q->head;
        }
        q->head->next = tmpt;
        q->tail->next = NULL;
    }
}

圖解：

  1. 初始 tmpt 及 tmph






linkedlist



a

1

 



b

2

 



a:a->b:data






c

3

 



b:c->c:data






head

head



head->a





tail

tail



tail->c





tmph

tmph



tmph->b





tmpt

tmpt



tmpt->a
  1. tail 移至 head






linkedlist



a

1

 



b

2

 



a:a->b:data






c

3

 



b:c->c:data






head

head



head->a





tail

tail



tail->a





tmph

tmph



tmph->b





tmpt

tmpt



tmpt->a
  1. while 迴圈






linkedlist



a

1

 



b

2

 



a:a->b:data






b:c->a:data






c

3

 



head

head



head->c





tail

tail



tail->a





tmph

tmph



tmph->b





tmpt

tmpt



tmpt->a












linkedlist



a

1

 



b

2

 



a:a->b:data






b:c->a:data






c

3

 



head

head



head->c





tail

tail



tail->a





tmph

tmph



tmph->c





tmpt

tmpt



tmpt->b
  1. while 迴圈結束 head->next 為 NULL






linkedlist



a

1

 



b

2

 



b:c->a:data






c

3

 



c:c->b:data






head

head



head->c





tail

tail



tail->a





tmph

tmph



tmph->c





tmpt

tmpt



tmpt->b

q_sort








































queue_t*  merge_list(queue_t *l1, queue_t *l2)
{
    if (!l1) return l2;
    if (!l2) return l1;
    if( l1->value < l2->value) {
        l1->next = merge(l1->next, l2);
        return l1;
    } else {
        l2->next = merge(l2->next, l1);
        return l2;
    }
}
queue_t* merge_sort(list_ele_t *l)
{
    if (!q || !q->next) return q;
    list_ele_t* fast;
    list_ele_t* slow;
    fast = q->head->next;
    slow = q->head;
    while (fast && fast->next) {
        fast = fast->next->next;
        slow = slow->next;
    }
    fast = slow->next;
    slow->next = NULL;
    list_ele_t* l1 = merge_sort(q);
    list_ele_t* l2 = merge_sort(q2);
    return merge_list(l1,l2);
}
void q_sort(queue_t *q)
{
    if (q && q->size > 0) {
        merge_sort(q);
        return;
    } else {
        printf("Something going wrong!!");
        return;
    }
}

卡在merge_sort()，不知道應該用什麼型態的 input ，考慮到 recursive 呼叫。
參考前人實作：ZhuMon，採用 pointer to pointer 的方式，即可不用考慮回傳 type 的問題。













































void merge_sort(list_ele_t **head)
{
    if(!(*head) || !((*head)->next)) return;

    list_ele_t* fast;
    list_ele_t* slow;

    fast = (*head)->next;
    slow = *head;
    while (fast && fast->next) {
        fast = fast->next->next;
        slow = slow->next;
    }
    fast = slow->next;
    slow->next = NULL;
    slow = *head;
    merge_sort(&fast);
    merge_sort((&slow));

    list_ele_t **tmp = head;
    *head = NULL;
    while (fast && slow) {
        if (strcmp(fast->value, slow->value) < 0) {
            *tmp = fast;
            fast = fast->next;
        } else {
            *tmp = slow;
            slow = slow->next;
        }
        tmp = &(*tmp)->next;
    }
    *tmp = fast ? fast : slow;
}
void q_sort(queue_t *q)
{
    if (!q || q->size == 1) {
        return;
    } else if (q && q->size > 1) {
        merge_sort(&q->head);
        return;
    } else {
        return;
    }
}

發現 sorting 在包含大寫的時候會不正常:

Last changed by 
 
kevin30292
0
457

Read more

Assignment 1

Paper Term LLVM https://llvm.org/ LLVM IR https://blog.gopheracademy.com/advent-2018/llvm-ir-and-go/ LLVM IR is a low-level intermediate representation used by the LLVM compiler framework. You can think of LLVM IR as a ==platform-independent assembly language== with an infinite number of function local registers. SSA https://www.geeksforgeeks.org/static-single-assignment-with-relevant-examples/

Jun 15, 2023
2023 Spring Break

Mar 11 to Mar 19 CheckList [x] airlines UA $598 [x] airB&B [x] rental car [x] park ticket California National Park Sequoia

Feb 24, 2023
Florida

Tampa Tarpon Springs Sponge Docks 735 Dodecanese Blvd, Tarpon Springs, FL 34689 Shells Seafood Restaurant $$ 202 S Dale Mabry Hwy, Tampa, FL 33609 https://goo.gl/maps/1npaAUwccFYCUaHU9 google maps ==4.5== (2700) Menu

Dec 26, 2022
Lab 2 (Working)

Question Investigate two options highlighting the major concepts and components needed for it. https://pytorch.org/tutorials/beginner/dist_overview.html Distributed Data-Parallel Training (DDP) It is a single-program multiple-data training paradigm. The model is replicated on every GPUs, and every GPUs will train different set data. It need communicaiton to synchronize the gradients, thus this approach need some libraries to perfrom allreduce and brodcast operation. such as NCCL, gloo or some MPI libraries. It will only support data parallelism, but it is the easiest way to do distributed training. RPC-Based Distributed Training (RPC)

Nov 13, 2022
Read more from kevin30292
Published on HackMD