C의 분리된 공용체

C:
에서 이 Haskell 유형을 어떻게 표현하는지 즉시 명확하지 않습니다.

data Tree = Leaf Int | Inner Tree Tree

Haskell 및 Rust와 같은 언어와 달리 C에는 기본 지원이 부족합니다.
분리된 노동조합. 그러나 약간의 추가 입력을 하려는 경우 이를 표현하는 데 필요한 모든 재료를 제공합니다.

먼저 깨달아야 할 점은 분리된 결합이 다음으로 구성된다는 것입니다.

• 다양한 변형
• 각 항목에는 관련 데이터가 있습니다.

이진 트리 예에는 "leaf"와 "inner"라는 두 가지 변형이 있습니다. 리프 변형은 단일 정수(해당 데이터)를 저장하고 내부 변형은 두 개의 트리(왼쪽 및 오른쪽 하위 항목을 나타냄)를 저장합니다.

두 개의 필드가 있는 구조체를 사용하여 C에서 이러한 동물을 표현할 수 있습니다.

1. 어떤 변형이 표시되는지 나타내는 "유형 태그"(일반적으로 정수)입니다.
2. 변형과 관련된 데이터를 저장하는 데이터 필드

열거형을 사용하여 다양한 변형 유형 태그를 정의하는 것이 편리합니다.

enum tree_type {
        TREE_LEAF,
        TREE_INNER,
};

데이터 저장은 어떻게 되나요? 이것이 바로 노조가 해결하기 위해 존재하는 문제입니다.

노동조합

Union은 다양한 유형의 데이터를 저장할 수 있는 메모리 덩어리일 뿐입니다. 예를 들어, 다음은 32비트 정수 또는 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;

int_or_chars 유니온과 같은 유니온은 가장 큰 멤버를 수용할 수 있을 만큼 큰 메모리 덩어리를 마음대로 사용할 수 있습니다. 작동 방식을 보여주는 도식은 다음과 같습니다.

+ ---- + ---- + ---- + ---- + ---- +
| byte |      |      |      |      |
+ ---- + ---- + ---- + ---- + ---- +
||
||

quux에 문자 배열을 저장한 후 quux.num을 인쇄하면 "가비지"가 발생하는 이유를 설명하는 데 도움이 됩니다. 이는 가비지가 아니라 정수로 해석되는 문자열 "abcd"였습니다. (내 컴퓨터에서 quux.num은 64636261로 16진수로 인쇄됩니다. 문자 'a'는 ASCII 값 0x61, 'b' 값은 0x62, 'c'는 0x63, 'd'는 0x64입니다. 내 프로세서가 리틀 엔디안이므로 순서가 반대입니다.)

Union에 대한 마지막 참고 사항으로, sizeof:
에서 보고한 크기에 놀랄 수도 있습니다.

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

내 컴퓨터에서 Union int_or_chars 유형의 크기는 예상한 5바이트가 아니라 8바이트입니다. 내 프로세서 아키텍처에 규정된 정렬 요구 사항으로 인해 일부 패딩이 추가되었습니다.

이진 트리로 돌아가기

이제 이진 트리 유형을 Haskell에서 C로 계속 변환할 준비가 되었습니다. 변형 유형을 나타내는 열거형을 이미 정의했습니다. 이제 데이터를 저장하기 위한 Union이 필요합니다.

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

여기서 struct inner_data는 "내부" 변형의 왼쪽 및 오른쪽 하위 항목을 포함하는 구조체입니다.

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

첫 번째 경우 공용체에는 inner_data 구조체가 포함되어 있지만 두 번째 경우에는 이 구조체에 대한 포인터를 저장합니다. 결과적으로 첫 번째 공용체는 16바이트로 약간 더 크며, 내 컴퓨터의 포인터 버전은 8바이트입니다. 불행하게도 영향을 받는 것은 내부 노드만이 아닙니다. 리프 노드는 이와 동일한 16바이트 공용체를 사용하지만 단일(4바이트) int만 저장합니다. 좀 낭비적인 느낌이네요.

그러나 이것이 전부는 아닙니다. 내부 노드의 왼쪽 및 오른쪽 하위 항목에 액세스할 때마다 추가 간접 비용을 지불하게 됩니다. 특히 가리키는 메모리가 캐시되지 않은 경우 읽기 비용이 반드시 저렴하지는 않습니다.

여기에 제시된 기본 접근 방식은 대부분의 경우 더 나은 출발점이 될 것이며 몇 바이트를 줄이려는 노력(흰색으로 인해 추가 읽기가 발생함)이 될 때까지 그만한 가치가 없을 것이라고 생각합니다.

위 내용은 C의 분리된 공용체의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!