練習(xí)34：動(dòng)態(tài)數(shù)組

原文：Exercise 34: Dynamic Array

譯者：飛龍

動(dòng)態(tài)數(shù)組是自增長的數(shù)組，它與鏈表有很多相同的特性。它通常占據(jù)更少的空間，跑得更快，還有一些其它的優(yōu)勢(shì)屬性。這個(gè)練習(xí)會(huì)涉及到它的一些缺點(diǎn)，比如從開頭移除元素會(huì)很慢，并給出解決方案（只從末尾移除）。

動(dòng)態(tài)數(shù)組簡單地實(shí)現(xiàn)為void **指針的數(shù)組，它是預(yù)分配內(nèi)存的，并且指向數(shù)據(jù)。在鏈表中你創(chuàng)建了完整的結(jié)構(gòu)體來儲(chǔ)存void *value指針，但是動(dòng)態(tài)數(shù)組中你只需要一個(gè)儲(chǔ)存它們的單個(gè)數(shù)組。也就是說，你并不需要?jiǎng)?chuàng)建任何其它的指針儲(chǔ)存上一個(gè)或下一個(gè)元素。它們可以直接索引。

我會(huì)給你頭文件作為起始，你需要為實(shí)現(xiàn)打下它們：

#ifndef _DArray_h
#define _DArray_h
#include <stdlib.h>
#include <assert.h>
#include <lcthw/dbg.h>

typedef struct DArray {
    int end;
    int max;
    size_t element_size;
    size_t expand_rate;
    void **contents;
} DArray;

DArray *DArray_create(size_t element_size, size_t initial_max);

void DArray_destroy(DArray *array);

void DArray_clear(DArray *array);

int DArray_expand(DArray *array);

int DArray_contract(DArray *array);

int DArray_push(DArray *array, void *el);

void *DArray_pop(DArray *array);

void DArray_clear_destroy(DArray *array);

#define DArray_last(A) ((A)->contents[(A)->end - 1])
#define DArray_first(A) ((A)->contents[0])
#define DArray_end(A) ((A)->end)
#define DArray_count(A) DArray_end(A)
#define DArray_max(A) ((A)->max)

#define DEFAULT_EXPAND_RATE 300


static inline void DArray_set(DArray *array, int i, void *el)
{
    check(i < array->max, "darray attempt to set past max");
    if(i > array->end) array->end = i;
    array->contents[i] = el;
error:
    return;
}

static inline void *DArray_get(DArray *array, int i)
{
    check(i < array->max, "darray attempt to get past max");
    return array->contents[i];
error:
    return NULL;
}

static inline void *DArray_remove(DArray *array, int i)
{
    void *el = array->contents[i];

    array->contents[i] = NULL;

    return el;
}

static inline void *DArray_new(DArray *array)
{
    check(array->element_size > 0, "Can't use DArray_new on 0 size darrays.");

    return calloc(1, array->element_size);

error:
    return NULL;
}

#define DArray_free(E) free((E))

#endif

這個(gè)頭文件向你展示了static inline的新技巧，它就類似#define宏的工作方式，但是它們更清楚，并且易于編寫。如果你需要?jiǎng)?chuàng)建一塊代碼作為宏，并且不需要代碼生成，可以使用static inline函數(shù)。

為鏈表生成for循環(huán)的LIST_FOREACH不可能寫為static inline函數(shù)，因?yàn)樗枰裳h(huán)的內(nèi)部代碼塊。實(shí)現(xiàn)它的唯一方式是灰調(diào)函數(shù)，但是這不夠塊，并且難以使用。

之后我會(huì)修改代碼，并且讓你創(chuàng)建DArray的單元測試。

#include "minunit.h"
#include <lcthw/darray.h>

static DArray *array = NULL;
static int *val1 = NULL;
static int *val2 = NULL;

char *test_create()
{
    array = DArray_create(sizeof(int), 100);
    mu_assert(array != NULL, "DArray_create failed.");
    mu_assert(array->contents != NULL, "contents are wrong in darray");
    mu_assert(array->end == 0, "end isn't at the right spot");
    mu_assert(array->element_size == sizeof(int), "element size is wrong.");
    mu_assert(array->max == 100, "wrong max length on initial size");

    return NULL;
}

char *test_destroy()
{
    DArray_destroy(array);

    return NULL;
}

char *test_new()
{
    val1 = DArray_new(array);
    mu_assert(val1 != NULL, "failed to make a new element");

    val2 = DArray_new(array);
    mu_assert(val2 != NULL, "failed to make a new element");

    return NULL;
}

char *test_set()
{
    DArray_set(array, 0, val1);
    DArray_set(array, 1, val2);

    return NULL;
}

char *test_get()
{
    mu_assert(DArray_get(array, 0) == val1, "Wrong first value.");
    mu_assert(DArray_get(array, 1) == val2, "Wrong second value.");

    return NULL;
}

char *test_remove()
{
    int *val_check = DArray_remove(array, 0);
    mu_assert(val_check != NULL, "Should not get NULL.");
    mu_assert(*val_check == *val1, "Should get the first value.");
    mu_assert(DArray_get(array, 0) == NULL, "Should be gone.");
    DArray_free(val_check);

    val_check = DArray_remove(array, 1);
    mu_assert(val_check != NULL, "Should not get NULL.");
    mu_assert(*val_check == *val2, "Should get the first value.");
    mu_assert(DArray_get(array, 1) == NULL, "Should be gone.");
    DArray_free(val_check);

    return NULL;
}

char *test_expand_contract()
{
    int old_max = array->max;
    DArray_expand(array);
    mu_assert((unsigned int)array->max == old_max + array->expand_rate, "Wrong size after expand.");

    DArray_contract(array);
    mu_assert((unsigned int)array->max == array->expand_rate + 1, "Should stay at the expand_rate at least.");

    DArray_contract(array);
    mu_assert((unsigned int)array->max == array->expand_rate + 1, "Should stay at the expand_rate at least.");

    return NULL;
}

char *test_push_pop()
{
    int i = 0;
    for(i = 0; i < 1000; i++) {
        int *val = DArray_new(array);
        *val = i * 333;
        DArray_push(array, val);
    }

    mu_assert(array->max == 1201, "Wrong max size.");

    for(i = 999; i >= 0; i--) {
        int *val = DArray_pop(array);
        mu_assert(val != NULL, "Shouldn't get a NULL.");
        mu_assert(*val == i * 333, "Wrong value.");
        DArray_free(val);
    }

    return NULL;
}


char * all_tests() {
    mu_suite_start();

    mu_run_test(test_create);
    mu_run_test(test_new);
    mu_run_test(test_set);
    mu_run_test(test_get);
    mu_run_test(test_remove);
    mu_run_test(test_expand_contract);
    mu_run_test(test_push_pop);
    mu_run_test(test_destroy);

    return NULL;
}

RUN_TESTS(all_tests);

這向你展示了所有操作都如何使用，它會(huì)使DArray的實(shí)現(xiàn)變得容易：

#include <lcthw/darray.h>
#include <assert.h>


DArray *DArray_create(size_t element_size, size_t initial_max)
{
    DArray *array = malloc(sizeof(DArray));
    check_mem(array);
    array->max = initial_max;
    check(array->max > 0, "You must set an initial_max > 0.");

    array->contents = calloc(initial_max, sizeof(void *));
    check_mem(array->contents);

    array->end = 0;
    array->element_size = element_size;
    array->expand_rate = DEFAULT_EXPAND_RATE;

    return array;

error:
    if(array) free(array);
    return NULL;
}

void DArray_clear(DArray *array)
{
    int i = 0;
    if(array->element_size > 0) {
        for(i = 0; i < array->max; i++) {
            if(array->contents[i] != NULL) {
                free(array->contents[i]);
            }
        }
    }
}

static inline int DArray_resize(DArray *array, size_t newsize)
{
    array->max = newsize;
    check(array->max > 0, "The newsize must be > 0.");

    void *contents = realloc(array->contents, array->max * sizeof(void *));
    // check contents and assume realloc doesn't harm the original on error

    check_mem(contents);

    array->contents = contents;

    return 0;
error:
    return -1;
}

int DArray_expand(DArray *array)
{
    size_t old_max = array->max;
    check(DArray_resize(array, array->max + array->expand_rate) == 0,
            "Failed to expand array to new size: %d",
            array->max + (int)array->expand_rate);

    memset(array->contents + old_max, 0, array->expand_rate + 1);
    return 0;

error:
    return -1;
}

int DArray_contract(DArray *array)
{
    int new_size = array->end < (int)array->expand_rate ? (int)array->expand_rate : array->end;

    return DArray_resize(array, new_size + 1);
}


void DArray_destroy(DArray *array)
{
    if(array) {
        if(array->contents) free(array->contents);
        free(array);
    }
}

void DArray_clear_destroy(DArray *array)
{
    DArray_clear(array);
    DArray_destroy(array);
}

int DArray_push(DArray *array, void *el)
{
    array->contents[array->end] = el;
    array->end++;

    if(DArray_end(array) >= DArray_max(array)) {
        return DArray_expand(array);
    } else {
        return 0;
    }
}

void *DArray_pop(DArray *array)
{
    check(array->end - 1 >= 0, "Attempt to pop from empty array.");

    void *el = DArray_remove(array, array->end - 1);
    array->end--;

    if(DArray_end(array) > (int)array->expand_rate && DArray_end(array) % array->expand_rate) {
        DArray_contract(array);
    }

    return el;
error:
    return NULL;
}

這占你展示了另一種處理復(fù)雜代碼的方法，觀察頭文件并閱讀單元測試，而不是一頭扎進(jìn).c實(shí)現(xiàn)中。這種“具體的抽象”讓你理解代碼如何一起工作，并且更容易記住。

優(yōu)點(diǎn)和缺點(diǎn)

DArray在你需要這些操作時(shí)占優(yōu)勢(shì)。

• 迭代。你可以僅僅使用基本的for循環(huán)，使用DArray_count和DArray_get來完成任務(wù)。不需要任何特殊的宏。并且由于不處理指針，它非常快。
• 索引。你可以使用DArray_get和DArray_set來隨機(jī)訪問任何元素，但是List上你就必須經(jīng)過第N個(gè)元素來訪問第N+1個(gè)元素。
• 銷毀。你只需要以兩個(gè)操作銷毀結(jié)構(gòu)體和content。但是List需要一些列的free調(diào)用同時(shí)遍歷每個(gè)元素。
• 克隆。你只需要復(fù)制結(jié)構(gòu)體和content，用兩步復(fù)制整個(gè)結(jié)構(gòu)。List需要遍歷所有元素并且復(fù)制每個(gè)ListNode和值。
• 排序。你已經(jīng)見過了，如果你需要對(duì)數(shù)據(jù)排序，List非常麻煩。DArray上可以實(shí)現(xiàn)所有高效的排序算法，因?yàn)槟憧梢噪S機(jī)訪問任何元素。
• 大量數(shù)據(jù)。如果你需要儲(chǔ)存大量數(shù)據(jù)，DArray由于基于content，比起相同數(shù)量的ListNode占用更少空間而占優(yōu)。

然而List在這些操作上占優(yōu)勢(shì)。

• 在開頭插入和移除元素。DArray需要特殊的優(yōu)化來高效地完成它，并且通常還需要一些復(fù)制操作。
• 分割和連接。List只需要復(fù)制一些指針就能完成，但是DArray需要復(fù)制涉及到的所有數(shù)組。
• 少量數(shù)據(jù)。如果你只需要存儲(chǔ)幾個(gè)元素，通常使用List所需的空間要少于DArray，因?yàn)?code>DArray需要考慮到日后的添加而擴(kuò)展背后的空間，但是List只需要元素所需的空間。

考慮到這些，我更傾向使用DArray來完成其它人使用List所做的大部分事情。對(duì)于任何需要少量節(jié)點(diǎn)并且在兩端插入刪除的，我會(huì)使用List。我會(huì)想你展示兩個(gè)相似的數(shù)據(jù)結(jié)構(gòu)，叫做Stack和Queue，它們也很重要。

如何改進(jìn)

像往常一樣，瀏覽每個(gè)函數(shù)和操作，并且執(zhí)行防御性編程檢查，以及添加先決條件、不變量等任何可以使實(shí)現(xiàn)更健壯的東西。

附加題

• 改進(jìn)單元測試來覆蓋耕作操作，并使用for循環(huán)來測試迭代。
• 研究DArray上如何實(shí)現(xiàn)冒泡排序和歸并排序，但是不要馬上實(shí)現(xiàn)它們。我會(huì)在下一張實(shí)現(xiàn)DArray的算法，之后你可以完成它。
• 為一些常用的操作編寫一些性能測試，并與List中的相同操作比較。你已經(jīng)做過很多次了，但是這次需要編寫重復(fù)執(zhí)行所涉及操作的單元測試，之后在主運(yùn)行器中計(jì)時(shí)。
• 觀察DArray_expand如何使用固定增長（size + 300）來實(shí)現(xiàn)。通常動(dòng)態(tài)數(shù)組都以倍數(shù)增長（size * 2）的方式實(shí)現(xiàn)，但是我發(fā)現(xiàn)它會(huì)花費(fèi)無用的內(nèi)存并且沒有真正取得性能收益。測試我的斷言，并且看看什么情況下需要倍數(shù)增長而不是固定增長。