2016q3 Homework1 (phonebook)

contributed by <Quexint>

報告

大綱

• 作業須知

環境

• OS: Arch Linux 4.7.4-1-ARCH
• CPU: Intel® Core™2 Quad CPU @ 2.40GHz
• MEM: 4G
• GCC: 6.2.1

規格

給定 N 筆字串，然後給定 Q 筆搜索，求搜索時間最短。

$N\le 500000$

$Q\le 500000$

$L_i\le 16$

實驗

對於每種版本，記錄執行 100 次實驗的時間。

每次實驗 N 為 349990，Q 為 3499。

比較

• Trie 的建構時間是 Linked-List 的 5 倍左右。
• Trie 的搜索時間是 Linked-List 的 12000 倍左右。(27.397376:0.002337,
  $O(NL):O(L)$)

開發記錄

v1.0 Structure Compression

根據影片中的提示，先對 structure 做瘦身。

typedef struct __PHONE_BOOK_ENTRY {
    char lastName[MAX_LAST_NAME_SIZE];
    struct __CONTENT_ENTRY *contentPtr;
    struct __PHONE_BOOK_ENTRY *pNext;
} entry;

typedef struct __CONTENT_ENTRY {
	char firstName[16];
	char email[16];
	char phone[10];
	char cell[10];
	char addr1[16];
	char addr2[16];
	char city[16];
	char state[2];
	char zip[5];
} content;

entry *append(char lastName[], entry *e)
{
    e->pNext = (entry *)malloc(sizeof(entry));
    e = e->pNext;
    e->contentPtr = (content *)malloc(sizeof(content));
    strcpy(e->lastName, lastName);
    e->pNext = NULL;
    return e;
}

發現沒比較好，而且 append 因為 malloc 兩次變慢了。

結論：因為沒有做到多次的資料搬移，所以用指標取代的效益沒有出現。

v1.1 append 加速

對 append 做瘦身：一次 malloc 好所需的大小再切割為兩塊。

entry *append(char lastName[], entry *e)
{
    e->pNext = (entry *)malloc(sizeof(entry) + sizeof(content));
    e = e->pNext;
    e->contentPtr = (content *)(((uint8_t*)e) + sizeof(entry));
    strcpy(e->lastName, lastName);
    e->pNext = NULL;
    return e;
}

結論：append 的速度跟之前差不多了。

v2a Memory Comparison

想法：將 char 的 16 次比較降為 int 的 4次比較。

避免 '\0' 之後的雜訊，再 mallc 前，先清空記憶體。

	memset(e->lastName, 0, sizeof(char) * MAX_LAST_NAME_SIZE);
	strcpy(e->lastName, lastName);

考慮到 branch prediction，放棄使用if(a[0]==b[0] && a[1]==b[1]...)，而改用memcmp。

結論：沒差。

v2b Trie

先重構 main.c,phonebook_orig.{h,c} 將 initial, free 寫成函式.

將 Key (lastName) 建構一顆 Trie，而 Value 則是 Sturct content。

結論：建構超慢(0.29xxx)，搜索超快(0.0000)，重構測試加多單一測試時的搜索次
數。

重構實驗

• 把 I/O 時間提出，純測 append 的時間。

    for(n = 0; fgets(last_name_record[n], sizeof(char) * MAX_LAST_NAME_SIZE, fp); n++) {
        i = 0;
        while(last_name_record[n][i] != '\0')
            i++;
        last_name_record[n][i - 1] = '\0';
    }

    clock_gettime(CLOCK_REALTIME, &start);
    for(i = 0; i < n; i++)
        e = append(last_name_record[i], e);
    clock_gettime(CLOCK_REALTIME, &end);

• 將搜索次數提高到 1% * 資料數

int test_num = max(n / 100, 1);
int *test_array = (int *) malloc(sizeof(int) * test_num);
for(i = 0; i < test_num; i++)
    test_array[i] = rand() % n;

clock_gettime(CLOCK_REALTIME, &start);
for(i = 0; i < test_num; i++)
    assert(NULL != findName(last_name_record[test_array[i]], e));
clock_gettime(CLOCK_REALTIME, &end);

結論：測的出 Trie 的效益，但單一測試的 orig 會跑很久。

size of entry : 136 bytes
execution time of append() : 0.052206 sec
execution time of findName() : 27.529620 sec

size of entry : 216 bytes
execution time of append() : 0.255502 sec
execution time of findName() : 0.002327 sec

單一測試下，Linked-List / Trie 的搜索時間複雜度為：

Linked-List: O(L) * O(N)
Trie: O(L)