C での素の共用体

C でこの Haskell 型を表現する方法はすぐにはわかりません:

data Tree = Leaf Int | Inner Tree Tree

Haskell や Rust などの言語とは異なり、C には
の組み込みサポートがありません。 素の結合。ただし、もう少し入力を加えても、表現するために必要なすべての要素が提供されます。

最初に理解すべきことは、素結合は次のもので構成されているということです。

• さまざまな バリアント
• それぞれに、いくつかの データが関連付けられています。

バイナリ ツリーの例には、「リーフ」と「インナー」という 2 つのバリアントがあります。リーフ バリアントは 1 つの整数 (そのデータ) を格納し、内部バリアントは 2 つのツリー (その左と右の子を表す) を格納します。

このような動物は、2 つのフィールドを持つ構造体を使用して C で表現できます。

1. どのバリアントが表現されているかを示す「型タグ」。通常は整数です。
2. バリアントに関連付けられたデータを保存する data フィールド。

列挙型を使用してさまざまなバリアント型のタグを定義すると便利です:

enum tree_type {
        TREE_LEAF,
        TREE_INNER,
};

データの保存についてはどうですか?これは、組合が解決するために存在するタイプの問題です。

労働組合

ユニオンは、さまざまな種類のデータを保存できる単なるメモリの塊です。たとえば、これは 32 ビット int または 5 文字の配列を格納できる共用体です。

union int_or_chars {
        int num;
        char letters[5];
};

union int_or_chars 型の変数は、いつでも int または 5 文字の配列のいずれかを保持できます (同時に両方を保持することはできません)。

union int_or_chars quux;

// We can store an int:
quux.num = 42;
printf("quux.num = %d\n", quux.num);
// => quux.num = 42

// Or 5 chars:
quux.letters[0] = 'a';
quux.letters[1] = 'b';
quux.letters[2] = 'c';
quux.letters[3] = 'd';
quux.letters[4] = 0;
printf("quux.letters = %s\n", quux.letters);
// => quux.letters = abcd

// But not both. The memory is "shared", so the chars saved above are
// now being interpreted as an int:
printf("quux.num = %x\n", quux.num);
// quux.num = 64636261

return 0;

union int_or_chars のような共用体は、最大のメンバーを保持するのに十分な大きさのメモリのチャンクを自由に使用できます。これがどのように機能するかを示す図は次のとおりです。

+ ---- + ---- + ---- + ---- + ---- +
| byte |      |      |      |      |
+ ---- + ---- + ---- + ---- + ---- +
|<--   int uses these 4  -->|
|<--  array of chars uses all 5 -->|

これは、quux に文字の配列を格納した後、quux.num を印刷すると「ガベージ」が発生する理由を説明するのに役立ちます。これはガベージではなく、文字列「abcd」が整数として解釈されたためです。 (私のマシンでは、quux.num は 64636261 と 16 進数で表示されます。文字「a」の ASCII 値は 0x61、「b」の値は 0x62、「c」は 0x63、「d」は 0x64 です。私のプロセッサはリトルエンディアンなので、順序が逆になります。)

共用体に関する最後の注意として、sizeof によって報告されるサイズに驚かれるかもしれません:

printf("%ld\n", sizeof(union int_or_chars));
// => 8

私のマシンでは、union int_or_chars 型のサイズは、予想されていた 5 バイトではなく、8 バイトです。私のプロセッサのアーキテクチャで規定されているアライメント要件のため、一部のパディングが追加されています。

二分木に戻る

これで、Haskell から C へのバイナリ ツリー型の変換を続行する準備が整いました。バリアントの型を表す enum をすでに定義しました。次に、データを保存するためのユニオンが必要です:

union tree_data {
        int leaf;
        struct inner_data inner;
};

ここで、struct inner_data は、「inner」バリアントの左と右の子を含む構造体です。

struct inner_data {
        struct tree *left;
        struct tree *right;
};

「内部」バリアントがその左と右の子へのポインタを維持していることに注意してください。間接化が必要なのは、そうしないと構造ツリーのサイズが固定されないためです。

これらの要素を配置したら、ツリー タイプを定義する準備が整いました。

enum tree_type {
        TREE_LEAF,
        TREE_INNER,
};

struct tree;
struct inner_data {
        struct tree *left;
        struct tree *right;
};

union tree_data {
        int leaf;
        struct inner_data inner;
};

// A representation of a binary tree.
struct tree {
        enum tree_type type;
        union tree_data data;
};

木と遊ぶ

ツリーを構築するための関数をいくつか書いてみましょう:

// Construct a leaf node.
struct tree *leaf(int value) {
        struct tree *t = malloc(sizeof(*t));
        t->type = TREE_LEAF;
        t->data.leaf = value;
        return t;
}

// Construct an inner node.
struct tree *inner(struct tree *left, struct tree *right) {
        struct tree *t = malloc(sizeof(*t));
        t->type = TREE_INNER;
        t->data.inner.left = left;
        t->data.inner.right = right;
        return t;
}

そしてそれらを印刷します:

void print_tree(struct tree *t) {
        switch (t->type) {
        case TREE_LEAF:
                printf("%d", t->data.leaf);
                return;
        case TREE_INNER:
                printf("(");
                print_tree(t->data.inner.left);
                printf(" ");
                print_tree(t->data.inner.right);
                printf(")");
                return;
        }
}

これにより、Haskell 式を翻訳できるようになります。

Inner (Inner (Leaf 1) (Leaf 2)) (Leaf 3)

C に次のように変換します:

inner(inner(leaf(1), leaf(2)), leaf(3));

例:

struct tree *t = inner(inner(leaf(1), leaf(2)), leaf(3));
print_tree(t);
// => ((1 2) 3)

もう少し興味深い例として、この深さ優先検索関数を翻訳してみましょう。

-- Check if a value is in a tree.
search :: Int -> Tree -> Bool
search v (Leaf w) = v == w
search v (Inner l r) = search v l || search v r

ツリータイプの使用:

// Check if a value is in a tree.
int search(int value, struct tree *t) {
        switch (t->type) {
        case TREE_LEAF:
                return t->data.leaf == value;
        case TREE_INNER:
                return (
                        search(value, t->data.inner.left) ||
                        search(value, t->data.inner.right)
                );
        }
}

確かにこれはより冗長ですが、変換プロセスは単純です (おそらくコンパイラーがこの種の処理を実行できる程度には...)。

トレードオフ

最後に、代替表現に伴うトレードオフについて少し余談を述べます。具体的には、
の代わりに次のように仮定します。

union tree_data {
        int leaf;
        struct inner_data inner;
};

私たちが使用したもの:

union tree_data {
        int leaf;
        struct inner_data *inner;
        //                ^ The difference.
};

最初のケースでは、共用体には struct inner_data が含まれますが、2 番目のケースでは、この構造体への ポインター が格納されます。その結果、最初の共用体は 16 バイトと少し大きくなります。これに対し、私のマシンのポインター バージョンでは 8 バイトです。残念ながら、影響を受けるのは内部ノードだけではありません。リーフ ノードはこれと同じ 16 バイトの共用体を使用しますが、単一 (4 バイト) int のみを格納します。ちょっともったいない気がします

しかし、それだけではありません。内部ノードの左右の子にアクセスするたびに、追加の間接的なコストを支払うことになります。特に、指すメモリがキャッシュされていない場合、読み取りは必ずしも安価であるとは限りません。

ここで紹介する主なアプローチは、ほとんどの場合、より良い出発点であり、数バイト (追加の読み取りが発生する白) を削減しようとしても、それが実現するまでは価値がないと思われます。

以上がC での素の共用体の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。