Hatena::ブログ(Diary)

hogeなlog

プロフィール

hogelog

hogelog

小室 直(こむろ すなお)。電気通信大学2003年入学。2010年修士卒業。プログラミングとかしてます。

カレンダー
1984 | 01 |
2006 | 07 | 08 | 09 | 10 | 11 | 12 |
2007 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2008 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2009 | 01 | 02 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 |
2010 | 01 | 06 | 08 | 09 | 10 | 11 | 12 |
2011 | 01 | 02 | 03 | 05 | 08 | 09 | 10 | 12 |
2012 | 01 | 04 | 06 |

January 02(Fri), 2009

[][] 精神衛生のため動的配列を実装する

twitterで

hogelog bufで1024とかつい2のn乗確保するけど、なんか2のn乗じゃなくて○○の方が良いとかそんな意見をどっかで見たことあるような気がすんだけど、気のせいだろうか
anemo @hogelog mallocが2^nで確保するのは、初期段階で必要なサイズがわからない時に、2^nずつ確保する量を増やしていくとコピーコストを抑えられるからだよ。 
anemo @hogelog だから、そういうアルゴリズムでなければ、2^nで確保する意味はまったくないんじゃないかなぁ。
anemo @hogelog STLのコンテナのどんどん増えていく操作(vectorのpush_backとか)で実装されてるよ。「amortized」とか、「ならし計算量」でぐぐってみて!
anemo http://en.wikipedia.org/wiki/Dynamic_array
anemo @hogelog いや、どうして2^nで確保していくと計算量が抑えられるのはまた違う理由だけど、説明めんどいからアルゴリズム系の本読んだほうがいいと思うw。 キリがいいってのは、4バイト境界に沿ってる以上の理由はないと思うなぁ。

みたいなやりとりがあった結果、俺は動的配列を実装せねばならないと強く感じたので実装。なんかやってみれば割とアッサリそれっぽいのができたような。#defineで型を設定させるあたりは思い付きでやった適当だけど。http://d.hatena.ne.jp/hayamiz/20071125/1196015746 までやるのは流石にやりすぎではという気もするし。

/* vector.h
 * 
 * before include vector.h,
#define VectorType <ANY_TYPE>
#define OutOfVector <ANY_TYPE>
 * enable define ANY_TYPE vector.
 */
#include <stdio.h>
#include <stdlib.h>

#ifndef VectorType
#define VectorType int
#endif
#ifndef OutOfVector
#define OutOfVector 0
#endif

typedef struct Vector Vector;
struct Vector {
    size_t size;
    size_t capacity;
    VectorType *data;
};
static Vector *vec_init(Vector *vec, size_t size) {
    size_t capacity = size;
    size_t pow;

    /* capacity set 2^n > size */
    for(pow=1;capacity>>1;++pow) {
        capacity >>= 1;
    }
    capacity <<= pow;

    if((vec->data = malloc(sizeof(VectorType)*capacity))==NULL) {
        perror("malloc");
        exit(1);
    }
    vec->size = 0;
    vec->capacity = capacity;
    return vec;
}
static void vec_destroy(Vector *vec) {
    free(vec->data);
    vec->data = NULL;
}
static Vector *vec_alloc(size_t size) {
    Vector *vec = malloc(sizeof(Vector));
    if(vec==NULL) {
        perror("malloc");
        exit(1);
    }
    return vec_init(vec, size);
}
static void vec_free(Vector *vec) {
    vec_destroy(vec);
    free(vec);
}
static Vector *vec_resize(Vector *vec, size_t size) {
    while(size > vec->capacity) {
        vec->capacity *= 2;
        vec->data = realloc(vec->data, sizeof(VectorType)*vec->capacity);
        if(vec->data==NULL) {
            perror("realloc");
            exit(1);
        }
    }
    vec->size = size;
    return vec;
}
static VectorType vec_ref(Vector *vec, size_t index) {
    if(index >= vec->size) {
        return OutOfVector;
    }
    return vec->data[index];
}
static VectorType vec_set(Vector *vec, size_t index, VectorType src) {
    if(index >= vec->size) {
        vec_resize(vec, index+1);
    }
    return vec->data[index] = src;
}
static VectorType vec_pop(Vector *vec) {
    VectorType value;
    if(vec->size == 0) {
        return OutOfVector;
    }
    value = vec_ref(vec, vec->size-1);
    vec->size -=1;
    return value;
}
static VectorType vec_push(Vector *vec, VectorType src) {
    return vec_set(vec, vec->size, src);
}
static int vec_empty(Vector *vec) {
    return vec && vec->size == 0;
}
static int vec_equal(Vector *a, Vector *b) {
    size_t i;
    if(a->size != b->size) {
        return 0;
    }
    for(i=0;i<a->size;++i) {
        if(vec_ref(a, i)!=vec_ref(b, i)) {
            return 0;
        }
    }
    return 1;
}

/* vim: set sw=4 ts=4 et: */

http://d.hatena.ne.jp/hayamiz/20071125/1196015746 を見て「そういえば今までテストケースというものを書いたことが無いこれはまずい」と思ったのでCUnitでテストケースも書いてみました。

#define Vector IntVector
#define VectorType int
#define OutOfVector 0
#include "vector.h"

#include <stdio.h>
#include <CUnit/CUnit.h>
#include <CUnit/Basic.h>

void vector_test_01() {
    IntVector vec;
    vec_init(&vec, 8);
    CU_ASSERT(vec.size == 0);
    CU_ASSERT(vec.capacity == 16);
    vec_destroy(&vec);
    CU_ASSERT(vec.data == NULL);

    vec_init(&vec, 2);
    CU_ASSERT(vec.size == 0);
    CU_ASSERT(vec.capacity == 4);
    vec_destroy(&vec);
    CU_ASSERT(vec.data == NULL);
}
void vector_test_02() {
    size_t i;
    IntVector vec;
    vec_init(&vec, 8);
    CU_ASSERT(vec.size == 0);
    CU_ASSERT(vec.capacity == 16);
    for(i=0;i<1000;++i) {
        vec_set(&vec, i, i);
        CU_ASSERT(vec_ref(&vec, i) == i);
        CU_ASSERT(vec.size == i+1);
    }
    CU_ASSERT(vec.size == 1000);
    CU_ASSERT(vec.capacity == 1024);
    vec_destroy(&vec);
    CU_ASSERT(vec.data == NULL);
}
void vector_test_03() {
    size_t i;
    IntVector vec;
    vec_init(&vec, 8);
    CU_ASSERT(vec.size == 0);
    CU_ASSERT(vec.capacity == 16);
    for(i=0;i<1000;++i) {
        CU_ASSERT(vec_push(&vec, i) == i);
        CU_ASSERT(vec_pop(&vec) == i);
        CU_ASSERT(vec_push(&vec, i) == i);
        CU_ASSERT(vec.size == i+1);
    }
    CU_ASSERT(vec.size == 1000);
    CU_ASSERT(vec.capacity == 1024);

    while(!vec_empty(&vec)) {
        int value = vec_pop(&vec);
        CU_ASSERT(vec.size == value);
    }
    CU_ASSERT(vec.size == 0);
    vec_destroy(&vec);
    CU_ASSERT(vec.data == NULL);
}
void vector_test_04() {
    size_t i;
    IntVector a, *b;

    vec_init(&a, 10);
    CU_ASSERT(a.size == 0);
    CU_ASSERT(a.capacity == 16);
    for(i=0;i<1000;++i) {
        CU_ASSERT(vec_push(&a, i) == i);
        CU_ASSERT(a.size == i+1);
    }
    CU_ASSERT(a.size == 1000);
    CU_ASSERT(a.capacity == 1024);


    b = vec_alloc(30);
    CU_ASSERT(b->size == 0);
    CU_ASSERT(b->capacity == 32);
    for(i=0;i<1000;++i) {
        CU_ASSERT(vec_push(b, i) == i);
        CU_ASSERT(b->size == i+1);
    }
    CU_ASSERT(b->size == 1000);
    CU_ASSERT(b->capacity == 1024);

    while(!vec_empty(&a)) {
        CU_ASSERT(!vec_empty(b));
        CU_ASSERT(vec_equal(&a, b));
        CU_ASSERT(vec_pop(&a) == vec_pop(b));
    }
    CU_ASSERT(a.size == 0);
    CU_ASSERT(b->size == 0);
    vec_destroy(&a);
    CU_ASSERT(a.data == NULL);
    vec_free(b);
}
int main(int argc, char *argv[]) {
    CU_pSuite vector_suite;
    CU_initialize_registry();
    vector_suite = CU_add_suite("Vector", NULL, NULL);
    CU_add_test(vector_suite, "vector_test_01", vector_test_01);
    CU_add_test(vector_suite, "vector_test_02", vector_test_02);
    CU_add_test(vector_suite, "vector_test_03", vector_test_03);
    CU_add_test(vector_suite, "vector_test_04", vector_test_04);
    CU_basic_run_tests();
    CU_cleanup_registry();

    return 0;
}
/* vim: set sw=4 ts=4 et: */

適当にCU_ASSERTで確かめたいコードぶちこみまくってコンパイル実行

$ gcc cunit_vector.c -lcunit -Wall
$ ./a.out


     CUnit - A Unit testing framework for C - Version 2.1-0
     http://cunit.sourceforge.net/



--Run Summary: Type      Total     Ran  Passed  Failed
               suites        1       1     n/a       0
               tests         4       4       4       0
               asserts   14028   14028   14028       0

ASSERTしたコードが全部成功していることがわかる。という使い方でいいんだろか。


「なんとなく」で実装したので既存の他の動的配列とかと挙動違うような気もする。

fd0fd0 2009/01/02 21:26 性能的な話だとここらへんかもしれませんね。
http://d.hatena.ne.jp/hyoshiok/20050828

hogeloghogelog 2009/01/05 18:42 とても嬉しい情報です。ありがとうございます。

minpouminpou 2015/01/24 23:28 vec_init(&vec, 0)
としたとき、書き込み時に延々0を2倍し続けるので無限ループになるように見えます

realloc時の返値は処理系依存だそうです
https://www.jpcert.or.jp/sc-rules/c-mem04-c.html

最近のコメント