练习34：动态数组

原文：Exercise 34: Dynamic Array

译者：飞龙

动态数组是自增长的数组，它与链表有很多相同的特性。它通常占据更少的空间，跑得更快，还有一些其它的优势属性。这个练习会涉及到它的一些缺点，比如从开头移除元素会很慢，并给出解决方案（只从末尾移除）。

动态数组简单地实现为void **指针的数组，它是预分配内存的，并且指向数据。在链表中你创建了完整的结构体来储存void *value指针，但是动态数组中你只需要一个储存它们的单个数组。也就是说，你并不需要创建任何其它的指针储存上一个或下一个元素。它们可以直接索引。

我会给你头文件作为起始，你需要为实现打下它们：

#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

这个头文件向你展示了static inline的新技巧，它就类似#define宏的工作方式，但是它们更清楚，并且易于编写。如果你需要创建一块代码作为宏，并且不需要代码生成，可以使用static inline函数。

为链表生成for循环的LIST_FOREACH不可能写为static inline函数，因为它需要生成循环的内部代码块。实现它的唯一方式是灰调函数，但是这不够块，并且难以使用。

之后我会修改代码，并且让你创建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);

这向你展示了所有操作都如何使用，它会使DArray的实现变得容易：

#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;
}

这占你展示了另一种处理复杂代码的方法，观察头文件并阅读单元测试，而不是一头扎进.c实现中。这种“具体的抽象”让你理解代码如何一起工作，并且更容易记住。

优点和缺点

DArray在你需要这些操作时占优势。

迭代。你可以仅仅使用基本的for循环，使用DArray_count和DArray_get来完成任务。不需要任何特殊的宏。并且由于不处理指针，它非常快。
索引。你可以使用DArray_get和DArray_set来随机访问任何元素，但是List上你就必须经过第N个元素来访问第N+1个元素。
销毁。你只需要以两个操作销毁结构体和content。但是List需要一些列的free调用同时遍历每个元素。
克隆。你只需要复制结构体和content，用两步复制整个结构。List需要遍历所有元素并且复制每个ListNode和值。
排序。你已经见过了，如果你需要对数据排序，List非常麻烦。DArray上可以实现所有高效的排序算法，因为你可以随机访问任何元素。
大量数据。如果你需要储存大量数据，DArray由于基于content，比起相同数量的ListNode占用更少空间而占优。

然而List在这些操作上占优势。

在开头插入和移除元素。DArray需要特殊的优化来高效地完成它，并且通常还需要一些复制操作。
分割和连接。List只需要复制一些指针就能完成，但是DArray需要复制涉及到的所有数组。
少量数据。如果你只需要存储几个元素，通常使用List所需的空间要少于DArray，因为DArray需要考虑到日后的添加而扩展背后的空间，但是List只需要元素所需的空间。

考虑到这些，我更倾向使用DArray来完成其它人使用List所做的大部分事情。对于任何需要少量节点并且在两端插入删除的，我会使用List。我会想你展示两个相似的数据结构，叫做Stack和Queue，它们也很重要。

如何改进

像往常一样，浏览每个函数和操作，并且执行防御性编程检查，以及添加先决条件、不变量等任何可以使实现更健壮的东西。

附加题

改进单元测试来覆盖耕作操作，并使用for循环来测试迭代。
研究DArray上如何实现冒泡排序和归并排序，但是不要马上实现它们。我会在下一张实现DArray的算法，之后你可以完成它。
为一些常用的操作编写一些性能测试，并与List中的相同操作比较。你已经做过很多次了，但是这次需要编写重复执行所涉及操作的单元测试，之后在主运行器中计时。
观察DArray_expand如何使用固定增长（size + 300）来实现。通常动态数组都以倍数增长（size * 2）的方式实现，但是我发现它会花费无用的内存并且没有真正取得性能收益。测试我的断言，并且看看什么情况下需要倍数增长而不是固定增长。

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

ex34.md

ex34.md

练习34：动态数组

优点和缺点

如何改进

附加题

Files

ex34.md

Latest commit

History

ex34.md

File metadata and controls

练习34：动态数组

优点和缺点

如何改进

附加题